YoVDO

An O(log log m) Prophet Inequality for Subadditive Combinatorial Auctions

Offered By: IEEE via YouTube

Tags

IEEE FOCS: Foundations of Computer Science Courses Algorithm Design Courses Auction Theory Courses

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 Nature
IEEE 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