Bidding mechanisms in graph games. (English) Zbl 1480.91053
Summary: A graph game proceeds as follows: two players move a token through a graph to produce a finite or infinite path, which determines the payoff of the game. We study bidding games in which in each turn, an auction determines which player moves the token. Bidding games were largely studied in combination with two variants of first-price auctions called “richman” and “poorman” bidding. We study taxman bidding, which span the spectrum between the two. The game is parameterized by a constant \(\tau\in [0,1]\): portion \(\tau\) of the winning bid is paid to the other player, and portion \(1-\tau\) to the bank. While finite-duration (reachability) taxman games have been studied before, we present, for the first time, results on infinite-duration taxman games: we unify, generalize, and simplify previous equivalences between bidding games and a class of stochastic games called random-turn games.
MSC:
| 91A43 | Games involving graphs |
| 91A15 | Stochastic games, stochastic differential games |
| 91A05 | 2-person games |
| 91B26 | Auctions, bargaining, bidding and selling, and other market models |
Keywords:
graph games; bidding games; Richman bidding; poorman bidding; mean-payoff games; parity games; stochastic games; random-turn gamesReferences:
| [1] | Apt, K.; Grädel, E., Lectures in Game Theory for Computer Scientists (2011), Cambridge University Press · Zbl 1214.91003 |
| [2] | Pnueli, A.; Rosner, R., On the synthesis of a reactive module, (Proc. 16th POPL (1989)), 179-190 |
| [3] | Rabin, M., Decidability of second order theories and automata on infinite trees, Trans. Am. Math. Soc., 141, 1-35 (1969) · Zbl 0221.02031 |
| [4] | Lazarus, A. J.; Loeb, D. E.; Propp, J. G.; Stromquist, W. R.; Ullman, D. H., Combinatorial games under auction play, Games Econ. Behav., 27, 229-264 (1999) · Zbl 0949.91001 |
| [5] | Lazarus, A. J.; Loeb, D. E.; Propp, J. G.; Ullman, D., Richman games, (Games of No Chance, vol. 29 (1996)), 439-449 · Zbl 0873.90139 |
| [6] | Peres, Y.; Schramm, O.; Sheffield, S.; Wilson, D. B., Tug-of-war and the infinity Laplacian, J. Am. Math. Soc., 22, 167-210 (2009) · Zbl 1206.91002 |
| [7] | Condon, A., The complexity of stochastic games, Inf. Comput., 96, 203-224 (1992) · Zbl 0756.90103 |
| [8] | Avni, G.; Henzinger, T. A.; Chonev, V., Infinite-duration bidding games, J. ACM, 66, Article 31 pp. (2019) · Zbl 1448.91060 |
| [9] | Avni, G.; Henzinger, T. A.; Ibsen-Jensen, R., Infinite-duration poorman-bidding games, (Proc. 14th WINE. Proc. 14th WINE, LNCS, vol. 11316 (2018), Springer), 21-36 · Zbl 1443.91070 |
| [10] | Puterman, M. L., Markov Decision Processes: Discrete Stochastic Dynamic Programming (2005), John Wiley & Sons, Inc.: John Wiley & Sons, Inc. New York, NY, USA · Zbl 1184.90170 |
| [11] | Avni, G.; Jecker, I.; Žikelić, Đ., Infinite-duration all-pay bidding games, (Proc. 32nd SODA (2021)), 617-636 · Zbl 07788376 |
| [12] | Howard, A. R., Dynamic Programming and Markov Processes (1960), MIT Press · Zbl 0091.16001 |
| [13] | Chatterjee, K., Robustness of structurally equivalent concurrent parity games, (Proc. 15th FoSSaCS (2012)), 270-285 · Zbl 1352.68178 |
| [14] | Solan, E., Continuity of the value of competitive Markov decision processes, J. Theor. Probab., 16, 831-845 (2003) · Zbl 1044.90087 |
| [15] | Zwick, U.; Paterson, M., The complexity of mean payoff games on graphs, Theor. Comput. Sci., 158, 343-359 (1996) · Zbl 0871.68138 |
| [16] | Canny, J. F., Some algebraic and geometric computations in PSPACE, (Proc. 20th STOC (1988)), 460-467 |
| [17] | Avni, G.; Henzinger, T. A., A survey of bidding games on graphs, (Proc. 31st CONCUR. Proc. 31st CONCUR, LIPIcs, vol. 171 (2020), Schloss Dagstuhl - Leibniz-Zentrum für Informatik), Article 2 pp. |
| [18] | Avni, G.; Ibsen-Jensen, R.; Tkadlec, J., All-pay bidding games on graphs, (Proc. 34th AAAI (2020), AAAI Press), 1798-1805 |
| [19] | Avni, G.; Henzinger, T. A.; Ibsen-Jensen, R.; Novotný, P., Bidding games on Markov decision processes, (Proc. 13th RP (2019)), 1-12 · Zbl 1455.91054 |
| [20] | Meir, R.; Kalai, G.; Tennenholtz, M., Bidding games and efficient allocations, Games Econ. Behav., 112, 166-193 (2018) · Zbl 1419.91072 |
| [21] | Develin, M.; Payne, S., Discrete bidding games, Electron. J. Comb., 17, Article R85 pp. (2010) · Zbl 1188.91048 |
| [22] | Bhatt, J.; Payne, S., Bidding chess, Math. Intell., 31, 37-39 (2009) · Zbl 1328.00021 |
| [23] | Aghajohari, M.; Avni, G.; Henzinger, T. A., Determinacy in discrete-bidding infinite-duration games, (Proc. 30th CONCUR. Proc. 30th CONCUR, LIPIcs, vol. 140 (2019)), Article 20 pp. · Zbl 07649928 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
