How to Sell Online (Fast) via Pricing-Based Algorithms

Abstract

Online resource allocation problems play a fundamental role in online decision making. In these problems, a sequence of agents arrives one-by-one, each with the goal of being assigned a subset of available items. An allocation decision is required to be made immediately and irrevocably. This introduces several challenges for the decision-maker: Future arrivals are unknown, agents can act strategically and the allocation decisions may be required within milliseconds. <br /> The goal of this thesis is to design algorithms which address these challenges and for which we can theoretically quantify the loss due to <br /> I. limited information about the future, <br /> II. limited computational power and/or <br /> III. strategic behavior of agents. <br /> In order to bound the loss due to limited information about the future (I.), we work in the Prophet Inequality model with stochastic prior information about the arriving agents. Given this prior knowledge, the goal is to design online algorithms which perform reasonably well compared to the expected offline optimum. For this class of problems, the contribution in this thesis is twofold: First, we give simplified proofs for existing pricing-based Prophet Inequalities for combinatorial auctions and matroids. Second, we show that asymptotically optimal welfare can be achieved once we restrict the class of distributions from which the values are sampled. <br /> Shifting the perspective to bound the loss due to limited computational power (II.), we provide a polynomial-time approximation algorithm for the optimal policy once buyers have multi-demand valuations. For these, we show how to use an LP-based rounding approach in order to beat existing results and derive state-of-the-art guarantees. As a side remark, all algorithmic approaches mentioned so far can also be applied when agents behave strategically. In particular, the algorithms are (or can be made) incentive compatible. <br /> Beyond the assumption that items are always available for sale, we consider the related model of two-sided markets: Items are initially held by strategic sellers. In this setting, we are able to bound the loss due to strategic behavior of agents (III.). In particular, we show that for matroid, knapsack and combinatorial double auctions, a reasonable fraction of the expected welfare of the optimal allocation is achievable when restricting to incentive compatibility, individual rationality and budget balance constraints. <br /> Complementing results in the Prophet model, we also argue about the loss due to limited information about the future (I.) in the Secretary model. Here, weights are chosen adversarially, but arrive in random order. We show that in this model, a single piece of information can help to beat prevalent bounds. In particular, we use a predicted additive gap as advice and are able to beat the guarantee of 1/e, which was tight in the classical model.