---
_id: '8599'
abstract:
- lang: eng
  text: 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.
acknowledgement: 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.
alternative_title:
- LIPIcs
article_number: '2'
article_processing_charge: No
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
citation:
  ama: 'Avni G, Henzinger TA. A survey of bidding games on graphs. In: <i>31st International
    Conference on Concurrency Theory</i>. Vol 171. Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik; 2020. doi:<a href="https://doi.org/10.4230/LIPIcs.CONCUR.2020.2">10.4230/LIPIcs.CONCUR.2020.2</a>'
  apa: 'Avni, G., &#38; Henzinger, T. A. (2020). A survey of bidding games on graphs.
    In <i>31st International Conference on Concurrency Theory</i> (Vol. 171). Virtual:
    Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPIcs.CONCUR.2020.2">https://doi.org/10.4230/LIPIcs.CONCUR.2020.2</a>'
  chicago: Avni, Guy, and Thomas A Henzinger. “A Survey of Bidding Games on Graphs.”
    In <i>31st International Conference on Concurrency Theory</i>, Vol. 171. Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href="https://doi.org/10.4230/LIPIcs.CONCUR.2020.2">https://doi.org/10.4230/LIPIcs.CONCUR.2020.2</a>.
  ieee: G. Avni and T. A. Henzinger, “A survey of bidding games on graphs,” in <i>31st
    International Conference on Concurrency Theory</i>, Virtual, 2020, vol. 171.
  ista: 'Avni G, Henzinger TA. 2020. A survey of bidding games on graphs. 31st International
    Conference on Concurrency Theory. CONCUR: Conference on Concurrency Theory, LIPIcs,
    vol. 171, 2.'
  mla: Avni, Guy, and Thomas A. Henzinger. “A Survey of Bidding Games on Graphs.”
    <i>31st International Conference on Concurrency Theory</i>, vol. 171, 2, Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href="https://doi.org/10.4230/LIPIcs.CONCUR.2020.2">10.4230/LIPIcs.CONCUR.2020.2</a>.
  short: G. Avni, T.A. Henzinger, in:, 31st International Conference on Concurrency
    Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
conference:
  end_date: 2020-09-04
  location: Virtual
  name: 'CONCUR: Conference on Concurrency Theory'
  start_date: 2020-09-01
date_created: 2020-10-04T22:01:36Z
date_published: 2020-08-06T00:00:00Z
date_updated: 2021-01-12T08:20:13Z
day: '06'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.4230/LIPIcs.CONCUR.2020.2
file:
- access_level: open_access
  checksum: 8f33b098e73724e0ac817f764d8e1a2d
  content_type: application/pdf
  creator: dernst
  date_created: 2020-10-05T14:13:19Z
  date_updated: 2020-10-05T14:13:19Z
  file_id: '8611'
  file_name: 2020_LIPIcsCONCUR_Avni.pdf
  file_size: 868510
  relation: main_file
  success: 1
file_date_updated: 2020-10-05T14:13:19Z
has_accepted_license: '1'
intvolume: '       171'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/3.0/
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: Z211
  name: The Wittgenstein Prize
publication: 31st International Conference on Concurrency Theory
publication_identifier:
  isbn:
  - '9783959771603'
  issn:
  - '18688969'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: A survey of bidding games on graphs
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/3.0/legalcode
  name: Creative Commons Attribution 3.0 Unported (CC BY 3.0)
  short: CC BY (3.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 171
year: '2020'
...
---
_id: '8600'
abstract:
- lang: eng
  text: 'A vector addition system with states (VASS) consists of a finite set of states
    and counters. A transition changes the current state to the next state, and every
    counter is either incremented, or decremented, or left unchanged. A state and
    value for each counter is a configuration; and a computation is an infinite sequence
    of configurations with transitions between successive configurations. A probabilistic
    VASS consists of a VASS along with a probability distribution over the transitions
    for each state. Qualitative properties such as state and configuration reachability
    have been widely studied for VASS. In this work we consider multi-dimensional
    long-run average objectives for VASS and probabilistic VASS. For a counter, the
    cost of a configuration is the value of the counter; and the long-run average
    value of a computation for the counter is the long-run average of the costs of
    the configurations in the computation. The multi-dimensional long-run average
    problem given a VASS and a threshold value for each counter, asks whether there
    is a computation such that for each counter the long-run average value for the
    counter does not exceed the respective threshold. For probabilistic VASS, instead
    of the existence of a computation, we consider whether the expected long-run average
    value for each counter does not exceed the respective threshold. Our main results
    are as follows: we show that the multi-dimensional long-run average problem (a)
    is NP-complete for integer-valued VASS; (b) is undecidable for natural-valued
    VASS (i.e., nonnegative counters); and (c) can be solved in polynomial time for
    probabilistic integer-valued VASS, and probabilistic natural-valued VASS when
    all computations are non-terminating.'
alternative_title:
- LIPIcs
article_number: '23'
article_processing_charge: No
arxiv: 1
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- 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: Jan
  full_name: Otop, Jan
  id: 2FC5DA74-F248-11E8-B48F-1D18A9856A87
  last_name: Otop
citation:
  ama: 'Chatterjee K, Henzinger TA, Otop J. Multi-dimensional long-run average problems
    for vector addition systems with states. In: <i>31st International Conference
    on Concurrency Theory</i>. Vol 171. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
    2020. doi:<a href="https://doi.org/10.4230/LIPIcs.CONCUR.2020.23">10.4230/LIPIcs.CONCUR.2020.23</a>'
  apa: 'Chatterjee, K., Henzinger, T. A., &#38; Otop, J. (2020). Multi-dimensional
    long-run average problems for vector addition systems with states. In <i>31st
    International Conference on Concurrency Theory</i> (Vol. 171). Virtual: Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPIcs.CONCUR.2020.23">https://doi.org/10.4230/LIPIcs.CONCUR.2020.23</a>'
  chicago: Chatterjee, Krishnendu, Thomas A Henzinger, and Jan Otop. “Multi-Dimensional
    Long-Run Average Problems for Vector Addition Systems with States.” In <i>31st
    International Conference on Concurrency Theory</i>, Vol. 171. Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik, 2020. <a href="https://doi.org/10.4230/LIPIcs.CONCUR.2020.23">https://doi.org/10.4230/LIPIcs.CONCUR.2020.23</a>.
  ieee: K. Chatterjee, T. A. Henzinger, and J. Otop, “Multi-dimensional long-run average
    problems for vector addition systems with states,” in <i>31st International Conference
    on Concurrency Theory</i>, Virtual, 2020, vol. 171.
  ista: 'Chatterjee K, Henzinger TA, Otop J. 2020. Multi-dimensional long-run average
    problems for vector addition systems with states. 31st International Conference
    on Concurrency Theory. CONCUR: Conference on Concurrency Theory, LIPIcs, vol.
    171, 23.'
  mla: Chatterjee, Krishnendu, et al. “Multi-Dimensional Long-Run Average Problems
    for Vector Addition Systems with States.” <i>31st International Conference on
    Concurrency Theory</i>, vol. 171, 23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2020, doi:<a href="https://doi.org/10.4230/LIPIcs.CONCUR.2020.23">10.4230/LIPIcs.CONCUR.2020.23</a>.
  short: K. Chatterjee, T.A. Henzinger, J. Otop, in:, 31st International Conference
    on Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
conference:
  end_date: 2020-09-04
  location: Virtual
  name: 'CONCUR: Conference on Concurrency Theory'
  start_date: 2020-09-01
date_created: 2020-10-04T22:01:36Z
date_published: 2020-08-06T00:00:00Z
date_updated: 2021-01-12T08:20:15Z
day: '06'
ddc:
- '000'
department:
- _id: KrCh
- _id: ToHe
doi: 10.4230/LIPIcs.CONCUR.2020.23
external_id:
  arxiv:
  - '2007.08917'
file:
- access_level: open_access
  checksum: 5039752f644c4b72b9361d21a5e31baf
  content_type: application/pdf
  creator: dernst
  date_created: 2020-10-05T14:04:25Z
  date_updated: 2020-10-05T14:04:25Z
  file_id: '8610'
  file_name: 2020_LIPIcsCONCUR_Chatterjee.pdf
  file_size: 601231
  relation: main_file
  success: 1
file_date_updated: 2020-10-05T14:04:25Z
has_accepted_license: '1'
intvolume: '       171'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S 11407_N23
  name: Rigorous Systems Engineering
- _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: 31st International Conference on Concurrency Theory
publication_identifier:
  isbn:
  - '9783959771603'
  issn:
  - '18688969'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Multi-dimensional long-run average problems for vector addition systems with
  states
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/3.0/legalcode
  name: Creative Commons Attribution 3.0 Unported (CC BY 3.0)
  short: CC BY (3.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 171
year: '2020'
...