On Relating Voting Systems and Argumentation Frameworks

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.

Introduction

Argumentation framework

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 i no two arguments a and b in B exist such that a attacks b. A conflict-free set B ✓ Args is a stable extension i 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 ✓ 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:

Args (or B defends b) i for any

Definition 4. A conflict-free set B ✓

defended by B.

Args is admissible i each argument in

B is 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 i 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). ⇤ Dierent voting systems may give very dierent 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 election 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 representing 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).

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), – for each argument a, b 2 Args, and the set B = Sb2 Args b s.t. ha, bi 2 R, we consider the set of votes hm 1(a), m 1(B0)i, where m 1(B0) = {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.

O ⇥ V P

m Args ⇥ R vs s

P(O) m 1

P(Args)

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 diculty 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 . Knowledge 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 )