Loading Events

« All Events

  • This event has passed.

Theory Seminar- Recent Developments in Combinatorial Auctions, Matt Weinberg (Princeton University)

September 23 at 12:00 PM - 1:00 PM

Abstract: In a combinatorial auction there are m items, and each of n players has a valuation function v_i which maps sets of items to non-negative reals. A designer wishes to partition the items into S_1,…,S_n to maximize the welfare (\sum_i v_i(S_i) ), perhaps assuming that all v_i lie in some class V (such as submodular, subadditive, etc.).

Within Algorithmic Game Theory, this problem serves as a lens through which to examine the interplay between computation and incentives. For example: is it the case that whenever a poly-time/poly-communication algorithm for honest players can achieve an approximation guarantee of c when all valuations lie in V, a poly-time/poly-communication truthful mechanism for strategic players can achieve an approximation guarantee of c when all valuations lie in V as well?

In this talk, I’ll give a brief history, then survey three recent results on this topic which:

– provide the first separation between achievable guarantees of poly-communication algorithms and poly-communication truthful mechanisms for any V (joint works with Mark Braverman and Jieming Mao, and with Sepehr Assadi, Hrishikesh Khandeparkar, and Raghuvansh Saxena).

– revisit existing separations between poly-time algorithms and poly-time truthful mechanisms via a new solution concept “Implementation in Advised Strategies” (joint work with Linda Cai and Clayton Thomas).

– resolve the communication complexity of combinatorial auctions for two subadditive players (joint work with Tomer Ezra, Michal Feldman, Eric Neyman, and Inbal Talgam-Cohen, time-permitting).

Details

Date:
September 23
Time:
12:00 PM - 1:00 PM
Event Category:
Event Tags:

Organizer

The Warren Center
Phone:
215-573-0861
Email:
Lhoot@seas.upenn.edu
View Organizer Website

Venue

Room 401B, 3401 Walnut
3401 Walnut Street
Philadelphia, PA 19104 United States
+ Google Map
View Venue Website