It only takes a few: On the Hardness of voting with a constant number of agentsReportar como inadecuado




It only takes a few: On the Hardness of voting with a constant number of agents - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Reference: Harrenstein, BP, Brandt, F, Kardel, K et al., (2013). It only takes a few: On the Hardness of voting with a constant number of agents.Citable link to this page:

 

It only takes a few: On the Hardness of voting with a constant number of agents

Abstract: Many hardness results in computational social choice make use of the fact that every directed graph may be induced by the pairwise majority relation. However, this fact requires that the number of voters is almost linear in the number of alternatives. It is therefore unclear whether existing hardness results remain intact when the number of voters is bounded, as is for example typically the case in search engine aggregation settings. In this paper, we provide sufficient conditions for majority graphs to be obtainable using a constant number of voters and leverage these conditions to show that winner determination for the Banks set, the tournament equilibrium set, and ranked pairs remains hard even when there is only a small constant number of voters.

Peer Review status:Peer reviewedPublication status:PublishedVersion:Publisher's version Funder: Deutsche Forschungsgemeinschaft   Conference Details: 2013 International Conference on Autonomous Agents and Multiagent Systems (AAMAS)Notes:Copyright © 2013, International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved. This is the publisher's version of the article. The final version is available online from the Association for Computing Machinery.

Bibliographic Details

Publisher: International Foundation for Autonomous Agents and Multiagent Systems

Publisher Website: http://www.ifaamas.org/

Host: 2013 International Conference on Autonomous Agents and Multiagent Systems (AAMAS)see more from them

Publication Website: http://dl.acm.org/citation.cfm?id=2484920

Issue Date: 2013-05Identifiers

Urn: uuid:2feb97f5-af27-433c-bb6b-d6f890b85106

Isbn: 978-1-4503-1993-5

Source identifier: 591944 Item Description

Type: Conference;

Version: Publisher's versionKeywords: Economics Theory Algorithms Social choice and voting computational complexity Tiny URL: pubs:591944

Relationships





Autor: Harrenstein, BP - institutionUniversity of Oxford Oxford, MPLS, Computer Science grantNumberAdvanced Grant 291528 -RACE- fundingE

Fuente: https://ora.ox.ac.uk/objects/uuid:2feb97f5-af27-433c-bb6b-d6f890b85106



DESCARGAR PDF




Documentos relacionados