External authors:

• Jose A. Soto ( Universidad de Chile )

Abstract:

In the online 2-bounded auction problem, we have a collection of items represented as nodes in a graph and bundles of size two represented by edges. Agents are presented sequentially, each with a random weight function over the bundles. The goal of the decision-maker is to find an allocation of bundles to agents of maximum weight so that every item is assigned at most once, i.e., the solution is a matching in the graph. When the agents are single-minded (i.e., put all the weight in a single bundle), we recover the maximum weight prophet matching problem under edge arrivals (a.k.a. prophet matching). In this work, we provide new and improved upper bounds on the competitiveness achievable by an algorithm for the general online 2-bounded auction and the (single-minded) prophet matching problems. For the adversarial arrival order of the agents, we show that no algorithm for the online 2-bounded auction problem achieves a competitiveness larger than 4/11, while no algorithm for prophet matching achieves a competitiveness larger than approximate to 0.4189. Using a continuous-time analysis, we also improve the known bounds for online 2-bounded auctions for random order arrivals to approximate to 0.5968 in the general case, a bound of approximate to 0.6867 in the IID model, and approximate to 0.6714 in prophet-secretary model.