License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2019.1
URN: urn:nbn:de:0030-drops-105778
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10577/
Go to the corresponding LIPIcs Volume Portal

Feldman, Michal

Auction Design under Interdependent Values (Invited Talk)

pdf-format:
LIPIcs-ICALP-2019-1.pdf (0.2 MB)

Abstract

We study combinatorial auctions with interdependent valuations. In such settings, every agent has a private signal, and every agent has a valuation function that depends on the private signals of all the agents. Interdependent valuations capture settings where agents lack information to determine their own valuations. Examples include auctions for artwork or oil drilling rights. For single item auctions and assume some restrictive conditions (the so-called single-crossing condition), full welfare can be achieved. However, in general, there are strong impossibility results on welfare maximization in the interdependent setting. This is in contrast to settings where agents are aware of their own valuations, where the optimal welfare can always be obtained by an incentive compatible mechanism.
Motivated by these impossibility results, we study welfare maximization for interdependent valuations through the lens of approximation. We introduce two valuation properties that enable positive results. The first is a relaxed, parameterized version of single crossing; the second is a submodularity condition over the signals. We obtain a host of approximation guarantees under these two notions for various scenarios.
Related publications: [Alon Eden et al., 2018; Alon Eden et al., 2019]

BibTeX - Entry

@InProceedings{feldman:LIPIcs:2019:10577,
  author =	{Michal Feldman},
  title =	{{Auction Design under Interdependent Values (Invited Talk)}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{1:1--1:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10577},
  URN =		{urn:nbn:de:0030-drops-105778},
  doi =		{10.4230/LIPIcs.ICALP.2019.1},
  annote =	{Keywords: Combinatorial auctions, Interdependent values, Welfare approximation}
}

Keywords: Combinatorial auctions, Interdependent values, Welfare approximation
Collection: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Issue Date: 2019
Date of publication: 04.07.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI