• 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

* 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, 2019, 15 (2) : 833-854. doi: 10.3934/jimo.2018073
References:
[1]

S. M. BaeS. 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.  Google Scholar

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

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

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

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

[7]

K. KilicM. 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.  Google Scholar

[8]

M. LangheinrichA. NakamuraN. AbeT. Kamba and Y. Koseki, Unintrusive customization techniques for web advertising, Computer Networks, 31 (1999), 1259-1272.  doi: 10.1016/S1389-1286(99)00033-X.  Google Scholar

[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. PanJ. ChangX. YangH. LiangJ. J. ZhangT. QureshiR. 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.  Google Scholar

[11]

J. E. PhelpsR. LewisL. MobilioD. 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.  Google Scholar

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

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

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

[16]

J. TurnerA. 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.  Google Scholar

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

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

show all references

References:
[1]

S. M. BaeS. 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.  Google Scholar

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

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

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

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

[7]

K. KilicM. 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.  Google Scholar

[8]

M. LangheinrichA. NakamuraN. AbeT. Kamba and Y. Koseki, Unintrusive customization techniques for web advertising, Computer Networks, 31 (1999), 1259-1272.  doi: 10.1016/S1389-1286(99)00033-X.  Google Scholar

[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. PanJ. ChangX. YangH. LiangJ. J. ZhangT. QureshiR. 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.  Google Scholar

[11]

J. E. PhelpsR. LewisL. MobilioD. 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.  Google Scholar

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

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

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

[16]

J. TurnerA. 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.  Google Scholar

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

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

Figure 1.  The sample mean revenues of the six algorithms for varying number of replications in Experiment 111
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 $h$ value
Initial StatesIteration Number
Transition RatesResolution (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 StatesIteration Number
Transition RatesResolution (i.e., Step Length in Time)
$\beta$-probabilities
Exposure Payment Matrix
Min./Max. Display Constraint
Min./Max. Payment Constraint
Table 2.  Experimental Conditions
Experiment #Maximum DisplayMinimum PaymentMaximum Payment
11151040
11251070
12153040
12253070
21181040
21281070
22183040
22283070
Experiment #Maximum DisplayMinimum PaymentMaximum Payment
11151040
11251070
12153040
12253070
21181040
21281070
22183040
22283070
Table 3.  Revenue performance of the algorithms for different experimental conditions
HeuristicsFinite DifferenceValue Iteration
Exp.#ABCRandomSMRERSMRER
11132.2545.4642.2428.8345.9345.5745.9044.57
11232.6945.9942.2428.9946.4746.0146.4945.01
12113.2814.869.549.7030.7530.4630.7929.61
12213.8215.409.549.8633.7133.3833.6432.35
21133.8149.5549.1329.7149.6349.2749.6248.16
21235.2849.8549.3430.1149.8949.5549.9148.46
22115.6631.4430.7511.5234.8034.3634.8533.17
22217.0031.7530.9611.9239.9439.9039.9038.55
HeuristicsFinite DifferenceValue Iteration
Exp.#ABCRandomSMRERSMRER
11132.2545.4642.2428.8345.9345.5745.9044.57
11232.6945.9942.2428.9946.4746.0146.4945.01
12113.2814.869.549.7030.7530.4630.7929.61
12213.8215.409.549.8633.7133.3833.6432.35
21133.8149.5549.1329.7149.6349.2749.6248.16
21235.2849.8549.3430.1149.8949.5549.9148.46
22115.6631.4430.7511.5234.8034.3634.8533.17
22217.0031.7530.9611.9239.9439.9039.9038.55
[1]

Yahia Zare Mehrjerdi. A new methodology for solving bi-criterion fractional stochastic programming. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020054

[2]

Predrag S. Stanimirović, Branislav Ivanov, Haifeng Ma, Dijana Mosić. A survey of gradient methods for solving nonlinear optimization. Electronic Research Archive, 2020, 28 (4) : 1573-1624. doi: 10.3934/era.2020115

[3]

Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020031

[4]

Bahaaeldin Abdalla, Thabet Abdeljawad. Oscillation criteria for kernel function dependent fractional dynamic equations. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020443

[5]

Chao Xing, Jiaojiao Pan, Hong Luo. Stability and dynamic transition of a toxin-producing phytoplankton-zooplankton model with additional food. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020275

[6]

Haixiang Yao, Ping Chen, Miao Zhang, Xun Li. Dynamic discrete-time portfolio selection for defined contribution pension funds with inflation risk. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020166

[7]

Zhenzhen Wang, Tianshou Zhou. Asymptotic behaviors and stochastic traveling waves in stochastic Fisher-KPP equations. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020323

[8]

Lorenzo Zambotti. A brief and personal history of stochastic partial differential equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 471-487. doi: 10.3934/dcds.2020264

[9]

Siyang Cai, Yongmei Cai, Xuerong Mao. A stochastic differential equation SIS epidemic model with regime switching. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020317

[10]

Xuhui Peng, Rangrang Zhang. Approximations of stochastic 3D tamed Navier-Stokes equations. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5337-5365. doi: 10.3934/cpaa.2020241

[11]

Yueyang Zheng, Jingtao Shi. A stackelberg game of backward stochastic differential equations with partial information. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020047

[12]

Reza Chaharpashlou, Abdon Atangana, Reza Saadati. On the fuzzy stability results for fractional stochastic Volterra integral equation. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020432

[13]

Christian Beck, Lukas Gonon, Martin Hutzenthaler, Arnulf Jentzen. On existence and uniqueness properties for solutions of stochastic fixed point equations. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020320

[14]

Giuseppina Guatteri, Federica Masiero. Stochastic maximum principle for problems with delay with dependence on the past through general measures. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020048

[15]

Yangrong Li, Shuang Yang, Qiangheng Zhang. Odd random attractors for stochastic non-autonomous Kuramoto-Sivashinsky equations without dissipation. Electronic Research Archive, 2020, 28 (4) : 1529-1544. doi: 10.3934/era.2020080

[16]

Pengyu Chen. Non-autonomous stochastic evolution equations with nonlinear noise and nonlocal conditions governed by noncompact evolution families. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020383

[17]

Lin Shi, Xuemin Wang, Dingshi Li. Limiting behavior of non-autonomous stochastic reaction-diffusion equations with colored noise on unbounded thin domains. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5367-5386. doi: 10.3934/cpaa.2020242

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (161)
  • HTML views (1437)
  • Cited by (1)

Other articles
by authors

[Back to Top]