---
_id: '10674'
abstract:
- lang: eng
  text: '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.'
acknowledgement: "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).\r\n"
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Milad
  full_name: Aghajohari, Milad
  last_name: Aghajohari
- first_name: Guy
  full_name: Avni, Guy
  id: 463C8BC2-F248-11E8-B48F-1D18A9856A87
  last_name: Avni
  orcid: 0000-0001-5588-8287
- first_name: Thomas A
  full_name: Henzinger, Thomas A
  id: 40876CD8-F248-11E8-B48F-1D18A9856A87
  last_name: Henzinger
  orcid: 0000-0002-2985-7724
citation:
  ama: Aghajohari M, Avni G, Henzinger TA. Determinacy in discrete-bidding infinite-duration
    games. <i>Logical Methods in Computer Science</i>. 2021;17(1):10:1-10:23. doi:<a
    href="https://doi.org/10.23638/LMCS-17(1:10)2021">10.23638/LMCS-17(1:10)2021</a>
  apa: Aghajohari, M., Avni, G., &#38; Henzinger, T. A. (2021). Determinacy in discrete-bidding
    infinite-duration games. <i>Logical Methods in Computer Science</i>. International
    Federation for Computational Logic. <a href="https://doi.org/10.23638/LMCS-17(1:10)2021">https://doi.org/10.23638/LMCS-17(1:10)2021</a>
  chicago: Aghajohari, Milad, Guy Avni, and Thomas A Henzinger. “Determinacy in Discrete-Bidding
    Infinite-Duration Games.” <i>Logical Methods in Computer Science</i>. International
    Federation for Computational Logic, 2021. <a href="https://doi.org/10.23638/LMCS-17(1:10)2021">https://doi.org/10.23638/LMCS-17(1:10)2021</a>.
  ieee: M. Aghajohari, G. Avni, and T. A. Henzinger, “Determinacy in discrete-bidding
    infinite-duration games,” <i>Logical Methods in Computer Science</i>, vol. 17,
    no. 1. International Federation for Computational Logic, p. 10:1-10:23, 2021.
  ista: Aghajohari M, Avni G, Henzinger TA. 2021. Determinacy in discrete-bidding
    infinite-duration games. Logical Methods in Computer Science. 17(1), 10:1-10:23.
  mla: Aghajohari, Milad, et al. “Determinacy in Discrete-Bidding Infinite-Duration
    Games.” <i>Logical Methods in Computer Science</i>, vol. 17, no. 1, International
    Federation for Computational Logic, 2021, p. 10:1-10:23, doi:<a href="https://doi.org/10.23638/LMCS-17(1:10)2021">10.23638/LMCS-17(1:10)2021</a>.
  short: M. Aghajohari, G. Avni, T.A. Henzinger, Logical Methods in Computer Science
    17 (2021) 10:1-10:23.
date_created: 2022-01-25T16:32:13Z
date_published: 2021-02-03T00:00:00Z
date_updated: 2023-08-17T06:56:42Z
day: '03'
ddc:
- '510'
department:
- _id: ToHe
doi: 10.23638/LMCS-17(1:10)2021
external_id:
  arxiv:
  - '1905.03588'
  isi:
  - '000658724600010'
file:
- access_level: open_access
  checksum: b35586a50ed1ca8f44767de116d18d81
  content_type: application/pdf
  creator: alisjak
  date_created: 2022-01-26T08:04:50Z
  date_updated: 2022-01-26T08:04:50Z
  file_id: '10690'
  file_name: 2021_LMCS_AGHAJOHAR.pdf
  file_size: 819878
  relation: main_file
  success: 1
file_date_updated: 2022-01-26T08:04:50Z
has_accepted_license: '1'
intvolume: '        17'
isi: 1
issue: '1'
keyword:
- computer science
- computer science and game theory
- logic in computer science
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
page: 10:1-10:23
project:
- _id: 264B3912-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: M02369
  name: Formal Methods meets Algorithmic Game Theory
- _id: 25F2ACDE-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S11402-N23
  name: Rigorous Systems Engineering
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: Z211
  name: The Wittgenstein Prize
publication: Logical Methods in Computer Science
publication_identifier:
  eissn:
  - 1860-5974
publication_status: published
publisher: International Federation for Computational Logic
quality_controlled: '1'
scopus_import: '1'
status: public
title: Determinacy in discrete-bidding infinite-duration games
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 17
year: '2021'
...