Auswahl der wissenschaftlichen Literatur zum Thema „Nearly single-peaked preferences“

The facility location game is an extensively studied problem in mechanism design. In the classical model, the cost of each agent is her distance to the nearest facility. In this paper, we consider a novel model where each facility charges an entrance fee, which is a function of the facility's location. Thus, in our model, the cost of each agent is the sum of the distance to the facility and the entrance fee of the facility. The generalized model captures more real-life scenarios. In our model, the entrance fee function can be an arbitrary function, and the corresponding preferences of agents may not be single-peaked anymore: this makes the problem complex and requires new techniques in the analysis. We systematically study the model and design strategyproof mechanisms with nice approximation ratios and also complement these with nearly-tight impossibility results. Specifically, for one-facility and two-facility games, we provide upper and lower bounds for the approximation ratios given by deterministic and randomized mechanisms, with respect to the utilitarian and egalitarian objectives. Most of our bounds are tight, and these bounds are independent of the entrance fee functions. Our results also match the results of the classical model.

Structured preference domains, such as, for example, the domains of single-peaked and single-crossing preferences, are known to admit efficient algorithms for many problems in computational social choice. Some of these algorithms extend to preferences that are close to having the respective structural property, i.e., can be made to enjoy this property by performing minor changes to voters' preferences, such as deleting a small number of voters or candidates. However, it has recently been shown that finding the optimal number of voters or candidates to delete in order to achieve the desired structural property is NP-hard for many such domains. In this paper, we show that these problems admit efficient approximation algorithms. Our results apply to all domains that can be characterized in terms of forbidden configurations; this includes, in particular, single-peaked and single-crossing elections. For a large range of scenarios, our approximation results are optimal under a plausible complexity-theoretic assumption. We also provide parameterized complexity results for this class of problems.

Understanding when and how computational complexity can be used to protect elections against different manipulative actions has been a highly active research area over the past two decades. A recent body of work, however, has shown that many of the NP-hardness shields, previously obtained, vanish when the electorate has single-peaked or nearly single-peaked preferences. In light of these results, we investigate whether it is possible to reimpose NP-hardness shields for such electorates by allowing the voters to specify partial preferences instead of insisting they cast complete ballots. In particular, we show that in single-peaked and nearly single-peaked electorates, if voters are allowed to submit top-truncated ballots, then the complexity of manipulation and bribery for many voting rules increases from being in P to being NP-complete.

Cette thèse étudie des aspects structurels et algorithmiques des restrictions de domaines de préférences, en se focalisant sur les préférences unimodales et les préférences Euclidiennes. Dans la première partie de la thèse, nous introduisons d'abord une généralisation des préférences unimodales sur des graphes quelconques, en se focalisant sur des aspects algorithmiques, notamment le problème de reconnaissance. Dans un deuxième temps, nous nous intéressons aux préférences presque unimodales. Plus précisément, nous proposons une nouvelle métrique d'unimodalité approchée et nous étudions ses propriétés théoriques et computationnelles. La deuxième partie de la thèse est consacrée à l'étude des préférences d-Euclidiennes (où d est la dimension) par rapport à différentes normes. Nous proposons d'abord une heuristique de reconnaissance des préférences 2-Euclidiennes par rapport à la norme l_2, et étudions son efficacité en pratique. Enfin, nous étudions des aspects structurels des préférences 2-Euclidiennes par rapport à la norme l_1
This thesis studies structural and algorithmic aspects of preference domain restrictions, namely single-peaked preferences and Euclidean preferences. In the first part of the thesis, we first introduce a generalization of the notion of single-peakedness on an arbitrary graph. We focus, in particular, on algorithmic aspects, namely the problem of recognition. The notion of nearly single-peakedness is then studied. More precisely, we introduce a new metric of nearly single-peakedness, and we study its theoretical and computational properties. The second part of the thesis is devoted to the study of d-Euclidean preferences (where d is the dimension of the real space) with respect to different norms. We first propose a heuristic algorithm for recognizing 2-Euclidean preferences with respect to the l_2 norm, and study its practical efficiency in practice. Finally, we focus on structural aspects of 2-Euclidean preferences with respect to the l_1 norm

We investigate winner determination for two popular proportional representation systems: the Monroe and Chamberlin-Courant (abbrv. CC) systems. Our study focuses on (nearly) single-peaked resp. single-crossing preferences. We show that for single-crossing approval preferences, winner determination of the Monroe rule is polynomial, and for both rules, winner determination mostly admits FPT algorithms with respect to the number of voters to delete to obtain single-peaked or single-crossing preferences. Our results answer some complexity questions from the literature [19, 29, 22].

We present an almost optimal algorithm for the classic Chamberlin-Courant multiwinner voting rule (CC) on single-peaked preference profiles. Given n voters and m candidates, it runs in almost linear time in the input size improving the previous best O(nm^2) time algorithm. We also study multiwinner voting rules on nearly single-peaked preference profiles in terms of the candidate-deletion operation. We show a polynomial-time algorithm for CC where a given candidate-deletion set D has logarithmic size. Actually, our algorithm runs in 2^|D| * poly(n,m) time and the base of the power cannot be improved under the Strong Exponential Time Hypothesis. We also adapt these results to all non-constant Thiele rules which generalize CC with approval ballots.