An O(log log m) Prophet Inequality for Subadditive Combinatorial Auctions.
Paul DüttingThomas KesselheimBrendan LucierPublished in: CoRR (2020)
Keyphrases
- combinatorial auctions
- log log
- positive integer
- winner determination
- resource allocation
- approximation algorithms
- single item
- multi unit
- mixed integer
- mechanism design
- multi unit combinatorial auctions
- mathematical programming
- affine transform
- special case
- undirected graph
- affine invariance
- worst case
- auction mechanisms
- agnostic learning
- singular value decomposition
- spectral signatures