An O(log log m) Prophet Inequality for Subadditive Combinatorial Auctions
Offered By: IEEE via YouTube
Course Description
Overview
Explore an advanced algorithm for subadditive combinatorial auctions in this 26-minute IEEE conference talk. Delve into the intricacies of the O(log log m) prophet inequality as presented by experts Paul Duetting, Thomas Kesselheim, and Brendan Lucier. Learn about combinatorial auctions, prior results, and the concept of balanced prices. Discover how to go beyond these prices and understand the key lemma equivalent. Gain insights into achieving O(log log m) complexity and grasp the implications of this research in the field of algorithmic game theory and auction design.
Syllabus
Intro
Combinatorial Auction
Prior Results
Beyond Balanced Prices
Equivalent to Key Lemma
Getting O(log log m)
Conclusion
Taught by
IEEE FOCS: Foundations of Computer Science
Tags
Related Courses
An Improved Exponential-Time Approximation Algorithm for Fully-Alternating Games Against NatureIEEE via YouTube Computation in the Brain Tutorial - Part 2
IEEE via YouTube Computation in the Brain - Part 1
IEEE via YouTube Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model
IEEE via YouTube Cookbook Lower Bounds for Statistical Inference in Distributed and Constrained Settings - Part 1
IEEE via YouTube