Expressiveness and optimization under incentive compatibility constraints in dynamic auctions

This thesis designs and analyzes auctions for persistent goods in three domains with arriving and departing bidders, quantifying tradeoffs between design objectives. The central objective is incentive compatibility, ensuring that it is in bidders' best interest to reveal their private information truthfully. Other primary concerns are expressiveness, i.e. the richness of the effective bidding language, and optimization, in the form of aiming towards high revenue or high value of the allocation of goods to bidders.In the first domain, an arriving bidder requests a fixed number of goods by his departure, introducing combinatorial constraints. I achieve the global property of incentive compatibility via self-correction, a local verification procedure, applied to a heuristic modification of an online stochastic algorithm. This heuristic is flexible and has encouraging empirical performance in terms of allocation value, revenue and computation overhead.In the second domain, impatient buyers make instantaneous reservation offers for future goods. Introducing the practical ability of cancellations by the seller leads to an auction with worst-case guarantees without any assumption on the sequence of offers. A buyer whose reservation is canceled incurs a utility loss proportional to his value, but receives an equivalent cancellation fee from the seller. A simple payment scheme ensures a novel incentive compatibility concept: no bidder can profit from a lower bid while no truthful winner can profit from any different bid. I establish that no fully incentive-compatible auction can achieve similar worst-case guarantees.In the third domain, I consider the first dynamic generalization of the classical economic model of interdependent values for a single good. In this model, a bidder's value for the good depends explicitly on other bidders' private information. I characterize incentive-compatible dynamic interdependent-value auctions and I establish that they can be reasonable if and only if no bidder can manipulate his departure. I suggest and analyze a mixed-integer programming formulation and a heuristic for designing such an auction to maximize revenue when bidders have fixed arrivals and departures.