Computing a mechanism for a Bayesian and partially observable Markov approach

Clempner, Julio B. ; Poznyak, Alexander S.

International Journal of Applied Mathematics and Computer Science, Tome 33 (2023) no. 3, pp. 463-478.

Résumé

The design of incentive-compatible mechanisms for a certain class of finite Bayesian partially observable Markov games is proposed using a dynamic framework. We set forth a formal method that maintains the incomplete knowledge of both the Bayesian model and the Markov system’s states. We suggest a methodology that uses Tikhonov’s regularization technique to compute a Bayesian Nash equilibrium and the accompanying game mechanism. Our framework centers on a penalty function approach, which guarantees strong convexity of the regularized reward function and the existence of a singular solution involving equality and inequality constraints in the game. We demonstrate that the approach leads to a resolution with the smallest weighted norm. The resulting individually rational and ex post periodic incentive compatible system satisfies this requirement. We arrive at the analytical equations needed to compute the game’s mechanism and equilibrium. Finally, using a supply chain network for a profit maximization problem, we demonstrate the viability of the proposed mechanism design.

Détail

Keywords: dynamic mechanism design, partially observable Markov chains, games with private information, Bayesian equilibrium
Mots-clés : mechanizm dynamiczny, łańcuchy Markova, równowaga Bayesa

Bibliographie

[1] [1] Asian, S. and Nie, X. (2014). Coordination in supply chains with uncertain demand and disruption risks: Existence, analysis, and insights, IEEE Transactions on Systems, Man, and Cybernetics: Systems 44(9): 1139-1154.

[2] [2] Athey, S. and Segal, I. (2013). An efficient dynamic mechanism, Econometrica 81(6): 2463-2485.

[3] [3] Atkeson, A. and Lucas, R. (1992). On efficient distribution with private information, Review of Economic Studies 59(3): 427-453.

[4] [4] Battaglini, M. (2005). Long-term contracting with Markovian consumers, American Economic Review 95(3): 637-658.

[5] [5] Bergemann, D. and Said, M. (2011). Dynamic auctions: A survey, in J.J. Cochran et al. (Eds), Wiley Encyclopedia of Operations Research and Management Science, John Wiley, Hoboken, pp. 1511-1522.

[6] [6] Board, S. (2007). Selling options, Journal of Economic Theory 136(1): 324-340.

[7] [7] Board, S. and Skrzypacz, A. (2016,). Revenue management with forward-looking buyers, Journal of Political Economy 124(4): 1046-1087.

[8] [8] Clempner, J.B. and Poznyak, A.S. (2015). Computing the strong Nash equilibrium for Markov chains games, Applied Mathematics and Computation 265(15): 911-927.

[9] [9] Clempner, J.B. and Poznyak, A.S. (2016). Convergence analysis for pure and stationary strategies in repeated potential games: Nash, Lyapunov and correlated equilibria, Expert Systems with Applications 46(C): 474-484.

[10] [10] Clempner, J.B. and Poznyak, A.S. (2018a). A Tikhonov regularization parameter approach for solving Lagrange constrained optimization problems, Engineering Optimization 50(11): 1996-2012.

[11] [11] Clempner, J.B. and Poznyak, A.S. (2018b). A Tikhonov regularized penalty function approach for solving polylinear programming problems, Journal of Computational and Applied Mathematics 328: 267-286.

[12] [12] Courty, P. and Li, H. (2000). Sequential screening, Review of Economic Studies 67(4): 697-717.

[13] [13] Eső, P. and Szentes, B. (2007). Optimal information disclosure in auctions and the handicap auction, Review of Economic Studies 74(3): 705-731.

[14] [14] Gallien, J. (2006). Dynamic mechanism design for online commerce, Operations Research 54(2): 291-310.

[15] [15] Garg, D. and Narahari, Y. (2008). Mechanism design for single leader Stackelberg problems and application to procurement auction design, IEEE Transactions on Automation Science and Engineering 5(3): 377-393.

[16] [16] Gershkov, A. and Moldovanu, B. (2009). Dynamic revenue maximization with heterogenous objects: A mechanism design approach, American Economic Journal: Microeconomics 1(2): 168-198.

[17] [17] Hartline, J.D. and Lucier, B. (2015). Non-optimal mechanism design, American Economic Review 105(10): 3102-3124.

[18] [18] Jackson, M. (2003). Mechanism theory, in U. Derigs (Ed.), Optimization and Operations Research: An Insight into the Encyclopedia of Life Support Systems, EOLSS Publishers, Oxford, pp. 1-46.

[19] [19] Kakade, S., Lobel, I. and Nazerzadeh, H. (2013). Optimal dynamic mechanism design and the virtual-pivot mechanism, Operations Research 61(4): 837-854.

[20] [20] Khoury, B., Nejjari, F. and Puig, V. (2022). Reliability-aware zonotopic tube-based model predictive control of a drinking water network, International Journal of Applied Mathematics and Computer Science 32(2): 197-211, DOI: 10.34768/amcs-2022-0015.

[21] [21] Maskin, E. and Riley, J. (1984). Monopoly with incomplete information, Rand Journal of Economics 15(2): 171-196.

[22] [22] Myerson, R. (1981). Optimal auction design, Mathematics of Operations Research 6(1): 58-73.

[23] [23] Myerson, R.B. (1983). Mechanism design by an informed principal, Econometrica 51(6): 1767-1797.

[24] [24] Nocedal, J. and Wright, S. (2006). Numerical Optimization, Springer, New York.

[25] [25] Pavan, A., Segal, I. and Toikka, J. (2014). Dynamic mechanism design: A Myersonian approach, Econometrica 82(2): 601-653.

[26] [26] Zeifman, A., Satin, Y., Kryukova, A., Razumchik, R., Kiseleva, K. and Shilova, G. (2020). On three methods for bounding the rate of convergence for some continuous-time Markov chains, International Journal of Applied Mathematics and Computer Science 30(2): 251-266, DOI: 10.34768/amcs-2020-0020.