The Polyhedral Geometry of Truthful Auctions

In an auction mechanism, the objective is to allocate m items to n players by asking the players for their valuations of the items. The difference set of an allocation is the set of valuation vectors that the auction mechanism maps to the given allocation. Using tropical geometry, we give a complete characterization of the geometry of the difference sets that can appear for an incentive compatible multi-unit auction showing that they correspond to regular subdivisions of the unit cube.

This observation is then used to construct mechanisms that are robust in the sense that the set of items allocated to a player does change only slightly when the player's reported valuation is changed slightly.