Title: Combinatorial Auctions with Online XOS Bidders,
Abstract: In combinatorial auctions, a designer must decide how to allocate a set of
indivisible items amongst a set of bidders. Each bidder has a valuation
function which gives the utility they obtain from any subset of the items. Our
focus is specifically on welfare maximization, where the objective is to
maximize the sum of valuations that the bidders place on the items that they
were allocated (the valuation functions are assumed to be reported truthfully).
We analyze an online problem in which the algorithm is not given the set of
bidders in advance. Instead, the bidders are revealed sequentially in a
uniformly random order, similarly to secretary problems. The algorithm must
make an irrevocable decision about which items to allocate to the current
bidder before the next one is revealed. When the valuation functions lie in the
class $XOS$ (which includes submodular functions), we provide a black box
reduction from offline to online optimization. Specifically, given an
$\alpha$-approximation algorithm for offline welfare maximization, we show how
to create a $(0.199 \alpha)$-approximation algorithm for the online problem.
Our algorithm draws on connections to secretary problems; in fact, we show that
the online welfare maximization problem itself can be viewed as a particular
kind of secretary problem with nonuniform arrival order.