A Multi Dimensional Online Contention Resolution Scheme

Multi-buyer revenue maximization with item pricing can achieve logarithmic approximation compared to optimal ex-ante mechanisms

For subadditive valuations, there exists a logarithmic factor gap between sequential item pricing and ex-ante item pricing revenue

Key technical innovation is development of a new Online Contention Resolution Scheme (OCRS) that handles revenue objectives

Ex-ante relaxation allows allocating items with certain probabilities while satisfying supply constraints in expectation rather than strictly

For gross substitutes valuations, single pricing achieves constant factor approximation while XOS valuations require logarithmic factors

Non-availability of items can significantly shift buyer preferences and complicate revenue extraction

Algorithm works by factoring multi-buyer problems into single buyer components while maintaining allocation probabilities

Supply constraints are handled by proactively removing items to prevent over-allocation

Important assumption is independence of value distributions across buyers (but correlation across items for same buyer is allowed)

Open questions remain around tightness of bounds, handling correlated values between buyers, and improving approximation factors for special cases like submodular valuations