Portal:Complex Systems Digital Campus/CHOICE

. C o s y p e d i a . the repository for Open Questions, Challenges and Ressources of the . Complex Systems Digital Campus

CHOICE

Preferential Vote for Social Choice

Great Challenge: Majority Judgment and its MAJ Dapp

Description

We may think of the political process as a machine which makes social decisions when the views of representatives and their constituents are fed into it. A citizen will regard some ways of designing this machine as more just than others. So a complete conception of justice is not only able to assess laws and policies but it can also rank procedures for selecting which political opinion is to be enacted into law.

     — John Rawls

The traditional theory of social choice offers paradoxes such as those of Condorcet’s or Arrow’s. The theorem of Arrow says that, for more that two choices, there exists no aggregation function of individual choices except the preference of one individual, the ‘dictator’. Such impossibility is consonant with a ‘centralized society’.

In the Arrow’s approach, the voters are directly ‘ranking’ the competitors, in a vertical way. In the ‘Majority Judgment’ of Balinsky and Laraki, the voters are indirectly ‘grading’ the competitors, in a horizontal way with the same grade language L. A Social Ranking Function (SRF) can then aggregate horizontally the judge’s social grading before using the vertical social ranking.

The first sub-challenge is devoted to the study and dissemination of the Majority Judgment theory. It is a first contribution to its Knowledge Map of this domain necessary for the personalized education of all want to use it.

The second sub-challenge is about the implementation of the most appealing Social Ranking Function, called the ‘Majority Ranking’. This implementation is elegant and is completely adapted to a decentralized organisation with incremental addition of judges or candidates: the ‘anonymity’ of judges and the ‘impartiality’ for the candidates provides a first step that is an accumulation matrix.

The third challenge is to study the NEW symmetric grading/ranking game where the judges are grading the candidates and the candidates are grading the judges. It can be useful for peer-to-peer jury, for learners facing tasks and a lot of other situations.

The forth challenge is the study of Majority Ranking practice. The ‘majority-ranking’ algorithm was tested in a lot of fields, politics, wine concourses, skate competitions. In the WWW DAO, it will be used for many usages, the modification of smart contract, the election of representatives, the Proof of Authority (PoA) by scientists, the Olympiads of advice-recommendation ecosystem, the concourses of ‘smart innovation’. Last but not least it will be used at the heart of the main WWW DAO task, i.e. social learning: managing the exploitation and exploration compromise in a rapidly changing world needs ‘grading the whole result’ of ‘new bad known options’ and observing the grading trajectories (cf. RAPSODY Dapp). More generally, it can be used in the future for a generalized peer-to-peer control about the trust in any kind of information as it is the case in the scientific communities, e.g. for facing fake news.

The theory of the ‘Majority Judgement’ and the practice of the Majority-Ranking is a great step toward a ‘decentralized society’ where citizens could consider that a majority-ranking machine is more “just” that any other procedure according to the citation of Rawls.

Keywords

Social Choice theory, Arrow's theorem, Condorcet paradox, majority judgment, social grading, social ranking, multiple juries, multi-criteria ranking,symmetric ranking games, theory and practice of social choice.

Board

• Paul Bourgine (chair | paul.bourgine@polytechnique.edu)
• Cyril Bertelle (co-chair)

Bibliography

• Kenneth J. Arrow. 1951 (2nd ed. 1963). Social Choice and Individual Values. New Haven CT: Yale University Press.
• Majority Judgment, Michel Balinski & Rida Laraki, MIT Press Cambridge, 2010

Challenge 1: Research and dissemination of Social Choice theory (e-team)

Description

The challenge is the theoretical and empirical study of the Majority Judgment and its comparison with other Social Choice theories and practices. A knowledge map of its main results and practices for its teaching and dissemination will be designed and produced (using the IKM Dapp).

What follows is a contribution to the Knowledge Map of the Majority Judgment theory. For facilitating the design and proof of new theorems, it is proposed to use a specialized Coq environment (reference?) for asserting the soundness of the theorems.

The theoretical study is starting with the ‘aggregation functions’ and their associated ‘order functions’ that are in one-to-one correspondence. The axiomatic of Social Grading Function (SRF) is then developed in one-to-one correspondence with ‘order function’. Finally the axiomatic of Social Ranking Function (SRF) provides a one-to-one correspondence between SGF and SRF. The references of the theorems are those of the Balinsky’s and Laraki’s book.

In the Balinski and Laraki approach, ‘ranking’ is replaced by ‘grading’. Grading is using a language L, e.g. {‘excellent’, ‘very good’,’good’, ‘passable’}. The language can be descriptive phrases. With m candidates and n judges, the grading matrix is belonging to L^(m*n).

Fig.1: The first step is the horizontal ‘aggregation function'. Here the language L has 5 grades used by all judges.

• (right) there is 6 individual candidatures and 6 judges providing their grading matrix Φ. For each candidate, the ‘judge’s anonymity’ allows to range the grades in decreasing order r1 ≥ .. ≥ rn.
• (left) again the ‘judge’s anonymity’ allows to summarize the grading matrix into a ‘count matrix’ giving the number of each grades obtained by each individual candidate.

Fig.2: The second step is the order function for finer grading (and thus ranking in case of two competitors receiving the same grade by the aggregation function). This finer grading is a lexicographic-order one (with an 'alphabet' defined by the language L in decreasing order): the iteration start with c1 the grades with repetition of a competitor; f is applied a first time giving the grade α1 and this grade is removed from c1 by decreasing the α1 number by 1; f is applied a second time to c2 giving the grade α2 and this grade is removed from c2 in the same way .. and the same process continues until all the numbers are zero. The theorem says that the order function is uniquely defined by its aggregation function. It means that the order function are not adding 'new' functions: they just allows the finest possible grading starting from an aggregation function: the order between two competitors is equivalent only if the two competitors grading are exactly the same.

Fig. 3: A Social Grading Function

Fig. 3: A Social Grading Function (SGF) is doing globally what the Order Function is doing for each line (axiom IIAG: Independence to Irrelevant Alternatives in Grading). The axioms a-b-d are natural. The order-consistency is a necessary invariance up to a monotonic continuous transformation of the ‘ordinal language’ into different ‘continuous scales’ (internal to the judges). The theorem is saying that an SGF is uniquely defined by its order function, itself uniquely defined by its aggregation function.

Fig. 4: The SRF axioms are the same as SGF axioms except the IIAR**, the ‘Independence of Irrelevant Alternatives in Ranking’ of the 2 candidates from all others. IIAR is related to the IIAG is the ‘independence of the grading’ of one candidate from all others. The similarity between axioms has the theorem as a result: the SRF is uniquely defined by its SGF. Please notice that a complete order ‘≥’ is generating an equivalence ‘i1 ≈ i2’ (i1 ≥ i2 and i2 ≥ i1) and a ‘strict order’ ‘i1 > i2’ (i1 ≥ i2 and not i2 ≈ i1).

Fig. 5: The outstanding point of SGF properties is their equivalence: if one is wished, all the other are coming with. The definitions of the properties above are as follows:

(order-consistent) if f (r1, . . . , rn) ≥ f (s1, . . . , sn) implies f(φ(r1), . . . , φ(rn)) ≥ f(φ(s1), . . . , φ(sn)) for all increasing, continuous functions φ : [0,R] → [R1,R2] , φ( 0) = R1 , φ(R) = R2

(strategy-proof-in-grading) if: • when a judge’s input grade is r+ > r , any change in his input can only lead to a lower grade • when a judge’s input grade is r− < r , any change in his input can only lead to a higher grade.

(partially strategy-proof-in-ranking) when rA<rB and when any judge j is of the opposite opinion, rA j > rBj , then: • if he can decrease B’s final grade, he cannot increase A’s final grade, and • if he can increase A’s final grade, he cannot decrease B’s final grade.

(strategy-proof-in-grading) Let ‘r’ a jury’s final grade, • when a judge’s input grade is r+ > r , any change in his input can only lead to a lower grade • when a judge’s input grade is r− < r , any change in his input can only lead to a higher grade.

(minimizing the manipulability) means that for any r, at most one judge may both increase and decrease a final grade.

(reinforcing) f (r1 , . . . , rk−1 , rk , rk+1 , . . . , rn ) = r and rk > r*k ≥ r or r ≥ r*k > rk implies f (r1 , . . . , rk−1 , r*k , rk+1 , . . . , rn ) = r.

(conform with the assigned grades) when {r1,..., rn}⊂ S => f (r1,..., rn) ∈ S

(language-consistent) if f(φ(r1), . . . , φ(rn)) = φ(f (r1, . . . , rn)) for all increasing, continuous functions φ : [ 0,R] → [R1,R2] , φ( 0) = R1 , φ(R) = R2

Fig. 6: The middlemost functions are depending only from the middlemost interval, i.e. the median singleton {r(n+1)/2} if the number of judges is odd or the interval {rn/2, r(n+2)/2} if even. These monotonic functions are in between their lowest one 'fmaj' and their highest one 'fo/maj'. A Rawlsian max-min criteria is defining fmaj as the minimal middlemost that is also the maximal one respecting consensus. The role of consensus is well exemplified when ranking candidates ‘B’ and ‘C’: 'Fmaj' provides for ‘B’ {V. Good, V. Good, V. Good, V. Good, Good, Excellent} and for ‘C’ {V. Good, V. Good, Good, Excellent, Passable, Excellent}; the lexicographic comparison is equal for the two first in the list but, for the third one, ‘B’ with V. Good is better than ‘C’ with Good (‘B’ >maj ‘C’). 'Fo/maj' that respects dissent provides a third one V. Good for ‘B’ and Excellent for ‘C’: ‘C’ >o/maj ‘B’.

Fig. 7: Again the outstanding point of middlemost properties is their equivalence for SGF/Order Function as well as for SRF: if one is wished, all the other are coming with. Furthermore, all the middlemost functions are converging toward fmaj when the number of voters is much larger than the size of the language: that is also the case for middlemost SGF and SRF. The definitions of the properties above are as follows:

(maximize the social welfare) when the final grade f (r1..., rn) = r minimizes the total disutility of all the judges: ∆(r) = ∑j∈J d(r, rj).

(minimizing the lexi-probability of cheating), i.e. that the probability of cheating measured lexicographically

(counter crankiness) for r1 ≥ .. ≥ rn, n ≥ 3, f satisfies f (r1, r2,.. ,rn-1,rn) = f (r2,.. ,rn-1)

(respects consensus) when all of A’s grades belong to the middlemost interval of B’s grades, and this implies that A’s final grade is not below B’s final grade.

(respects dissent) when all of A’s grades belong to the middlemost interval of B’s grades, and this implies that A’s final grade is not above B’s final grade..

(choice monotonic) A ≥S B and one judge raises the grade he gives to A, then A >S B

(middlemost SRF) A ≥S B depends only on the set of grades that belong to the first of the kth middlemost intervals where they differ.

The strategy with grading horizontally before ranking vertically is completely different from the direct vertical ranking of the Arrow’s theorem that has no solution if ranking more than two candidates. With grading first, there is an infinity of possible ranking: it is thus possible to add some supplementary satisfying axioms. Curiously, the supplementary axioms arrive by set of equivalent appealing properties. It was already seen that the important ‘order-consistency’ is characterizing the ‘order function’ inside the more general ‘aggregation functions’: such 'more general' is not so much because any order function is uniquely defined by an aggregation function. Order functions are order-consistent, i.e they are invariant through a continuous monotonic change of the grading scale (implicit for each judge); furthermore, when used for ranking, they avoid ties except in case of exact equality! Now, wanting to have anyone property of the middlemost brings all the set of their characteristic equivalent properties! Finally, if adding the appealing consensus respect, there is only ONE choice: Fmaj. Furthermore, when the number of judges or voters becomes large, all the middlemost function are converging toward Fmaj.

Members

• Paul Bourgine (chair)

Bibliography

• Kenneth J. Arrow. 1951 (2nd ed. 1963). Social Choice and Individual Values. New Haven CT: Yale University Press.
• Majority Judgment, Michel Balinski & Rida Laraki, MIT Press Cambridge, 2010
• other publications, Michel Balinski & Rida Laraki

Challenge 2: The implementation of the MAJ Dapp with its extensions (e-team)

Description

The middlemost aggregation functions emerge as the best possible order function to determine the final grade: they especially always agree with a majority decision. fmaj and fo/ma are symmetrically defined. But fmaj is preferable by:

• according more credence to agreement than disagreement, to positive than to negative

• using a Rawlsian max-min criterion of consensus.

• being asymptotically the same as all the middlemost functions when the number of voters is increasing (almost surely).

The MAJ Dapp is the implementation of 'Fmaj' and the Majority-Ranking '>maj' algorithm and all its extensions.

fig. 8: The Majority-Grad fmaj as a middlemost function is depending only from the middlemost interval, i.e. the median singleton {r(n+1)/2} if the number of judges is odd or the interval {rn/2, r(n+2)/2}. But after removing r(n+2)/2 from this interval, the number of judges is odd and rn/2 is selected. Thus with the Majority-Grad everything relies on the sequence of alternating grades that emanate outward from the middle. In case of the matrix C with integer number, it is not restrictive to start with a odd number then remove as many middle pairs as possible as done for the abbreviation Majority-Value (aM-V).

The extension of the MAJ Dapp will be:

- aggregation of juries of different sizes (theorems 13.6 and 13.7)

- approval voting (chapter 18)

- multicriteria ranking (chapter 20)

Members

• Paul Bourgine (chair)
• Jorge Louçã (co-chair)

Bibliography

• Majority Judgment, Michel Balinski & Rida Laraki, MIT Press Cambridge, 2010
• other publications, Michel Balinski & Rida Laraki

Challenge 3: The antisymmetric Majority-Ranking (e-team)

Description

That is a very useful case in social learning when the learner is facing more or less difficult tasks. The language can be (“very difficult”, “difficult”, “ok”, “easy”, “very easy”). In the converse point of view, the task 'can says’ conversely about the learner in the same interaction: “very weak”, “weak”, “ok”, “strong”, “very strong”. It is like a ‘zero sum game’. the result is a complete ranking of the learners and a complete ranking of the tasks. The antisymmetric Majority-Ranking will be theoretically studied and implemented as the 'antiMAJ Dapp'

It is not necessarily a ‘zero sum game’. It can be any reciprocal grading-ranking game (two matrices) between the ‘judges’ and the ‘candidates’ respecting the axioms. the result is two complete 'reciprocal ranking of the candidates AND the judges. The reciprocal Majority-Ranking will be theoretically studied and implemented 'recMAJ Dapp'.

‘Judges’ and ‘candidates’ can be the same population as a peer-to-peer grading. There is one grading matrix. The result is one complete p2p ranking. The p2p Majority-Ranking will be theoretically studied and implemented 'p2pMAJ Dapp'.

Members

• Paul Bourgine (chair)
• Pierre Collet (co-chair)
• Pierre Parrend

Bibliography

• Majority Judgment, Michel Balinski & Rida Laraki, MIT Press Cambridge, 2010
• other publications, Michel Balinski & Rida Laraki

Challenge 4: Qualified Grading in Majority Ranking (e-team)

Description

Definition (Qualified Grading in Majority Ranking): The ‘Qualified Grading in Majority Grading’ is fixing the minimum grade for being accepted by majority ranking, e.g. 4 stars in a scale of 5 stars: thus the top ranking formulation of the MAJ Dapp is accepted only if its first grade is at least 4 stars, i. e. 4 stars or 5 stars. It is not possible to change the ‘Qualified Grading in Majority Grading’: only the ‘Qualified Grade’ can be changed.

Members

• Paul Bourgine (chair)

Bibliography

• Majority Judgment, Michel Balinski & Rida Laraki, MIT Press Cambridge, 2010
• other publications, Michel Balinski & Rida Laraki

Challenge 5: Studying the practice of the Majority-Ranking with the MAJ Dapp (e-team)

Description

The theory of the ‘Majority Judgement’ and the practice of the Majority-Ranking function is a great step towards a ‘decentralized society’: citizens could consider that a majority-ranking machine is more “just” that any other procedure according to the citation of Rawls.

The middlemost aggregation functions emerge as the best possible choices amongst the order function to determine the final grads with their supplementary very appealing properties: they especially always agree with a majority decision. The majority-grad fmaj is preferred for a little jury within the middlemost function because it is the only middlemost that respect consensus. And it is not distinguishable from the other middlemost functions for large jury.

The theory of the ‘Majority Judgment’ is opening a new road for aggregating the individual choices through the ‘majority-ranking algorithm’ for practical use. The applications of Majority-Ranking can be extremely diverse and sophisticated in all domains.

The WWW DAO will be a focal place for testing the ‘Majority Judgment’ in large variety of domains. In particular, it will be at the heart of the construction of a new ‘autonomous and decentralized DAO of DAOs’ (SIRE Dapp) as well as the Social Learning algorithm (RAPSODY Dapp). It will work as a Proof of Authority (PoA) for little jury as well as for compromise between exploration and exploitation in large cohorts sharing the same challenges.

Because the data of the MAJ Dapp will be available as for all other Dapps of the WWW DAO, deep experimental studies can be done about their successes and also their difficulties or failures. New refining of the Dapp can be designed for example in the case of the aggregation of several juries about the same kind of social choice.

Members

• Cyrille Bertelle (chair)

Bibliography

• Majority Judgment, Michel Balinski & Rida Laraki, MIT Press Cambridge, 2010
• other publications, Michel Balinski & Rida Laraki

Name of sub-challenge n (e-team)

Return to the Wikiversity Portal of the Complex Systems Digital Campus

Return to the Complex Systems Digital Campus main website