The quality of equilibria for set packing and throughput scheduling games

Jasper Jong () and Marc Uetz ()
Additional contact information
Jasper Jong: University of Twente
Marc Uetz: University of Twente

International Journal of Game Theory, 2020, vol. 49, issue 1, No 14, 344 pages

Abstract: Abstract We introduce set packing games as an abstraction of situations in which n selfish players select disjoint subsets of a finite set of indivisible items, and analyze the quality of several equilibria for this basic class of games. Special attention is given to a subclass of set packing games, namely throughput scheduling games, where the items represent jobs, and the subsets that a player can select are those jobs that this player can schedule feasibly. We show that the quality of three types of equilibrium solutions is only moderately suboptimal. Specifically, the paper gives tight bounds on the price of anarchy for Nash equilibria, subgame perfect equilibria of games with sequential play, and k-collusion Nash equilibria. Under the assumption that players are allowed to play suboptimally and achieve an $$\alpha $$α-approximate equilibrium, our tight price of anarchy bounds are $$\alpha +1$$α+1 for Nash and subgame perfect equilibria, but less than $$\alpha +1/(e-1)$$α+1/(e-1) for subgame perfect equilibria when games are symmetric. For k-collusion Nash equilibria, the price of anarchy equals $$\alpha +(n-k)/(n-1)$$α+(n-k)/(n-1), where $$1\le k\le n$$1≤k≤n.

Keywords: Set packing; Throughput scheduling; Price of anarchy (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s00182-019-00693-1 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:jogath:v:49:y:2020:i:1:d:10.1007_s00182-019-00693-1

Ordering information: This journal article can be ordered from
http://www.springer. ... eory/journal/182/PS2

DOI: 10.1007/s00182-019-00693-1

Access Statistics for this article

International Journal of Game Theory is currently edited by Shmuel Zamir, Vijay Krishna and Bernhard von Stengel

More articles in International Journal of Game Theory from Springer, Game Theory Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().