Inapproximability results for combinatorial auctions with submodular utility functions

Subhash Khot, Richard J. Lipton, Evangelos Markakis, Aranyak Mehta

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider the following allocation problem arising in the setting of combinatorial auctions: a set of goods is to be allocated to a set of players so as to maximize the sum of the utilities of the players (i.e., the social welfare). In the case when the utility of each player is a monotone submodular function, we prove that there is no polynomial time approximation algorithm which approximates the maximum social welfare by a factor better than 1 - 1/e ≃ 0.632, unless P= NP. Our result is based on a reduction from a multi-prover proof system for MAX-3-COLORING.

Original languageEnglish (US)
Title of host publicationInternet and Network Economics - First International Workshop, WINE 2005, Proceedings
Pages92-101
Number of pages10
DOIs
StatePublished - 2005
Event1st International Workshop on Internet and Network Economics, WINE 2005 - Hong Kong, China
Duration: Dec 15 2005Dec 17 2005

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3828 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other1st International Workshop on Internet and Network Economics, WINE 2005
CountryChina
CityHong Kong
Period12/15/0512/17/05

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Inapproximability results for combinatorial auctions with submodular utility functions'. Together they form a unique fingerprint.

  • Cite this

    Khot, S., Lipton, R. J., Markakis, E., & Mehta, A. (2005). Inapproximability results for combinatorial auctions with submodular utility functions. In Internet and Network Economics - First International Workshop, WINE 2005, Proceedings (pp. 92-101). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3828 LNCS). https://doi.org/10.1007/11600930_10