Journal article
k-Majority digraphs and the hardness of voting with a constant number of voters
- Abstract:
-
Many hardness results in computational social choice use the fact that every digraph may be induced as the pairwise majority relation of some preference profile. The standard construction requires a number of voters that is almost linear in the number of alternatives and it is unclear whether hardness holds when the number of voters is bounded. In this paper, we systematically study majority digraphs inducible by a constant number of voters. First, we characterize digraphs inducible by two or...
Expand abstract
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, pdf, 509.3KB, Terms of use)
-
- Publisher copy:
- 10.1016/j.jcss.2019.04.005
Authors
Funding
Bibliographic Details
- Publisher:
- Elsevier
- Journal:
- Journal of Computer and System Sciences More from this journal
- Volume:
- 105
- Issue:
- November 2019
- Pages:
- 130-157
- Publication date:
- 2019-05-09
- Acceptance date:
- 2019-04-19
- DOI:
- EISSN:
-
1090-2724
- ISSN:
-
0022-0000
Item Description
- Language:
-
English
- Keywords:
- Pubs id:
-
pubs:1004423
- UUID:
-
uuid:598a8c09-7dd5-4a39-86c9-c31e5ba84ec2
- Local pid:
-
pubs:1004423
- Source identifiers:
-
1004423
- Deposit date:
-
2019-08-27
Terms of use
- Copyright holder:
- Elsevier
- Copyright date:
- 2019
- Rights statement:
- © 2019 Published by Elsevier Inc.
- Notes:
- This is the accepted manuscript version of the article. The publisher's version is available online
Metrics
If you are the owner of this record, you can report an update to it here: Report update to this record