Preferences single-peaked on nice trees
Preference profiles that are single-peaked on trees enjoy desirable properties: they admit a Condorcet winner (Demange 1982), and there are hard voting problems that become tractable on this domain (Yu et al., 2013). Trick (1989) proposed a polynomial-time algorithm that finds some tree with respect...
| Main Authors: | , |
|---|---|
| Formato: | Conference item |
| Idioma: | English |
| Publicado em: |
AAAI Press
2016
|
| _version_ | 1826281755822260224 |
|---|---|
| author | Peters, D Elkind, E |
| author_facet | Peters, D Elkind, E |
| author_sort | Peters, D |
| collection | OXFORD |
| description | Preference profiles that are single-peaked on trees enjoy desirable properties: they admit a Condorcet winner (Demange 1982), and there are hard voting problems that become tractable on this domain (Yu et al., 2013). Trick (1989) proposed a polynomial-time algorithm that finds some tree with respect to which a given preference profile is single-peaked. However, some voting problems are only known to be easy for profiles that are single-peaked on "nice" trees, and Trick's algorithm provides no guarantees on the properties of the tree that it outputs. To overcome this issue, we build on the work of Trick and Yu et al. to develop a structural approach that enables us to compactly represent all trees with respect to which a given profile is single-peaked. We show how to use this representation to efficiently find the "best" tree for a given profile, according to a number of criteria; for other criteria, we obtain NP-hardness results. In particular, we show that it is NP-hard to decide whether an input profile is single-peaked with respect to a given tree. To demonstrate the applicability of our framework, we use it to identify a new class of profiles that admit an efficient algorithm for a popular variant of the Chamberlin-Courant rule. |
| first_indexed | 2024-03-07T00:33:35Z |
| format | Conference item |
| id | oxford-uuid:80a7457e-5014-44ad-a51a-17a08fa6e3e8 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T00:33:35Z |
| publishDate | 2016 |
| publisher | AAAI Press |
| record_format | dspace |
| spelling | oxford-uuid:80a7457e-5014-44ad-a51a-17a08fa6e3e82022-03-26T21:24:45ZPreferences single-peaked on nice treesConference itemhttp://purl.org/coar/resource_type/c_5794uuid:80a7457e-5014-44ad-a51a-17a08fa6e3e8EnglishSymplectic ElementsAAAI Press2016Peters, DElkind, EPreference profiles that are single-peaked on trees enjoy desirable properties: they admit a Condorcet winner (Demange 1982), and there are hard voting problems that become tractable on this domain (Yu et al., 2013). Trick (1989) proposed a polynomial-time algorithm that finds some tree with respect to which a given preference profile is single-peaked. However, some voting problems are only known to be easy for profiles that are single-peaked on "nice" trees, and Trick's algorithm provides no guarantees on the properties of the tree that it outputs. To overcome this issue, we build on the work of Trick and Yu et al. to develop a structural approach that enables us to compactly represent all trees with respect to which a given profile is single-peaked. We show how to use this representation to efficiently find the "best" tree for a given profile, according to a number of criteria; for other criteria, we obtain NP-hardness results. In particular, we show that it is NP-hard to decide whether an input profile is single-peaked with respect to a given tree. To demonstrate the applicability of our framework, we use it to identify a new class of profiles that admit an efficient algorithm for a popular variant of the Chamberlin-Courant rule. |
| spellingShingle | Peters, D Elkind, E Preferences single-peaked on nice trees |
| title | Preferences single-peaked on nice trees |
| title_full | Preferences single-peaked on nice trees |
| title_fullStr | Preferences single-peaked on nice trees |
| title_full_unstemmed | Preferences single-peaked on nice trees |
| title_short | Preferences single-peaked on nice trees |
| title_sort | preferences single peaked on nice trees |
| work_keys_str_mv | AT petersd preferencessinglepeakedonnicetrees AT elkinde preferencessinglepeakedonnicetrees |