The quality of equilibria for set packing and throughput scheduling games

Jasper de Jong, Marc Uetz*

*Corresponding author for this work

    Research output: Contribution to journalArticleAcademicpeer-review

    11 Downloads (Pure)

    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 α-approximate equilibrium, our tight price of anarchy bounds are α+ 1 for Nash and subgame perfect equilibria, but less than α+ 1 / (e- 1) for subgame perfect equilibria when games are symmetric. For k-collusion Nash equilibria, the price of anarchy equals α+ (n- k) / (n- 1) , where 1 ≤ k≤ n.

    Original languageEnglish
    Pages (from-to)321-344
    Number of pages24
    JournalInternational journal of game theory
    Volume49
    DOIs
    Publication statusPublished - 19 Aug 2019

    Keywords

    • Price of anarchy
    • Set packing
    • Throughput scheduling

    Fingerprint Dive into the research topics of 'The quality of equilibria for set packing and throughput scheduling games'. Together they form a unique fingerprint.

  • Cite this