
-
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
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.
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. Google Scholar |
[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. Google Scholar |
[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. Google Scholar |
[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. Google Scholar |
[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. Google Scholar |
[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. Google Scholar |
[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. Google Scholar |
[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. Google Scholar |
[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. |







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 |
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 |
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] |
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 |
[2] |
Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399 |
[3] |
Lakmi Niwanthi Wadippuli, Ivan Gudoshnikov, Oleg Makarenkov. Global asymptotic stability of nonconvex sweeping processes. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1129-1139. doi: 10.3934/dcdsb.2019212 |
[4] |
Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021 |
[5] |
Simone Cacace, Maurizio Falcone. A dynamic domain decomposition for the eikonal-diffusion equation. Discrete & Continuous Dynamical Systems - S, 2016, 9 (1) : 109-123. doi: 10.3934/dcdss.2016.9.109 |
[6] |
Xianchao Xiu, Ying Yang, Wanquan Liu, Lingchen Kong, Meijuan Shang. An improved total variation regularized RPCA for moving object detection with dynamic background. Journal of Industrial & Management Optimization, 2020, 16 (4) : 1685-1698. doi: 10.3934/jimo.2019024 |
[7] |
Yuncherl Choi, Taeyoung Ha, Jongmin Han, Sewoong Kim, Doo Seok Lee. Turing instability and dynamic phase transition for the Brusselator model with multiple critical eigenvalues. Discrete & Continuous Dynamical Systems - A, 2021 doi: 10.3934/dcds.2021035 |
[8] |
Eduardo Casas, Christian Clason, Arnd Rösch. Preface special issue on system modeling and optimization. Mathematical Control & Related Fields, 2021 doi: 10.3934/mcrf.2021008 |
[9] |
Meiqiao Ai, Zhimin Zhang, Wenguang Yu. First passage problems of refracted jump diffusion processes and their applications in valuing equity-linked death benefits. Journal of Industrial & Management Optimization, 2021 doi: 10.3934/jimo.2021039 |
[10] |
J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008 |
[11] |
Diana Keller. Optimal control of a linear stochastic Schrödinger equation. Conference Publications, 2013, 2013 (special) : 437-446. doi: 10.3934/proc.2013.2013.437 |
[12] |
Seung-Yeal Ha, Dongnam Ko, Chanho Min, Xiongtao Zhang. Emergent collective behaviors of stochastic kuramoto oscillators. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1059-1081. doi: 10.3934/dcdsb.2019208 |
[13] |
María J. Garrido-Atienza, Bohdan Maslowski, Jana Šnupárková. Semilinear stochastic equations with bilinear fractional noise. Discrete & Continuous Dynamical Systems - B, 2016, 21 (9) : 3075-3094. doi: 10.3934/dcdsb.2016088 |
[14] |
Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024 |
[15] |
Abdulrazzaq T. Abed, Azzam S. Y. Aladool. Applying particle swarm optimization based on Padé approximant to solve ordinary differential equation. Numerical Algebra, Control & Optimization, 2021 doi: 10.3934/naco.2021008 |
[16] |
Mohsen Abdolhosseinzadeh, Mir Mohammad Alipour. Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 321-332. doi: 10.3934/naco.2020028 |
[17] |
Reza Lotfi, Yahia Zare Mehrjerdi, Mir Saman Pishvaee, Ahmad Sadeghieh, Gerhard-Wilhelm Weber. A robust optimization model for sustainable and resilient closed-loop supply chain network design considering conditional value at risk. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 221-253. doi: 10.3934/naco.2020023 |
[18] |
Shangzhi Li, Shangjiang Guo. Permanence and extinction of a stochastic SIS epidemic model with three independent Brownian motions. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2693-2719. doi: 10.3934/dcdsb.2020201 |
[19] |
Xianming Liu, Guangyue Han. A Wong-Zakai approximation of stochastic differential equations driven by a general semimartingale. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2499-2508. doi: 10.3934/dcdsb.2020192 |
[20] |
Pengfei Wang, Mengyi Zhang, Huan Su. Input-to-state stability of infinite-dimensional stochastic nonlinear systems. Discrete & Continuous Dynamical Systems - B, 2021 doi: 10.3934/dcdsb.2021066 |
2019 Impact Factor: 1.366
Tools
Metrics
Other articles
by authors
[Back to Top]