# American Institute of Mathematical Sciences

doi: 10.3934/jimo.2018073

## Exact and heuristic methods for personalized display advertising in virtual reality platforms

 Faculty of Engineering and Natural Sciences, Sabanci University, Istanbul, 34956, Turkey

* Corresponding author: Kemal Kilic

Received  October 2016 Revised  December 2017 Published  June 2018

In this paper, motivated from a real problem faced by an online Virtual Reality (VR) platform provider, we study a personalized advertisement assignment problem. In this platform users log in/out and change their virtual locations. A number of advertisers are willing to pay for ad locations to reach these users. Every time a user visits a new location, the company displays one of the ads. At the end of a fixed time horizon, a reward is collected which depends on the number of ads of each advertiser displayed to different users. The objective is to assign ads dynamically to maximize the expected reward. The problem is studied in a framework where the behaviors of users are modeled with two-state continuous-time Markov processes. We describe two exact and four heuristic algorithms. We compare these algorithms and conduct a sensitivity analysis over problem and algorithm specific parameters. These are the main contributions of the current paper. Exact algorithms suffer from the curse of dimensionality, hence, heuristic methods might be considered instead in some cases. However, exact methods can also be used as part of heuristics since the experimental analysis demonstrates that they are robust for parameters that influence the computational requirements.

Citation: Kemal Kilic, Menekse G. Saygi, Semih O. Sezer. Exact and heuristic methods for personalized display advertising in virtual reality platforms. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2018073
##### References:

show all references

##### References:
The sample mean revenues of the six algorithms for varying number of replications in Experiment 111
Computed expected revenues (ER) and the sample mean revenues (SMR) obtained for various L = 1/h values for the finite difference algorithm in Experiment #111
Computed expected revenues determined at each iteration (that is, $n \mapsto U_n$) for the value iteration algorithms with different resolution parameter values in Experiment # 111
Computed expected revenues determined by the value iteration algorithm after 40 iterations for different resolution parameter values in Experiment #111
The computational time in days for the value iteration algorithm with iteration number = 40, for different resolution parameter values in Experiment 111
The expected revenues determined by the value iteration algorithm with iteration number = 40, for different resolution parameter values in Experiment 111
The sample mean revenues (SMRs) determined by the finite difference algorithm for different h-value in Experiment 111
Parameters for numerical experiments
 Problem Specific Parameters Algorithm Specific Parameters Problem Size $h$ value Initial States Iteration Number Transition Rates Resolution (i.e., Step Length in Time) $\beta$-probabilities Exposure Payment Matrix Min./Max. Display Constraint Min./Max. Payment Constraint
 Problem Specific Parameters Algorithm Specific Parameters Problem Size $h$ value Initial States Iteration Number Transition Rates Resolution (i.e., Step Length in Time) $\beta$-probabilities Exposure Payment Matrix Min./Max. Display Constraint Min./Max. Payment Constraint
Experimental Conditions
 Experiment # Maximum Display Minimum Payment Maximum Payment 111 5 10 40 112 5 10 70 121 5 30 40 122 5 30 70 211 8 10 40 212 8 10 70 221 8 30 40 222 8 30 70
 Experiment # Maximum Display Minimum Payment Maximum Payment 111 5 10 40 112 5 10 70 121 5 30 40 122 5 30 70 211 8 10 40 212 8 10 70 221 8 30 40 222 8 30 70
Revenue performance of the algorithms for different experimental conditions
 Heuristics Finite Difference Value Iteration Exp.# A B C Random SMR ER SMR ER 111 32.25 45.46 42.24 28.83 45.93 45.57 45.90 44.57 112 32.69 45.99 42.24 28.99 46.47 46.01 46.49 45.01 121 13.28 14.86 9.54 9.70 30.75 30.46 30.79 29.61 122 13.82 15.40 9.54 9.86 33.71 33.38 33.64 32.35 211 33.81 49.55 49.13 29.71 49.63 49.27 49.62 48.16 212 35.28 49.85 49.34 30.11 49.89 49.55 49.91 48.46 221 15.66 31.44 30.75 11.52 34.80 34.36 34.85 33.17 222 17.00 31.75 30.96 11.92 39.94 39.90 39.90 38.55
 Heuristics Finite Difference Value Iteration Exp.# A B C Random SMR ER SMR ER 111 32.25 45.46 42.24 28.83 45.93 45.57 45.90 44.57 112 32.69 45.99 42.24 28.99 46.47 46.01 46.49 45.01 121 13.28 14.86 9.54 9.70 30.75 30.46 30.79 29.61 122 13.82 15.40 9.54 9.86 33.71 33.38 33.64 32.35 211 33.81 49.55 49.13 29.71 49.63 49.27 49.62 48.16 212 35.28 49.85 49.34 30.11 49.89 49.55 49.91 48.46 221 15.66 31.44 30.75 11.52 34.80 34.36 34.85 33.17 222 17.00 31.75 30.96 11.92 39.94 39.90 39.90 38.55
 [1] Yi Zhang, Xiao-Li Ma. Research on image digital watermarking optimization algorithm under virtual reality technology. Discrete & Continuous Dynamical Systems - S, 2018, 0 (0) : 1427-1440. doi: 10.3934/dcdss.2019098 [2] H.Thomas Banks, Shuhua Hu. Nonlinear stochastic Markov processes and modeling uncertainty in populations. Mathematical Biosciences & Engineering, 2012, 9 (1) : 1-25. doi: 10.3934/mbe.2012.9.1 [3] Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023 [4] Vladimir Kazakov. Sampling - reconstruction procedure with jitter of markov continuous processes formed by stochastic differential equations of the first order. Conference Publications, 2009, 2009 (Special) : 433-441. doi: 10.3934/proc.2009.2009.433 [5] Wael Bahsoun, Paweł Góra. SRB measures for certain Markov processes. Discrete & Continuous Dynamical Systems - A, 2011, 30 (1) : 17-37. doi: 10.3934/dcds.2011.30.17 [6] Mathias Staudigl. A limit theorem for Markov decision processes. Journal of Dynamics & Games, 2014, 1 (4) : 639-659. doi: 10.3934/jdg.2014.1.639 [7] Artur Stephan, Holger Stephan. Memory equations as reduced Markov processes. Discrete & Continuous Dynamical Systems - A, 2019, 39 (4) : 2133-2155. doi: 10.3934/dcds.2019089 [8] Xian Chen, Zhi-Ming Ma. A transformation of Markov jump processes and applications in genetic study. Discrete & Continuous Dynamical Systems - A, 2014, 34 (12) : 5061-5084. doi: 10.3934/dcds.2014.34.5061 [9] A. M. Vershik. Polymorphisms, Markov processes, quasi-similarity. Discrete & Continuous Dynamical Systems - A, 2005, 13 (5) : 1305-1324. doi: 10.3934/dcds.2005.13.1305 [10] Andrzej Nowakowski, Jan Sokolowski. On dual dynamic programming in shape control. Communications on Pure & Applied Analysis, 2012, 11 (6) : 2473-2485. doi: 10.3934/cpaa.2012.11.2473 [11] Jérôme Renault. General limit value in dynamic programming. Journal of Dynamics & Games, 2014, 1 (3) : 471-484. doi: 10.3934/jdg.2014.1.471 [12] Amin Aalaei, Hamid Davoudpour. Two bounds for integrating the virtual dynamic cellular manufacturing problem into supply chain management. Journal of Industrial & Management Optimization, 2016, 12 (3) : 907-930. doi: 10.3934/jimo.2016.12.907 [13] A. Mittal, N. Hemachandra. Learning algorithms for finite horizon constrained Markov decision processes. Journal of Industrial & Management Optimization, 2007, 3 (3) : 429-444. doi: 10.3934/jimo.2007.3.429 [14] Oliver Junge, Alex Schreiber. Dynamic programming using radial basis functions. Discrete & Continuous Dynamical Systems - A, 2015, 35 (9) : 4439-4453. doi: 10.3934/dcds.2015.35.4439 [15] Eduardo Espinosa-Avila, Pablo Padilla Longoria, Francisco Hernández-Quiroz. Game theory and dynamic programming in alternate games. Journal of Dynamics & Games, 2017, 4 (3) : 205-216. doi: 10.3934/jdg.2017013 [16] Rein Luus. Optimal control of oscillatory systems by iterative dynamic programming. Journal of Industrial & Management Optimization, 2008, 4 (1) : 1-15. doi: 10.3934/jimo.2008.4.1 [17] Qing Liu, Armin Schikorra. General existence of solutions to dynamic programming equations. Communications on Pure & Applied Analysis, 2015, 14 (1) : 167-184. doi: 10.3934/cpaa.2015.14.167 [18] Sie Long Kek, Mohd Ismail Abd Aziz, Kok Lay Teo, Rohanin Ahmad. An iterative algorithm based on model-reality differences for discrete-time nonlinear stochastic optimal control problems. Numerical Algebra, Control & Optimization, 2013, 3 (1) : 109-125. doi: 10.3934/naco.2013.3.109 [19] Sie Long Kek, Kok Lay Teo, Mohd Ismail Abd Aziz. Filtering solution of nonlinear stochastic optimal control problem in discrete-time with model-reality differences. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 207-222. doi: 10.3934/naco.2012.2.207 [20] Sie Long Kek, Mohd Ismail Abd Aziz. Output regulation for discrete-time nonlinear stochastic optimal control problems with model-reality differences. Numerical Algebra, Control & Optimization, 2015, 5 (3) : 275-288. doi: 10.3934/naco.2015.5.275

2017 Impact Factor: 0.994

## Tools

Article outline

Figures and Tables