Search Mailing List Archives
[theory-seminar] Theory Seminar (5/10): Kira Goldner
ofirgeri at stanford.edu
Mon May 6 15:37:46 PDT 2019
This week in the theory seminar, Kira Goldner (University of Washington) will give a talk on Mechanism Design under Interdependent Valuations (see abstract below). The talk will be as usual on Friday, 3:00pm in Gates 463A.
The abstracts of past and upcoming seminar talks is also available on the theory seminar webpage:
Hope to see you there!
Mechanism Design under Interdependent Valuations
Speaker: Kira Goldner (University of Washington)
We study buyers with interdependent valuations: where one buyer's private information about an item impacts how much another buyer is willing to pay for it. In this setting, if a buyer misreports his own private information, he can impact not only what the auctioneer believes his own value is, but also what the auctioneer believes regarding other buyers' values as well, allowing him to essentially corrupt their values. As a result, the usual mechanism design tricks fall short, and welfare maximization is notoriously difficult. Almost all prior work in this setting requires a very strong "single-crossing" condition on the valuation functions in order to obtain any positive results.
We introduce two more natural notions -- first, a relaxed, parameterized notion of single-crossing, and second, a completely unrelated notion, one of submodularity over the private information of buyers -- that each separately enable good approximation guarantees to optimal welfare. These conditions, combined with the lens of approximation, allow us to go beyond not only the restrictive single-crossing notion, but to go far beyond the single-item setting and to give positive results for even the very general setting of combinatorial auctions.
Joint work with Alon Eden, Michal Feldman, Amos Fiat, and Anna Karlin.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the theory-seminar