TY - GEN
T1 - Limited supply online auctions for revenue maximization
AU - Krysta, Piotr
AU - Telelis, Orestis
PY - 2012
Y1 - 2012
N2 - We consider the design of competitive truthful auctions for prior-free revenue maximization, to sell copies of a single good in limited supply to unit-demand bidders that arrive online. The online model, first studied in [Hajiaghayi, Kleinberg, Parkes, ACM EC 2004] and recently revisited in [Koutsoupias and Pierrakos, WINE 2010], is reminiscent of the secretary problem, in that the order of the bidders' arrival is chosen uniformly at random. The benchmark against which the generated revenue is compared is the one introduced by Goldberg et al. [Games and Economic Behavior 55(2):242-269, 2006]. We consider two variants of limited supply; a hard constraint of k available copies and convex production cost curve for each copy. For each case we present an algorithmic reduction of the problem to the problem of unlimited supply studied by Koutsoupias and Pierrakos. Our reduction for the case of k available copies yields a 26e-competitive auction thus improving significantly upon the best known ratio of 6338, from [Hajiaghayi, Kleinberg, Parkes, ACM EC 2004].
AB - We consider the design of competitive truthful auctions for prior-free revenue maximization, to sell copies of a single good in limited supply to unit-demand bidders that arrive online. The online model, first studied in [Hajiaghayi, Kleinberg, Parkes, ACM EC 2004] and recently revisited in [Koutsoupias and Pierrakos, WINE 2010], is reminiscent of the secretary problem, in that the order of the bidders' arrival is chosen uniformly at random. The benchmark against which the generated revenue is compared is the one introduced by Goldberg et al. [Games and Economic Behavior 55(2):242-269, 2006]. We consider two variants of limited supply; a hard constraint of k available copies and convex production cost curve for each copy. For each case we present an algorithmic reduction of the problem to the problem of unlimited supply studied by Koutsoupias and Pierrakos. Our reduction for the case of k available copies yields a 26e-competitive auction thus improving significantly upon the best known ratio of 6338, from [Hajiaghayi, Kleinberg, Parkes, ACM EC 2004].
UR - https://www.scopus.com/pages/publications/84871369203
UR - https://www.scopus.com/pages/publications/84871369203#tab=citedBy
U2 - 10.1007/978-3-642-35311-6_41
DO - 10.1007/978-3-642-35311-6_41
M3 - Conference contribution
AN - SCOPUS:84871369203
SN - 9783642353109
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 519
EP - 525
BT - Internet and Network Economics - 8th International Workshop, WINE 2012, Proceedings
T2 - 8th International Workshop on Internet and Network Economics, WINE 2012
Y2 - 10 December 2012 through 12 December 2012
ER -