A bidding game for allocation of indivisible goods

Abstract:

We consider allocations of indivisible goods to agents with possibly unequal entitlements, in a setting without payments. We present a fairly natural allocation mechanism, referred to as the bidding game. We ask whether the game has the property that the allocations output by this game (say, in equilibrium), enjoy ex-post fairness properties. To answer this, for various values of 0 < r < 1, we design ``r-safe strategies", that guarantee to any player who uses them that no matter what strategies other players use, she will receive a bundle of value that is at least an r-fraction of her APS (the ``anyprice share"  – this fairness concept will be reviewed in the talk).  Such strategies imply the existence of r-APS allocatons, in which every agent gets at least an r-fraction of her APS. For additive, submodular and subadditive classes of valuations, our results give the current best ratios r for r-APS allocations (among all allocation mechanisms, not just the bidding game).