Divyarthi Mohan, Constant Approximation for Auctions with Private Interdependent Valuations

Abstract:

The interdependent value (IDV) model, introduced by Milgrom and Weber, has been pivotal in studying auctions with more realistic representation of agent valuations, where each bidder i has a private signal s_i for the item, and a public valuation function v_i(s_1,\ldots, s_n) which maps all bidders' private signals into a valuation function. Our work considers the more challenging setting where the valuation functions are private as well. We provide a new truthful mechanism that achieves O(1)-approximation to the optimal social welfare when the valuations are submodular-over-signals (SoS). Prior to our work, the best known approximation ratio was O(\log^2 n) by Eden, Goldner, Zheng for monotone SoS valuations. Moreover, we extend our results to obtain a constant factor approximation for the multi-unit auctions settings with unit-demand buyers.

This is joint work with Alon Eden, Michal Feldman, Kira Goldner and Simon Mauras.

 

Location:

Feldman 115, Edmond Safra Campus

 

Google Calendar:

https://calendar.google.com/calendar/u/1?cid=cmF0aW9uYWxpdHkuaHVqaUBnbWFpbC5jb20