Prompt Mechanisms for Online Auctions
Prompt Mechanisms for Online Auctions
复制标题
网上拍卖提示机制
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Lisa Fleischer
中科院分区：
文献类型：
--
作者：
Richard Cole;Shahar Dobzinski;Lisa Fleischer
我们研究以下在线问题：在每个时间单位，提供一个销售的物品。投标人动态地到达并出发，每个出价者都有兴趣在他的到来和离开之间赢得一个项目。我们的目标是设计最大化福利的真实机制，即赢得竞标者的实用程序的总和。
我们首先考虑这个问题的假设是，每个出价者的私人信息是他获取物品的价值。在这种模型中，恒定竞争力的机制是已知的，但是我们观察到这些机制遭受了以下缺点的困扰：投标人只有在他出发时才能学习他的付款。我们认为这些机制本质上是无法使用的，因为它们对任何实施机制都施加了一些看似不受欢迎的要求。
为了结晶这些问题，我们定义了迅速和tardemenismis的概念。我们提出了两个及时的机制，一种是确定性的，另一种随机的，可以保证持续的竞争比率。我们表明，我们的确定性机制对于此设置是最佳的。
然后，我们研究一个模型，其中价值和出发时间都是私人信息。尽管在确定性设置中只能保证一个微不足道的竞争比率，但我们使用随机化来获得及时的真实$ {it theta}（frac 1 {log m}）$ - 竞争机制。然后，我们表明，在该模型中，没有真实的随机机制可以比$ frac 1 2 $更好地达到比率。
We study the following online problem: at each time unit, one of midentical items is offered for sale. Bidders arrive and depart dynamically, and each bidder is interested in winning one item between his arrival and departure. Our goal is to design truthful mechanisms that maximize the welfare, the sum of the utilities of winning bidders.
We first consider this problem under the assumption that the private information for each bidder is his value for getting an item. In this model constant-competitive mechanisms are known, but we observe that these mechanisms suffer from the following disadvantage: a bidder might learn his payment only when he departs. We argue that these mechanism are essentially unusable, because they impose several seemingly undesirable requirements on any implementation of the mechanisms.
To crystalize these issues, we define the notions of promptand tardymechanisms. We present two prompt mechanisms, one deterministic and the other randomized, that guarantee a constant competitive ratio. We show that our deterministic mechanism is optimal for this setting.
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 randomization to obtain a prompt truthful ${it Theta}(frac 1 {log m})$-competitive mechanism. We then show that no truthful randomized mechanism can achieve a ratio better than $frac 1 2$ in this model.