×

zbMATH — the first resource for mathematics

Optimizing over pure stationary equilibria in consensus stopping games. (English) Zbl 1433.91012
Summary: Consensus decision-making, a widely utilized group decision-making process, requires the consent of all participants. We consider consensus stopping games, a class of stochastic games arising in the context of consensus decision-making that require the consent of all players to terminate the game. We show that a consensus stopping game may have many pure stationary equilibria, which in turn raises the question of equilibrium selection. Given an objective criterion, we study the NP-hard problem of finding a best pure stationary equilibrium. We characterize the pure stationary equilibria, show that they form an independence system, and develop several families of valid inequalities. We then solve the equilibrium selection problem as a mixed-integer linear program by a branch-and-cut approach. Our computational results demonstrate the effectiveness of our approach over a commercial solver.
MSC:
91A15 Stochastic games, stochastic differential games
91A55 Games of timing
91B06 Decision theory
Software:
CPLEX; Visual C++
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aguirregabiria, V., Mira, P.: Sequential estimation of dynamic discrete games. Econometrica 75(1), 1-53 (2007) · Zbl 1201.91012
[2] Alagoz, O.: Optimal Policies for the Acceptance of Living- and Cadaveric-donor Livers. Ph.D. thesis, University of Pittsburgh (2004)
[3] Awasthi, P., Sandholm, T.: Online stochastic optimization in the large: application to kidney exchange. In: Proceedings of the International Joint Conference on Artificial Intelligence, vol. 9, pp. 405-411 (2009)
[4] Barlow, R.E., Proschan, F.: Mathematical Theory of Reliability. Wiley, Hoboken (1965) · Zbl 0132.39302
[5] Benders, J.F.: Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik 4(1), 238-252 (1962) · Zbl 0109.38302
[6] Blackwell, D.: Discounted dynamic programming. Ann. Math. Stat. 36(1), 226-235 (1965) · Zbl 0133.42805
[7] Borkovsky, R.N., Doraszelski, U., Kryukov, Y.: A user’s guide to solving dynamic stochastic games using the homotopy method. Oper. Res. 58(4-Part-2), 1116-1132 (2010) · Zbl 1232.91035
[8] Cunningham, D.E.: Veto players and civil war duration. Am. J. Polit. Sci. 50(4), 875-892 (2006)
[9] Dehghanian, A.: Integer Programming Approaches to Stochastic Games Arising in Paired Kidney Exchange and Industrial Organization. Ph.D. thesis, University of Pittsburgh (2015)
[10] Denardo, E.V.: Contraction mappings in the theory underlying dynamic programming. SIAM Rev. 9(2), 165-177 (1967) · Zbl 0154.45101
[11] Doraszelski, U., Escobar, J.F.: A theory of regular Markov perfect equilibria in dynamic stochastic games: genericity, stability, and purification. Theor. Econ. 5(3), 369-402 (2010) · Zbl 1210.91015
[12] Doraszelski, U., Satterthwaite, M.: Computable Markov-perfect industry dynamics. RAND J. Econ. 41(2), 215-243 (2010)
[13] Eliashberg, J., Winkler, R.L.: Risk sharing and group decision making. Manag. Sci. 27(11), 1221-1235 (1981) · Zbl 0465.90007
[14] Ergin, H., Sonmez, T., Unver, M.U.: Lung exchange. Technical report, Boston College, Department of Economics (2015) · Zbl 1420.91356
[15] Ericson, R., Pakes, A.: Markov-perfect industry dynamics: a framework for empirical work. Rev. Econ. Stud. 62(1), 53-82 (1995) · Zbl 0828.90026
[16] European Communities: The Treaty of Lisbon. European Communities (2007)
[17] Filar, J.A., Vrieze, K.: Competitive Markov Decision Processes. Springer, New York (1997) · Zbl 0934.91002
[18] Filar, J.A., Schultz, T.A., Thuijsman, F., Vrieze, O.J.: Nonlinear programming and stationary equilibria in stochastic games. Math. Program. 50(1-3), 227-237 (1991) · Zbl 0753.90086
[19] Filson, D., Werner, S.: A bargaining model of war and peace: anticipating the onset, duration, and outcome of war. Am. J. Polit. Sci. 46(4), 819-837 (2002)
[20] Fink, A.M.: Equilibrium in a stochastic \[n\] n-person game. J. Sci. Hiroshima Univ. Ser. AI 28(1), 89-93 (1964) · Zbl 0126.36506
[21] Fischetti, M., Salvagnin, D., Zanette, A.: A note on the selection of Benders’ cuts. Math. Program. 124(1-2), 175-182 (2010) · Zbl 1198.90302
[22] Glorie, K.M., van de Klundert, J.J., Wagelmans, A.P.M.: Kidney exchange with long chains: an efficient pricing algorithm for clearing barter exchanges with branch-and-price. Manuf. Serv. Oper. Manag. 16(4), 498-512 (2014)
[23] Heller, Y.: Sequential correlated equilibria in stopping games. Oper. Res. 60(1), 209-224 (2012) · Zbl 1242.91029
[24] Herings, P., Peeters, R.J.A.P.: Stationary equilibria in stochastic games: structure, selection, and computation. J. Econ. Theory 118(1), 32-60 (2004) · Zbl 1117.91009
[25] Hörner, J., Sugaya, T., Takahashi, S., Vieille, N.: Recursive methods in discounted stochastic games: an algorithm for \[\delta \rightarrow\] δ→ 1 and a folk theorem. Econometrica 79(4), 1277-1318 (2011) · Zbl 1271.91063
[26] ILOG-CPLEX 12.4.: IBM ILOG CPLEX Optimization Studio 12.4 Information Center (2012)
[27] Köppe, M., Ryan, C.T., Queyranne, M.: Rational generating functions and integer programming games. Oper. Res. 59(6), 1445-1460 (2011) · Zbl 1241.91031
[28] Kurt, M.: Dynamic Decision Models for Managing the Major Complications of Diabetes. Ph.D. thesis, University of Pittsburgh (2012)
[29] Magnanti, T.L., Wong, R.T.: Accelerating Benders decomposition: algorithmic enhancement and model selection criteria. Oper. Res. 29(3), 464-484 (1981) · Zbl 0455.90064
[30] Maskin, E., Tirole, J.: Markov perfect equilibrium: I. Observable actions. J. Econ. Theory 100(2), 191-219 (2001) · Zbl 1011.91022
[31] Montgomery, R.A., Zachary, A.A., Ratner, L.E., Segev, D.L., Hiller, J.M., Houp, J., Cooper, M., Kavoussi, L., Jarrett, T., Burdick, J., Maley, W.R., Melancon, J.K., Kozlowski, T., Simpkins, C.E., Phillips, M., Desai, A., Reeb, B., Kraus, E., Rabb, H., Leffell, M.S., Warren, D.S.: Clinical results from transplanting incompatible live kidney donor/recipient pairs using kidney paired donation. J. Am. Med. Assoc. 294(13), 1655-1663 (2005)
[32] Nemhauser, G.L., Trotter Jr., L.E.: Properties of vertex packing and independence system polyhedra. Math. Program. 6(1), 48-61 (1974) · Zbl 0281.90072
[33] Nowak, A.S., Szajowski, K.: Advances in Dynamic Games. Springer, Berlin (2005) · Zbl 1060.91001
[34] Qiu, F., Ahmed, S., Dey, S.S., Wolsey, L.A.: Covering linear programming with violations. INFORMS J. Comput. 26(3), 531-546 (2014) · Zbl 1304.90139
[35] Raghavan, T.E.S., Syed, Z.: A policy-improvement type algorithm for solving zero-sum two-person stochastic games of perfect information. Math. Program. 95(3), 513-532 (2003) · Zbl 1049.91016
[36] Shapley, L.S.: Stochastic games. Proc. Natl. Acad. Sci. U. S. A. 39(10), 1095-1100 (1953) · Zbl 0051.35805
[37] Shmaya, E., Solan, E.: Two-player nonzero-sum stopping games in discrete time. Ann. Probab. 32(3), 2733-2764 (2004) · Zbl 1079.60045
[38] Singer, J.D.: Reconstructing the correlates of war dataset on material capabilities of states, 1816-1985. Int. Interact. 14(2), 115-132 (1988)
[39] Singer, JD; Bremer, S.; Stuckey, J.; Russett, B. (ed.), Capability distribution, uncertainty, and major power war, 1820-1965, 19-48 (1972), Beverly Hills
[40] Sobel, M.J.: Noncooperative stochastic games. Ann. Math. Stat. 42(6), 1930-1935 (1971) · Zbl 0229.90059
[41] Solan, E.; Meyers, RA (ed.), Stochastic games, 3064-3074 (2012), New York
[42] Solan, E., Vieille, N.: Quitting games. Math. Oper. Res. 26(2), 265-285 (2001) · Zbl 1082.91008
[43] Steinberg, R.H.: In the shadow of law or power? Consensus-based bargaining and outcomes in the GATT/WTO. Int. Organ. 56(2), 339-374 (2002)
[44] Tsebelis, G.: Veto Players: How Political Institutions Work. Princeton University Press, Princeton (2002)
[45] Ünver, M.U.: Dynamic kidney exchange. Rev. Econ. Stud. 77(1), 372-414 (2010) · Zbl 1180.92046
[46] Weintraub, G.Y., Benkard, C.L., Van Roy, B.: Markov perfect industry dynamics with many firms. Econometrica 76(6), 1375-1411 (2008) · Zbl 1154.91346
[47] Weintraub, G.Y., Benkard, C.L., Van Roy, B.: Computational methods for oblivious equilibrium. Oper. Res. 58(4), 1247-1265 (2010) · Zbl 1232.91334
[48] Weis, L., Metzger, M., Haymann, J.P., Thervet, E., Flamant, M., Vrtovsnik, F., Gauci, C., Houillier, P., Froissart, M., Letavernier, E., et al.: Renal function can improve at any stage of chronic kidney disease. PLoS One 8(12), e81835 (2013)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.