Document Open Access Logo

A Survey of Bidding Games on Graphs (Invited Paper)

Authors Guy Avni, Thomas A. Henzinger

PDF
Thumbnail PDF

File

LIPIcs.CONCUR.2020.2.pdf
  • Filesize: 0.82 MB
  • 21 pages

Document Identifiers

Author Details

Guy Avni
  • IST Austria, Klosterneuburg, Austria
Thomas A. Henzinger
  • IST Austria, Klosterneuburg, Austria

Funding

This research was supported in part by the Austrian Science Fund (FWF) under grant Z211-N23 (Wittgenstein Award).

Acknowledgements

We would like to thank all our collaborators Milad Aghajohari, Ventsislav Chonev, Rasmus Ibsen-Jensen, Ismäel Jecker, Petr Novotný, Josef Tkadlec, and Đorđe Žikelić; we hope the collaboration was as fun and meaningful for you as it was for us.

Cite As Get BibTex

Guy Avni and Thomas A. Henzinger. A Survey of Bidding Games on Graphs (Invited Paper). In 31st International Conference on Concurrency Theory (CONCUR 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 171, pp. 2:1-2:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.CONCUR.2020.2

Abstract

A graph game is a two-player zero-sum game in which the players move a token throughout a graph to produce an infinite path, which determines the winner or payoff of the game. In bidding games, both players have budgets, and in each turn, we hold an "auction" (bidding) to determine which player moves the token. In this survey, we consider several bidding mechanisms and study their effect on the properties of the game. Specifically, bidding games, and in particular bidding games of infinite duration, have an intriguing equivalence with random-turn games in which in each turn, the player who moves is chosen randomly. We show how minor changes in the bidding mechanism lead to unexpected differences in the equivalence with random-turn games.

Subject Classification

ACM Subject Classification
  • Theory of computation → Solution concepts in game theory
  • Theory of computation → Formal languages and automata theory
Keywords
  • Bidding games
  • Richman bidding
  • poorman bidding
  • mean-payoff
  • parity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. M. Aghajohari, G. Avni, and T. A. Henzinger. Determinacy in discrete-bidding infinite-duration games. In Proc. 30th CONCUR, volume 140 of LIPIcs, pages 20:1-20:17, 2019. Google Scholar
  2. R. Alur, T. A. Henzinger, and O. Kupferman. Alternating-time temporal logic. J. ACM, 49(5):672-713, 2002. Google Scholar
  3. K.R. Apt and E. Grädel. Lectures in Game Theory for Computer Scientists. Cambridge University Press, 2011. Google Scholar
  4. G. Avni, T. A. Henzinger, and V. Chonev. Infinite-duration bidding games. J. ACM, 66(4):31:1-31:29, 2019. Google Scholar
  5. G. Avni, T. A. Henzinger, and R. Ibsen-Jensen. Infinite-duration poorman-bidding games. In Proc. 14th WINE, volume 11316 of LNCS, pages 21-36. Springer, 2018. Google Scholar
  6. G. Avni, T. A. Henzinger, R. Ibsen-Jensen, and P. Novotný. Bidding games on markov decision processes. In Proc. 13th RP, pages 1-12, 2019. Google Scholar
  7. G. Avni, T. A. Henzinger, and Đ. Žikelić. Bidding mechanisms in graph games. In In Proc. 44th MFCS, volume 138 of LIPIcs, pages 11:1-11:13, 2019. Google Scholar
  8. G. Avni, R. Ibsen-Jensen, and J. Tkadlec. All-pay bidding games on graphs. Proc. 34th AAAI, 2020. Google Scholar
  9. G. Avni, I. Jecker, and Đ. Žikelić. Infinite-duration all-pay bidding games. CoRR, abs/2005.06636, 2020. URL: http://arxiv.org/abs/2005.06636.
  10. M. R. Baye and H. C. Hoppe. The strategic equivalence of rent-seeking, innovation, and patent-race games. Games and Economic Behavior, 44(2):217-226, 2003. Google Scholar
  11. J. Bhatt and S. Payne. Bidding chess. Math. Intelligencer, 31:37-39, 2009. Google Scholar
  12. E. Borel. La théorie du jeu les équations intégrales á noyau symétrique. Comptes Rendus de l'Académie, 173(1304-1308):58, 1921. Google Scholar
  13. T. Brázdil, V. Brozek, K. Etessami, and A. Kucera. Approximating the termination value of one-counter mdps and stochastic games. In Proc. 38th ICALP, pages 332-343, 2011. Google Scholar
  14. T. Brázdil, V. Brozek, K. Etessami, A. Kucera, and D. Wojtczak. One-counter markov decision processes. In Proc. 21st SODA, pages 863-874, 2010. Google Scholar
  15. J. F. Canny. Some algebraic and geometric computations in PSPACE. In Proc. 20th STOC, pages 460-467, 1988. Google Scholar
  16. K. Chatterjee, A. K. Goharshady, and Y. Velner. Quantitative analysis of smart contracts. In Proc. 27th ESOP, pages 739-767, 2018. Google Scholar
  17. A. Condon. The complexity of stochastic games. Inf. Comput., 96(2):203-224, 1992. Google Scholar
  18. M. Develin and S. Payne. Discrete bidding games. The Electronic Journal of Combinatorics, 17(1):R85, 2010. Google Scholar
  19. A. E. Emerson, C. S. Jutla, and P. A. Sistla. On model-checking for fragments of μ-calculus. In Proc. 5th CAV, pages 385-396, 1993. Google Scholar
  20. A. R. Howard. Dynamic Programming and Markov Processes. MIT Press, 1960. Google Scholar
  21. K. A. Konrad and D. Kovenock. Multi-battle contests. Games and Economic Behavior, 66(1):256-274, 2009. Google Scholar
  22. U. Larsson and J. Wästlund. Endgames in bidding chess. Games of No Chance 5, 70, 2018. Google Scholar
  23. A. J. Lazarus, D. E. Loeb, J. G. Propp, W. R. Stromquist, and D. H. Ullman. Combinatorial games under auction play. Games and Economic Behavior, 27(2):229-264, 1999. Google Scholar
  24. A. J. Lazarus, D. E. Loeb, J. G. Propp, and D. Ullman. Richman games. Games of No Chance, 29:439-449, 1996. Google Scholar
  25. R. Meir, G. Kalai, and M. Tennenholtz. Bidding games and efficient allocations. Games and Economic Behavior, 2018. URL: https://doi.org/10.1016/j.geb.2018.08.005.
  26. M. Menz, J. Wang, and J. Xie. Discrete all-pay bidding games. CoRR, abs/1504.02799, 2015. Google Scholar
  27. Y. Peres, O. Schramm, S. Sheffield, and D. B. Wilson. Tug-of-war and the infinity laplacian. J. Amer. Math. Soc., 22:167-210, 2009. Google Scholar
  28. Y. Peres and Z. Sunic. Biased infinity laplacian boundary problem on finite graphs. CoRR, abs/1912.13394, 2019. URL: http://arxiv.org/abs/1912.13394.
  29. A. Pnueli and R. Rosner. On the synthesis of a reactive module. In Proc. 16th POPL, pages 179-190, 1989. Google Scholar
  30. M. L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, Inc., New York, NY, USA, 2005. Google Scholar
  31. M.O. Rabin. Decidability of second order theories and automata on infinite trees. Transaction of the AMS, 141:1-35, 1969. Google Scholar
  32. G. Tullock. Toward a Theory of the Rent Seeking Society, chapter Efficient rent seeking, pages 97-112. College Station: Texas A&M Press, 1980. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact