---
_id: '5788'
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 or payoff of the game. Such
    games are central in formal verification since they model the interaction between
    a non-terminating system and its environment. We study bidding games in which
    the players bid for the right to move the token. Two bidding rules have been defined.
    In Richman bidding, in each round, the players simultaneously submit bids, and
    the higher bidder moves the token and pays the other player. Poorman bidding is
    similar except that the winner of the bidding pays the “bank” rather than the
    other player. While poorman reachability games have been studied before, we present,
    for the first time, results on infinite-duration poorman games. A central quantity
    in these games is the ratio between the two players’ initial budgets. The questions
    we study concern a necessary and sufficient ratio with which a player can achieve
    a goal. For reachability objectives, such threshold ratios are known to exist
    for both bidding rules. We show that the properties of poorman reachability games
    extend to complex qualitative objectives such as parity, similarly to the Richman
    case. Our most interesting results concern quantitative poorman games, namely
    poorman mean-payoff games, where we construct optimal strategies depending on
    the initial ratio, by showing a connection with random-turn based games. The connection
    in itself is interesting, because it does not hold for reachability poorman games.
    We also solve the complexity problems that arise in poorman bidding games.
alternative_title:
- LNCS
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: Thomas A
  full_name: Henzinger, Thomas A
  id: 40876CD8-F248-11E8-B48F-1D18A9856A87
  last_name: Henzinger
  orcid: 0000−0002−2985−7724
- first_name: Rasmus
  full_name: Ibsen-Jensen, Rasmus
  id: 3B699956-F248-11E8-B48F-1D18A9856A87
  last_name: Ibsen-Jensen
  orcid: 0000-0003-4783-0389
citation:
  ama: 'Avni G, Henzinger TA, Ibsen-Jensen R. Infinite-duration poorman-bidding games.
    In: Vol 11316. Springer; 2018:21-36. doi:<a href="https://doi.org/10.1007/978-3-030-04612-5_2">10.1007/978-3-030-04612-5_2</a>'
  apa: 'Avni, G., Henzinger, T. A., &#38; Ibsen-Jensen, R. (2018). Infinite-duration
    poorman-bidding games (Vol. 11316, pp. 21–36). Presented at the 14th International
    Conference on Web and Internet Economics, WINE, Oxford, UK: Springer. <a href="https://doi.org/10.1007/978-3-030-04612-5_2">https://doi.org/10.1007/978-3-030-04612-5_2</a>'
  chicago: Avni, Guy, Thomas A Henzinger, and Rasmus Ibsen-Jensen. “Infinite-Duration
    Poorman-Bidding Games,” 11316:21–36. Springer, 2018. <a href="https://doi.org/10.1007/978-3-030-04612-5_2">https://doi.org/10.1007/978-3-030-04612-5_2</a>.
  ieee: G. Avni, T. A. Henzinger, and R. Ibsen-Jensen, “Infinite-duration poorman-bidding
    games,” presented at the 14th International Conference on Web and Internet Economics,
    WINE, Oxford, UK, 2018, vol. 11316, pp. 21–36.
  ista: Avni G, Henzinger TA, Ibsen-Jensen R. 2018. Infinite-duration poorman-bidding
    games. 14th International Conference on Web and Internet Economics, WINE, LNCS,
    vol. 11316, 21–36.
  mla: Avni, Guy, et al. <i>Infinite-Duration Poorman-Bidding Games</i>. Vol. 11316,
    Springer, 2018, pp. 21–36, doi:<a href="https://doi.org/10.1007/978-3-030-04612-5_2">10.1007/978-3-030-04612-5_2</a>.
  short: G. Avni, T.A. Henzinger, R. Ibsen-Jensen, in:, Springer, 2018, pp. 21–36.
conference:
  end_date: 2018-12-17
  location: Oxford, UK
  name: 14th International Conference on Web and Internet Economics, WINE
  start_date: 2018-12-15
date_created: 2018-12-30T22:59:14Z
date_published: 2018-11-21T00:00:00Z
date_updated: 2026-04-16T09:54:39Z
day: '21'
department:
- _id: ToHe
doi: 10.1007/978-3-030-04612-5_2
external_id:
  arxiv:
  - '1804.04372'
  isi:
  - '000865933000002'
intvolume: '     11316'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1804.04372
month: '11'
oa: 1
oa_version: Preprint
page: 21-36
project:
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: Z211
  name: Formal methods for the design and analysis of complex systems
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S 11407_N23
  name: Rigorous Systems Engineering
- _id: 264B3912-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: M02369
  name: Formal Methods meets Algorithmic Game Theory
publication_identifier:
  isbn:
  - '9783030046118'
  issn:
  - 0302-9743
publisher: Springer
quality_controlled: '1'
scopus_import: '1'
status: public
title: Infinite-duration poorman-bidding games
type: conference
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 11316
year: '2018'
...