Figure 1.
The sample mean revenues of the six algorithms for varying number of replications in Experiment 111
-
Previous Article
An integrated Principal Component Analysis and multi-objective mathematical programming approach to agile supply chain network design under uncertainty
- JIMO Home
- This Issue
-
Next Article
On the global optimal solution for linear quadratic problems of switched system
April
2019, 15(2): 833-854.
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 |
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.
Keywords:
Stochastic optimization,
Markov processes,
dynamic programming,
personalized advertisement,
Virtual Reality.
Mathematics Subject Classification:
Primary: 90C40; Secondary: 90C39.
Citation:
Kemal Kilic, Menekse G. Saygi, Semih O. Sezer. Exact and heuristic methods for personalized display advertising in virtual reality platforms. Journal of Industrial and Management Optimization,
2019, 15
(2)
: 833-854.
doi: 10.3934/jimo.2018073
![]()
References:
| [1] |
S. M. Bae, S. C. Park and S. H. Ha,
Fuzzy web ad selector based on web usage mining, Intelligent Systems, IEEE, 18 (2003), 62-69.
|
| [2] |
M. C. Campbell and K. L. Keller,
Brand familiarity and advertising repetition effects, Journal of Consumer Research, 30 (2003), 292-304.
doi: 10.1086/376800. |
| [3] |
S. A. Freedman, E. Dayan, Y. B. Kimelman, H. Weissman and R. Eitan, Early intervention for preventing posttraumatic stress disorder: An internet-based virtual reality treatment European Journal of Psychotraumatology, 6 (2015), 25608.
doi: 10.3402/ejpt.v6.25608. |
| [4] |
S. H. Ha, An intelligent system for personalized advertising on the internet, in E-Commerce
and Web Technologies, Springer, 2004, 21–30.
doi: 10.1007/978-3-540-30077-9_3. |
| [5] |
P. Kazienko and M. Adamski,
Adrosa adaptive personalization of web advertising, Information Sciences, 177 (2007), 2269-2295.
doi: 10.1016/j.ins.2007.01.002. |
| [6] |
K. Kilic and O. Bozkurt,
Computational intelligence based decision support tool for personalized advertisement assignment system, International Journal of Computational Intelligence Systems, 6 (2013), 396-410.
doi: 10.1080/18756891.2013.780725. |
| [7] |
K. Kilic, M. G. Saygi and S. O. Sezer,
A mathematical model for personalized advertisement in virtual reality environments, Mathematical Methods of Operations Research, 85 (2017), 241-264.
doi: 10.1007/s00186-016-0567-8. |
| [8] |
M. Langheinrich, A. Nakamura, N. Abe, T. Kamba and Y. Koseki,
Unintrusive customization techniques for web advertising, Computer Networks, 31 (1999), 1259-1272.
doi: 10.1016/S1389-1286(99)00033-X. |
| [9] |
A. Marchand and T. Hennig-Thurau,
Value creation in the video game industry: Industry economics, consumer benefits, and research opportunities, Journal of Interactive Marketing, 27 (2013), 141-157.
|
| [10] |
J. J. Pan, J. Chang, X. Yang, H. Liang, J. J. Zhang, T. Qureshi, R. Howell and T. Hickish,
Virtual reality training and assessment in laparoscopic rectum surgery, The International Journal of Medical Robotics and Computer Assisted Surgery, 11 (2015), 194-209.
doi: 10.1002/rcs.1582. |
| [11] |
J. E. Phelps, R. Lewis, L. Mobilio, D. Perry and N. Raman,
Viral marketing or electronic word-of-mouth advertising: Examining consumer responses and motivations to pass along email, Journal of Advertising Research, 44 (2004), 333-348.
doi: 10.1017/S0021849904040371. |
| [12] |
S. Schmidt and M. Eisend,
Advertising repetition: A meta-analysis on effective frequency in advertising, Journal of Advertising, 44 (2015), 415-428.
doi: 10.1080/00913367.2015.1018460. |
| [13] |
J. A. Tomlin,
An entropy approach to unintrusive targeted advertising on the web, Computer Networks, 33 (2000), 767-774.
doi: 10.1016/S1389-1286(00)00062-1. |
| [14] |
W. W. Tsang and A. S. Fu,
Virtual reality exercise to improve balance control in older adults at risk of falling, Hong Kong Medical Journal, 22 (2016), 19-22.
|
| [15] |
J. Turner,
The planning of guaranteed targeted display advertising, Operations Research, 60 (2012), 18-33.
doi: 10.1287/opre.1110.0996. |
| [16] |
J. Turner, A. Scheller-Wolf and S. Tayur,
Or practice-scheduling of dynamic in-game advertising, Operations Research, 59 (2011), 1-16.
doi: 10.1287/opre.1100.0852. |
| [17] |
I. Yaveroglu and N. Donthu,
Advertising repetition and placement issues in on-line environments, Journal of Advertising, 37 (2008), 31-44.
doi: 10.2753/JOA0091-3367370203. |
| [18] |
ZenithOptimedia, Advertising expenditure forecasts march 2016,
https://www.performics.com/executive-summary-advertising-expenditure-forecasts-march-2016/, 2016, Accessed March 28, 2018. |
| [19] |
N. Zhou, Y. Chen and H. Zhang, Study on personalized recommendation model of internet
advertisement, in Integration and Innovation Orient to E-Society Volume 2, Springer, 2007,
176–183.
doi: 10.1007/978-0-387-75494-9_22. |
show all references
References:
| [1] |
S. M. Bae, S. C. Park and S. H. Ha,
Fuzzy web ad selector based on web usage mining, Intelligent Systems, IEEE, 18 (2003), 62-69.
|
| [2] |
M. C. Campbell and K. L. Keller,
Brand familiarity and advertising repetition effects, Journal of Consumer Research, 30 (2003), 292-304.
doi: 10.1086/376800. |
| [3] |
S. A. Freedman, E. Dayan, Y. B. Kimelman, H. Weissman and R. Eitan, Early intervention for preventing posttraumatic stress disorder: An internet-based virtual reality treatment European Journal of Psychotraumatology, 6 (2015), 25608.
doi: 10.3402/ejpt.v6.25608. |
| [4] |
S. H. Ha, An intelligent system for personalized advertising on the internet, in E-Commerce
and Web Technologies, Springer, 2004, 21–30.
doi: 10.1007/978-3-540-30077-9_3. |
| [5] |
P. Kazienko and M. Adamski,
Adrosa adaptive personalization of web advertising, Information Sciences, 177 (2007), 2269-2295.
doi: 10.1016/j.ins.2007.01.002. |
| [6] |
K. Kilic and O. Bozkurt,
Computational intelligence based decision support tool for personalized advertisement assignment system, International Journal of Computational Intelligence Systems, 6 (2013), 396-410.
doi: 10.1080/18756891.2013.780725. |
| [7] |
K. Kilic, M. G. Saygi and S. O. Sezer,
A mathematical model for personalized advertisement in virtual reality environments, Mathematical Methods of Operations Research, 85 (2017), 241-264.
doi: 10.1007/s00186-016-0567-8. |
| [8] |
M. Langheinrich, A. Nakamura, N. Abe, T. Kamba and Y. Koseki,
Unintrusive customization techniques for web advertising, Computer Networks, 31 (1999), 1259-1272.
doi: 10.1016/S1389-1286(99)00033-X. |
| [9] |
A. Marchand and T. Hennig-Thurau,
Value creation in the video game industry: Industry economics, consumer benefits, and research opportunities, Journal of Interactive Marketing, 27 (2013), 141-157.
|
| [10] |
J. J. Pan, J. Chang, X. Yang, H. Liang, J. J. Zhang, T. Qureshi, R. Howell and T. Hickish,
Virtual reality training and assessment in laparoscopic rectum surgery, The International Journal of Medical Robotics and Computer Assisted Surgery, 11 (2015), 194-209.
doi: 10.1002/rcs.1582. |
| [11] |
J. E. Phelps, R. Lewis, L. Mobilio, D. Perry and N. Raman,
Viral marketing or electronic word-of-mouth advertising: Examining consumer responses and motivations to pass along email, Journal of Advertising Research, 44 (2004), 333-348.
doi: 10.1017/S0021849904040371. |
| [12] |
S. Schmidt and M. Eisend,
Advertising repetition: A meta-analysis on effective frequency in advertising, Journal of Advertising, 44 (2015), 415-428.
doi: 10.1080/00913367.2015.1018460. |
| [13] |
J. A. Tomlin,
An entropy approach to unintrusive targeted advertising on the web, Computer Networks, 33 (2000), 767-774.
doi: 10.1016/S1389-1286(00)00062-1. |
| [14] |
W. W. Tsang and A. S. Fu,
Virtual reality exercise to improve balance control in older adults at risk of falling, Hong Kong Medical Journal, 22 (2016), 19-22.
|
| [15] |
J. Turner,
The planning of guaranteed targeted display advertising, Operations Research, 60 (2012), 18-33.
doi: 10.1287/opre.1110.0996. |
| [16] |
J. Turner, A. Scheller-Wolf and S. Tayur,
Or practice-scheduling of dynamic in-game advertising, Operations Research, 59 (2011), 1-16.
doi: 10.1287/opre.1100.0852. |
| [17] |
I. Yaveroglu and N. Donthu,
Advertising repetition and placement issues in on-line environments, Journal of Advertising, 37 (2008), 31-44.
doi: 10.2753/JOA0091-3367370203. |
| [18] |
ZenithOptimedia, Advertising expenditure forecasts march 2016,
https://www.performics.com/executive-summary-advertising-expenditure-forecasts-march-2016/, 2016, Accessed March 28, 2018. |
| [19] |
N. Zhou, Y. Chen and H. Zhang, Study on personalized recommendation model of internet
advertisement, in Integration and Innovation Orient to E-Society Volume 2, Springer, 2007,
176–183.
doi: 10.1007/978-0-387-75494-9_22. |
Figure 2.
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
Figure 3.
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
Figure 4.
Computed expected revenues determined by the value iteration algorithm after 40 iterations for different resolution parameter values in Experiment #111
Figure 5.
The computational time in days for the value iteration algorithm with iteration number = 40, for different resolution parameter values in Experiment 111
Figure 6.
The expected revenues determined by the value iteration algorithm with iteration number = 40, for different resolution parameter values in Experiment 111
Figure 7.
The sample mean revenues (SMRs) determined by the finite difference algorithm for different h-value in Experiment 111
Table 1.
Parameters for numerical experiments
| Problem Specific Parameters | Algorithm Specific Parameters |
| Problem Size | |
| Initial States | Iteration Number |
| Transition Rates | Resolution (i.e., Step Length in Time) |
|
| |
| Exposure Payment Matrix | |
| Min./Max. Display Constraint | |
| Min./Max. Payment Constraint |
| Problem Specific Parameters | Algorithm Specific Parameters |
| Problem Size | |
| Initial States | Iteration Number |
| Transition Rates | Resolution (i.e., Step Length in Time) |
|
| |
| Exposure Payment Matrix | |
| Min./Max. Display Constraint | |
| Min./Max. Payment Constraint |
Table 2.
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 |
Table 3.
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 and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 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] |
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 |
| [4] |
Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control and Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023 |
| [5] |
Erdem Memik, Sasha Nikolic. The Virtual reality electrical substation field trip: Exploring student perceptions and cognitive learning. STEM Education, 2021, 1 (1) : 47-59. doi: 10.3934/steme.2021004 |
| [6] |
Wael Bahsoun, Paweł Góra. SRB measures for certain Markov processes. Discrete and Continuous Dynamical Systems, 2011, 30 (1) : 17-37. doi: 10.3934/dcds.2011.30.17 |
| [7] |
Mathias Staudigl. A limit theorem for Markov decision processes. Journal of Dynamics and Games, 2014, 1 (4) : 639-659. doi: 10.3934/jdg.2014.1.639 |
| [8] |
Artur Stephan, Holger Stephan. Memory equations as reduced Markov processes. Discrete and Continuous Dynamical Systems, 2019, 39 (4) : 2133-2155. doi: 10.3934/dcds.2019089 |
| [9] |
Mahdi Karimi, Seyed Jafar Sadjadi. Optimization of a Multi-Item Inventory model for deteriorating items with capacity constraint using dynamic programming. Journal of Industrial and Management Optimization, 2022, 18 (2) : 1145-1160. doi: 10.3934/jimo.2021013 |
| [10] |
Angelica Pachon, Federico Polito, Costantino Ricciuti. On discrete-time semi-Markov processes. Discrete and Continuous Dynamical Systems - B, 2021, 26 (3) : 1499-1529. doi: 10.3934/dcdsb.2020170 |
| [11] |
Thomas Kruse, Mikhail Urusov. Approximating exit times of continuous Markov processes. Discrete and Continuous Dynamical Systems - B, 2020, 25 (9) : 3631-3650. doi: 10.3934/dcdsb.2020076 |
| [12] |
Xian Chen, Zhi-Ming Ma. A transformation of Markov jump processes and applications in genetic study. Discrete and Continuous Dynamical Systems, 2014, 34 (12) : 5061-5084. doi: 10.3934/dcds.2014.34.5061 |
| [13] |
A. M. Vershik. Polymorphisms, Markov processes, quasi-similarity. Discrete and Continuous Dynamical Systems, 2005, 13 (5) : 1305-1324. doi: 10.3934/dcds.2005.13.1305 |
| [14] |
Andrzej Nowakowski, Jan Sokolowski. On dual dynamic programming in shape control. Communications on Pure and Applied Analysis, 2012, 11 (6) : 2473-2485. doi: 10.3934/cpaa.2012.11.2473 |
| [15] |
Jérôme Renault. General limit value in dynamic programming. Journal of Dynamics and Games, 2014, 1 (3) : 471-484. doi: 10.3934/jdg.2014.1.471 |
| [16] |
A. Mittal, N. Hemachandra. Learning algorithms for finite horizon constrained Markov decision processes. Journal of Industrial and Management Optimization, 2007, 3 (3) : 429-444. doi: 10.3934/jimo.2007.3.429 |
| [17] |
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 and Optimization, 2013, 3 (1) : 109-125. doi: 10.3934/naco.2013.3.109 |
| [18] |
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 and Optimization, 2012, 2 (1) : 207-222. doi: 10.3934/naco.2012.2.207 |
| [19] |
Sie Long Kek, Mohd Ismail Abd Aziz. Output regulation for discrete-time nonlinear stochastic optimal control problems with model-reality differences. Numerical Algebra, Control and Optimization, 2015, 5 (3) : 275-288. doi: 10.3934/naco.2015.5.275 |
| [20] |
Oliver Junge, Alex Schreiber. Dynamic programming using radial basis functions. Discrete and Continuous Dynamical Systems, 2015, 35 (9) : 4439-4453. doi: 10.3934/dcds.2015.35.4439 |
2021 Impact Factor: 1.411
Tools
Metrics
Other articles
by authors
[Back to Top]