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) Approximation algorithms (68W25) Combinatorial optimization (90C27) Welfare economics (91B15) Utility theory (91B16) Auctions, bargaining, bidding and selling, and other market models (91B26)

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

(29)

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

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)