[UTMD-061] Discrete Pricing in Multi-object Auctions (by Ryan Tierney, Yu Zhou)


Ryan Tierney, Yu Zhou


We study the auction model of selling multiple heterogenous objects in which (i) unit demand agents have utility functions accommodating wealth effects and (ii) prices can only be discretely adjusted. The minimum price equilibrium (MPE), a natural generalization of the Vickrey allocation to settings without assuming quasi-linearity, plays a central role in designing efficient and incentive-compatible auctions. Nevertheless, discrete prices do not always support the MPEs. We instead propose an efficient equilibrium notion, tight equilibrium, and calculate the upper and lower deviation bounds between any tight equilibrium price and the (unique) MPE price. We also develop a descending-price auction that finds a tight equilibrium in finitely many steps. We further introduce a new notion of incentive compatibility, compensating strategy-proofness, to measure the non-manipulability of our proposed auction in an approximate sense.