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).