Manipulation with Bounded Single-Peaked Width : A Parameterized Study. Yang, Y., Saarlandes, U., Mmci, C., E., & Saarbrücken, D. 7(Mmci):77-85, 2015. Paper abstract bibtex We study the manipulation problem in elections with bounded single-peaked width from the parameterized complexity point of view. In particular, we focus on the Borda, Copelandα and Maximin voting correspondences. For Borda, we prove that the unweighted manipulation problem with two manipulators is fixed-parameter tractable with respect to single-peaked width. For Maximin and Copelandα for every 0 ≤ α ≤ 1, we prove that the unweighted manipulation problem is fixed-parameter tractable with respect to the combined parameter (k, t), where k denotes the single-peaked width and t denotes the number of manipulators. In addition, we study the weighted manipulation problem for Maximin and Copelandα for every 0 ≤ α ≤ 1 in single-peaked elections and achieve several polynomial-time solvability results.
@article{
title = {Manipulation with Bounded Single-Peaked Width : A Parameterized Study},
type = {article},
year = {2015},
identifiers = {[object Object]},
keywords = {borda,copeland,fixed-parameter tractable,maximin,parameterized com-,plexity,single-peaked width,weighted election},
pages = {77-85},
volume = {7},
id = {92ad9185-4092-3a4a-bf32-8abccb8e07e8},
created = {2016-07-09T17:08:36.000Z},
file_attached = {true},
profile_id = {6835648d-fd3c-34d3-a1a2-9a7b291884eb},
group_id = {c5a02f2e-65c1-39ec-ac2e-a720cb3dfc60},
last_modified = {2016-07-09T17:08:36.000Z},
read = {false},
starred = {false},
authored = {false},
confirmed = {true},
hidden = {false},
abstract = {We study the manipulation problem in elections with bounded single-peaked width from the parameterized complexity point of view. In particular, we focus on the Borda, Copelandα and Maximin voting correspondences. For Borda, we prove that the unweighted manipulation problem with two manipulators is fixed-parameter tractable with respect to single-peaked width. For Maximin and Copelandα for every 0 ≤ α ≤ 1, we prove that the unweighted manipulation problem is fixed-parameter tractable with respect to the combined parameter (k, t), where k denotes the single-peaked width and t denotes the number of manipulators. In addition, we study the weighted manipulation problem for Maximin and Copelandα for every 0 ≤ α ≤ 1 in single-peaked elections and achieve several polynomial-time solvability results.},
bibtype = {article},
author = {Yang, Yongjie and Saarlandes, Universität and Mmci, Campus E and Saarbrücken, D-},
number = {Mmci}
}
Downloads: 0
{"_id":"t9LcyxnCkoSBo2erx","bibbaseid":"yang-saarlandes-mmci-saarbrcken-manipulationwithboundedsinglepeakedwidthaparameterizedstudy-2015","downloads":0,"creationDate":"2016-07-09T17:03:16.685Z","title":"Manipulation with Bounded Single-Peaked Width : A Parameterized Study","author_short":["Yang, Y.","Saarlandes, U.","Mmci, C., E.","Saarbrücken, D."],"year":2015,"bibtype":"article","biburl":null,"bibdata":{"title":"Manipulation with Bounded Single-Peaked Width : A Parameterized Study","type":"article","year":"2015","identifiers":"[object Object]","keywords":"borda,copeland,fixed-parameter tractable,maximin,parameterized com-,plexity,single-peaked width,weighted election","pages":"77-85","volume":"7","id":"92ad9185-4092-3a4a-bf32-8abccb8e07e8","created":"2016-07-09T17:08:36.000Z","file_attached":"true","profile_id":"6835648d-fd3c-34d3-a1a2-9a7b291884eb","group_id":"c5a02f2e-65c1-39ec-ac2e-a720cb3dfc60","last_modified":"2016-07-09T17:08:36.000Z","read":false,"starred":false,"authored":false,"confirmed":"true","hidden":false,"abstract":"We study the manipulation problem in elections with bounded single-peaked width from the parameterized complexity point of view. In particular, we focus on the Borda, Copelandα and Maximin voting correspondences. For Borda, we prove that the unweighted manipulation problem with two manipulators is fixed-parameter tractable with respect to single-peaked width. For Maximin and Copelandα for every 0 ≤ α ≤ 1, we prove that the unweighted manipulation problem is fixed-parameter tractable with respect to the combined parameter (k, t), where k denotes the single-peaked width and t denotes the number of manipulators. In addition, we study the weighted manipulation problem for Maximin and Copelandα for every 0 ≤ α ≤ 1 in single-peaked elections and achieve several polynomial-time solvability results.","bibtype":"article","author":"Yang, Yongjie and Saarlandes, Universität and Mmci, Campus E and Saarbrücken, D-","number":"Mmci","bibtex":"@article{\n title = {Manipulation with Bounded Single-Peaked Width : A Parameterized Study},\n type = {article},\n year = {2015},\n identifiers = {[object Object]},\n keywords = {borda,copeland,fixed-parameter tractable,maximin,parameterized com-,plexity,single-peaked width,weighted election},\n pages = {77-85},\n volume = {7},\n id = {92ad9185-4092-3a4a-bf32-8abccb8e07e8},\n created = {2016-07-09T17:08:36.000Z},\n file_attached = {true},\n profile_id = {6835648d-fd3c-34d3-a1a2-9a7b291884eb},\n group_id = {c5a02f2e-65c1-39ec-ac2e-a720cb3dfc60},\n last_modified = {2016-07-09T17:08:36.000Z},\n read = {false},\n starred = {false},\n authored = {false},\n confirmed = {true},\n hidden = {false},\n abstract = {We study the manipulation problem in elections with bounded single-peaked width from the parameterized complexity point of view. In particular, we focus on the Borda, Copelandα and Maximin voting correspondences. For Borda, we prove that the unweighted manipulation problem with two manipulators is fixed-parameter tractable with respect to single-peaked width. For Maximin and Copelandα for every 0 ≤ α ≤ 1, we prove that the unweighted manipulation problem is fixed-parameter tractable with respect to the combined parameter (k, t), where k denotes the single-peaked width and t denotes the number of manipulators. In addition, we study the weighted manipulation problem for Maximin and Copelandα for every 0 ≤ α ≤ 1 in single-peaked elections and achieve several polynomial-time solvability results.},\n bibtype = {article},\n author = {Yang, Yongjie and Saarlandes, Universität and Mmci, Campus E and Saarbrücken, D-},\n number = {Mmci}\n}","author_short":["Yang, Y.","Saarlandes, U.","Mmci, C., E.","Saarbrücken, D."],"urls":{"Paper":"http://bibbase.org/service/mendeley/6835648d-fd3c-34d3-a1a2-9a7b291884eb/file/47af977a-f05a-231b-5d8e-345c15e39914/2015-Manipulation_with_Bounded_Single-Peaked_Width__A_Parameterized_Study.pdf.pdf"},"bibbaseid":"yang-saarlandes-mmci-saarbrcken-manipulationwithboundedsinglepeakedwidthaparameterizedstudy-2015","role":"author","keyword":["borda","copeland","fixed-parameter tractable","maximin","parameterized com-","plexity","single-peaked width","weighted election"],"downloads":0},"search_terms":["manipulation","bounded","single","peaked","width","parameterized","study","yang","saarlandes","mmci","saarbrücken"],"keywords":["borda","copeland","fixed-parameter tractable","maximin","parameterized com-","plexity","single-peaked width","weighted election"],"authorIDs":[]}