Online ascending auctions for gradually expiring items

• 成果类型: Article
• 署名作者: Lavi, Ron; Nisan, Noam
• 署名单位: Technion Israel Institute of Technology; Hebrew University of Jerusalem
• 刊物名称: JOURNAL OF ECONOMIC THEORY
• ISSN/ISSBN: 0022-0531
• DOI: 10.1016/j.jet.2014.07.010
• 发表日期: 2015
• 页码: 45-76
• 关键词: Multi-item ascending auctions; robust mechanism design; dynamic mechanism design

摘要

We consider dynamic auction mechanisms for the allocation of multiple items. Items are identical, but have different expiration times, and each item must be allocated before it expires. Buyers are of dynamic nature, and arrive and depart over time. Our goal is to design mechanisms that maximize the social welfare. We begin by showing that dominant-strategy incentive-compatibility cannot be used in this case, since any such auction cannot obtain any constant fraction of the optimal social welfare. We then design two auctions that perform well under a wide class of semi-myopic strategies. For every combination of such strategies, the auction is associated with a different algorithm (or allocation rule), and so we have a family of semi-myopic algorithms. We show that any algorithm in this family obtains at least 1/3 of the optimal social welfare. We also provide some game-theoretic justification for acting in a semi-myopic way. We suggest a new notion of Set-Nash equilibrium, where we cannot pinpoint a single best-response strategy, but rather only a set to which best-response strategies belong. We show that our auctions have a Set-Nash equilibrium which is all semi-myopic. (C) 2014 Elsevier Inc. All rights reserved.