---
_id: '6761'
abstract:
- lang: eng
  text: In resource allocation games, selfish players share resources that are needed
    in order to fulfill their objectives. The cost of using a resource depends on
    the load on it. In the traditional setting, the players make their choices concurrently
    and in one-shot. That is, a strategy for a player is a subset of the resources.
    We introduce and study dynamic resource allocation games. In this setting, the
    game proceeds in phases. In each phase each player chooses one resource. A scheduler
    dictates the order in which the players proceed in a phase, possibly scheduling
    several players to proceed concurrently. The game ends when each player has collected
    a set of resources that fulfills his objective. The cost for each player then
    depends on this set as well as on the load on the resources in it – we consider
    both congestion and cost-sharing games. We argue that the dynamic setting is the
    suitable setting for many applications in practice. We study the stability of
    dynamic resource allocation games, where the appropriate notion of stability is
    that of subgame perfect equilibrium, study the inefficiency incurred due to selfish
    behavior, and also study problems that are particular to the dynamic setting,
    like constraints on the order in which resources can be chosen or the problem
    of finding a scheduler that achieves stability.
article_processing_charge: No
article_type: original
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: Orna
  full_name: Kupferman, Orna
  last_name: Kupferman
citation:
  ama: Avni G, Henzinger TA, Kupferman O. Dynamic resource allocation games. <i>Theoretical
    Computer Science</i>. 2020;807:42-55. doi:<a href="https://doi.org/10.1016/j.tcs.2019.06.031">10.1016/j.tcs.2019.06.031</a>
  apa: Avni, G., Henzinger, T. A., &#38; Kupferman, O. (2020). Dynamic resource allocation
    games. <i>Theoretical Computer Science</i>. Elsevier. <a href="https://doi.org/10.1016/j.tcs.2019.06.031">https://doi.org/10.1016/j.tcs.2019.06.031</a>
  chicago: Avni, Guy, Thomas A Henzinger, and Orna Kupferman. “Dynamic Resource Allocation
    Games.” <i>Theoretical Computer Science</i>. Elsevier, 2020. <a href="https://doi.org/10.1016/j.tcs.2019.06.031">https://doi.org/10.1016/j.tcs.2019.06.031</a>.
  ieee: G. Avni, T. A. Henzinger, and O. Kupferman, “Dynamic resource allocation games,”
    <i>Theoretical Computer Science</i>, vol. 807. Elsevier, pp. 42–55, 2020.
  ista: Avni G, Henzinger TA, Kupferman O. 2020. Dynamic resource allocation games.
    Theoretical Computer Science. 807, 42–55.
  mla: Avni, Guy, et al. “Dynamic Resource Allocation Games.” <i>Theoretical Computer
    Science</i>, vol. 807, Elsevier, 2020, pp. 42–55, doi:<a href="https://doi.org/10.1016/j.tcs.2019.06.031">10.1016/j.tcs.2019.06.031</a>.
  short: G. Avni, T.A. Henzinger, O. Kupferman, Theoretical Computer Science 807 (2020)
    42–55.
date_created: 2019-08-04T21:59:20Z
date_published: 2020-02-06T00:00:00Z
date_updated: 2023-08-17T13:52:49Z
day: '06'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.1016/j.tcs.2019.06.031
external_id:
  isi:
  - '000512219400004'
file:
- access_level: open_access
  checksum: e86635417f45eb2cd75778f91382f737
  content_type: application/pdf
  creator: dernst
  date_created: 2020-10-09T06:31:22Z
  date_updated: 2020-10-09T06:31:22Z
  file_id: '8639'
  file_name: 2020_TheoreticalCS_Avni.pdf
  file_size: 1413001
  relation: main_file
  success: 1
file_date_updated: 2020-10-09T06:31:22Z
has_accepted_license: '1'
intvolume: '       807'
isi: 1
language:
- iso: eng
month: '02'
oa: 1
oa_version: Submitted Version
page: 42-55
project:
- _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
- _id: 264B3912-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: M02369
  name: Formal Methods meets Algorithmic Game Theory
publication: Theoretical Computer Science
publication_identifier:
  issn:
  - '03043975'
publication_status: published
publisher: Elsevier
quality_controlled: '1'
related_material:
  record:
  - id: '1341'
    relation: earlier_version
    status: public
scopus_import: '1'
status: public
title: Dynamic resource allocation games
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 807
year: '2020'
...
---
_id: '2246'
abstract:
- lang: eng
  text: 'Muller games are played by two players moving a token along a graph; the
    winner is determined by the set of vertices that occur infinitely often. The central
    algorithmic problem is to compute the winning regions for the players. Different
    classes and representations of Muller games lead to problems of varying computational
    complexity. One such class are parity games; these are of particular significance
    in computational complexity, as they remain one of the few combinatorial problems
    known to be in NP ∩ co-NP but not known to be in P. We show that winning regions
    for a Muller game can be determined from the alternating structure of its traps.
    To every Muller game we then associate a natural number that we call its trap
    depth; this parameter measures how complicated the trap structure is. We present
    algorithms for parity games that run in polynomial time for graphs of bounded
    trap depth, and in general run in time exponential in the trap depth. '
author:
- first_name: Andrey
  full_name: Grinshpun, Andrey
  last_name: Grinshpun
- first_name: Pakawat
  full_name: Phalitnonkiat, Pakawat
  last_name: Phalitnonkiat
- first_name: Sasha
  full_name: Rubin, Sasha
  id: 2EC51194-F248-11E8-B48F-1D18A9856A87
  last_name: Rubin
- first_name: Andrei
  full_name: Tarfulea, Andrei
  last_name: Tarfulea
citation:
  ama: Grinshpun A, Phalitnonkiat P, Rubin S, Tarfulea A. Alternating traps in Muller
    and parity games. <i>Theoretical Computer Science</i>. 2014;521:73-91. doi:<a
    href="https://doi.org/10.1016/j.tcs.2013.11.032">10.1016/j.tcs.2013.11.032</a>
  apa: Grinshpun, A., Phalitnonkiat, P., Rubin, S., &#38; Tarfulea, A. (2014). Alternating
    traps in Muller and parity games. <i>Theoretical Computer Science</i>. Elsevier.
    <a href="https://doi.org/10.1016/j.tcs.2013.11.032">https://doi.org/10.1016/j.tcs.2013.11.032</a>
  chicago: Grinshpun, Andrey, Pakawat Phalitnonkiat, Sasha Rubin, and Andrei Tarfulea.
    “Alternating Traps in Muller and Parity Games.” <i>Theoretical Computer Science</i>.
    Elsevier, 2014. <a href="https://doi.org/10.1016/j.tcs.2013.11.032">https://doi.org/10.1016/j.tcs.2013.11.032</a>.
  ieee: A. Grinshpun, P. Phalitnonkiat, S. Rubin, and A. Tarfulea, “Alternating traps
    in Muller and parity games,” <i>Theoretical Computer Science</i>, vol. 521. Elsevier,
    pp. 73–91, 2014.
  ista: Grinshpun A, Phalitnonkiat P, Rubin S, Tarfulea A. 2014. Alternating traps
    in Muller and parity games. Theoretical Computer Science. 521, 73–91.
  mla: Grinshpun, Andrey, et al. “Alternating Traps in Muller and Parity Games.” <i>Theoretical
    Computer Science</i>, vol. 521, Elsevier, 2014, pp. 73–91, doi:<a href="https://doi.org/10.1016/j.tcs.2013.11.032">10.1016/j.tcs.2013.11.032</a>.
  short: A. Grinshpun, P. Phalitnonkiat, S. Rubin, A. Tarfulea, Theoretical Computer
    Science 521 (2014) 73–91.
date_created: 2018-12-11T11:56:33Z
date_published: 2014-02-13T00:00:00Z
date_updated: 2021-01-12T06:56:16Z
day: '13'
department:
- _id: KrCh
doi: 10.1016/j.tcs.2013.11.032
intvolume: '       521'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: http://arxiv.org/abs/1303.3777
month: '02'
oa: 1
oa_version: Submitted Version
page: 73 - 91
publication: Theoretical Computer Science
publication_identifier:
  issn:
  - '03043975'
publication_status: published
publisher: Elsevier
publist_id: '4703'
quality_controlled: '1'
scopus_import: 1
status: public
title: Alternating traps in Muller and parity games
type: journal_article
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 521
year: '2014'
...