The quality of equilibria for set packing and throughput scheduling games

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