---
_id: '14518'
abstract:
- lang: eng
  text: We consider bidding games, a class of two-player zero-sum graph games. The
    game proceeds as follows. Both players have bounded budgets. A token is placed
    on a vertex of a graph, in each turn the players simultaneously submit bids, and
    the higher bidder moves the token, where we break bidding ties in favor of Player
    1. Player 1 wins the game iff the token visits a designated target vertex. We
    consider, for the first time, poorman discrete-bidding in which the granularity
    of the bids is restricted and the higher bid is paid to the bank. Previous work
    either did not impose granularity restrictions or considered Richman bidding (bids
    are paid to the opponent). While the latter mechanisms are technically more accessible,
    the former is more appealing from a practical standpoint. Our study focuses on
    threshold budgets, which is the necessary and sufficient initial budget required
    for Player 1 to ensure winning against a given Player 2 budget. We first show
    existence of thresholds. In DAGs, we show that threshold budgets can be approximated
    with error bounds by thresholds under continuous-bidding and that they exhibit
    a periodic behavior. We identify closed-form solutions in special cases. We implement
    and experiment with an algorithm to find threshold budgets.
acknowledgement: This research was supported in part by ISF grant no. 1679/21, ERC
  CoG 863818 (FoRM-SMArt) and the European Union’s Horizon 2020 research and innovation
  programme under the Marie SkłodowskaCurie Grant Agreement No. 665385.
article_processing_charge: No
arxiv: 1
author:
- first_name: Guy
  full_name: Avni, Guy
  id: 463C8BC2-F248-11E8-B48F-1D18A9856A87
  last_name: Avni
  orcid: 0000-0001-5588-8287
- first_name: Tobias
  full_name: Meggendorfer, Tobias
  id: b21b0c15-30a2-11eb-80dc-f13ca25802e1
  last_name: Meggendorfer
  orcid: 0000-0002-1712-2165
- first_name: Suman
  full_name: Sadhukhan, Suman
  last_name: Sadhukhan
- first_name: Josef
  full_name: Tkadlec, Josef
  id: 3F24CCC8-F248-11E8-B48F-1D18A9856A87
  last_name: Tkadlec
  orcid: 0000-0002-1097-9684
- first_name: Dorde
  full_name: Zikelic, Dorde
  id: 294AA7A6-F248-11E8-B48F-1D18A9856A87
  last_name: Zikelic
  orcid: 0000-0002-4681-1699
citation:
  ama: 'Avni G, Meggendorfer T, Sadhukhan S, Tkadlec J, Zikelic D. Reachability poorman
    discrete-bidding games. In: <i>Frontiers in Artificial Intelligence and Applications</i>.
    Vol 372. IOS Press; 2023:141-148. doi:<a href="https://doi.org/10.3233/FAIA230264">10.3233/FAIA230264</a>'
  apa: 'Avni, G., Meggendorfer, T., Sadhukhan, S., Tkadlec, J., &#38; Zikelic, D.
    (2023). Reachability poorman discrete-bidding games. In <i>Frontiers in Artificial
    Intelligence and Applications</i> (Vol. 372, pp. 141–148). Krakow, Poland: IOS
    Press. <a href="https://doi.org/10.3233/FAIA230264">https://doi.org/10.3233/FAIA230264</a>'
  chicago: Avni, Guy, Tobias Meggendorfer, Suman Sadhukhan, Josef Tkadlec, and Dorde
    Zikelic. “Reachability Poorman Discrete-Bidding Games.” In <i>Frontiers in Artificial
    Intelligence and Applications</i>, 372:141–48. IOS Press, 2023. <a href="https://doi.org/10.3233/FAIA230264">https://doi.org/10.3233/FAIA230264</a>.
  ieee: G. Avni, T. Meggendorfer, S. Sadhukhan, J. Tkadlec, and D. Zikelic, “Reachability
    poorman discrete-bidding games,” in <i>Frontiers in Artificial Intelligence and
    Applications</i>, Krakow, Poland, 2023, vol. 372, pp. 141–148.
  ista: 'Avni G, Meggendorfer T, Sadhukhan S, Tkadlec J, Zikelic D. 2023. Reachability
    poorman discrete-bidding games. Frontiers in Artificial Intelligence and Applications.
    ECAI: European Conference on Artificial Intelligence vol. 372, 141–148.'
  mla: Avni, Guy, et al. “Reachability Poorman Discrete-Bidding Games.” <i>Frontiers
    in Artificial Intelligence and Applications</i>, vol. 372, IOS Press, 2023, pp.
    141–48, doi:<a href="https://doi.org/10.3233/FAIA230264">10.3233/FAIA230264</a>.
  short: G. Avni, T. Meggendorfer, S. Sadhukhan, J. Tkadlec, D. Zikelic, in:, Frontiers
    in Artificial Intelligence and Applications, IOS Press, 2023, pp. 141–148.
conference:
  end_date: 2023-10-04
  location: Krakow, Poland
  name: 'ECAI: European Conference on Artificial Intelligence'
  start_date: 2023-09-30
date_created: 2023-11-12T23:00:56Z
date_published: 2023-09-28T00:00:00Z
date_updated: 2025-07-14T09:09:57Z
day: '28'
ddc:
- '000'
department:
- _id: ToHe
- _id: KrCh
doi: 10.3233/FAIA230264
ec_funded: 1
external_id:
  arxiv:
  - '2307.15218'
file:
- access_level: open_access
  checksum: 1390ca38480fa4cf286b0f1a42e8c12f
  content_type: application/pdf
  creator: dernst
  date_created: 2023-11-13T10:16:10Z
  date_updated: 2023-11-13T10:16:10Z
  file_id: '14529'
  file_name: 2023_FAIA_Avni.pdf
  file_size: 501011
  relation: main_file
  success: 1
file_date_updated: 2023-11-13T10:16:10Z
has_accepted_license: '1'
intvolume: '       372'
language:
- iso: eng
license: https://creativecommons.org/licenses/by-nc/4.0/
month: '09'
oa: 1
oa_version: Published Version
page: 141-148
project:
- _id: 2564DBCA-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '665385'
  name: International IST Doctoral Program
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
  call_identifier: H2020
  grant_number: '863818'
  name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: Frontiers in Artificial Intelligence and Applications
publication_identifier:
  isbn:
  - '9781643684369'
  issn:
  - 0922-6389
publication_status: published
publisher: IOS Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: Reachability poorman discrete-bidding games
tmp:
  image: /images/cc_by_nc.png
  legal_code_url: https://creativecommons.org/licenses/by-nc/4.0/legalcode
  name: Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)
  short: CC BY-NC (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 372
year: '2023'
...