Coalitional Games on Graphs: Core Structure, Substitutes and Frugality

摘要

This note correlates some notions in mechanism design to concepts from game theory. We formalize the notion of frugality and extend it to define the frugality ratio of a mechanism. We establish the equivalence of frugality and a slightly modified version of the agents are substitutes condition. We show that if the core forms a lattice, then the agents satisfy the substitutes condition. This leads to a three-way equivalence of the core being a lattice, agents satisfying the substitutes condition, and the VCG payment being frugal. Archer and Tardos showed that the VCG payment in the Shortest Path game can be very high as compared to the cost of second best solution. On the other hand, the VCG payment in games like MST coincide with the cost of the second best solution. This can be attributed to the fundamental difference in the structure of the core. The core of the MST game is a lattice, implying that within the core, the agents are in some sense independent. On the other hand, the core for the shortest path game does not satisfy the lattice property, and a change in the bid of one agent affects other agents even inside the core. Thus, the basic structure of the core can provide an insight into why the particular mechanism (in this case, VCG) exhibits very different characteristics, in terms of frugality of payments, from one game to another.