Fair cake-cutting is the division of a cake or resource among N users so that each user is content. Users may value a given piece of cake differently, and information about how a user values different parts of the cake can only be obtained by request

摘要

The celebrated Vickrey-Clarke-Grove(VCG) mechanism induces selfish agents to behave truthfully by paying them a premium. In the process, it may end up paying more than the actual cost to the agents. For the minimum spanning tree problem, if the market is "competitive", one can show that VCG never pays too much. On the other hand, for the shortest s-t path problem, Archer and Tardos [5] showed that VCG can overpay by a factor of Ω(n). A natural question that arises then is: For what problems does VCG overpay by a lot? We quantify this notion of overpayment, and show that the class of instances for which VCG never overpays is a natural generalization of matroids, that we call frugoids. We then give some sufficient conditions to upper bound and lower bound the overpayment in other cases, and apply these to several important combinatorial problems. We also relate the overpayment in an suitable model to the locality ratio of a natural local search procedure.