=Paper=
{{Paper
|id=Vol-1195/short1
|storemode=property
|title=On Relating Voting Systems and Argumentation Frameworks
|pdfUrl=https://ceur-ws.org/Vol-1195/short1.pdf
|volume=Vol-1195
|dblpUrl=https://dblp.org/rec/conf/cilc/BenedettiBP14
}}
==On Relating Voting Systems and Argumentation Frameworks==
https://ceur-ws.org/Vol-1195/short1.pdf
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