Auctions, Equilibria, and Budgets

Abstract

We design algorithms for markets consisting of multiple items, and agents with budget constraints on the maximum amount of money they can afford to spend. This problem can be considered under two broad frameworks. (a) From the standpoint of Auction Theory, the agents valuation functions over the items are private knowledge. Here, a "truthful auction" computes the subset of items received by every agent and her payment, and ensures that no agent can manipulate the scheme to her advantage by misreporting her valuation function. The question is to design a truthful auction whose outcome can be computed in polynomial time. (b) A different, but equally important, question is to investigate if and when the market is in "equilibrium", meaning that every item is assigned a price, every agent gets her utility-maximizing subset of items under the current prices, and every unallocated item is priced at zero. First, we consider the setting of multiple heterogeneous items and present approximation algorithms for revenue-optimal truthful auctions. When the items are homogeneous, we give an efficient algorithm whose outcome defines a truthful and Pareto-optimal auction. Finally, we focus on the notion of "competitive equilibrium", which is a well known solution concept for market clearing. We present efficient algorithms for finding competitive equilibria in markets with budget constrained agents, and show that these equilibria outcomes have strong revenue guarantees.