Inapproximability results for combinatorial auctions with submodular utility functions

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

doi:10.1007/s00453-007-9105-7

Inapproximability results for combinatorial auctions with submodular utility functions

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

Computer Science

Research output: Contribution to journal › Article › peer-review

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 language	English (US)
Pages (from-to)	3-18
Number of pages	16
Journal	Algorithmica (New York)
Volume	52
Issue number	1
DOIs	https://doi.org/10.1007/s00453-007-9105-7
State	Published - Sep 2008

Keywords

Combinatorial auctions
Hardness of approximation
Social welfare
Submodular

ASJC Scopus subject areas

General Computer Science
Computer Science Applications
Applied Mathematics

Access to Document

10.1007/s00453-007-9105-7

Cite this

@article{41e3f870dd204e8baf025538f391bcd8,

title = "Inapproximability results for combinatorial auctions with submodular utility functions",

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.",

keywords = "Combinatorial auctions, Hardness of approximation, Social welfare, Submodular",

author = "Subhash Khot and Lipton, {Richard J.} and Evangelos Markakis and Aranyak Mehta",

year = "2008",

month = sep,

doi = "10.1007/s00453-007-9105-7",

language = "English (US)",

volume = "52",

pages = "3--18",

journal = "Algorithmica (New York)",

issn = "0178-4617",

publisher = "Springer New York",

number = "1",

}

TY - JOUR

T1 - Inapproximability results for combinatorial auctions with submodular utility functions

AU - Khot, Subhash

AU - Lipton, Richard J.

AU - Markakis, Evangelos

AU - Mehta, Aranyak

PY - 2008/9

Y1 - 2008/9

N2 - 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.

AB - 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.

KW - Combinatorial auctions

KW - Hardness of approximation

KW - Social welfare

KW - Submodular

UR - http://www.scopus.com/inward/record.url?scp=49149102694&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=49149102694&partnerID=8YFLogxK

U2 - 10.1007/s00453-007-9105-7

DO - 10.1007/s00453-007-9105-7

M3 - Article

AN - SCOPUS:49149102694

SN - 0178-4617

VL - 52

SP - 3

EP - 18

JO - Algorithmica (New York)

JF - Algorithmica (New York)

IS - 1

ER -

Inapproximability results for combinatorial auctions with submodular utility functions

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this