Combinatorial Philosopher Inequalities

In online combinatorial allocation, agents arrive sequentially and items are allocated in an online manner. The algorithm designer only knows the distribution of each agent’s valuation, while the actual realization of the valuation is revealed only upon her arrival. Against the offline benchmark, Feldman, Gravin, and Lucier (SODA 2015) designed an optimal 0.5-competitive algorithm for XOS agents. An emerging line of work focuses on designing approximation algorithms against the (computationally unbounded) optimal online algorithm. The primary goal is to design algorithms with approximation ratios strictly greater than 0.5, surpassing the impossibility result against the offline optimum. Positive results are established for unit-demand agents (Papadimitriou, Pollner, Saberi, Wajc, MOR 2024), and for \(k\)-demand agents (Braun, Kesselheim, Pollner, Saberi, EC 2024).