Rahul Garg, Vijay Kumar, Atri Rudra and Akshat
Verma
Coalition Games on Graphs: core structure, substitutes and frugality
Abstract :
In this work, we investigate the core structure and
mechanisms for network design problems
that can be modeled as coalitional games with
transferable utilities using ideas from mechanism design and
game theory. We
establish an equivalence between the game-theoretic notion of
agents being substitutes and the notion of frugality
of a mechanism. We characterize the core of the network design
game and relate it to outcomes in a sealed bid auction with VCG
payments. We show that in a game, agents are substitutes if and
only if the core of the game forms a complete lattice. Using the insights
obtained by observing the core structure of specific
problems (in light of our equivalence results) where VCG mechanism
leads to frugal payoff, we design a Global Descending Price auction
for all network design problems
that always terminates to a frugal payoff in the core
(if the core is non-empty).
Versions