Document Open Access Logo

Determinacy in Discrete-Bidding Infinite-Duration Games

Authors Milad Aghajohari, Guy Avni, Thomas A. Henzinger

PDF
Thumbnail PDF

File

LIPIcs.CONCUR.2019.20.pdf
  • Filesize: 0.7 MB
  • 17 pages

Document Identifiers

Author Details

Milad Aghajohari
  • Sharif University of Technology, Iran
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 grants S11402-N23 (RiSE/SHiNE), Z211-N23 (Wittgenstein Award), and M 2369-N33 (Meitner fellowship).

Cite AsGet BibTex

Milad Aghajohari, Guy Avni, and Thomas A. Henzinger. Determinacy in Discrete-Bidding Infinite-Duration Games. In 30th International Conference on Concurrency Theory (CONCUR 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 140, pp. 20:1-20:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.CONCUR.2019.20

Abstract

In two-player games on graphs, the players move a token through a graph to produce an infinite path, which determines the winner of the game. Such games are central in formal methods since they model the interaction between a non-terminating system and its environment. In bidding games the players bid for the right to move the token: in each round, the players simultaneously submit bids, and the higher bidder moves the token and pays the other player. Bidding games are known to have a clean and elegant mathematical structure that relies on the ability of the players to submit arbitrarily small bids. Many applications, however, require a fixed granularity for the bids, which can represent, for example, the monetary value expressed in cents. We study, for the first time, the combination of discrete-bidding and infinite-duration games. Our most important result proves that these games form a large determined subclass of concurrent games, where determinacy is the strong property that there always exists exactly one player who can guarantee winning the game. In particular, we show that, in contrast to non-discrete bidding games, the mechanism with which tied bids are resolved plays an important role in discrete-bidding games. We study several natural tie-breaking mechanisms and show that, while some do not admit determinacy, most natural mechanisms imply determinacy for every pair of initial budgets.

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 games
  • determinacy
  • concurrent games
  • discrete bidding

Metrics

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

Related Versions

References

  1. S. Almagor, G. Avni, and O. Kupferman. Repairing Multi-Player Games. In Proc. 26th CONCUR, pages 325-339, 2015. 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. B. Aminof and S. Rubin. First-cycle games. Inf. Comput., 254:195-216, 2017. Google Scholar
  4. K.R. Apt and E. Grädel. Lectures in Game Theory for Computer Scientists. Cambridge University Press, 2011. Google Scholar
  5. N. Atzei, M. Bartoletti, and T. Cimoli. A survey of attacks on Ethereum smart contracts. IACR Cryptology ePrint Archive, 2016:1007, 2016. Google Scholar
  6. G. Avni, S. Guha, and O. Kupferman. An Abstraction-Refinement Methodology for Reasoning about Network Games. Games, 9(3), 2018. Google Scholar
  7. G. Avni, T. A. Henzinger, and V. Chonev. Infinite-Duration Bidding Games. In Proc. 28th CONCUR, volume 85 of LIPIcs, pages 21:1-21:18, 2017. Google Scholar
  8. 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
  9. G. Avni, T. A. Henzinger, and O. Kupferman. Dynamic Resource Allocation Games. In Proc. 9th SAGT, pages 153-166, 2016. Google Scholar
  10. G. Avni, T. A. Henzinger, and Đ. Žikelić. Bidding Mechanisms in Graph Games. In In Proc. 44th MFCS, 2019. Google Scholar
  11. G. Avni, O. Kupferman, and T. Tamir. Network-formation games with regular objectives. Inf. Comput., 251:165-178, 2016. Google Scholar
  12. J. Bhatt and S. Payne. Bidding Chess. Math. Intelligencer, 31:37-39, 2009. Google Scholar
  13. T. Brihaye, V. Bruyère, J. De Pril, and H. Gimbert. On Subgame Perfection in Quantitative Reachability Games. Logical Methods in Computer Science, 9(1), 2012. Google Scholar
  14. K. Chatterjee. Nash Equilibrium for Upward-Closed Objectives. In Proc. 15th CSL, volume 4207, pages 271-286. Springer, 2006. Google Scholar
  15. K. Chatterjee, A. K. Goharshady, and Y. Velner. Quantitative Analysis of Smart Contracts. In Proc. 27th ESOP, pages 739-767, 2018. Google Scholar
  16. K. Chatterjee, T. A. Henzinger, and M. Jurdzinski. Games with secure equilibria. Theor. Comput. Sci., 365(1-2):67-82, 2006. Google Scholar
  17. K. Chatterjee, T. A. Henzinger, and N. Piterman. Strategy logic. Inf. Comput., 208(6):677-693, 2010. Google Scholar
  18. K. Chatterjee, R. Majumdar, and M. Jurdzinski. On Nash Equilibria in Stochastic Games. In Proc. 13th CSL, pages 26-40, 2004. Google Scholar
  19. A. Condon. On Algorithms for Simple Stochastic Games. In Proc. DIMACS, pages 51-72, 1990. Google Scholar
  20. M. Develin and S. Payne. Discrete Bidding Games. The Electronic Journal of Combinatorics, 17(1):R85, 2010. Google Scholar
  21. E.A. Emerson and C. Jutla. Tree Automata, μ-Calculus and Determinacy. In Proc. 32nd FOCS, pages 368-377, 1991. Google Scholar
  22. D. Fisman, O. Kupferman, and Y. Lustig. Rational Synthesis. In Proc. 16th TACAS, pages 190-204, 2010. Google Scholar
  23. E. Grädel, W. Thomas, and T. Wilke. Automata, Logics, and Infinite Games: A Guide to Current Research, volume 2500. Springer, 2002. Google Scholar
  24. O. Kupferman and T. Tamir. Hierarchical Network Formation Games. In Proc. 23rd TACAS, pages 229-246, 2017. Google Scholar
  25. 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
  26. A. J. Lazarus, D. E. Loeb, J. G. Propp, and D. Ullman. Richman Games. Games of No Chance, 29:439-449, 1996. Google Scholar
  27. D. A. Martin. The Determinacy of Blackwell Games. J. Symb. Log., 63(4):1565-1581, 1998. Google Scholar
  28. D.A. Martin. Borel Determinacy. Annals of Mathematics, 65:363-371, 1975. Google Scholar
  29. 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.
  30. M. Menz, J. Wang, and J. Xie. Discrete All-Pay Bidding Games. CoRR, abs/1504.02799, 2015. URL: http://arxiv.org/abs/1504.02799.
  31. F. Mogavero, A. Murano, G. Perelli, and M. Y. Vardi. Reasoning About Strategies: On the Model-Checking Problem. ACM Trans. Comput. Log., 15(4):34:1-34:47, 2014. Google Scholar
  32. S. Muthukrishnan. Ad Exchanges: Research Issues. In Proc. 5th WINE, pages 1-12, 2009. Google Scholar
  33. N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani. Algorithmic Game Theory. Cambridge University Press, 2007. Google Scholar
  34. 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
  35. A. Pnueli and R. Rosner. On the Synthesis of a Reactive Module. In Proc. 16th POPL, pages 179-190, 1989. Google Scholar
  36. M.O. Rabin. Decidability of Second Order Theories and Automata on Infinite Trees. Transaction of the AMS, 141:1-35, 1969. Google Scholar
  37. S. Le Roux. Concurrent Games and Semi-Random Determinacy. In Proc. 43rd MFCS, pages 40:1-40:15, 2018. 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 Imprint Privacy Contact