False-Name-Proof Locations of Two Facilities: Economic and Algorithmic Approaches
False-Name-Proof Locations of Two Facilities: Economic and Algorithmic Approaches
复制标题
DOI：
10.1609/aaai.v30i1.10029
复制
发表时间：
2016-02
期刊：
影响因子：
--
通讯作者：
Akihisa Sonoda;Taiki Todo;M. Yokoo
中科院分区：
文献类型：
--
作者：
Akihisa Sonoda;Taiki Todo;M. Yokoo
本文考虑了一个代理可以伪装成多个代理的机制设计问题，即在一个区间上定位两个相同的设施。一个机制选择一对位置上的时间间隔，根据声明的单峰的代理商的喜好。代理的效用由更好的代理的位置决定（通常是更接近她的理想点）。该模型可以表示各种应用程序域。例如，假设一家公司将发布其产品线的两种型号，并在在线论坛上进行问卷调查以确定其详细规格。通常情况下，一个客户只会购买一个模型，但她可以通过几个电子邮件帐户登录到论坛多次回答。我们首先描述了可能的结果的机制，满足假名证明，以及一些温和的条件。通过推广这一结果，我们完全刻画了在一个圆上定位两个设施时这类防假名机制的特征。然后，我们澄清的近似比率的假名证明机制的线度量的社会和最大成本。
This paper considers a mechanism design problem for locating two identical facilities on an interval, in which an agent can pretend to be multiple agents. A mechanism selects a pair of locations on the interval according to the declared single-peaked preferences of agents. An agent's utility is determined by the location of the better one (typically the closer to her ideal point). This model can represent various application domains. For example, assume a company is going to release two models of its product line and performs a questionnaire survey in an online forum to determine their detailed specs. Typically, a customer will buy only one model, but she can answer multiple times by logging onto the forum under several email accounts. We first characterize possible outcomes of mechanisms that satisfy false-name-proofness, as well as some mild conditions. By extending the result, we completely characterize the class of false-name-proof mechanisms when locating two facilities on a circle. We then clarify the approximation ratios of the false-name-proof mechanisms on a line metric for the social and maximum costs.