Seminar

"Informational Size and Informative Simplicity" - Di Feng

Abstract: We introduces the concept of informative simplicity in economics design, a field traditionally focused on mapping problems to allocations. This concept, derived from the older notion of informational size, assesses mechanisms based on the minimal information they require to select allocations. We examines this concept in matching markets and auctions, revealing surprising insights about their simplicity. For instance, in matching markets, the immediate acceptance mechanism is simpler than the simple directorship mechanism. In auctions, the first-price auction is simpler in static contexts, and the descending deferred acceptance clock auction is simpler in dynamic contexts. These findings offer a fresh perspective in economics design, emphasizing the importance of information simplicity in both theory and practice.

 

"On the Hardness of Dominant-Strategy Mechanism Design" - Shiri Ron

Abstract: We study the communication complexity of dominant strategy implementations of combinatorial auctions. We start with two domains that are generally considered ``easy'': multi-unit auctions with decreasing marginal values and combinatorial auctions with gross substitutes valuations. For both domains we have fast algorithms that find the welfare-maximizing allocation with communication complexity that is poly-logarithmic in the input size. This immediately implies that welfare maximization can be achieved in ex-post equilibrium with no significant communication cost, by using VCG payments. In contrast, we show that in both domains the communication complexity of any dominant strategy implementation that achieves the optimal welfare is polynomial in the input size.

We then move on to studying the approximation ratios achievable by dominant strategy mechanisms. For multi-unit auctions with decreasing marginal values, we provide a dominant-strategy communication FPTAS. For combinatorial auctions with general valuations, we show that there is no dominant strategy mechanism that achieves an approximation ratio better than m^{1-\epsilon} that uses poly(m,n) bits of communication, where m is the number of items and n is the number of bidders. In contrast, a randomized dominant strategy mechanism that achieves an O(√m) approximation with poly(m,n) communication is known. This proves the first gap between communication efficient deterministic dominant strategy mechanisms and randomized ones.En route, we solve some open problems in the area of simultaneous combinatorial auctions.

Based on joint work with Shahar Dobzinski and Jan Vondrák.