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

DOI10.1016/J.JCSS.2021.08.003zbMATH Open1476.91070OpenAlexW3197763973MaRDI QIDQ2237895FDOQ2237895

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/

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

zbMATH Keywords

prophet inequalities(approximate) subadditivitycombinatorial welfare maximization

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (2)

• Approximation algorithm of maximizing non-monotone non-submodular functions under knapsack constraint
• A constant factor prophet inequality for online combinatorial auctions

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)