Vol-3194/paper54


Wolfgang Fahl

Paper

Paper
edit
description  
id  Vol-3194/paper54
wikidataid  Q117344893→Q117344893
title  Clustered Majority Judgement
pdfUrl  https://ceur-ws.org/Vol-3194/paper54.pdf
dblpUrl  https://dblp.org/rec/conf/sebd/AnniciellodFMMQ22
volume  Vol-3194→Vol-3194
session  →

Paper[edit]

Paper
edit
description  
id  Vol-3194/paper54
wikidataid  Q117344893→Q117344893
title  Clustered Majority Judgement
pdfUrl  https://ceur-ws.org/Vol-3194/paper54.pdf
dblpUrl  https://dblp.org/rec/conf/sebd/AnniciellodFMMQ22
volume  Vol-3194→Vol-3194
session  →

Clustered Majority Judgement[edit]

load PDF

Clustered Majority Judgement
    Arianna Anniciello1 , Emanuele d’Ajello1 , Davide Formica2 , Elio Masciari1 ,
    Gaia Mattia1 , Stefano Quintarelli2 and Davide Zaccarella1
1
  University of Napoli Federico II, Napoli, Italy
e.dajello@studenti.unina.it,ga.mattia@studenti.unina.it,elio.masciari@unina.it, d.zaccarella@studenti.unina.it
2
  Copernicani, Milano, Italy
frmdvd@gmail.com, stefano@quintarelli.it


                                         Abstract
                                         In order to overcome the classical methods of judgement, in the literature there is a lot of material about
                                         different methodology and their intrinsic limitations. One of the most relevant modern model to deal
                                         with votation system dynamics is the Majority Judgement.
                                         It was created with the aim of reducing polarization of the electorate in modern democracies and not to
                                         alienate minorities, thanks to its use of a highest median rule, producing more informative results than
                                         the existing alternatives. Nonetheless, as shown in the literature, in the case of multiwinner elections it
                                         can lead to scenarios in which minorities, albeit numerous, are not adequately represented.
                                         For this reason our aim is to implement a clustered version of this algorithm, in order to mitigate these
                                         disadvantages: it creates clusters taking into account the similarity between the expressed judgements
                                         and then for, each of these created groups, Majority Judgement rule is applied to return a ranking over
                                         the set of candidates. These traits make the algorithm available for applications in different areas of
                                         interest in which a decisional process is involved.

                                         Keywords
                                         Decision Making, Social Choice, Cluster, Majority Judgement.




1. Introduction
Voting rules are different and behave differently according to their limitations or sometimes
paradoxal traits. Asking for a more inclusive democracy also represents a modern citizens’
quest, but what does exactly it mean? First of all, we want to underline why a majority voting
system embodies the best option between the classical judgement methods.
Consider three agents who express their binary judgement ("Yes" or "No") for two statements A,
B, A ∧ B and A ←→ B. Premised-based rule take majority decisions on A and B and then infers
conclusions on the other two propositions.
As shown in the table 1, results are quite different based on the used rule.
We now focus on Agent 2 case: he’s represented in just one of the single proposition (A), and his
judgement doesn’t agree with the outcome, in the other cases. So, a huge liability of this model
could appear: Agent 2 could think about manipulating the outcome, pretending a disagreement
for A. The premised model reacts by providing as final outcome on 3 agents’ votation a "No" for
both A ∧ B and A ←→ B, as originally expressed by Agent 2.


SEBD 2022: The 30rd Italian Symposium on Advanced Database Systems
                                       © 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
    CEUR
    Workshop
    Proceedings
                  http://ceur-ws.org
                  ISSN 1613-0073
                                       CEUR Workshop Proceedings (CEUR-WS.org)
�                                           A     B     A∧B     A ←→ B
                         Agent 1           Yes   Yes    Yes       Yes
                         Agent 2           Yes   No     No        No
                         Agent 3           No    Yes    No        No
                         Premised rule     Yes   Yes    Yes       Yes
                         Majority          Yes   Yes    No        No
Table 1
Three agent case of voting


In such a way, a strategical approach on voting could lead to a deviation effect, providing as
result the best tricker’s choice.
Looking at the table, we can also highlight another paradoxal aspect: considering majority-based
outcome, the latest two propositions are inconsistent with "Yes" value assigned to both A and B.
This is known as discursive dilemma and deals with inconsistency problem in judgement
aggregation based on majority rule [1].
Both premised and majority rule present drawbacks, but the latter has one important feature: it
doesn’t suffer from deficiency shown by the first, so that, if an Agent care about the number of
propositions agreeing with his own judgement, then it is always in his best interest to report
his true preference. For this reason we focus our attention on majority rule as a transparent
asset in decisional process, while trying to deal with its intrinsic problems related to judgement
aggregation [2].
Our attempt is not aimed to solve above-mentioned dilemma, rather joining a more refined
majority rule (Majority Judgement) with cluster approach’s advantages in aggregating similar
patterns.


2. Majority Judgement
2.1. A brief overview of collective decision making
Many business magazines such as Harvard Business Review and Millionaire.it focus on business
meetings, highlighting how inefficiently these meetings are conducted. Business meetings are
often perceived as useless and unproductive for many reasons: scope meetings are quite vaguely
defined, a very large number of people are involved and there is no such figure as a mediator,
making decision processes increase in complexity and effort. [3] provides a guide on how to
plan and conduct a meeting in order to make it effective. In this work are defined different
kinds of meeting and the main techniques which can be used to meet each kind of meeting’s
specific target. Talking about business meetings and management, leadership is a key variable.
Tannenbaum and Schmidt [4] introduce model about leadership styles. The model’s parameters
take into account the leader’s main features, his subordinates’ features and the general context.
Hence one can easily tell a good leader needs to know and adopt different leadership styles
depending on different situations. The managerial grid proposed in [5] categorize leaders upon
how focused they are across a production-oriented (completing tasks) and a people-oriented
�(supporting individuals) dimension. In 1973 Vroom and Yetton [6] presented some leadership
styles that Vroom and Jabo revised later in 1988. Besides these descriptive decision theories,
which provide theoretical models, many group decision making techniques have been studied
to provide a means to choose between the alternatives proposed in a meeting. The most cited
decision making techniques in [7] are based on brainstorming and mind mapping processes
and focus on priority ranking techniques. The latter are based on voting techniques, such as
Nominal Group Technique, Paired Comparison Analysis and Grid Analysis. During board of
direction’s meetings, voting is often used to converge into a final decision.
   Social choice theory studies methods to consolidate the different views of many individuals
into a single outcome. The main applications of social choice theory are voting and jury
decisions[8]. During voting, electors in a democracy choose one candidate among a list of
many candidates, while in a jury decision the individual judges evaluate competitors in a
competition (e.g sport competition, wine competitions, etc.), ranking them. Social choice
theory’s fundamental problem is to find a social decision function that elaborates the preference
of judges or voters converging into a jury or electoral decisions while adhering to the main
principles of fair voting procedures such as non-dictatorship, universality, independence of
irrelevant alternative. Arrow’s impossibility theorem shows that the fundamental problem has
no acceptable solution in the traditional model [9]. In [10] Condorcet and Borda methods and
limits, Arrow’s impossibility theorem and Majority Judgement are illustrated.
   Majority Judgement (MJ) is a voting technique proposed by two mathematicians in 2007,
Michel Balinski and Rida Laraki, aiming to overcome traditional voting methods’ paradoxes
and inconsistencies. In [11], published in 2007, Balinski and Laraki briefly describe MJ, moving
from a social choice theory analysis which highlights traditional voting methods failures.
Hence the need for a voting method where voters evaluate candidates in terms of a common
language rather than simply ranking them. MJ makes it possible, since this method asks
for electors/judges to express a judgment on all the candidates/competitors, using a known
common language. Theorems and experiments confirm that, while there is no method which
can completely overcome strategic voting, majority judgment strongly resists manipulation.
Balinski and Laraki present MJ as a method both for evaluation and ranking of competitors,
candidates or alternatives. In [12] authors explain how electors don’t really make a personal
ranking of candidates, as traditional methods input assume, and that this is the reason behind
the inadequacy of traditional voting models. Forcing electors to rank candidates leads to
incoherence, impossibility and incompatibility. Balinski and Laraki [13] present the case of the
French presidential elections of 2002 and the results experiment related to the MJ conducted on
the occasion of the French presidential elections of 2007. Analyzing data from the 2002 election,
the authors describe the limits of the system First Pass the Post (FFP), which allows voters to
express just one preference. Voters are induced to strategic voting: voting the candidate who
is most likely to win against those deemed worst rather than voting the preferred candidate.
In the 2002 French presidential election, Jospin, the left’s leading candidate, was eliminated
in the first round, despite being one of the favorites according to polls. In the second round
Chirac of the moderate right beat Le Pen, representative of the far right. The vast majority of
Chirac’s votes were against Le Pen rather than him. They were, therefore, strategic votes. As a
result of the 2002 experience, in the 2007 elections the number of registered voters increased
sharply, from 41.2 million in 2002 to 44.5 million in 2007 and it was much discussed in the
�media whether there could have been strategic votes aimed at to avoid sensational defeats of
the favorite candidates in the first round. According to a poll conducted on the election day, 30%
of French voters voted strategically in 2007. The minor left candidates, in fact, obtained 27% in
2002 and 11% in 2007, the minor right 16%. in 2002 and 3% in 2002. This is a perfect example
of Arrow’s paradox: the winner depends on the presence or absence of candidates, including
those who have absolutely no chance of winning. Strategic nominations are also encouraged.

2.2. Formal aspects
To introduce social choice theory formally, consider a simple decision problem: a collective
choice between two alternatives. The first involves imposing some ‘procedural’ requirements
on the relationship between individual votes and social decisions and showing that majority
rule is the only aggregation rule satisfying them. May (1952) [14] [15] introduced four such
requirements for majority voting rule must satisfies:

    • Universal domain: the domain of admissible inputs of the aggregation rule consists of
      all logically possible profiles of votes < 𝑣1 , 𝑣2 , ..., 𝑣𝑛 >, where each 𝑣𝑖 ∈ [−1, 1] (to cope
      with any level of ‘pluralism’ in its inputs);
    • Anonimity: applying any kind of permutation on individual preferences does not affect
      the outcome (to treat all voters equally), i.e.,

                                   𝑓 (𝑣1 , 𝑣2 , ..., 𝑣𝑛 ) = 𝑓 (𝑤1 , 𝑤2 , ..., 𝑤𝑛 )                   (1)

    • Neutrality: each alternative has the same weight and for any admissible profile <
      𝑣1, 𝑣2, ..., 𝑣𝑛 >, if the votes for the two alternatives are reversed, the social decision is
      reversed too (to treat all alternatives equally), i.e.

                               𝑓 (−𝑣1 , −𝑣2 , ..., −𝑣𝑛 ) = −𝑓 (𝑣1 , 𝑣2 , ..., 𝑣𝑛 )                   (2)

    • Positive responsiveness: For any admissible profile < 𝑣1 , 𝑣2 , ..., 𝑣𝑛 >, if some voters
      change their votes in favour of one alternative (say the first) and all other votes remain
      the same, the social decision does not change in the opposite direction; if the social
      decision was a tie prior to the change, the tie is broken in the direction of the change,
      i.e., if [𝑤𝑖 > 𝑣𝑖 for some 𝑖 and 𝑤𝑗 = 𝑣𝑗 for all other 𝑗] and 𝑓 (𝑣1 , 𝑣2 , ..., 𝑣𝑛 ) = 0 or 1, then
      𝑓 (𝑤1 , 𝑤2 , ..., 𝑤𝑛 ) = 1.

The May theorem (Theorem: "An aggregation rule satisfies universal domain, anonymity, neutral-
ity, and positive responsiveness if and only if it is majority rule") provides an argument for the
majority rule based on four plausible procedural desires and the theorem helps us characterize
other aggregation rules in terms of which desiderata they violate.
But that’s with regards to binary choice. Now, we consider a set 𝑁 = [1, 2, ..., 𝑛] of individ-
uals (𝑛 ≥ 2). Let 𝑋 = [𝑥, 𝑦, 𝑧, ...] be a set of social alternatives, for example possible policy
platforms, election candidates, or other[16]. Each individual 𝑖 ∈ 𝑁 has a preference ordering
𝑅𝑖 over these alternatives that rapresents a complete and transitive binary relation on X. For
any 𝑥, 𝑦 ∈ 𝑋, 𝑥𝑅𝑖 𝑦 means that individual 𝑖 weakly prefers 𝑥 to 𝑦. We write 𝑥𝑃𝑖 𝑦 if 𝑥𝑅𝑖 𝑦
and not 𝑦𝑅𝑖 𝑥 (‘individual 𝑖 strictly prefers 𝑥 to 𝑦’), and 𝑥𝐼𝑖 𝑦 if 𝑥𝑅𝑖 𝑦 and 𝑦𝑅𝑖 𝑥 (‘individual 𝑖 is
�indifferent between 𝑥 and 𝑦’). But we must specify that at the heart of social choice theory is
the analysis of preference aggregation, understood as the aggregation of several individuals’
preference rankings of two or more social alternatives into a single, collective preference rank-
ing (or choice) over these alternatives [17]. In case of many successful alternatives, we need a
more sophisticated model to deal with preferences’ aggregation [18]. A multi-winner election
(V,C,F,k) is defined by a set of voters V expressing preferences over a number of candidates
C, and then a voting rule F returns a subset of size k winning candidates. A voting rule can
perform its role on different types of ordered preferences, even though the most common refers
to a pre-fixed linear order on the alternatives. In most of cases, these are chosen a priori.
Formally we denote set of judgements performed by the i-th voter as profile preferences P𝑖 .
Each profile contains information about the grade of candidates by voters. The voting rule F
associates with every profile P a non-empty subset of winning candidates.
In multi-winner elections more precise traits are required, compared to the ones stated in May’s
theory [19]. Indeed:

    • Representation: for each partition of voters
                                                              ⌊︁ 𝑛 ⌋︁)︁
                                       𝑉𝑖 ∈ 𝑉 (with |𝑉𝑖 | ≥                                       (3)
                                                                𝑘
      at least one successful candidate is elected from that partition;
    • Proportionality: for each partition of voters
                                                           ⌊︁ 𝑛 ⌋︁)︁
                                     𝑉𝑖 ∈ 𝑉 (with |𝑉𝑖 | ≥                                         (4)
                                                              𝑘
      number of elected candidate is proportional to the partition’s size.

   An implicit assumption so far has been that preferences are ordinal and not interpersonally
comparable: preference orderings contain no information about each individual’s strength or
about how to compare different individuals’ preferences with one another [20]. Statements such
as ‘Individual 1 prefers alternative x more than Individual 2 prefers alternative y’ or ‘Individual l
prefers a switch from x to y more than Individual 2 prefers a switch from x* to y*’ are considered
meaningless. In voting contexts, this assumption may be plausible, but in welfare-evaluation
contexts—when a social planner seeks to rank different social alternatives in an order of social
welfare—the use of richer information may be justified.


2.3. Single-winner Majority judgement
In order to describe the majority judgement, we need to use a table that refers to ranking for all
the candidates 𝐶, by using tuples [21]. Suppose having six possible choices we may use the
words: excellent, very good, good, discrete, bad, very bad.
So each candidate is described by a bounded set of vote.
In general, letting 𝛼 = (𝛼1 , 𝛼2 , ..., 𝛼𝑛 ) be a candidate A’s set of n grades (written from highest
to lowest, 𝛼𝑖 ≥ 𝛼𝑖+1 for all 𝑖), there is a majority of (at least) 𝑛 − 𝑘 + 1 for n A’s grade to beat
most 𝛼𝑘 and at least 𝛼𝑛−𝑘+1 , for all 1 ≤ 𝑘 ≤ (𝑛+1)  2 . We call this the (n-k+1) - majority for [𝛼𝑘 ,
�𝛼𝑛−𝑘+1 ].
As already mentioned any possible ranking tuple that we choose to describe must follow ordering
relations.
So the ranking should respect domination: namely, evaluate one candidate above another when
that candidate’s grades dominate the other’s.
The described majority judgement is a single winner system, found comparing recursively
median grade between candidates: first, grades are ordered in columns from the highest to
the lowest according to the order relation, then the middle column (lower middle if number
of grades are even) with the highest grade between candidates’row is selected [22]. If there’s
a tie, algorithm keeps on discarding grades equal in value to the shared median, until one of
the tied candidate is found to have the highest median. Before describing how it’s possible to




Figure 1: Example with 5 grades, between the dashed lines it’s reported the median grade. Highest
occurrences in "Good" determines the winner.

generalize this single winner system to a multi winner strategy, thanks to the use of clusters
[23], we focus our attention on how these works, analyzing in particular K-medoids.


3. Clustering approach
3.1. How clusters work
There’s no precise definition of clustering, mostly due to the huge variety in different clustering
algorithms. We can state that they share the ability to divide data into groups with some
common features. According to some general traits, we can distinguish types of clustering:
1. Connectivity models: data points in a sample space exhibits similarity according to the
distance between them. Two approaches are equally valid: bottom-up where each observation
constitutes a group and then pairs of clusters are merged; top-down, where observation are
included in one cluster and then it’s segregated; but in both approaches is not included the
possibility of modifying a cluster once created;
2. Distribution models: once created a cluster, model check probabilities on observations
following a particular distribution. Good performances are not always guaranteed since these
models are prone to overfit data if no constraint on complexity is made;
3. Density models: areas of higher density are identified and local cluster are there created,
while remaining data can be grouped into arbitrary shaped region, with no assumption about
da ta distribution; for their flexibility, these models are fit to handle noise better than organizing
data on fixed required body.
Since we would like to model clusters that satisfy requirements expressed before, based on
pretty fixed structure with no assumption about distribution followed by data, it seems more
accurate considering a different class of clustering algorithm known as centroid models.
�3.2. K-Medoids
Clustering is the process of grouping a set of objects in order to have each similar object to each
other in one cluster, that are dissimilar to objects in other clusters.
For our goal, namely selecting winners from a group of candidates, K-medoids clustering are
used, because medoids are the representative objects that are considered, in order to have a
result that belongs to the group of candidates [24]: it is based on the most centrally located
object in a cluster, so it is less sensitive to outliers in comparison with the K-means clustering,
which is not the best model in our case since it could result in something that is not present in
the candidate list due to the fact that is an average-based method rather than median. In fact,
the medoid is a data point (unlike the centroid) which has the least total distance to the other
members of its cluster.
Another advantage for this choice is that the mean of the data points is a measure that gets
highly affected by the extreme points; so, in K-Means algorithm, the centroid may get shifted to
a wrong position and hence result in incorrect clustering if the data has outliers because then
other points will move away from. On the contrary, the K-Medoids algorithm is the most central
element of the cluster, such that its distance from other points is minimum. Thus, K-Medoids
algorithm is more robust to outliers and noise than K-Means algorithm.
The K-medoid we use is part of the python sklearn library [25], which is oriented to machine
learning. This library supports partitioning around medoids (PAM) [26] proposed by Kaufman
and Rousseeuw (1990), that is known to be most powerful. The workflow of PAM is described
below [27].
The PAM procedure consists of two phases: BUILD and SWAP:

    • In the BUILD phase, primary clustering is performed, during which k objects are succes-
      sively selected as medoids.
    • The SWAP phase is an iterative process in which the algorithm makes attempts to improve
      some of the medoids. At each iteration of the algorithm, a pair is selected (medoid and
      non-medoid) such that replacing the medoid with a non-medoid object gives the best
      value of the objective function (the sum of the distances from each object to the nearest
      medoid). The procedure for changing the set of medoids is repeated as long as there is a
      possibility of improving the value of the objective function.

Suppose that 𝑛 objects having 𝑝 variables each should be grouped into 𝑘 (𝑘 < 𝑛) clusters,
where 𝑘 is known. Let us define j-th variable of object 𝑖 as 𝑋𝑖𝑗 (𝑖 = 1, ..., 𝑛; 𝑗 = 1, ..., 𝑝). As a
dissimilarity measure is used the Euclidean distance, that is defined, between object 𝑖 and object
𝑗, by:                                   ⎯
                                         ⎸ 𝑝
                                         ⎸∑︁
                                   𝑑𝑖𝑗 = ⎷ (𝑋𝑖𝑎 − 𝑋𝑗𝑎 )2                                          (5)
                                             𝑎=1

where 𝑖 and 𝑗 range from 1 to 𝑛. The medoids is selected in this way:

    • calculate the Euclidean distance between every pair of all objects;
                              𝑑
    • calculate 𝑣𝑗 = 𝑛𝑖=1 ∑︀𝑛 𝑖𝑗 𝑑𝑖𝑙 ;
                     ∑︀
                               𝑙=1
�    • sort all 𝑣𝑗 for 𝑗 = 1, ..., 𝑛 in ascending order and select the first 𝑘 object that have smallest
      initial medoids value;
    • from each object to the nearest medoid we can obtain the initial cluster result;
    • calculate the sum of distances from all objects to their medoids;
    • update the current medoid in each cluster by replacing with the new medoid, selected
      minimizing the total distance from a certain object to other objects in its cluster;
    • assign each object to the nearest medoid and obtain the cluster result;
    • calculate the sum of distance from all objects to their medoids, so if the sum is equal to
      the previous one, then stop the algorithm; otherwise, go back to the update step.
In our case, prior knowledge about the number of winners is required, and identified clusters
are restricted in minimum size that is number of voters on the number of candidates ( 𝑛𝑘 ).


3.3. Clustered Majority Judgement
Multi winner majority judgement exploits clustering approach to apply to each group majority
judgement [28]. Given k the number of candidates to be elected, algorithm seeks the optimal
number of cluster to create.
This ranges from 1 to k and has to satisfy an important additional requirement: once selected a
number of clusters, if a tie occurs and so k’ vacant seats are left, algorithm is repeated k’ times
until tie’s broken. In case there’s no broken tie, fixed number of cluster is changed.


3.4. Algorithm
In order to explain how the algorithm deals with polarization problem, most relevant steps are
described in pseudocode and in annotated strides:

   1. set the number of winners as maximum number of clusters;
   2. cluster are created decreasing the previous maximum number of clusters until the optimal
      number is not achieved. This number is bound by the size of cluster, that satisfies the
      following proportion: number of voters : number of winners = number of voters in one
      cluster : one winner (line 8 in pseudocode);
   3. the function winners calculates the median for every created cluster (line 15 of pseu-
      docode);
   4. check that winners from cluster are different between each other (line 29 in pseudocode);
      in case it’s not true (condition="ko" on pseudocode) algorithm goes back to step 2 with a
      maximum number of cluster equal to number of vacant seats and the proceedings are
      held until all seats have been filled.


3.5. Case Studies
In this section, we describe two interesting comparisons of majority judgement (MJ) and
clustered majority judgement (CMJ).
�Algorithm 1
Require: 𝑘 ≥ 0
Ensure: 𝑛_𝑤𝑖𝑛𝑛𝑒𝑟𝑠 = (𝑛1 , ..., 𝑛𝑘 ), 𝑘 > 1
  𝑘 ← 𝑛𝑢𝑚𝑏𝑒𝑟_𝑤𝑖𝑛𝑛𝑒𝑟𝑠
  𝑚𝑎𝑥_𝑐𝑙𝑢𝑠𝑡𝑒𝑟 ← 𝑘
  𝑐𝑜𝑛𝑑𝑖𝑡𝑖𝑜𝑛 ← ”𝑘𝑜”
  while 𝑐𝑜𝑛𝑑𝑖𝑡𝑖𝑜𝑛 = ”𝑘𝑜” do
     𝑐𝑙𝑢𝑠𝑡𝑒𝑟_𝑙𝑖𝑠𝑡 ← 𝑐𝑙𝑢𝑠𝑡𝑒𝑟(𝑣𝑜𝑡𝑒_𝑙𝑖𝑠𝑡)
     for all list_cluster do
         𝑤𝑖𝑛𝑛𝑒𝑟𝑠_𝑝𝑒𝑟_𝑐𝑙𝑢𝑠𝑡𝑒𝑟 ← 𝑐𝑜𝑚𝑝𝑢𝑡𝑒_𝑤𝑖𝑛𝑛𝑒𝑟𝑠(𝑐𝑙𝑢𝑠𝑡𝑒𝑟)
         𝑎𝑙𝑙_𝑤𝑖𝑛𝑛𝑒𝑟𝑠 ← 𝑙𝑖𝑠𝑡_𝑜𝑓 _𝑎𝑙𝑙_𝑤𝑖𝑛𝑛𝑒𝑟𝑠(𝑤𝑖𝑛𝑛𝑒𝑟𝑠_𝑝𝑒𝑟_𝑐𝑙𝑢𝑠𝑡𝑒𝑟)
     end for
     𝑙𝑖𝑠𝑡_𝑤𝑖𝑛𝑛𝑒𝑟_𝑑𝑖𝑠𝑡𝑖𝑛𝑐𝑡 = 𝑙𝑖𝑠𝑡_𝑜𝑓 _𝑎𝑙𝑙_𝑑𝑖𝑠𝑡𝑖𝑛𝑐𝑡_𝑤𝑖𝑛𝑛𝑒𝑟𝑠(𝑎𝑙𝑙_𝑤𝑖𝑛𝑛𝑒𝑟𝑠)
     𝑜𝑝𝑡𝑖𝑜𝑛_𝑟𝑒𝑚𝑎𝑖𝑛𝑖𝑛𝑔 ← 𝑛𝑢𝑚𝑏𝑒𝑟_𝑤𝑖𝑛𝑛𝑒𝑟𝑠 − 𝑙𝑒𝑛(𝑙𝑖𝑠𝑡_𝑤𝑖𝑛𝑛𝑒𝑟_𝑑𝑖𝑠𝑡𝑖𝑛𝑐𝑡)
     if 𝑜𝑝𝑡𝑖𝑜𝑛_𝑟𝑒𝑚𝑎𝑖𝑛𝑖𝑛𝑔 = 0 then
         𝑐𝑜𝑛𝑑𝑖𝑡𝑖𝑜𝑛 =′ 𝑜𝑘 ′
     else
         𝑘 ← 𝑜𝑝𝑡𝑖𝑜𝑛_𝑟𝑒𝑚𝑎𝑖𝑛𝑖𝑛𝑔
         𝑐𝑜𝑛𝑑𝑖𝑡𝑖𝑜𝑛 ←′ 𝑘𝑜′
     end if
  end while


3.5.1. Case study 1: President of the Republic election
In order to test our algorithm, we asked an heterogeneous group of voters to express judgements
on a pre-defined list of possible candidates as President of the Republic before the elections took
place. This list has been created according to the rumours circulated on that period, creating a
bias effect on our results, as it was excluded a possible rielection of Sergio Mattarella.
In spite of it, we focus on how the algorithm has worked in order to balance polarization,
returning a subset of winners with size chosen a priori, that we may interpret as best solutions
for majority of people who took part into the venture.
Input parameters of Clustered Majority Judgement test are Excellent, Very Good, Good, Accept-
able, Poor, To Reject, No Opinion and the number of winners is set a priori equal to 3. 125 voters
took part into this election and the algorithm form three clusters, exactly like the number of
winners.
Testing our algorithm on the described election has shown how difference preference has a
leverage on judgement aggregation: for example, voters in Cluster 1 are more bound to express
"Good" judgement for candidates considered neutral in terms of political ideas, than the cluster
3 in which voters have a tendency in judging neutral ones as "Fair" or "Poor". Cluster 2 has
intermediate traits and no particular tendency is emphasized. We can compare CMJ results
with single-winner MJ ranking, comparing the Table 2 and Table 3. The comparison shows
different results for the third candidate, highlighting how clustering influences outcome, giving
more weight to minorities’ judgement.
�                            Cluster    Cluster size       Winner
                           Cluster 1       65           Mario Draghi
                           Cluster 2       35          Paolo Gentiloni
                           Cluster 3       25         Anna Finocchiaro
Table 2
CMJ results

                                  Ranking MJ       Candidate
                                      1           Mario Draghi
                                      2          Paolo Gentiloni
                                      3           Emma Bonino
Table 3
Top 3 of single-winner Majority Judgement applied to voters




3.6. Case Study 2: Working hours per week
The last case study is a good paradigm for deciding how to manage working hours in the office,
given a fixed number of working hours to be done (18 hours). In this case, we asked 160 students
of University Federico II of Naples to choose the best combination of working hours, in presence
(P) or with online lectures (O). We used again the grades Excellent, Very Good, Good, Acceptable,
Poor, To Reject, No Opinion and the five options are:
   1. 6 hours (P) - 6 hours (O) - 6 hours (P or O)
   2. 10 hours (P) - 4 hours (O) - 4 hours (P or O)
   3. 8 hours (P) - 6 hours (O) - 4 hours (P or O)
   4. 7 hours (P) - 9 hours (O) - 2 hours (P or O)
   5. 5 hours (P) - 5 hours (O) - 8 hours (P or O)
The results of MJ method, with the traditional compute of medians takes back as winner the
option 4 (7 hours (P) - 9 hours (O) - 2 hours (P or O)) that has the highest number of "Good"
votes.
Instead the compute of winner with CMJ method takes back a different situation: we fixed 2 as
number of winners (and number of clusters) and the first one is the option 3 (8 hours (P) - 6
hours (O) - 4 hours (P or O)) and the second one is the option 4, the same winner of MJ method.
As we can see, probably because the number of voters is quite high, the results are not the same
like in case study 2. With CMJ, we take into account the wide spectrum of preferences, with
special regards for the most polarising ones, which are the most influent in creating different
clusters.
Especially for this reason, we may prefer CMJ to MJ for this case-study’s lookalike situations,
where a shared solution should be taken, considering the different impact it can have on the
heterogenous groups (clusters) the judgement is made by.
�Conclusions
In section 1, we dealt with logical issues involved in voting rules and judgement aggregation,
highlighting majority rule’s resistance to strategical vote.
In section 2, a more fined model of majority rule, Majority Judgement, has been presented as an
option to better estimate the most shared candidate.
In section 3, the related works have been shown and in section 4, all possible categories of
clustering approach has been reported in order to choose the fittest one for our generalization
of Majority Judgement as a multi-winner strategy. After that, three different case studies are
reported, with a particular attention to the comparison between MJ and CMJ results.
In spite of non-deterministic nature of K-Medoids, Clustered Majority Judgement is thought to
be used in high populated disputes. For these reasons, we feel confident about clustering’s role
of taking into account all different perspectives could be shown in such situation.
Moreover, our implementation is not strictly linked to political field, as is clearly shown in
the case studies (except the first one), mostly because it requires only some fixed parameters:
number of winners, number of grades and grades themselves.
An important future challenge could be speeding up the algorithm or making a more flexible
structure, even though all the constraints already explained in previous sections need to be
satisfied.



References
 [1] A. S. G. Bellec, F. Scherr, A solution to the learning dilemma for recurrent networks of
     spiking neurons, in: Nat Commun, 2020.
 [2] J. Kleinberg, An impossibility theorem for clustering, in: Cornell University, 2002.
 [3] B. J. Streibel, The manager’s guide to effective meetings / barbara j. streibel., in: The
     manager’s guide to effective meetings, McGraw-Hill, 2003.
 [4] R. S. Tannenbaum, W. H. Schmidt, How to choose a leadership pattern, 2009.
 [5] R. R. Blake, J. S. Mouton, L. B. Barnes, L. E. Greiner, Breakthrough in organization
     development, Graduate School of Business Administration, Harvard University, 1964.
 [6] V. H. Vroom, P. W. Yetton, Leadership and decision-making, University of Pittsburgh Pre,
     1973.
 [7] E. Verzuh, A. P. Association, et al., A guide to the project management body of knowledge:
     Pmbok guide, Project Management Institute, Inc., 2021.
 [8] F. Brandt, V. Conitzer, U. Endriss, J. Lang, A. D. Procaccia, Handbook of computational
     social choice, Cambridge University Press, 2016.
 [9] K. J. Arrow, Social choice and individual values, Yale university press, 2012.
[10] P. Serafini, La matematica in soccorso della democrazia: Cosa significa votare e come si
     può migliorare il voto, Independently Published, 2019.
[11] M. Balinski, R. Laraki, A theory of measuring, electing, and ranking, National Acad
     Sciences, 2007.
[12] M. Balinski, R. Laraki, Judge: Don’t vote!, volume 62, INFORMS, 2014, pp. 483–511.
�[13] M. Balinski, R. Laraki, Election by majority judgment: experimental evidence, in: In Situ
     and Laboratory Experiments on Electoral Law Reform, Springer, 2011.
[14] K. O. May, A set of indipendent necessary and sufficient conditions for simple majority
     decision, in: Carleton College, 1952.
[15] B. Fazzinga, S. Flesca, F. Furfaro, E. Masciari, Rfid data compression for supporting
     aggregate queries (????).
[16] C. List, Social choice theory, in: The Stanford Encyclopedia of Philosophy, Metaphysics
     Research Lab, Stanford University, 2022.
[17] J. C. Garcia-Bermejo, A plea for the majority method in aggregating judgements, in:
     Oxford Journal, 2011.
[18] M. P. Klaus Nehring a, Incoherent majorities: The mcgarvey problem in judgement
     aggregation, in: Science Direct, Elsevier, 2011.
[19] A. Fabre, Tie-breaking the highest median: Alternatives to the majority judgment, in:
     Paris School of Economics, 2018.
[20] M. Ceci, R. Corizzo, F. Fumarola, M. Ianni, D. Malerba, G. Maria, E. Masciari,
     M. Oliverio, A. Rashkovska, Big data techniques for supporting accurate predic-
     tions of energy production from renewable sources, volume 0, 2015, p. 62 – 71.
     URL:        https://www.scopus.com/inward/record.uri?eid=2-s2.0-85007505126&doi=10.
     1145%2f2790755.2790762&partnerID=40&md5=612b2eb0409a5c8dd065f9213971ec6f.
     doi:10.1145/2790755.2790762, cited by: 15.
[21] M. Balinski, Fair majority voting (or how to eliminate gerrymandering, in: The American
     Mathematical Monthly, Vol. 115, No. 2, Mathematical Association of America, 2006.
[22] L. Caroprese, E. Zumpano, A logic framework for P2P deductive databases, Theory
     Pract. Log. Program. 20 (2020) 1–43. URL: https://doi.org/10.1017/S1471068419000073.
     doi:10.1017/S1471068419000073.
[23] L. Caroprese, E. Zumpano, Aggregates and priorities in P2P data management systems,
     in: 15th International Database Engineering and Applications Symposium (IDEAS 2011),
     September 21 - 27, 2011, Lisbon, Portugal, ACM, 2011, pp. 1–7. URL: https://doi.org/10.
     1145/2076623.2076625. doi:10.1145/2076623.2076625.
[24] L. Caroprese, E. Zumpano, Declarative semantics for P2P data management system, J.
     Data Semant. 9 (2020) 101–122. URL: https://doi.org/10.1007/s13740-020-00115-6. doi:10.
     1007/s13740-020-00115-6.
[25] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel,
     P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher,
     M. Perrot, E. Duchesnay, Scikit-learn: Machine learning in Python, in: Journal of Machine
     Learning Research, 2011.
[26] P. J. R. Leonard Kaufman, Partitioning around medoids, in: Finding Groups in Data: An
     Introduction to Cluster Analysis, John Wiley & Sons, 2015.
[27] C.-H. J. Hae-Sang Park, A simple and fast algorithm for k-medoids clustering, in: POSTECH,
     Elsevier, 2008.
[28] S. Q. Andrea Loreggia, Nicholas Mattei, Artificial intelligence research for fighting, in:
     Political Polarisation: A Research Agenda, 2020.
�

Clustered Majority Judgement[edit]

load PDF

Clustered Majority Judgement
    Arianna Anniciello1 , Emanuele d’Ajello1 , Davide Formica2 , Elio Masciari1 ,
    Gaia Mattia1 , Stefano Quintarelli2 and Davide Zaccarella1
1
  University of Napoli Federico II, Napoli, Italy
e.dajello@studenti.unina.it,ga.mattia@studenti.unina.it,elio.masciari@unina.it, d.zaccarella@studenti.unina.it
2
  Copernicani, Milano, Italy
frmdvd@gmail.com, stefano@quintarelli.it


                                         Abstract
                                         In order to overcome the classical methods of judgement, in the literature there is a lot of material about
                                         different methodology and their intrinsic limitations. One of the most relevant modern model to deal
                                         with votation system dynamics is the Majority Judgement.
                                         It was created with the aim of reducing polarization of the electorate in modern democracies and not to
                                         alienate minorities, thanks to its use of a highest median rule, producing more informative results than
                                         the existing alternatives. Nonetheless, as shown in the literature, in the case of multiwinner elections it
                                         can lead to scenarios in which minorities, albeit numerous, are not adequately represented.
                                         For this reason our aim is to implement a clustered version of this algorithm, in order to mitigate these
                                         disadvantages: it creates clusters taking into account the similarity between the expressed judgements
                                         and then for, each of these created groups, Majority Judgement rule is applied to return a ranking over
                                         the set of candidates. These traits make the algorithm available for applications in different areas of
                                         interest in which a decisional process is involved.

                                         Keywords
                                         Decision Making, Social Choice, Cluster, Majority Judgement.




1. Introduction
Voting rules are different and behave differently according to their limitations or sometimes
paradoxal traits. Asking for a more inclusive democracy also represents a modern citizens’
quest, but what does exactly it mean? First of all, we want to underline why a majority voting
system embodies the best option between the classical judgement methods.
Consider three agents who express their binary judgement ("Yes" or "No") for two statements A,
B, A ∧ B and A ←→ B. Premised-based rule take majority decisions on A and B and then infers
conclusions on the other two propositions.
As shown in the table 1, results are quite different based on the used rule.
We now focus on Agent 2 case: he’s represented in just one of the single proposition (A), and his
judgement doesn’t agree with the outcome, in the other cases. So, a huge liability of this model
could appear: Agent 2 could think about manipulating the outcome, pretending a disagreement
for A. The premised model reacts by providing as final outcome on 3 agents’ votation a "No" for
both A ∧ B and A ←→ B, as originally expressed by Agent 2.


SEBD 2022: The 30rd Italian Symposium on Advanced Database Systems
                                       © 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
    CEUR
    Workshop
    Proceedings
                  http://ceur-ws.org
                  ISSN 1613-0073
                                       CEUR Workshop Proceedings (CEUR-WS.org)
�                                           A     B     A∧B     A ←→ B
                         Agent 1           Yes   Yes    Yes       Yes
                         Agent 2           Yes   No     No        No
                         Agent 3           No    Yes    No        No
                         Premised rule     Yes   Yes    Yes       Yes
                         Majority          Yes   Yes    No        No
Table 1
Three agent case of voting


In such a way, a strategical approach on voting could lead to a deviation effect, providing as
result the best tricker’s choice.
Looking at the table, we can also highlight another paradoxal aspect: considering majority-based
outcome, the latest two propositions are inconsistent with "Yes" value assigned to both A and B.
This is known as discursive dilemma and deals with inconsistency problem in judgement
aggregation based on majority rule [1].
Both premised and majority rule present drawbacks, but the latter has one important feature: it
doesn’t suffer from deficiency shown by the first, so that, if an Agent care about the number of
propositions agreeing with his own judgement, then it is always in his best interest to report
his true preference. For this reason we focus our attention on majority rule as a transparent
asset in decisional process, while trying to deal with its intrinsic problems related to judgement
aggregation [2].
Our attempt is not aimed to solve above-mentioned dilemma, rather joining a more refined
majority rule (Majority Judgement) with cluster approach’s advantages in aggregating similar
patterns.


2. Majority Judgement
2.1. A brief overview of collective decision making
Many business magazines such as Harvard Business Review and Millionaire.it focus on business
meetings, highlighting how inefficiently these meetings are conducted. Business meetings are
often perceived as useless and unproductive for many reasons: scope meetings are quite vaguely
defined, a very large number of people are involved and there is no such figure as a mediator,
making decision processes increase in complexity and effort. [3] provides a guide on how to
plan and conduct a meeting in order to make it effective. In this work are defined different
kinds of meeting and the main techniques which can be used to meet each kind of meeting’s
specific target. Talking about business meetings and management, leadership is a key variable.
Tannenbaum and Schmidt [4] introduce model about leadership styles. The model’s parameters
take into account the leader’s main features, his subordinates’ features and the general context.
Hence one can easily tell a good leader needs to know and adopt different leadership styles
depending on different situations. The managerial grid proposed in [5] categorize leaders upon
how focused they are across a production-oriented (completing tasks) and a people-oriented
�(supporting individuals) dimension. In 1973 Vroom and Yetton [6] presented some leadership
styles that Vroom and Jabo revised later in 1988. Besides these descriptive decision theories,
which provide theoretical models, many group decision making techniques have been studied
to provide a means to choose between the alternatives proposed in a meeting. The most cited
decision making techniques in [7] are based on brainstorming and mind mapping processes
and focus on priority ranking techniques. The latter are based on voting techniques, such as
Nominal Group Technique, Paired Comparison Analysis and Grid Analysis. During board of
direction’s meetings, voting is often used to converge into a final decision.
   Social choice theory studies methods to consolidate the different views of many individuals
into a single outcome. The main applications of social choice theory are voting and jury
decisions[8]. During voting, electors in a democracy choose one candidate among a list of
many candidates, while in a jury decision the individual judges evaluate competitors in a
competition (e.g sport competition, wine competitions, etc.), ranking them. Social choice
theory’s fundamental problem is to find a social decision function that elaborates the preference
of judges or voters converging into a jury or electoral decisions while adhering to the main
principles of fair voting procedures such as non-dictatorship, universality, independence of
irrelevant alternative. Arrow’s impossibility theorem shows that the fundamental problem has
no acceptable solution in the traditional model [9]. In [10] Condorcet and Borda methods and
limits, Arrow’s impossibility theorem and Majority Judgement are illustrated.
   Majority Judgement (MJ) is a voting technique proposed by two mathematicians in 2007,
Michel Balinski and Rida Laraki, aiming to overcome traditional voting methods’ paradoxes
and inconsistencies. In [11], published in 2007, Balinski and Laraki briefly describe MJ, moving
from a social choice theory analysis which highlights traditional voting methods failures.
Hence the need for a voting method where voters evaluate candidates in terms of a common
language rather than simply ranking them. MJ makes it possible, since this method asks
for electors/judges to express a judgment on all the candidates/competitors, using a known
common language. Theorems and experiments confirm that, while there is no method which
can completely overcome strategic voting, majority judgment strongly resists manipulation.
Balinski and Laraki present MJ as a method both for evaluation and ranking of competitors,
candidates or alternatives. In [12] authors explain how electors don’t really make a personal
ranking of candidates, as traditional methods input assume, and that this is the reason behind
the inadequacy of traditional voting models. Forcing electors to rank candidates leads to
incoherence, impossibility and incompatibility. Balinski and Laraki [13] present the case of the
French presidential elections of 2002 and the results experiment related to the MJ conducted on
the occasion of the French presidential elections of 2007. Analyzing data from the 2002 election,
the authors describe the limits of the system First Pass the Post (FFP), which allows voters to
express just one preference. Voters are induced to strategic voting: voting the candidate who
is most likely to win against those deemed worst rather than voting the preferred candidate.
In the 2002 French presidential election, Jospin, the left’s leading candidate, was eliminated
in the first round, despite being one of the favorites according to polls. In the second round
Chirac of the moderate right beat Le Pen, representative of the far right. The vast majority of
Chirac’s votes were against Le Pen rather than him. They were, therefore, strategic votes. As a
result of the 2002 experience, in the 2007 elections the number of registered voters increased
sharply, from 41.2 million in 2002 to 44.5 million in 2007 and it was much discussed in the
�media whether there could have been strategic votes aimed at to avoid sensational defeats of
the favorite candidates in the first round. According to a poll conducted on the election day, 30%
of French voters voted strategically in 2007. The minor left candidates, in fact, obtained 27% in
2002 and 11% in 2007, the minor right 16%. in 2002 and 3% in 2002. This is a perfect example
of Arrow’s paradox: the winner depends on the presence or absence of candidates, including
those who have absolutely no chance of winning. Strategic nominations are also encouraged.

2.2. Formal aspects
To introduce social choice theory formally, consider a simple decision problem: a collective
choice between two alternatives. The first involves imposing some ‘procedural’ requirements
on the relationship between individual votes and social decisions and showing that majority
rule is the only aggregation rule satisfying them. May (1952) [14] [15] introduced four such
requirements for majority voting rule must satisfies:

    • Universal domain: the domain of admissible inputs of the aggregation rule consists of
      all logically possible profiles of votes < 𝑣1 , 𝑣2 , ..., 𝑣𝑛 >, where each 𝑣𝑖 ∈ [−1, 1] (to cope
      with any level of ‘pluralism’ in its inputs);
    • Anonimity: applying any kind of permutation on individual preferences does not affect
      the outcome (to treat all voters equally), i.e.,

                                   𝑓 (𝑣1 , 𝑣2 , ..., 𝑣𝑛 ) = 𝑓 (𝑤1 , 𝑤2 , ..., 𝑤𝑛 )                   (1)

    • Neutrality: each alternative has the same weight and for any admissible profile <
      𝑣1, 𝑣2, ..., 𝑣𝑛 >, if the votes for the two alternatives are reversed, the social decision is
      reversed too (to treat all alternatives equally), i.e.

                               𝑓 (−𝑣1 , −𝑣2 , ..., −𝑣𝑛 ) = −𝑓 (𝑣1 , 𝑣2 , ..., 𝑣𝑛 )                   (2)

    • Positive responsiveness: For any admissible profile < 𝑣1 , 𝑣2 , ..., 𝑣𝑛 >, if some voters
      change their votes in favour of one alternative (say the first) and all other votes remain
      the same, the social decision does not change in the opposite direction; if the social
      decision was a tie prior to the change, the tie is broken in the direction of the change,
      i.e., if [𝑤𝑖 > 𝑣𝑖 for some 𝑖 and 𝑤𝑗 = 𝑣𝑗 for all other 𝑗] and 𝑓 (𝑣1 , 𝑣2 , ..., 𝑣𝑛 ) = 0 or 1, then
      𝑓 (𝑤1 , 𝑤2 , ..., 𝑤𝑛 ) = 1.

The May theorem (Theorem: "An aggregation rule satisfies universal domain, anonymity, neutral-
ity, and positive responsiveness if and only if it is majority rule") provides an argument for the
majority rule based on four plausible procedural desires and the theorem helps us characterize
other aggregation rules in terms of which desiderata they violate.
But that’s with regards to binary choice. Now, we consider a set 𝑁 = [1, 2, ..., 𝑛] of individ-
uals (𝑛 ≥ 2). Let 𝑋 = [𝑥, 𝑦, 𝑧, ...] be a set of social alternatives, for example possible policy
platforms, election candidates, or other[16]. Each individual 𝑖 ∈ 𝑁 has a preference ordering
𝑅𝑖 over these alternatives that rapresents a complete and transitive binary relation on X. For
any 𝑥, 𝑦 ∈ 𝑋, 𝑥𝑅𝑖 𝑦 means that individual 𝑖 weakly prefers 𝑥 to 𝑦. We write 𝑥𝑃𝑖 𝑦 if 𝑥𝑅𝑖 𝑦
and not 𝑦𝑅𝑖 𝑥 (‘individual 𝑖 strictly prefers 𝑥 to 𝑦’), and 𝑥𝐼𝑖 𝑦 if 𝑥𝑅𝑖 𝑦 and 𝑦𝑅𝑖 𝑥 (‘individual 𝑖 is
�indifferent between 𝑥 and 𝑦’). But we must specify that at the heart of social choice theory is
the analysis of preference aggregation, understood as the aggregation of several individuals’
preference rankings of two or more social alternatives into a single, collective preference rank-
ing (or choice) over these alternatives [17]. In case of many successful alternatives, we need a
more sophisticated model to deal with preferences’ aggregation [18]. A multi-winner election
(V,C,F,k) is defined by a set of voters V expressing preferences over a number of candidates
C, and then a voting rule F returns a subset of size k winning candidates. A voting rule can
perform its role on different types of ordered preferences, even though the most common refers
to a pre-fixed linear order on the alternatives. In most of cases, these are chosen a priori.
Formally we denote set of judgements performed by the i-th voter as profile preferences P𝑖 .
Each profile contains information about the grade of candidates by voters. The voting rule F
associates with every profile P a non-empty subset of winning candidates.
In multi-winner elections more precise traits are required, compared to the ones stated in May’s
theory [19]. Indeed:

    • Representation: for each partition of voters
                                                              ⌊︁ 𝑛 ⌋︁)︁
                                       𝑉𝑖 ∈ 𝑉 (with |𝑉𝑖 | ≥                                       (3)
                                                                𝑘
      at least one successful candidate is elected from that partition;
    • Proportionality: for each partition of voters
                                                           ⌊︁ 𝑛 ⌋︁)︁
                                     𝑉𝑖 ∈ 𝑉 (with |𝑉𝑖 | ≥                                         (4)
                                                              𝑘
      number of elected candidate is proportional to the partition’s size.

   An implicit assumption so far has been that preferences are ordinal and not interpersonally
comparable: preference orderings contain no information about each individual’s strength or
about how to compare different individuals’ preferences with one another [20]. Statements such
as ‘Individual 1 prefers alternative x more than Individual 2 prefers alternative y’ or ‘Individual l
prefers a switch from x to y more than Individual 2 prefers a switch from x* to y*’ are considered
meaningless. In voting contexts, this assumption may be plausible, but in welfare-evaluation
contexts—when a social planner seeks to rank different social alternatives in an order of social
welfare—the use of richer information may be justified.


2.3. Single-winner Majority judgement
In order to describe the majority judgement, we need to use a table that refers to ranking for all
the candidates 𝐶, by using tuples [21]. Suppose having six possible choices we may use the
words: excellent, very good, good, discrete, bad, very bad.
So each candidate is described by a bounded set of vote.
In general, letting 𝛼 = (𝛼1 , 𝛼2 , ..., 𝛼𝑛 ) be a candidate A’s set of n grades (written from highest
to lowest, 𝛼𝑖 ≥ 𝛼𝑖+1 for all 𝑖), there is a majority of (at least) 𝑛 − 𝑘 + 1 for n A’s grade to beat
most 𝛼𝑘 and at least 𝛼𝑛−𝑘+1 , for all 1 ≤ 𝑘 ≤ (𝑛+1)  2 . We call this the (n-k+1) - majority for [𝛼𝑘 ,
�𝛼𝑛−𝑘+1 ].
As already mentioned any possible ranking tuple that we choose to describe must follow ordering
relations.
So the ranking should respect domination: namely, evaluate one candidate above another when
that candidate’s grades dominate the other’s.
The described majority judgement is a single winner system, found comparing recursively
median grade between candidates: first, grades are ordered in columns from the highest to
the lowest according to the order relation, then the middle column (lower middle if number
of grades are even) with the highest grade between candidates’row is selected [22]. If there’s
a tie, algorithm keeps on discarding grades equal in value to the shared median, until one of
the tied candidate is found to have the highest median. Before describing how it’s possible to




Figure 1: Example with 5 grades, between the dashed lines it’s reported the median grade. Highest
occurrences in "Good" determines the winner.

generalize this single winner system to a multi winner strategy, thanks to the use of clusters
[23], we focus our attention on how these works, analyzing in particular K-medoids.


3. Clustering approach
3.1. How clusters work
There’s no precise definition of clustering, mostly due to the huge variety in different clustering
algorithms. We can state that they share the ability to divide data into groups with some
common features. According to some general traits, we can distinguish types of clustering:
1. Connectivity models: data points in a sample space exhibits similarity according to the
distance between them. Two approaches are equally valid: bottom-up where each observation
constitutes a group and then pairs of clusters are merged; top-down, where observation are
included in one cluster and then it’s segregated; but in both approaches is not included the
possibility of modifying a cluster once created;
2. Distribution models: once created a cluster, model check probabilities on observations
following a particular distribution. Good performances are not always guaranteed since these
models are prone to overfit data if no constraint on complexity is made;
3. Density models: areas of higher density are identified and local cluster are there created,
while remaining data can be grouped into arbitrary shaped region, with no assumption about
da ta distribution; for their flexibility, these models are fit to handle noise better than organizing
data on fixed required body.
Since we would like to model clusters that satisfy requirements expressed before, based on
pretty fixed structure with no assumption about distribution followed by data, it seems more
accurate considering a different class of clustering algorithm known as centroid models.
�3.2. K-Medoids
Clustering is the process of grouping a set of objects in order to have each similar object to each
other in one cluster, that are dissimilar to objects in other clusters.
For our goal, namely selecting winners from a group of candidates, K-medoids clustering are
used, because medoids are the representative objects that are considered, in order to have a
result that belongs to the group of candidates [24]: it is based on the most centrally located
object in a cluster, so it is less sensitive to outliers in comparison with the K-means clustering,
which is not the best model in our case since it could result in something that is not present in
the candidate list due to the fact that is an average-based method rather than median. In fact,
the medoid is a data point (unlike the centroid) which has the least total distance to the other
members of its cluster.
Another advantage for this choice is that the mean of the data points is a measure that gets
highly affected by the extreme points; so, in K-Means algorithm, the centroid may get shifted to
a wrong position and hence result in incorrect clustering if the data has outliers because then
other points will move away from. On the contrary, the K-Medoids algorithm is the most central
element of the cluster, such that its distance from other points is minimum. Thus, K-Medoids
algorithm is more robust to outliers and noise than K-Means algorithm.
The K-medoid we use is part of the python sklearn library [25], which is oriented to machine
learning. This library supports partitioning around medoids (PAM) [26] proposed by Kaufman
and Rousseeuw (1990), that is known to be most powerful. The workflow of PAM is described
below [27].
The PAM procedure consists of two phases: BUILD and SWAP:

    • In the BUILD phase, primary clustering is performed, during which k objects are succes-
      sively selected as medoids.
    • The SWAP phase is an iterative process in which the algorithm makes attempts to improve
      some of the medoids. At each iteration of the algorithm, a pair is selected (medoid and
      non-medoid) such that replacing the medoid with a non-medoid object gives the best
      value of the objective function (the sum of the distances from each object to the nearest
      medoid). The procedure for changing the set of medoids is repeated as long as there is a
      possibility of improving the value of the objective function.

Suppose that 𝑛 objects having 𝑝 variables each should be grouped into 𝑘 (𝑘 < 𝑛) clusters,
where 𝑘 is known. Let us define j-th variable of object 𝑖 as 𝑋𝑖𝑗 (𝑖 = 1, ..., 𝑛; 𝑗 = 1, ..., 𝑝). As a
dissimilarity measure is used the Euclidean distance, that is defined, between object 𝑖 and object
𝑗, by:                                   ⎯
                                         ⎸ 𝑝
                                         ⎸∑︁
                                   𝑑𝑖𝑗 = ⎷ (𝑋𝑖𝑎 − 𝑋𝑗𝑎 )2                                          (5)
                                             𝑎=1

where 𝑖 and 𝑗 range from 1 to 𝑛. The medoids is selected in this way:

    • calculate the Euclidean distance between every pair of all objects;
                              𝑑
    • calculate 𝑣𝑗 = 𝑛𝑖=1 ∑︀𝑛 𝑖𝑗 𝑑𝑖𝑙 ;
                     ∑︀
                               𝑙=1
�    • sort all 𝑣𝑗 for 𝑗 = 1, ..., 𝑛 in ascending order and select the first 𝑘 object that have smallest
      initial medoids value;
    • from each object to the nearest medoid we can obtain the initial cluster result;
    • calculate the sum of distances from all objects to their medoids;
    • update the current medoid in each cluster by replacing with the new medoid, selected
      minimizing the total distance from a certain object to other objects in its cluster;
    • assign each object to the nearest medoid and obtain the cluster result;
    • calculate the sum of distance from all objects to their medoids, so if the sum is equal to
      the previous one, then stop the algorithm; otherwise, go back to the update step.
In our case, prior knowledge about the number of winners is required, and identified clusters
are restricted in minimum size that is number of voters on the number of candidates ( 𝑛𝑘 ).


3.3. Clustered Majority Judgement
Multi winner majority judgement exploits clustering approach to apply to each group majority
judgement [28]. Given k the number of candidates to be elected, algorithm seeks the optimal
number of cluster to create.
This ranges from 1 to k and has to satisfy an important additional requirement: once selected a
number of clusters, if a tie occurs and so k’ vacant seats are left, algorithm is repeated k’ times
until tie’s broken. In case there’s no broken tie, fixed number of cluster is changed.


3.4. Algorithm
In order to explain how the algorithm deals with polarization problem, most relevant steps are
described in pseudocode and in annotated strides:

   1. set the number of winners as maximum number of clusters;
   2. cluster are created decreasing the previous maximum number of clusters until the optimal
      number is not achieved. This number is bound by the size of cluster, that satisfies the
      following proportion: number of voters : number of winners = number of voters in one
      cluster : one winner (line 8 in pseudocode);
   3. the function winners calculates the median for every created cluster (line 15 of pseu-
      docode);
   4. check that winners from cluster are different between each other (line 29 in pseudocode);
      in case it’s not true (condition="ko" on pseudocode) algorithm goes back to step 2 with a
      maximum number of cluster equal to number of vacant seats and the proceedings are
      held until all seats have been filled.


3.5. Case Studies
In this section, we describe two interesting comparisons of majority judgement (MJ) and
clustered majority judgement (CMJ).
�Algorithm 1
Require: 𝑘 ≥ 0
Ensure: 𝑛_𝑤𝑖𝑛𝑛𝑒𝑟𝑠 = (𝑛1 , ..., 𝑛𝑘 ), 𝑘 > 1
  𝑘 ← 𝑛𝑢𝑚𝑏𝑒𝑟_𝑤𝑖𝑛𝑛𝑒𝑟𝑠
  𝑚𝑎𝑥_𝑐𝑙𝑢𝑠𝑡𝑒𝑟 ← 𝑘
  𝑐𝑜𝑛𝑑𝑖𝑡𝑖𝑜𝑛 ← ”𝑘𝑜”
  while 𝑐𝑜𝑛𝑑𝑖𝑡𝑖𝑜𝑛 = ”𝑘𝑜” do
     𝑐𝑙𝑢𝑠𝑡𝑒𝑟_𝑙𝑖𝑠𝑡 ← 𝑐𝑙𝑢𝑠𝑡𝑒𝑟(𝑣𝑜𝑡𝑒_𝑙𝑖𝑠𝑡)
     for all list_cluster do
         𝑤𝑖𝑛𝑛𝑒𝑟𝑠_𝑝𝑒𝑟_𝑐𝑙𝑢𝑠𝑡𝑒𝑟 ← 𝑐𝑜𝑚𝑝𝑢𝑡𝑒_𝑤𝑖𝑛𝑛𝑒𝑟𝑠(𝑐𝑙𝑢𝑠𝑡𝑒𝑟)
         𝑎𝑙𝑙_𝑤𝑖𝑛𝑛𝑒𝑟𝑠 ← 𝑙𝑖𝑠𝑡_𝑜𝑓 _𝑎𝑙𝑙_𝑤𝑖𝑛𝑛𝑒𝑟𝑠(𝑤𝑖𝑛𝑛𝑒𝑟𝑠_𝑝𝑒𝑟_𝑐𝑙𝑢𝑠𝑡𝑒𝑟)
     end for
     𝑙𝑖𝑠𝑡_𝑤𝑖𝑛𝑛𝑒𝑟_𝑑𝑖𝑠𝑡𝑖𝑛𝑐𝑡 = 𝑙𝑖𝑠𝑡_𝑜𝑓 _𝑎𝑙𝑙_𝑑𝑖𝑠𝑡𝑖𝑛𝑐𝑡_𝑤𝑖𝑛𝑛𝑒𝑟𝑠(𝑎𝑙𝑙_𝑤𝑖𝑛𝑛𝑒𝑟𝑠)
     𝑜𝑝𝑡𝑖𝑜𝑛_𝑟𝑒𝑚𝑎𝑖𝑛𝑖𝑛𝑔 ← 𝑛𝑢𝑚𝑏𝑒𝑟_𝑤𝑖𝑛𝑛𝑒𝑟𝑠 − 𝑙𝑒𝑛(𝑙𝑖𝑠𝑡_𝑤𝑖𝑛𝑛𝑒𝑟_𝑑𝑖𝑠𝑡𝑖𝑛𝑐𝑡)
     if 𝑜𝑝𝑡𝑖𝑜𝑛_𝑟𝑒𝑚𝑎𝑖𝑛𝑖𝑛𝑔 = 0 then
         𝑐𝑜𝑛𝑑𝑖𝑡𝑖𝑜𝑛 =′ 𝑜𝑘 ′
     else
         𝑘 ← 𝑜𝑝𝑡𝑖𝑜𝑛_𝑟𝑒𝑚𝑎𝑖𝑛𝑖𝑛𝑔
         𝑐𝑜𝑛𝑑𝑖𝑡𝑖𝑜𝑛 ←′ 𝑘𝑜′
     end if
  end while


3.5.1. Case study 1: President of the Republic election
In order to test our algorithm, we asked an heterogeneous group of voters to express judgements
on a pre-defined list of possible candidates as President of the Republic before the elections took
place. This list has been created according to the rumours circulated on that period, creating a
bias effect on our results, as it was excluded a possible rielection of Sergio Mattarella.
In spite of it, we focus on how the algorithm has worked in order to balance polarization,
returning a subset of winners with size chosen a priori, that we may interpret as best solutions
for majority of people who took part into the venture.
Input parameters of Clustered Majority Judgement test are Excellent, Very Good, Good, Accept-
able, Poor, To Reject, No Opinion and the number of winners is set a priori equal to 3. 125 voters
took part into this election and the algorithm form three clusters, exactly like the number of
winners.
Testing our algorithm on the described election has shown how difference preference has a
leverage on judgement aggregation: for example, voters in Cluster 1 are more bound to express
"Good" judgement for candidates considered neutral in terms of political ideas, than the cluster
3 in which voters have a tendency in judging neutral ones as "Fair" or "Poor". Cluster 2 has
intermediate traits and no particular tendency is emphasized. We can compare CMJ results
with single-winner MJ ranking, comparing the Table 2 and Table 3. The comparison shows
different results for the third candidate, highlighting how clustering influences outcome, giving
more weight to minorities’ judgement.
�                            Cluster    Cluster size       Winner
                           Cluster 1       65           Mario Draghi
                           Cluster 2       35          Paolo Gentiloni
                           Cluster 3       25         Anna Finocchiaro
Table 2
CMJ results

                                  Ranking MJ       Candidate
                                      1           Mario Draghi
                                      2          Paolo Gentiloni
                                      3           Emma Bonino
Table 3
Top 3 of single-winner Majority Judgement applied to voters




3.6. Case Study 2: Working hours per week
The last case study is a good paradigm for deciding how to manage working hours in the office,
given a fixed number of working hours to be done (18 hours). In this case, we asked 160 students
of University Federico II of Naples to choose the best combination of working hours, in presence
(P) or with online lectures (O). We used again the grades Excellent, Very Good, Good, Acceptable,
Poor, To Reject, No Opinion and the five options are:
   1. 6 hours (P) - 6 hours (O) - 6 hours (P or O)
   2. 10 hours (P) - 4 hours (O) - 4 hours (P or O)
   3. 8 hours (P) - 6 hours (O) - 4 hours (P or O)
   4. 7 hours (P) - 9 hours (O) - 2 hours (P or O)
   5. 5 hours (P) - 5 hours (O) - 8 hours (P or O)
The results of MJ method, with the traditional compute of medians takes back as winner the
option 4 (7 hours (P) - 9 hours (O) - 2 hours (P or O)) that has the highest number of "Good"
votes.
Instead the compute of winner with CMJ method takes back a different situation: we fixed 2 as
number of winners (and number of clusters) and the first one is the option 3 (8 hours (P) - 6
hours (O) - 4 hours (P or O)) and the second one is the option 4, the same winner of MJ method.
As we can see, probably because the number of voters is quite high, the results are not the same
like in case study 2. With CMJ, we take into account the wide spectrum of preferences, with
special regards for the most polarising ones, which are the most influent in creating different
clusters.
Especially for this reason, we may prefer CMJ to MJ for this case-study’s lookalike situations,
where a shared solution should be taken, considering the different impact it can have on the
heterogenous groups (clusters) the judgement is made by.
�Conclusions
In section 1, we dealt with logical issues involved in voting rules and judgement aggregation,
highlighting majority rule’s resistance to strategical vote.
In section 2, a more fined model of majority rule, Majority Judgement, has been presented as an
option to better estimate the most shared candidate.
In section 3, the related works have been shown and in section 4, all possible categories of
clustering approach has been reported in order to choose the fittest one for our generalization
of Majority Judgement as a multi-winner strategy. After that, three different case studies are
reported, with a particular attention to the comparison between MJ and CMJ results.
In spite of non-deterministic nature of K-Medoids, Clustered Majority Judgement is thought to
be used in high populated disputes. For these reasons, we feel confident about clustering’s role
of taking into account all different perspectives could be shown in such situation.
Moreover, our implementation is not strictly linked to political field, as is clearly shown in
the case studies (except the first one), mostly because it requires only some fixed parameters:
number of winners, number of grades and grades themselves.
An important future challenge could be speeding up the algorithm or making a more flexible
structure, even though all the constraints already explained in previous sections need to be
satisfied.



References
 [1] A. S. G. Bellec, F. Scherr, A solution to the learning dilemma for recurrent networks of
     spiking neurons, in: Nat Commun, 2020.
 [2] J. Kleinberg, An impossibility theorem for clustering, in: Cornell University, 2002.
 [3] B. J. Streibel, The manager’s guide to effective meetings / barbara j. streibel., in: The
     manager’s guide to effective meetings, McGraw-Hill, 2003.
 [4] R. S. Tannenbaum, W. H. Schmidt, How to choose a leadership pattern, 2009.
 [5] R. R. Blake, J. S. Mouton, L. B. Barnes, L. E. Greiner, Breakthrough in organization
     development, Graduate School of Business Administration, Harvard University, 1964.
 [6] V. H. Vroom, P. W. Yetton, Leadership and decision-making, University of Pittsburgh Pre,
     1973.
 [7] E. Verzuh, A. P. Association, et al., A guide to the project management body of knowledge:
     Pmbok guide, Project Management Institute, Inc., 2021.
 [8] F. Brandt, V. Conitzer, U. Endriss, J. Lang, A. D. Procaccia, Handbook of computational
     social choice, Cambridge University Press, 2016.
 [9] K. J. Arrow, Social choice and individual values, Yale university press, 2012.
[10] P. Serafini, La matematica in soccorso della democrazia: Cosa significa votare e come si
     può migliorare il voto, Independently Published, 2019.
[11] M. Balinski, R. Laraki, A theory of measuring, electing, and ranking, National Acad
     Sciences, 2007.
[12] M. Balinski, R. Laraki, Judge: Don’t vote!, volume 62, INFORMS, 2014, pp. 483–511.
�[13] M. Balinski, R. Laraki, Election by majority judgment: experimental evidence, in: In Situ
     and Laboratory Experiments on Electoral Law Reform, Springer, 2011.
[14] K. O. May, A set of indipendent necessary and sufficient conditions for simple majority
     decision, in: Carleton College, 1952.
[15] B. Fazzinga, S. Flesca, F. Furfaro, E. Masciari, Rfid data compression for supporting
     aggregate queries (????).
[16] C. List, Social choice theory, in: The Stanford Encyclopedia of Philosophy, Metaphysics
     Research Lab, Stanford University, 2022.
[17] J. C. Garcia-Bermejo, A plea for the majority method in aggregating judgements, in:
     Oxford Journal, 2011.
[18] M. P. Klaus Nehring a, Incoherent majorities: The mcgarvey problem in judgement
     aggregation, in: Science Direct, Elsevier, 2011.
[19] A. Fabre, Tie-breaking the highest median: Alternatives to the majority judgment, in:
     Paris School of Economics, 2018.
[20] M. Ceci, R. Corizzo, F. Fumarola, M. Ianni, D. Malerba, G. Maria, E. Masciari,
     M. Oliverio, A. Rashkovska, Big data techniques for supporting accurate predic-
     tions of energy production from renewable sources, volume 0, 2015, p. 62 – 71.
     URL:        https://www.scopus.com/inward/record.uri?eid=2-s2.0-85007505126&doi=10.
     1145%2f2790755.2790762&partnerID=40&md5=612b2eb0409a5c8dd065f9213971ec6f.
     doi:10.1145/2790755.2790762, cited by: 15.
[21] M. Balinski, Fair majority voting (or how to eliminate gerrymandering, in: The American
     Mathematical Monthly, Vol. 115, No. 2, Mathematical Association of America, 2006.
[22] L. Caroprese, E. Zumpano, A logic framework for P2P deductive databases, Theory
     Pract. Log. Program. 20 (2020) 1–43. URL: https://doi.org/10.1017/S1471068419000073.
     doi:10.1017/S1471068419000073.
[23] L. Caroprese, E. Zumpano, Aggregates and priorities in P2P data management systems,
     in: 15th International Database Engineering and Applications Symposium (IDEAS 2011),
     September 21 - 27, 2011, Lisbon, Portugal, ACM, 2011, pp. 1–7. URL: https://doi.org/10.
     1145/2076623.2076625. doi:10.1145/2076623.2076625.
[24] L. Caroprese, E. Zumpano, Declarative semantics for P2P data management system, J.
     Data Semant. 9 (2020) 101–122. URL: https://doi.org/10.1007/s13740-020-00115-6. doi:10.
     1007/s13740-020-00115-6.
[25] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel,
     P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher,
     M. Perrot, E. Duchesnay, Scikit-learn: Machine learning in Python, in: Journal of Machine
     Learning Research, 2011.
[26] P. J. R. Leonard Kaufman, Partitioning around medoids, in: Finding Groups in Data: An
     Introduction to Cluster Analysis, John Wiley & Sons, 2015.
[27] C.-H. J. Hae-Sang Park, A simple and fast algorithm for k-medoids clustering, in: POSTECH,
     Elsevier, 2008.
[28] S. Q. Andrea Loreggia, Nicholas Mattei, Artificial intelligence research for fighting, in:
     Political Polarisation: A Research Agenda, 2020.
�
🖨 🚪