Improved prophet inequalities for combinatorial welfare maximization with (approximately) subadditive agents

DOI10.1016/J.JCSS.2021.08.003MaRDI QIDQ2237895zbMATH OpenOpenAlexFDO

Authors Hanrui Zhang

Publication date 28 October 2021

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2020/12948/

zbMATH Keywords

prophet inequalities(approximate) subadditivitycombinatorial welfare maximization

Mathematics Subject Classification ID

Auctions, bargaining, bidding and selling, and other market models (91B26)

Recommendations

• Combinatorial prophet inequalities
• Prophet secretary for combinatorial auctions and matroids
• Prophet inequalities made easy: stochastic optimization by pricing nonstochastic inputs
• On maximizing welfare when utility functions are subadditive
• On maximizing welfare when utility functions are subadditive

Cites work

• scientific article; zbMATH DE number 7559067 (Why is no real title available?)
• A simple \(O(\log\log(\mathrm{rank}))\)-competitive algorithm for the matroid secretary problem
• Approximation algorithms for combinatorial auctions with complement-free bidders
• Bayesian combinatorial auctions: expanding single buyer mechanisms to many buyers
• Combinatorial auctions via posted prices
• Combinatorial prophet inequalities
• Matroid prophet inequalities
• Multi-parameter mechanism design and sequential posted pricing
• On maximizing welfare when utility functions are subadditive
• On the complexity of approximating \(k\)-dimensional matching
• Online contention resolution schemes
• Polymatroid Prophet Inequalities
• Prophet inequalities made easy: stochastic optimization by pricing nonstochastic inputs
• Prophet secretary for combinatorial auctions and matroids
• Semiamarts and finite values
• Simple mechanisms for subadditive buyers via duality
• The communication requirements of efficient allocations and supporting prices
• Welfare guarantees for combinatorial auctions with item bidding

Cited in

(3)

• A constant factor prophet inequality for online combinatorial auctions
• Approximation algorithm of maximizing non-monotone non-submodular functions under knapsack constraint
• An $O(\log \log m)$ Prophet Inequality for Subadditive Combinatorial Auctions

Describes a project that uses

Uses Software

• Sociodynamica

This page was built for publication: Improved prophet inequalities for combinatorial welfare maximization with (approximately) subadditive agents

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