Prompt Mechanisms for Online AuctionsRichard Cole Shahar Dobzinski Lisa FleischerNovember 12, 2007AbstractWe study the following online problem: at each time unit, one of m identical items is offeredfor sale. Bidders arrive and depart dynamically, and each bidder is interested in winning one itembetween his arrival and departure. Our goal is to design truthful mechanisms that maximize thewelfare, the sum of the utilities of winning bidders.We first consider this problem under the assumption that the private information for each bidderis his value for getting an item. In this model constant-competitive mechanisms are known, butwe observe that these mechanisms suffer from the following disadvantage: a bidder might learn hispayment only when he departs. We argue that these mechanism are essentially unusable, becausethey impose several seemingly undesirable requirements on any implementation of the mechanisms.To crystalize these issues, we define the notions of prompt and tardy mechanisms. We presenttwo prompt truthful mechanisms – one deterministic and the other randomized, that guarantee aconstant competitive ratio. We also prove that our deterministic mechanism is optimal for thissetting.We then study a model in which both the value and the departure time are private information.While in the deterministic setting only a trivial competitive ratio can be guaranteed, we use ran-domization to obtain a prompt truthful Θ(1log m)-competitive mechanism. Finally, we show that notruthful randomized mechanism can achieve a ratio better than12in this model.1 Introduction1.1 Bac kgroundThe field of algorithmic mechanism design attempts to handle the strategic behavior of selfish agentsin a computationally feasible way. To date, most work in this field has sought to design truthfulmechanisms for static settings, such as auctions. In reality, however, the setting of many problems isonline, meaning that the mechanism has no prior information regarding the identity of the participatingplayers, or that the goods that are for sale are unknown in advance. Examples include sponsored searchauctions [12], single-good auctions [10], and even pricing WiFi at Starbucks [5].This paper considers the following online auction problem: at each time unit exactly one of midentical items is offered for sale. The item at time t is called item t.Therearen bidders, where bidderi arrives at time aiand departs at time di, both unknown before bidder i’s arrival. The interval [ai,di]will be called bidder i’s time window, and the set of items offered in i’s time window will be denotedby Wi. Each bidder is interested in winning at most one of the items within Wi.Letvidenote thevalue to the ith bidder of getting an item in Wi. Our goal is to maximize the social welfare: the sum ofthe values of the bidders that get some item within their time window. As usual in online algorithms,are goal is to optimize the competitive ratio: the worst-case ratio between the welfare achieved by thealgorithm and the optimal welfare.This problem is equivalent to scheduling unit-length jobs on a single machine. In the non-strategicsetting, this problem and its variants have been widely studied (e.g., [1, 8, 3]). The best determin-istic algorithm to date guarantees a competitive ratio of ≈ 0.547 [4, 11], while it is known that nodeterministic algorithm can obtain a ratio better than2√5+1≈ 0.618 [2]. In the randomized setting, acompetitive ratio of 1 −1eis achieved by [1], and no algorithm can achieve a ratio better than 0.8[2].This scheduling problem provides an excellent example of the extra barriers we face when designingonline mechanisms. The only general technique known for designing truthful mechanisms is the VCGpayment scheme. In the offline setting we can obtain an optimal solution in polynomial time (withbipartite matching), and then we can apply VCG. In the online setting, however, it is impossible tofind an optimal solution, and thus we cannot use VCG. Yet, truthful competitive mechanisms do exist.The competitive ratio of these mechanisms depends on the specific private-information model eachmechanism was designed for. This paper considers two different natural models:• The Value-Only model: Here, the private information of bidder i consists of only his valuevi, and the arrival time and the departure time are known to all (but both are unknown prior tothe arrival of bidder i).• The Generalized Model: The private information of bidder i consists of two numbers: hisvalue viand his departure time di. The arrival time is public information (but unknown prior tothe arrival of bidder i).1.2 The Value-Only Model: Is Monotonicity Enough?The only private information of a bidder in the value-only model is his value, and thus this model fallsunder the category of single-parameter environments – environments in which the private informationof each bidder consists of only one number. Fortunately, designing truthful mechanisms for single-parameter environments is quite well understood: an algorithm is truthful if and only if it is monotone.That is, a winning bidder that raises his bid remains a winner.Using the above characterization, it is possible to prove that the greedy algorithm is monotone [7](see Section 2.4 for a description). Together with the result of [8], this gives a truthful mechanism thatis12competitive.However, a closer look at this mechanism may make one wonder if it is indeed applicable. Thenotions of prompt and tardy mechanisms we define next highlight the issue.Definition 1.1 We say that a mechanism for the scheduling problem is prompt if a bidder that winsan item always learns his payment immediately after winning the item. A mechanism is tardy if it isnot prompt.The tardiness in the above mechanism [7, 8] is substantial: there are inputs for which a bidderlearns his payment only when he departs. Tardy mechanisms seem very unintuitive for the bidders,and in addition they suffer from the following disadvantages:• Uncertain ty: A winning bidder does not know the cost of the item that he won, and thus doesnot know how much money he still has available. E.g., suppose the mechanism is used in a LasVegas ticket office for selling tickets to a daily show. A tourist that wins a ticket is uncertain ofthe price of this privilege, and thus might not be able to determine how much money he has leftto spend during his Las Vegas vacation.• Debt C ollection: A winning bidder might pay the mechanism