On maximizing welfare when utility functions are subadditive

DOI10.1145/1132516.1132523MaRDI QIDQ2931368zbMATH OpenOpenAlexFDO

Authors Uriel Feige

Publication date 25 November 2014

Published in Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1132516.1132523

zbMATH Keywords

combinatorial auctionsrandomized rounding

Mathematics Subject Classification ID

Randomized algorithms (68W20) Combinatorial optimization (90C27) Auctions, bargaining, bidding and selling, and other market models (91B26) Approximation algorithms (68W25) Utility theory (91B16) Welfare economics (91B15)

Recommendations

• On maximizing welfare when utility functions are subadditive
• The submodular welfare problem with demand queries
• Optimal approximation for the submodular welfare problem in the value oracle model
• Inapproximability results for combinatorial auctions with submodular utility functions
• Oblivious rounding and the integrality gap

Cited in

(28)

• The balloon popping problem revisited: lower and upper bounds
• (Almost) efficient mechanisms for bilateral trading
• Maximizing a class of submodular utility functions
• Optimization with demand oracles
• On competitiveness in uniform utility allocation markets
• Welfare maximization and the supermodular degree
• Santa Claus Meets Hypergraph Matchings
• A constant factor prophet inequality for online combinatorial auctions
• Economic efficiency requires interaction
• Scheduling to Maximize Participation
• Permutation betting markets: singleton betting with extra information
• The implicit welfare weights used when maximizing aggregate surplus
• Approximating Nash social welfare under binary XOS and binary subadditive valuations
• Best-response dynamics in combinatorial auctions with item bidding
• Learning in auctions: regret is hard, envy is easy
• Optimal bounds on approximation of submodular and XOS functions by juntas
• PASS approximation: a framework for analyzing and designing heuristics
• On maximizing welfare when utility functions are subadditive
• Improved prophet inequalities for combinatorial welfare maximization with (approximately) subadditive agents
• Inapproximability results for combinatorial auctions with submodular utility functions
• Energy efficient monitoring in sensor networks
• Scheduling to maximize participation
• Tight bounds on \(\ell_1\) approximation and learning of self-bounding functions
• Oblivious rounding and the integrality gap
• Combinatorial reallocation mechanisms
• The submodular welfare problem with demand queries
• Approximation algorithms for inventory problems with submodular or routing costs
• Truthful randomized mechanisms for combinatorial auctions

This page was built for publication: On maximizing welfare when utility functions are subadditive

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2931368)