Computer Science – Computer Science and Game Theory
Scientific paper
2011-07-12
Computer Science
Computer Science and Game Theory
Scientific paper
We introduce the Knapsack Game, in which $m$ identical resources are to be allocated among $n$ selfish agents. Each agent requests some number of resources $x_i$ and specifies its true valuation $v_i(x_i)$ for receiving them, to a central entity. We assume that the valuation functions exhibit diminishing marginal returns. The pairs $(x_i, v_i(x_i))$ can be thought of as size-value pairs defining a knapsack problem with capacity $m$. The central entity must use some publicly-known mechanism to solve this knapsack problem, deciding which requests to satisfy in order to maximize the social welfare. We motivate our formulation by noting an application to the classical communication-theoretic problem of power allocation to parallel channels. Unfortunately, it turns out that the natural mechanism of computing an optimal solution to the knapsack problem instance specified by the requests gives the players the wrong incentives and yields an unbounded Price of Anarchy (PoA). Instead, and somewhat surprisingly, we show that a simpler mechanism, based on the knapsack {\it highest ratio greedy} algorithm, provides a PoA of 2. We also give an algorithm computing a Nash equilibrium strategy profile in $O((n \log m)^2)$ time. Our primary algorithmic result shows that extending the mechanism to multiple rounds can arbitrarily strengthen the guarantee. Specifically, in this extension, the $m$ items are partitioned into $k$ carefully-sized subsets, and then allocated successively in $k$ consecutive knapsack games. We show that this mechanism yields a PoA of $1 + \frac{1}{k}$, yielding a graceful tradeoff between communication complexity and the social welfare. The k-round result follows from our second major result, which shows a surprising analytical number-theoretic min-sup identity, and which may be of independent interest.
Bar-Noy Amotz
Gai Yi
Johnson Matthew P.
Krishnamachari Bhaskar
Rabanca George
No associations
LandOfFree
Knapsack Games and the Truth but not the Whole Truth does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Knapsack Games and the Truth but not the Whole Truth, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Knapsack Games and the Truth but not the Whole Truth will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-165028