A Constant Factor Prophet Inequality for Online Combinatorial Auctions

Explore a groundbreaking Google TechTalk on online combinatorial auctions presented by Andrés Cristi. Delve into the world of prophet inequalities and their application to allocating indivisible items to agents arriving online. Discover a novel constant factor prophet inequality for subadditive valuations, resolving a major open problem in the field. Learn about the innovative Mirror Lemma sampling technique and its role in understanding algorithms with balanced item allocation. Gain insights into the application of Kakutani's fixed point theorem in this context. Understand the significance of this research for optimization problems with strategic agents, particularly in dynamic allocation scenarios relevant to modern platforms like routing apps, online advertisers, and marketplaces.

A Constant Factor Prophet Inequality for Online Combinatorial Auctions