Funding Games: the Truth but not the Whole Truth
share
We introduce the Funding Game, in which m identical resources are to be allocated among n selfish agents. Each agent requests a number of resources x_i and reports a valuation ṽ_i(x_i), which verifiably lower-bounds i's true value for receiving x_i items. The pairs (x_i, ṽ_i(x_i)) can be thought of as size-value pairs defining a knapsack problem with capacity m. A publicly-known algorithm is used to solve this knapsack problem, deciding which requests to satisfy in order to maximize the social welfare. We show that a simple mechanism based on the knapsack highest ratio greedy algorithm provides a Bayesian Price of Anarchy of 2, and for the complete information version of the game we give an algorithm that computes a Nash equilibrium strategy profile in O(n^2 ^2 m) time. Our primary algorithmic result shows that an extension of the mechanism to k rounds has a Price of Anarchy of 1 + 1/k, yielding a graceful tradeoff between communication complexity and the social welfare.
READ FULL TEXT