On Relating Voting Systems and Argumentation Frameworks Irene Benedetti? , Stefano Bistarelli?? , and Paolo Piersanti Dipartimento di Matematica e Informatica, Università di Perugia [irene.benedetti,bista]@dmi.unipg.it paolopiers@gmail.com Abstract. In the modern world formal voting theories are becoming established and can be used to determine if a Voting System (VS) is fair or not in order to preserve democracy. The Argumentation Framework (AF) is based on the exchange and the evaluation of interacting arguments which may represent information of various kinds. We define a bijective mapping between the two theories and investigate how fairness criteria defined for voting systems can be re-interpreted inside the Argumentation Frameworks. 1 Introduction The analysis of voting methods and their properties start from the pioneering work of Arrow [1]. Using his impossibility theorem results classical and nowadays voting and election systems can be analyzed and some fairness judgements can be expressed. The formal study of argumentation has come to be increasingly central as a core study within Artificial Intelligence and it is also of interest in several disciplines, such as Logic, Philosophy and Communication Theory [7]. Argumentation [4, 5] is based on the exchange and the evaluation of interacting arguments which may represent information of various kinds, especially beliefs or goals. Many theoretical and practical developments are built on Dung’s seminal theory of argumentation. We define a voting system VS as a function that associates to the given set of votes, the elected candidate(s). We then define a map from VSs to AFs and study the known semantics (ground extension in particular) as voting methods. 2 Argumentation framework Definition 1. An Argumentation Framework (AF) is a pair hArgs , Ri of a set Args of arguments and a binary relation R on Args called the attack relation. 8ai , aj 2 Args , ai R aj means that ai attacks aj . An AF may be represented by a directed graph (the interaction graph) whose nodes are arguments and edges represent the attack relation. A set of arguments B attacks an argument a if a is attacked by an argument of B. A set of arguments B attacks a set of arguments C if there is an argument b 2 B which attacks an argument c 2 C. ? partially supported by the Italian Research Project GNAMPA 2014: "Metodi Topologici: sviluppi ed applicazioni a problemi differenziali non lineari". ?? Partially supported by the italian MIUR project PRIN "Metodi logici per il trattamento dell’informazione" 309 I. Benedetti et al. On Relating Voting Systems and Argumentation Frameworks The “acceptability” of an argument [5] depends on its membership to some sets, called extensions. These extensions characterize collective “acceptability”. Dung [5] gave several semantics to “acceptability”. These various semantics produce none, one or several acceptable sets of arguments, called extensions. In Def. 2 we define the concepts of conflict-free and stable extensions: Definition 2. A set B ✓ Args is conflict-free iff no two arguments a and b in B exist such that a attacks b. A conflict-free set B ✓ Args is a stable extension iff for each argument which is not in B, there exists an argument in B that attacks it. The other semantics for “acceptability” rely upon the concept of defense: Definition 3. An argument b is defended by a set B ✓ Args (or B defends b) iff for any argument a 2 Args , if a attacks b then B attacks a. An admissible set of arguments according to Dung must be a conflict-free set which defends all its elements. Formally: Definition 4. A conflict-free set B ✓ Args is admissible iff each argument in B is defended by B. Besides the stable semantics, three semantics refining admissibility have been introduced by Dung [5]: Definition 5. A preferred extension is a maximal (w.r.t. set inclusion) admissible subset of Args . An admissible B ✓ Args is a complete extension iff each argument which is defended by B is in B. The least (w.r.t. set inclusion) complete extension is the grounded extension. A stable extension is also a preferred extension and a preferred extension is also a complete extension. Stable, preferred and complete semantics admit multiple extensions whereas the grounded semantics ascribes a single extension to a given argument system. Since the grounded extension is proven to be unique, and we are going to define a new voting systems using Argumentation Semantics, this semantics will be our best candidate (see Section 4). 3 Voting Systems The process of cooperative decision making has been formalized using formal social choice theory and formal game theory, see e.g. [3, 8]. A voting system enforces rules to ensure valid voting, and how votes are counted and aggregated to yield a final result. More formally, a voting system specifies the form of the ballot, the set of allowable votes, and the tallying method, an algorithm for determining the outcome. This outcome may be a single winner, or may involve multiple winners such as in the election of a legislative body. We focus our study on the non-preferential voting methods such as the block voting. Example 1 (Block voting). This non preferential voting method is used to elect n options from a group of m options (m > n). The voter has to point out l with n l preferences between the m available. Consider five candidates A, B, C, D and E and suppose each of them vote three options between the five proposed. Let’s suppose the result yielded by the election is as in Table 1. This situation leads to a tie because there are four candidates, each one with three votes received (or to elect all of them). ⇤ 310 I. Benedetti et al. On Relating Voting Systems and Argumentation Frameworks Table 1: Selecting the winner with block voting. Voter/ Candidate Vote Votes received A B, A, D 3 B C, D, E 3 C A, B, C 3 D D, E, A 3 E C, E, B 2 Different voting systems may give very different results, particularly in cases where there is no clear majority preference. Many fairness criteria were defined; We remind here the five basic criteria of fairness proposed by Arrow in 1950 [1] and revised in 1963 [2]. Definition 6 (Arrow Fairness Criteria). 1. Universal admissibility (unrestricted domain): Voting systems should not place any restrictions other than transitivity on how voters can rank the candidates in an election. 2. Monotonicity: if an election is held and a winner is declared, this winning candidate should remain the winner in any revote in which all preference changes are in favor of the winner of the original election. 3. Independence of irrelevant alternatives (IIA) (binary independence): If an elec- tion is held and a winner is declared, this winning candidate should remain the winner in any recalculation of votes as a result of one or more of the losing candidates dropping out. 4. Condition of citizens sovereignity (non imposition): Voting systems should not be imposed in any way. That is, there should never be a pair of candidates in an election, say A and B, such that A is preferred over or tied with B in the resulting social preference order regardless of how any of the voters vote. 5. Condition of non-dictatorship: Voting systems should not be dictatorial. That is, there should never be a voter v such that, for any pair of candidates A and B, if v prefers A over B, then society will also prefer A over B. Theorem 1 (Arrow [1,2]). If there are at least three candidates, any (preferential) voting method satisfying criteria 1,2 and 3 must be either imposed or dictatorial. 4 Main results In this section we formally define a voting system and the mapping between Voting Systems and Argumentation Frameworks. Definition 7 (Ballots and Voting Systems). A Ballot B is a pair B = hCands [Voters , V P i of a set Cands of Candidates, a set Voters of Voters and a Voting Procedure V P rep- resenting a binary relation on Voters ⇥ P(Cands ) (where given a set A with P(A) we denote the power set of A) that associates to each voter v 2 Voters her votes to the candidates C ✓ Cands . A Voting System vs : Cands [ Voters ⇥ V P ! P(Cands ) is a function assigning to a ballot B = hCands [ Voters , V P i a set (or more sets in case of ties) of winning candidates W ✓ P(Cands ). 311 I. Benedetti et al. On Relating Voting Systems and Argumentation Frameworks In the rest of this paper we assume the set of Candidates Cands , and the set of Voters Voters to coincide in an unique set of Options O = Cands = Voters (as in many real social elections). The first of our results is to show that using a suitable mapping between VSs and AFs, the Semantics of an argumentation framework can be used to define a voting system with interesting properties. More in detail, we map every option (representing candidates or voters) to an argument and the relation ‘a votes for b’ to the attacks a ! b0 for any b0 6= b (to support in this way b). Definition 8 (from VS to AF and back). We define a mapping m from VSs (more specifically from a ballot B) to AFs m : O ⇥ V P ! Args ⇥ R such that – for each option o 2 O we consider an argument a = m(o), – for each vote ho, Ci 2 O ⇥ P(O), we obtain the set of attacks m(ho, Ci) = {ha, m(c0 )i, s.t. c0 62 C} Using m 1 we can instead define the corresponding mapping from AFs to VSs: – for each argument a we consider the corresponding option (candidate/voter) o = m 1 (a), S – for each argument a, b 2 Args , and the set B = b2Args b s.t. ha, bi 2 R, we consider the set of votes hm 1 (a), m 1 (B 0 )i, where m 1 (B 0 ) = {m 1 (b0 ) s.t. b0 62 B} Chosen a semantic s (i.e. chosen an argumentation function), the result of the election described by the composition m 1 s m as in Fig. 1 is a voting system. We will study which fairness criteria it satisfies. vs O⇥VP P(O) m m 1 s Args ⇥ R P(Args ) Fig. 1: The voting system vs = m 1 s m. Proposition 1. The composition vs = m 1 s m : O ⇥ V P ! P(O) is a voting system. Theorem 2. Given a semantic grounded s, by the composition m 1 s m we obtain a voting method without ties that satisfies the IIA and monotonicity. We can apply the mapping in Proposition 1 to the Example 1 of Section 2: 312 I. Benedetti et al. On Relating Voting Systems and Argumentation Frameworks B A C E D Fig. 2: The AF obtained from Example 1. Example 2 (The mapping from block voting Example 1). The block voting example is transformed in the AF as in Figure 2. The elected candidates (using the grounded semantic) are the set {A, D}. ⇤ 5 Conclusions and Future Works Our proposal uses negative judgements (as attacks) instead of positive ones (preferences). The computation of (indirect) positive judgement given by explicitly negative judgment have been already used in Germany in 2005 to elect the German Bundestag [9]. We proved that the voting system constructed using grounded semantics (such as conflict free, admissible, stable,...) satisfies many fairness cirteria but the majority criteria. Indeed there are several voting systems that do not satisfy this criterion, see [6]. Moreover we would like to consider the result of an election with a voting system how a specific semantics in AFs. Finally, the situations where Cands 6= Voters as well as special restrictions on the voting mechanism (a candidate can vote only one candidate, or at least herself, or preference based votes) will be subject of further research. References 1. Arrow, K.J.: A difficulty in the concept of social welfare. The Journal of Political Economy 58(4), 328–346 (Aug 1950) 2. Arrow, K.J.: Social Choice and Individual Values. John Wiley & Sons, Inc., New York, London, Sydney (1963) 3. Arrow, K., Sen, A., Suzumura, K.: Handbook of social choice and welfare. Elsevier, Amsterdam [u.a.], 1. ed. edn. (2002) 4. Baroni, P., Caminada, M., Giacomin, M.: An introduction to argumentation semantics. Knowl- edge Eng. Review 26(4), 365–410 (2011) 5. Dung, P.M.: On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games. Artif. Intell. 77(2), 321–357 (1995) 6. Galam, S.: Sociophysics: A Physicist’s Modeling of Psycho-Political Phenomena (Understanding Complex Systems). Springer-Verlag (2012) 7. Modgil, S.: Reasoning about preferences in argumentation frameworks. Artif. Intell. 173(9-10), 901–934 (2009) 8. Moulin, H.: Axioms of cooperative decision making, Econometric Society Monographs, vol. 15. Cambridge University Press, (1988) 9. Pukelsheim, F.: Electoral reform in germany: A positive twist to negative voting weights? In: Voting Power in Practice Summer Workshop, Assessing Alternative Voting Procedures (2010) 313