Optimal online combinatorial auctions cannot ensure half the best outcome

The Optimal Competitive Ratio for Subadditive Online Combinatorial Auctions is Less Than 1/2

Computer Science and Game Theory

Summary

This paper looks at a type of auction where items are sold to several buyers arriving one after another, with values that don't simply add up. The authors show an example where any method used online will earn less than half the total value possible if buyers were known in advance. They find this limit happens from four buyers onwards, but if there are three or fewer buyers, a method can always get at least half the best possible total value. This means there's a hard barrier in how well online auctions can perform compared to offline ones.

What this means in practice

  • For auction platform designers: Design algorithms knowing that no online method can guarantee half the offline optimum for four or more buyers with subadditive valuations.
  • For online marketplace engineers: Recognize fundamental limits when allocating items to buyers arriving sequentially with complex value structures.

A theory result. No direct application yet.

Authors

Andrés Cristi, Jiechen Zhang

Abstract

We construct a four-buyer online combinatorial auction with independent subadditive valuations and a fixed, known arrival order in which every online rule earns strictly less than $1/2$ of the expected offline optimum. A common partition, revealed at the third arrival, gives the first three buyers one unit of welfare per item. If the rule uses three distinct partitions, either an item allocated early contributes zero or the fourth buyer's expected value for the remaining bundle is one less than its size. We compute the optimal online and offline welfare exactly and show that a $1/2$ guarantee always holds with at most three buyers.