A common generalization of budget games and congestion games

Fuga Kiyosue and Kenjiro Takazawa ()
Additional contact information
Fuga Kiyosue: SCSK Corporation
Kenjiro Takazawa: Hosei University

Journal of Combinatorial Optimization, 2024, vol. 48, issue 3, No 9, 18 pages

Abstract: Abstract Budget games were introduced by Drees, Riechers, and Skopalik (2014) as a model of noncooperative games arising from resource allocation problems. Budget games have several similarities to congestion games, one of which is that the matroid structure of the strategy space is essential for the existence of a pure Nash equilibrium (PNE). Despite these similarities, however, the theoretical relation between budget games and congestion games has been unclear. In this paper, we provide a common generalization of budget games and congestion games, called generalized budget games (g-budget games, for short), to establish a large class of noncooperative games retaining the nice property of the matroid structure. We show that the model of g-budget games includes weighted congestion games and player-specific congestion games under certain assumptions. We further show that g-budget games also include offset budget games, a generalized model of budget games by Drees, Feldotto, Riechers, and Skopalik (2019). We then prove that every matroid g-budget game has a PNE, which extends the result for budget games. We finally a PNE in a certain class of singleton g-budget games can be computed in a greedy manner.

Keywords: Noncooperative game; Pure Nash equilibrium; Matroid; 91A68; 91A14; 90C27 (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-024-01218-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:48:y:2024:i:3:d:10.1007_s10878-024-01218-7

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-024-01218-7

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().