《Sincerity-and-Manipulation-under-Approval-Voting.pdf》由会员分享，可在线阅读，更多相关《Sincerity-and-Manipulation-under-Approval-Voting.pdf（19页珍藏版）》请在三一文库上搜索。
1、Sincerity and Manipulation under Approval Voting Ulle Endriss Institute for Logic, Language and Computation University of Amsterdam 20 December 2011 Abstract Under approval voting, each voter can nominate as many candidates as she wishes and the election winners are those candidates that are nominat
2、ed most often. A voter is said to have voted sincerely if she prefers all those candidates she nominated to all other candidates. As there can be a set of winning candidates rather than just a single winner, a voters incentives to vote sincerely will depend on what assumptions we are willing to make
3、 regarding the principles by which voters extend their preferences over individual candidates to preferences over sets of candidates. We formulate two such principles, replacement and deletion, and we show that, under approval voting, a voter who accepts those two principles and who knows how the ot
4、her voters will vote will never have an incentive to vote insincerely. We then discuss the consequences of this result for a number of standard principles of preference extension in view of sincere voting under approval voting. Keywords: Approval voting, Manipulation, Ranking sets of objects JEL Cla
5、ssifi cation: D71 1Introduction Approval voting (AV) is a voting procedure that allows each voter to approve of as many candidates as she desires and that declares the candidate(s) collecting the most approvals the winner(s) of the election (Weber, 1978; Brams and Fishburn, 1978, 2007; Laslier and S
6、anver, 2010). AV has been strongly advocated by some, and severely criticised by others.While there may be no clear-cut conclusion to this debate, it is certainly true that AV has found its place as one of the major election systems studied in economic theory and political science and it is also wid
7、ely used in practice. Brams (2008), for instance, cites the use of AV to elect the secretary-general of the United Nations and its adoption by numerous professional societies, including the American Mathematical Society (AMS), Parts of this work have been presented at the 11th Conference on Theoreti
8、cal Aspects of Rationality and Knowledge (TARK) in Brussels in June 2007, the Social Choice Colloquium at the University of Tilburg in September 2007, the Dagstuhl Seminar on Computational Issues in Social Choice in October 2007, and the 7th International Meeting on Logic, Game Theory and Social Cho
9、ice (LGS) in Bucharest in July 2011, as well as local seminars at the Universities of Amsterdam, Padova, and Paris-Dauphine. The insightful feedback received from the participants of these meetings is gratefully acknowledged. Thanks are also due to Steve Brams and an anonymous reviewer for comments
10、on an earlier version of this paper, and to Remzi Sanver and Bill Zwicker for illuminating discussions on preference extensions. 1 the Institute for Operations Research and Management Sciences (INFORMS), and the Society for Social Choice and Welfare. As discussed, for instance, by Sanver (2010), des
11、pite its prominent position amongst the major voting procedures, AV does in fact not directly fi t into the standard model of voting used in social choice theory. In this model, each voter is assumed to have a ranking of the candidates representing her preferences; and voters vote by reporting such
12、a ranking (truthfully or otherwise) to the election chair. AV does not fi t this model, because in AV a ballot is a subset of the set of candidates rather than a ranking of those candidates. It is easy to see that it is impossible to encode the information required to recover a ranking from an AV ba
13、llot: there are more ways to rank n candidates than there are to pick a subset from a set of n candidates (for n 3). This means that the question of whether a voter will vote truthfully, central to much of voting theory, is not a meaningful question for AV: if we cannot fully express our preferences
14、, we can certainly not be expected to do so truthfully. This problem is well known (see, e.g., Niemi, 1984). Therefore, instead of truthfulness we will be interested in sincerity. In AV, a ballot is called sincere if the voter in question prefers each of the approved candidates to each of the disapp
15、roved candidates (Brams and Fishburn, 2007). That is, any given preference order will give rise to multiple sincere ballots to choose from. Suppose a voter has learned how everybody else will vote in a forthcoming AV election. The question we seek to answer in this paper is this: Are there reasonabl
16、e assumptions under which the set of best responses of such a voter will always include a sincere ballot? When there is more than one candidate with a maximal number of approvals, then AV produces a set of tied winners (from which we may have to select a single candidate using a suitable tie-breakin
17、g rule). Therefore, a voter considering to manipulate an election will have to reason over alternative sets of winning candidates. The assumptions we shall work with concern the principles by which a voter will extend her preferences over individual candidates to a preference order over (nonempty) s
18、ets of candidates when considering what ballot to submit. This is a well-studied problem in social choice theory, often referred to as ranking sets of objects (see, e.g., Barber a et al., 2004; G ardenfors, 1976; Kelly, 1977; Kannai and Peleg, 1984; Nitzan and Pattanaik, 1984; Puppe, 1995; Can et al
19、., 2009; Erdamar and Sanver, 2009; Geist and Endriss, 2011) and we shall be examining incentives to vote sincerely under AV for a range of diff erent such principles proposed in the literature. The remainder of this paper is organised as follows. In Section 2 we introduce our model, which involves d
20、efi ning the approval voting procedure and the notion of sincerity, and we state the question we shall address in this paper in more detail. A central aspect of the model concerns the assumptions made on how voter preferences over individual candidates extend to preferences over sets of candidates.
21、Section 3 reviews a range of axioms proposed in the literature for modelling this problem. Section 4 then presents our results on the existence of sincere best responses under AV for diff erent sets of assumptions on how preferences are extended to set preferences. Section 5 reviews related work, an
22、d in Section 6 we summarise our results and conclude. 2The Model In this section we defi ne our model and state the main problem we shall address. (An important detail of the model, namely how voters extend their preferences over individual candidates to sets of candidates, will largely be relegated
23、 to Section 3.) 2 2.1Preferences Recall that a preorder is a binary relation that is refl exive and transitive; a weak order is a preorder that is complete; and a total order is a weak order that is antisymmetric (Roberts, 1979). Throughout this paper, let X be a fi nite set of two or more candidate
24、s and let n = |X| denote the number of candidates. Let X = 2X denote the set of nonempty sets of candidates. We consider a fi nite set of voters. Each voter has preferences over individual candidates, modelled as a total order on X. That is, we write a b to express that the voter in question likes c
25、andidate a at least as much as candidate b. We write a b (strict preference) if a b but not b a. Each voter furthermore has preferences over election outcomes (before tie-breaking), i.e., over sets of candidates that the tie-breaking rule may choose from. This is modelled as a weak order and on her
26、beliefs regarding the nature of the tie-breaking rule in use.1While a voters , we assume that we do not know how to derive (besides also not knowing itself). For example, even if we were to learn that a b c, then this usually does not provide us with any hints regarding the relative ranking of a,c v
27、ersus b in terms of on X to a weak order b for all b A (with always clear from the context). Similarly, we write min(A) for the (unique) minimal element in A. Beyond her preference order , a voter might also have a utility (or valuation) function u : X R mapping individual candidates to numerical va
28、lues.Such a utility function induces a preference order , namely: a b if and only if u(a) u(b). But u on its own does not induce a corresponding weak order . (Recall that both ballots and outcomes are subsets of X.) The notation is best explained by means of a concrete example. Suppose there are 5 c
29、andidates. To denote the ballot that approves of the two top candidates and the bottom candidate according to our voters preferences, we write 11001. To denote outcomes, we use curly brackets rather than square brackets. For instance, 01000 is the election outcome in which our voters second favourit
30、e candidate is the sole winner. 2.3Sincere Best Responses Given a voters preference order , a ballot B X is called sincere if the voter really does prefer each approved candidate to each disapproved candidate; that is, if a b for all a B and all b XB. This is the standard notion of sincerity in AV a
31、s defi ned by Brams and Fishburn (2007, p. 29). Observe that according to this defi nition, abstention ballots are considered sincere.2 Suppose we have fi xed a principle of preference extension. Suppose furthermore a particular voter knows how all other voters are going to vote and is considering w
32、hich ballot to submit.We are interested in her incentives to vote sincerely in this kind of situation. She has an incentive to vote insincerely, if there exists an outcome she can achieve by means of an insincere ballot that (strictly) dominates (according to her , declared over the set of candidate
33、s X, is not suffi cient to fully describe her preferences over election outcomes, which are nonempty sets of candidates. We therefore need to choose a suitable set of assumptions that govern how a voters preference order over individual candidates are to be lifted to a preference relation b Formally
34、, axioms such as this are properties of triples (X, over those candidates, and a weak order , as fi xed. Besides (EXT), there are two further assumptions that we can safely make without any knowledge of the tie-breaking rule or the voters attitude towards risk: (MAX)max(A) a for all a A (GF2)A ? A b
35、if a b for all a A We shall write (GAR) for the conjunction of (GF1) and (GF2). The G ardenfors Principle is strictly stronger (more restrictive) than the Kelly Principle. We state this well-known fact as a lemma. In the statement of that lemma, the proof of which is straightforward, and throughout
36、the remainder of this paper, we say that a set of axioms entails another set of axioms , if for any triple (X, on X, and a weak order , 6 there can be no weak order that is consistent with both (GAR) and (IND). This suggests that, despite its intuitive appeal, the independence axiom is too restricti
37、ve to model set preferences. (MMX) is weaker and Kannai and Pelegs impossibility does not persist if we use that axiom instead. We shall refer to the conjunction 6 of (GAR) and (MMX) as the Kannai-Peleg Principle. Several preference extensions proposed in the literature are refi nements of (what we
38、call) the Kannai-Peleg Principle (Barber a et al., 2004). 3.4Nitzan-Pattanaik Principle: Median-Based Preferences Nitzan and Pattanaik (1984) suggest to rank alternative sets on the basis of their medians. The median of an odd-numbered set of candidates A is the candidate a A such that the number of
39、 elements in A that are preferred to a is equal to the number of elements in A that are considered inferior to a. For even-numbered sets, there are two median elements. Formally, we defi ne the median of a set A X as the subset med(A) = a A | #b A | b a #b A | a b 0,1,1, which always has either one
40、or two elements. We use this defi nition to formulate the following axiom: (MED)A med(A) We call the conjunction of (GAR) and (MED) the Nitzan-Pattanaik Principle. That is, under this principle, sets are compared by comparing their medians using the G ardenfors Principle. Like the Kannai-Peleg Princ
41、iple, the Nitzan-Pattanaik Principle is appealing from a cognitive point of view. Indeed, it is very natural to assume that a voters preferences over sets will depend on her preferences over a small number of distinguished elements within those sets, rather than the full sets. In the case of the Kan
42、nai-Peleg Principle, these distinguished elements are the best and the worst element in a set, while for the Nitzan-Pattanaik it is the middle-most element (or possibly the two middle-most elements). 3.5Uniform Tie-Breaking with Expected-Utility Maximisers Arguably the most natural choice for a tie-
43、breaking mechanism is the uniform tie-breaking rule, where each of the front-runners is selected as the election winner with equal probability. Assuming that the uniform tie-breaking rule is used together with the assumption that voters are expected-utility maximisers yields a very attractive framew
44、ork in which to analyse voters preferences over sets of candidates. While these assumptions have been axiomatised in the literature (see, e.g., Fishburn, 1972; Can et al., 2009), for our purposes it is more convenient to give a direct defi nition. Take a set of candidates X and a voter whose prefere
45、nces are represented by a total order on X and a weak order , i.e., for all a,b X we have u(a) u(b) if and only if a b; and (ii) for all A,B X we have A 1 |B| X bB u(b) 3.6Optimism and Pessimism Adopting the terminology of Taylor (2005), we say that a voter is optimistic if she prefers set A over se
46、t B whenever she prefers the best element in A over the best element in B. We use the following axiom to express optimism: (OPT)A max(A) 7 We say that a voter is an optimist if she conforms to (OPT) on top of the Kelly Principle. A voter who believes that the person charged with breaking ties shares
47、 her own preferences is one example for someone who will have optimistic set preferences. Similarly, if the uniform tie-breaking rule is used and a voter is an expected-utility maximiser with a very skewed utility function, giving much higher utility to a than to b whenever a b, then that voter will
48、 have set preferences that satisfy (OPT). A voter may also be pessimistic and judge sets of candidates in terms of the worst candidates in those sets. A pessimist is a voter that conforms to (KEL) and the following axiom: (PES)A min(A) 4Existence of Sincere Best Responses In this section we prove a
49、number of theorems that show that, under certain assumptions on the principles for preference extension that voters conform to, we are able to guarantee that each voter will have a sincere best response to any combination of ballots chosen by the other voters. That is, if a would-be manipulator obtains information on how the others will vote, she will never have an incentive to exploit this knowledge by casting an insincere ballot. 4.1An Example for Insincere M