Numerical solution of competitive advertising problem with a stochastic differential game approach using a combined Chelyshkov collocation with policy iteration method

Authors
Yazd University
Abstract
In the field of advertising‎, ‎there are always situations in which individuals or companies promote their products in order to find retrieval opportunities and attract customers in a competitive environment‎. ‎Several goals are followed in this paper‎. ‎First‎, ‎the historical development of applications of differential games in modeling strategic situations in competitive advertising is mentioned‎. ‎We then introduce the problem in a duopoly market under the influence of uncertainty in the framework of a stochastic differential game‎. ‎Finding the equilibrium strategy for this problem requires solving a nonlinear partial differential equations system also known as the Hamilton-Jacoby equation‎. ‎Another purpose of this paper is to propose an efficient and appropriate computational method for solving the Hamilton-Jacobi partial differential equations‎. ‎The proposed method for solving the problem is a combination of collocation methods by the derivative operator matrix based on Chelyshkov polynomials and policy iteration method‎. ‎The advantage of using the policy iteration method is that at each step‎, ‎instead of finding the solution to a nonlinear partial differential equation‎, ‎it is sufficient to solve a sequence of linear partial differential equations systems‎. ‎The convergence of the proposed method is provided in detail‎. ‎Finally‎, ‎we solve the corresponding Hamilton-Jacobi equations system by the proposed iterative algorithm‎.
Keywords

1. J.D.C‎. ‎Little‎, ‎Aggregate Advertising Models‎: ‎The State of the Art‎, ‎ Oper. Res. 27 (1979), 629-667‎.

2. K.M‎. ‎Lancaster‎, ‎A.S‎. ‎Judith‎, ‎Computer-Based Advertising Budgeting‎ Practices of Leading U.S‎. Consumer Advertisers‎, J Advert. 12 (4) (1983), 4-9. ‎

3. D.M‎. ‎Hanssens‎, ‎J.P‎. ‎Leonard‎, ‎L‎. ‎S‎. ‎Randall‎, ‎Market Response Models‎: ‎Econometric and Time Series Analysis‎, ‎Boston‎: ‎Kluwer Academic Publishers, 2001‎.

4. ‎L‎. ‎Friedman‎, ‎Game-Theory Models in the Allocation of Advertising Expenditures‎, ‎‎Oper. Res. 6 (1958), 699-709‎‎.

5. E‎. ‎Dockner‎, ‎J‎. ‎Steffen‎, ‎V‎. ‎L‎. ‎Ngo‎, ‎S‎. ‎Gerhard‎, ‎Differential Games in Economics and anagement Science‎, ‎Cambridge‎: ‎Cambridge‎ ‎University Press, 2000‎.

6. K.M‎. ‎Ramachandran‎, ‎C.P‎. ‎Tsokos‎, ‎Stochastic differential games‎: ‎theory and applications‎, Atlantis Press, USA‎, 2012‎.

7. M. Jensen, I. Smears, On the convergence of the finite element methods for Hamilton Jacobi Bellman equations, SIAM J. Numer. Anal. 51 (2013), 137–162.

8. F. Camilli and E.R. Jakobsen, A finite element like scheme for integro-partial differential Hamilton-Jacobi-Bellman equations, SIAM J. Numer. Anal. 47 (2009), 2407–2431.

9. H. Dong, N.V. Krylov, The rate of convergence of finite-difference approximations for parabolic Bellman equations with Lipschitz coefficients in cylindrical domains, Appl. Math. Optim. 56 (2007), 37–66.

10. N.V. Krylov, On the rate of convergence of finite-difference approximations for Bellman’s equation, St. Petersburg Math. J. 9(3) (1997), 245–256.

11. N.V. Krylov, On the rate of convergence of finite-difference approximations for Bellman’s equations with variable coefficients, Probab. Theory Related Fields 117(1) (2000), 1–16.

12. N.V. Krylov, The rate of convergence of finite-difference approximations for Bellman equations with Lipschitz coefficients, Appl. Math. Optim. 52(3) (2005), 365–399.

13. H. Dong and N.V. Krylov, On the rate of convergence of finite-difference approximations for Bellman’s equation with constant coefficients, Algebra Anal. 17 (2006), 295–313.

14. B‎. ‎Fornberg‎, ‎A practical guide to pseudospectral methods‎, ‎Cambridge Monographs‎, 1995‎.

15. C‎. ‎Canuto‎, ‎M.Y‎. ‎Hussaini‎, ‎A‎. ‎Quarteroni‎, ‎T.A‎. ‎Zang‎, ‎Spectral Methods in Fluid Dynamics‎, ‎Springer‎, ‎NewYork‎, 1988‎.

16. ‎J‎. ‎Boyd‎, ‎Chebyshev and Fourier Spectral Methods‎, ‎Dover‎‎, ‎second edition, 2001.

17. ‎J.C‎. ‎Mason‎, ‎D.C‎. ‎Handscomb‎, ‎Chebyshev Polynomials‎, ‎CRC Press LLC‎, 2003.

18. Z‎. ‎Avazzadeh‎, ‎M‎. ‎Heydari‎, ‎Chebyshev polynomials for solving two dimensional linear and nonlinear integral equations of the second kind‎, ‎Comput‎. ‎Appl‎. ‎Math‎. 31 (2012), 127-142.

19. E‎. ‎Scheiber‎, ‎On the Chebyshev approximation of a function with two variables‎, ‎arXiv:1504.04693‎, 2015.

20. E‎. ‎Tohidi‎, ‎Application of Chebyshev collocation method for solving two classes of non-classical parabolic PDEs‎, ‎Ain Shams Eng‎. ‎J‎. ‎(2015), 373-379‎.

21. V. S‎. ‎Chelyshkov‎, ‎Alternative Orthogonal Polynomials and quadratures‎, ETNA, ‎Electron‎. ‎Trans‎. ‎Numer‎. ‎Anal. 25 (2006), 17-26‎.

22. L‎. ‎Moradi‎, ‎F‎. ‎Mohammadi‎, ‎D‎. ‎Baleanu‎, ‎A direct numerical solution of time-delay fractional‎ ‎optimal control problems by using Chelyshkov wavelets‎, ‎J. Vib. Control. 25 (2018), 310-324‎.

23. C‎. ‎Oğuz‎, ‎M‎. ‎Sezer‎, ‎A.D‎. ‎Oguz‎, ‎Chelyshkov collocation approach to solve the systems‎ ‎of linear functional differential equations‎, ‎New Trends Math. Sci. 4 (2015), 83-97‎.

24. C‎. ‎Oğuz‎, ‎M‎. ‎Sezer‎, ‎Chelyshkov collocation method for a class of mixed functional‎ ‎integro-differential equations, Appl. Math. Comput. 259 (2015), 943-954‎.

25. Y‎. ‎Talaei‎, ‎M‎. ‎Asgari‎, ‎An operational matrix based on Chelyshkov polynomials‎ ‎for solving multi-order fractional differential equations‎, ‎Neural‎. ‎Comput‎. ‎Appl. 30 (2018), 1369-1378.

26. P‎. ‎Rahimkhani‎, ‎Y‎. ‎Ordokhani‎, ‎Numerical Solution of Volterra–Hammerstein Delay Integral Equations‎, ‎Iran. J. Sci. Technol. Trans. A Sci. 44 (2020), 445-457‎.

27. D. S‎. ‎Mohamed‎, ‎Chelyshkov’s Collocation Method for Solving Three-Dimensional Linear Fredholm‎ ‎Integral Equations‎, ‎MathLAB Journal 4 (2019), 163-171‎.

28. K. G‎. ‎Vamvoudakis‎, ‎F.L‎. ‎Lewis‎, ‎Multi-player non-zero-sum games‎: ‎online adaptive learning‎ ‎solution of coupled Hamilton-Jacobi equations‎, ‎Automatica 47(8) (2011), 1556-1569‎.

29. D‎. ‎Vrabie‎, ‎F. L‎. ‎Lewis‎, ‎Integral reinforcement learning for online computation of feedback‎ ‎Nash strategies of nonzero-sum differential games‎, ‎Proceedings of the IEEE conference on Decis‎. ‎Control‎. ‎(2010), 3066-3071‎.

30. D‎. ‎Liu‎, ‎Q‎. ‎Wei‎, ‎D‎. ‎Wang‎, ‎X‎. ‎Yang‎, ‎H‎. ‎Li‎, ‎Adaptive Dynamic Programming with Applications in Optimal Control‎, ‎Adv‎. ‎Ind‎. ‎Control‎. ‎springer‎, 2017.

31. H‎. ‎Li‎, ‎D‎. ‎Liu‎, ‎D‎. ‎Wang‎, ‎Adaptive dynamic programming for solving nonzero-sum differential games‎, ‎Conf‎. ‎Intell‎. ‎Control and Autom‎. ‎Sci‎. ‎(2013), 587-591‎.

32. E‎. ‎Suli and D‎. ‎F‎. ‎Mayers‎, ‎An Introduction to Numerical Analysis‎, ‎Cambridge University press‎, 2003.

33. M‎. ‎Gasca‎, ‎T‎. ‎Sauer‎, ‎On the history of multivariate polynomial interpolation‎, ‎J‎. ‎Comput‎. ‎Appl‎. Math‎. 122 (2000), 23-35‎.

34. Z. Nikooeinejad, A. Delavarkhalafi, M. Heydari, A numerical solution of open-loop Nash equilibrium in nonlinear differential games based on Chebyshev pseudospectral method, J. Comput. Appl. Math. 300 (2016), 369-384.

35. Z. Nikooeinejad, A. Delavarkhalafi, M. Heydari, Application of shifted Jacobi pseudospectral method for solving (in)finite-horizon minimax optimal control problems with uncertainty, Internat. J. Control. 13 (2017), 725-739.

36. Z. Nikooeinejad, M. Heydari, Nash equilibrium approximation of some class of stochastic differential games: A combined Chebyshev spectral collocation method with policy iteration, J. Comput. Appl. Math. 362 (2019), 41-54.

37. M. Saffarzade, G. B. Loghmani, M. Heydari, An iterative technique for the numerical solution of nonlinear stochastic It -Volterra integral equations, J. Comput. Appl. Math. 333 (2018), 74-86.

38. S. Alipour, F. Mirzaee, An iterative algorithm for solving two dimensional nonlinear stochastic integral equations: A combined successive approximations method with bilinear spline interpolation, Appl. Math. Comput. 371 (2020), 124947.