Inapproximability results for combinatorial auctions with submodular utility functions
type: Item
instance of: scholarly article
title: Inapproximability results for combinatorial auctions with submodular utility functions
zbMATH Open document ID: 1142.91485
author: Richard J. Lipton
author: Evangelos Markakis
author: Aranyak Mehta
author: Subhash Khot
published in: Algorithmica
publication date: 2008-09-12T00:00:00Z
review text: The authors consider allocation problems on a combinatorial auction where a set of goods is to be allocated to a set of players. A utility function is associated with each player specifying the happiness of the player for each subset of the goods. The goal for the auctioneer is to maximize the economic efficiency of the auction, which is the sum of the utilities of all the players. The allocation problem consists of finding a partition of a set of m indivisible goods among n players that maximizes the overall utility of the system. The authors study the computational complexity of this problem when players' utility functions are submodular. The main result in the paper is that there is no polynomial time approximation algorithm for the allocation problem with monotone submodular utility functions achieving a ratio better than \(1 - 1/e\), unless \(P = NP\). This result is based on a reduction from a multi-prover proof system for MAX-3-COLORING.
reviewed by: Justo Puerto
Mathematics Subject Classification ID: 91B26
Mathematics Subject Classification ID: 91B14
Mathematics Subject Classification ID: 91B16
zbMATH DE Number: 5343373
zbMATH Keywords: Combinatorial auctions
zbMATH Keywords: Submodular
zbMATH Keywords: Social welfare
zbMATH Keywords: Hardness of approximation
MaRDI profile type: Publication
full work available at URL: s00453-007-9105-7
OpenAlex ID: W4238439820
cites work: Algorithm Theory - SWAT 2004
cites work: Q4471296
cites work: Proof verification and the hardness of approximation problems
cites work: Approximation algorithms for combinatorial auctions with complement-free bidders
cites work: Truthful randomized mechanisms for combinatorial auctions
cites work: An improved approximation algorithm for combinatorial auctions with submodular bidders
cites work: A threshold of ln n for approximating set cover
cites work: On maximizing welfare when utility functions are subadditive
cites work: Approximating theDomatic Number
cites work: Zero knowledge and the chromatic number
cites work: The English auction with differentiated commodities
cites work: Bundling equilibrium in combinatorial auctions
cites work: Combinatorial auctions with decreasing marginal utilities
cites work: On the hardness of approximating minimization problems
cites work: The communication requirements of efficient allocations and supporting prices
cites work: The hardness of approximation: Gap location
cites work: A Parallel Repetition Theorem
cites work: Algorithm for optimal winner determination in combinatorial auctions
DOI: 10.1007/S00453-007-9105-7
description: scientific article; zbMATH DE number 5343373