False-name-proofness in online mechanisms
False-name-proofness in online mechanisms
复制标题
DOI：
--
复制
发表时间：
2012-06
期刊：
影响因子：
--
通讯作者：
Taiki Todo;Takayuki Mouri;Atsushi Iwasaki;M. Yokoo
中科院分区：
文献类型：
--
作者：
Taiki Todo;Takayuki Mouri;Atsushi Iwasaki;M. Yokoo
在真实的电子市场中，每个出价人都是随时间到达和离开的。因此，这种必须在不知道未来的情况下动态地做出决策的机制被称为在线机制。在在线机制中，机制设计者不太可能事先知道投标人的数量，也不可能核实所有投标人的身份。因此，投标人可以使用不同的标识符（例如，不同的电子邮件地址）。在本文中，我们形式化的假名操纵在线机制，并确定一个简单的属性称为（值，时间，标识符）-单调性的特点，分配规则的假名证明在线拍卖机制。据我们所知，这是第一个关于防假名在线机制的工作。此外，我们开发了一个新的假名证明的在线拍卖机制，k相同的项目。当k = 1时，该机制对应于候选人数目未知的秘书问题的最优停止规则。我们表明，这种机制的效率的竞争比是4和独立于k，假设只有投标人的到达时间的分布是已知的，投标人是不耐烦的。
In real electronic markets, each bidder arrives and departs over time. Thus, such a mechanism that must make decisions dynamically without knowledge of the future is called an online mechanism. In an online mechanism, it is very unlikely that the mechanism designer knows the number of bidders beforehand or can verify the identity of all of them. Thus, a bidder can easily submit multiple bids (false-name bids) using different identifiers (e.g., different e-mail addresses). In this paper, we formalize false-name manipulations in online mechanisms and identify a simple property called (value, time, identifier)-monotonicity that characterizes the allocation rules of false-name-proof online auction mechanisms. To the best of our knowledge, this is the first work on false-name-proof online mechanisms. Furthermore, we develop a new false-name-proof online auction mechanism for k identical items. When k = 1, this mechanism corresponds to the optimal stopping rule of the secretary problem where the number of candidates is unknown. We show that the competitive ratio of this mechanism for efficiency is 4 and independent from k by assuming that only the distribution of bidders' arrival times is known and that the bidders are impatient.