On maximizing welfare when utility functions are subadditive
DOI10.1145/1132516.1132523zbMATH Open1301.68270OpenAlexW1995275762MaRDI QIDQ2931368FDOQ2931368
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
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
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)
Cited In (28)
- Optimization with demand oracles
- Energy efficient monitoring in sensor networks
- On competitiveness in uniform utility allocation markets
- Inapproximability results for combinatorial auctions with submodular utility functions
- Permutation betting markets: singleton betting with extra information
- Santa Claus Meets Hypergraph Matchings
- Improved prophet inequalities for combinatorial welfare maximization with (approximately) subadditive agents
- Approximation algorithms for inventory problems with submodular or routing costs
- Economic efficiency requires interaction
- Scheduling to Maximize Participation
- 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
- On maximizing welfare when utility functions are subadditive
- Welfare maximization and the supermodular degree
- Oblivious rounding and the integrality gap
- Tight bounds on \(\ell_1\) approximation and learning of self-bounding functions
- Truthful randomized mechanisms for combinatorial auctions
- The balloon popping problem revisited: lower and upper bounds
- (Almost) efficient mechanisms for bilateral trading
- A constant factor prophet inequality for online combinatorial auctions
- PASS approximation: a framework for analyzing and designing heuristics
- The submodular welfare problem with demand queries
- Optimal bounds on approximation of submodular and XOS functions by juntas
- Scheduling to maximize participation
- Maximizing a class of submodular utility functions
- Combinatorial reallocation mechanisms
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)
