Peeking Behind the Ordinal Curtain: Improving Distortion via Cardinal Queries
Peeking Behind the Ordinal Curtain: Improving Distortion via Cardinal Queries
复制标题
窥视序数幕后：通过基数查询改善失真
DOI：
10.1609/aaai.v34i02.5544
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Alexandros A. Voudouris
中科院分区：
文献类型：
--
作者：
Georgios Amanatidis;Georgios Birmpas;Aris Filos;Alexandros A. Voudouris
扭曲的概念是由Procaccia和Rosenschein（2006）提出的，用于量化在试图最大化社会福利时仅使用有序信息的低效率。从那时起，这一研究领域蓬勃发展，并在各种基本情况下获得了畸变的边界。然而，现有的绝大多数文献都集中在除了代理对替代方案的顺序偏好之外一无所知的情况下。在本文中，我们采用了一种更具表现力的方法，并考虑了允许进一步询问一些基本查询的机制，以便获得对代理对备选方案的潜在值的部分访问。有了这个额外的能力，我们设计了新的确定性机制，实现了显著改善的扭曲界限，并优于最著名的随机有序机制。我们几乎完整地描绘了实现特定失真边界所需的查询数量。
The notion of distortion was introduced by Procaccia and Rosenschein (2006) to quantify the inefficiency of using only ordinal information when trying to maximize the social welfare. Since then, this research area has flourished and bounds on the distortion have been obtained for a wide variety of fundamental scenarios. However, the vast majority of the existing literature is focused on the case where nothing is known beyond the ordinal preferences of the agents over the alternatives. In this paper, we take a more expressive approach, and consider mechanisms that are allowed to further ask a few cardinal queries in order to gain partial access to the underlying values that the agents have for the alternatives. With this extra power, we design new deterministic mechanisms that achieve significantly improved distortion bounds and outperform the best-known randomized ordinal mechanisms. We draw an almost complete picture of the number of queries required to achieve specific distortion bounds.
登录
查看更多内容
影响因子：
1.2
作者：
Goel, Ashish;Krishnaswamy, Anilesh K.;Aitamurto, Tanja
通讯作者：
Aitamurto, Tanja
随机独裁者与随机裁判：社会选择的恒定样本复杂性机制
DOI：
--
发表时间：
2019
期刊：
AAAI Conference 2019
影响因子：
--
作者：
Brandon Fain, Ashish Goel
通讯作者：
Brandon Fain, Ashish Goel
将度量扭曲与社会选择规则的公平性联系起来
DOI：
10.1145/3230654.3230658
发表时间：
2018
期刊：
Systems and Computation
影响因子：
--
作者：
Goel, Ashish;Hulett, Reyna;Krishnaswamy, Anilesh K.
通讯作者：
Krishnaswamy, Anilesh K.
改进确定性社会选择规则的度量失真
DOI：
10.1145/3328526.3329550
发表时间：
2019
期刊：
Proceedings of the 2019 ACM Conference on Economics
影响因子：
--
作者：
Munagala, Kamesh;Wang, Kangning
通讯作者：
Wang, Kangning
DOI：
10.1609/aaai.v33i01.33011788
发表时间：
2019-07
期刊：
--
影响因子：
--
作者：
Gerdus Benade;Ariel D. Procaccia;Mingda Qiao
通讯作者：
Gerdus Benade;Ariel D. Procaccia;Mingda Qiao