Inapproximability results for combinatorial auctions with submodular utility functions

DOI10.1007/s00453-007-9105-7zbMath1142.91485OpenAlexW4238439820MaRDI QIDQ943868

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

Publication date: 12 September 2008

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-007-9105-7

zbMATH Keywords

Hardness of approximationCombinatorial auctionsSocial welfareSubmodular

Mathematics Subject Classification ID

Utility theory (91B16) Auctions, bargaining, bidding and selling, and other market models (91B26) Social choice (91B14)

Related Items (19)

Algorithmic Aspects of Private Bayesian Persuasion. ⋮ Near-Optimal Asymmetric Binary Matrix Partitions ⋮ An accelerated continuous greedy algorithm for maximizing strong submodular functions ⋮ Two-stage submodular maximization under knapsack and matroid constraints ⋮ Near-optimal asymmetric binary matrix partitions ⋮ Unnamed Item ⋮ A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation ⋮ Truthful randomized mechanisms for combinatorial auctions ⋮ When Are Welfare Guarantees Robust ⋮ Inapproximability results for combinatorial auctions with submodular utility functions ⋮ Optimal Allocation in Combinatorial Auctions with Quadratic Utility Functions ⋮ Truthful mechanism design via correlated tree rounding ⋮ Unnamed Item ⋮ Limitations of randomized mechanisms for combinatorial auctions ⋮ Mechanism design for perturbation stable combinatorial auctions ⋮ Unnamed Item ⋮ Approximation algorithms for vertex happiness ⋮ Breaking the Logarithmic Barrier for Truthful Combinatorial Auctions with Submodular Bidders ⋮ Approximating Nash Social Welfare under Submodular Valuations through (Un)Matchings

Cites Work

• Unnamed Item
• Inapproximability results for combinatorial auctions with submodular utility functions
• Zero knowledge and the chromatic number
• The hardness of approximation: Gap location
• The English auction with differentiated commodities
• Bundling equilibrium in combinatorial auctions
• The communication requirements of efficient allocations and supporting prices
• Combinatorial auctions with decreasing marginal utilities
• On maximizing welfare when utility functions are subadditive
• Proof verification and the hardness of approximation problems
• A threshold of ln n for approximating set cover
• Approximation algorithms for combinatorial auctions with complement-free bidders
• An improved approximation algorithm for combinatorial auctions with submodular bidders
• On the hardness of approximating minimization problems
• A Parallel Repetition Theorem
• Approximating theDomatic Number
• Algorithm Theory - SWAT 2004
• Truthful randomized mechanisms for combinatorial auctions
• Algorithm for optimal winner determination in combinatorial auctions

This page was built for publication: Inapproximability results for combinatorial auctions with submodular utility functions