On Maximizing Welfare When Utility Functions Are Subadditive

DOI10.1137/070680977zbMath1185.68855OpenAlexW1991223607MaRDI QIDQ5189541

No author found.

Publication date: 17 March 2010

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/070680977

zbMATH Keywords

linear programmingapproximation algorithmsrandomized roundingcombinatorial auctions

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (44)

Tight Approximation Bounds for Maximum Multi-coverage ⋮ Computing Stable Coalitions: Approximation Algorithms for Reward Sharing ⋮ Separating the Communication Complexity of Truthful and Nontruthful Algorithms for Combinatorial Auctions ⋮ Quality of local equilibria in discrete exchange economies ⋮ Fair allocation of indivisible goods: beyond additive valuations ⋮ Gross substitutability: an algorithmic survey ⋮ Pricing multi-unit markets ⋮ Combinatorial assortment optimization ⋮ Towards an optimal contention resolution scheme for matchings ⋮ Packing returning secretaries ⋮ Welfare maximization with friends-of-friends network externalities ⋮ Improved maximin guarantees for subadditive and fractionally subadditive fair allocation problem ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Uniform price auctions: equilibria and efficiency ⋮ Fractionally Subadditive Maximization under an Incremental Knapsack Constraint with Applications to Incremental Flows ⋮ Simultaneous auctions without complements are (almost) efficient ⋮ A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation ⋮ Unnamed Item ⋮ Limitations of VCG-based mechanisms ⋮ When Are Welfare Guarantees Robust ⋮ Improved prophet inequalities for combinatorial welfare maximization with (approximately) subadditive agents ⋮ Item bidding for combinatorial public projects ⋮ Unnamed Item ⋮ Limitations of randomized mechanisms for combinatorial auctions ⋮ Population monotonicity in fair division of multiple indivisible goods ⋮ Mechanism design for perturbation stable combinatorial auctions ⋮ Approximate Modularity Revisited ⋮ Unnamed Item ⋮ Risk-free bidding in complement-free combinatorial auctions ⋮ Improved Competitive Ratios for Submodular Secretary Problems (Extended Abstract) ⋮ Worst-Case Mechanism Design via Bayesian Analysis ⋮ Item Pricing for Combinatorial Public Projects ⋮ Computing a small agreeable set of indivisible items ⋮ Algorithms as Mechanisms: The Price of Anarchy of Relax and Round ⋮ A Simple and Approximately Optimal Mechanism for a Buyer with Complements ⋮ Approximation algorithms for vertex happiness ⋮ Polynomial-Time Approximation Schemes for Maximizing Gross Substitutes Utility Under Budget Constraints ⋮ Fractionally subadditive maximization under an incremental knapsack constraint ⋮ Unnamed Item ⋮ Unnamed Item ⋮ An $O(\log \log m)$ Prophet Inequality for Subadditive Combinatorial Auctions ⋮ Tight Approximation for Unconstrained XOS Maximization ⋮ Tight approximation bounds for maximum multi-coverage

This page was built for publication: On Maximizing Welfare When Utility Functions Are Subadditive