Clone structures in voters' preferences
In elections, a set of candidates ranked consecutively (though possibly in different order) by all voters is called a clone set, and its members are called clones. A clone structure is the family of all clone sets of a given election. In this paper we study properties of clone structures. In particu...
Saved in:
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Conference or Workshop Item |
| Language: | English |
| Published: |
2013
|
| Online Access: | https://hdl.handle.net/10356/98923 http://hdl.handle.net/10220/12634 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Nanyang Technological University |
| Language: | English |
| id |
sg-ntu-dr.10356-98923 |
|---|---|
| record_format |
dspace |
| spelling |
sg-ntu-dr.10356-989232020-03-07T12:31:20Z Clone structures in voters' preferences Elkind, Edith Faliszewski, Piotr Slinko, Arkadii School of Physical and Mathematical Sciences Conference on Electronic Commerce (13th : 2012 : Valencia, Spain) In elections, a set of candidates ranked consecutively (though possibly in different order) by all voters is called a clone set, and its members are called clones. A clone structure is the family of all clone sets of a given election. In this paper we study properties of clone structures. In particular, we give an axiomatic characterization of clone structures, show that they are organized hierarchically, and analyze clone structures in single-peaked and single-crossing elections. We describe a polynomial-time algorithm that finds a minimal collection of clones that need to be collapsed for an election to become single-peaked, and we show that this problem is NP-hard for single-crossing elections. 2013-07-31T06:56:24Z 2019-12-06T20:01:10Z 2013-07-31T06:56:24Z 2019-12-06T20:01:10Z 2012 2012 Conference Paper Elkind, E., Faliszewski, P., & Slinko, A. (2012). Clone structures in voters' preferences. Proceedings of the 13th ACM Conference on Electronic Commerce - EC '12, 496-513. https://hdl.handle.net/10356/98923 http://hdl.handle.net/10220/12634 10.1145/2229012.2229050 en |
| institution |
Nanyang Technological University |
| building |
NTU Library |
| country |
Singapore |
| collection |
DR-NTU |
| language |
English |
| description |
In elections, a set of candidates ranked consecutively (though possibly in different order) by all voters is called a clone set, and its members are called clones. A clone structure is the family of all clone sets of a given election. In this paper we study properties of clone structures. In particular, we give an axiomatic characterization of clone structures, show that they are organized hierarchically, and analyze clone structures in single-peaked and single-crossing elections. We describe a polynomial-time algorithm that finds a minimal collection of clones that need to be collapsed for an election to become single-peaked, and we show that this problem is NP-hard for single-crossing elections. |
| author2 |
School of Physical and Mathematical Sciences |
| author_facet |
School of Physical and Mathematical Sciences Elkind, Edith Faliszewski, Piotr Slinko, Arkadii |
| format |
Conference or Workshop Item |
| author |
Elkind, Edith Faliszewski, Piotr Slinko, Arkadii |
| spellingShingle |
Elkind, Edith Faliszewski, Piotr Slinko, Arkadii Clone structures in voters' preferences |
| author_sort |
Elkind, Edith |
| title |
Clone structures in voters' preferences |
| title_short |
Clone structures in voters' preferences |
| title_full |
Clone structures in voters' preferences |
| title_fullStr |
Clone structures in voters' preferences |
| title_full_unstemmed |
Clone structures in voters' preferences |
| title_sort |
clone structures in voters' preferences |
| publishDate |
2013 |
| url |
https://hdl.handle.net/10356/98923 http://hdl.handle.net/10220/12634 |
| _version_ |
1681041944304680960 |