Ulam Median is NP-hard for Four Permutations

Mursalin Habib

Ulam Median is NP-hard for Four Permutations

T0 review · 0 major / 6 minor · reviewed 2026-08-08 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Computing an Ulam median is NP-hard even with exactly four input permutations.

desk verdict A clean, correct reduction that settles the Ulam median threshold: NP-hard for four permutations, with a genuinely new anchor-block lemma. read the letter →

arxiv 2608.05544 v1 pith:OKYCZO47 submitted 2026-08-06 cs.CC

Mursalin Habib This is my paper · ORCID

classification cs.CC MSC 68Q1768R15

keywords UlamdistancemedianrankaggregationNP-hardnesslongestcommonsubsequence3-SATreductionpermutationconsensus

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper asks how many input rankings are enough to make the Ulam-median consensus problem computationally intractable. It proves that four permutations suffice: given four permutations of the same set of symbols, deciding whether a median with total Ulam distance at most a threshold exists is NP-hard. Because three permutations admit a polynomial-time exact algorithm, this pins the complexity threshold exactly at four. The result matters for rank aggregation, where Ulam distance charges once per displaced item rather than per inverted pair, and it separates the Ulam metric from the ordinary edit metric on strings, where medians of any fixed number of inputs remain easy.

What carries the argument

The load-bearing objects are the two gadgets and the anchor block. The clause-witness pair $\beta_1,\beta_2$ lists each clause's three literal occurrences in one order and in reverse, so a common subsequence can take at most one symbol per clause; its restricted longest-common-subsequence length counts exactly the number of clauses hit by a set $S$. The variable-consistency pair $\alpha_1,\alpha_2$ places each variable's positive block before its negative block in one permutation and in the opposite order in the other, so a common subsequence can use at most one polarity per variable; equality at $s/2$ forces each variable's chosen side to contain all positives or all negatives. The anchor block $Z$ of length $2s+1$ separates these two roles: the Anchor-block Lemma shows any candidate median can be rewritten as $\tau_L Z \tau_R$ without decreasing any of the four LCS scores, and the fixed-partition optimum identity reduces the problem to optimizing two independent LCS terms. The linking identity is $\max_\tau (\mathrm{LCS}(\tau,\gamma_1)+\mathrm{LCS}(\tau,\gamma_2)) = |S|+\mathrm{LCS}(\gamma_1,\gamma_2)$, which follows from the Ulam triangle inequality.

What would settle it

A polynomial-time algorithm that computes a true Ulam median for every four-permutation instance would refute Theorem 1.1 unless P = NP. More directly, the reduction predicts that for every satisfiable balanced 3-CNF formula the optimal total Ulam distance is exactly $5s/2 - m$ and for every unsatisfiable formula it is strictly larger; exhaustive search over all small formulas could test this predicted separation and would fail without it.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.1: computing an Ulam median is NP-hard even when the input consists of exactly four permutations. The proof is a reduction from the restricted 3-SAT variant in which every clause has three literals and each variable has equally many positive and negative occurrences. For a formula with literal-occurrence set $\Sigma$, the reduction builds four permutations $L_1 = \beta_1 Z$, $L_2 = \beta_2 Z$, $R_1 = Z \alpha_1$, and $R_2 = Z \alpha_2$ over an alphabet $\Sigma \cup \{z_1,\dots,z_{2s+1}\}$. Here $\beta_1,\beta_2$ are clause gadgets whose longest common subsequence is $m$ exactly when a chosen true set hits every clause, $\alpha_1,\alpha_2$ are variable-consistency gadgets whose longest common subsequence is $s/2$ exactly when each variable's chosen false set contains all positives or all negatives, and the long anchor block $Z$ forces every optimal median into the canonical form $\tau_L Z \tau_R$. The reduction proves that the formula is satisfiable if and only if some permutation has total Ulam distance at most $5s/2 - m$ from all four inputs.

Load-bearing premise

The reduction inherits the NP-hardness of the balanced 3-SAT variant from earlier work; if that variant were actually tractable, the reduction would no longer imply NP-hardness.

Editorial extensions

If this is right

Unless P = NP, no polynomial-time algorithm can compute an exact Ulam median for four or more input permutations.
The known polynomial-time algorithm for three permutations and this four-permutation hardness close the problem: the smallest hard instance size is exactly four.
Every polynomial-time approximation algorithm for Ulam median is necessarily non-exact on four inputs unless P = NP.
Any fixed-parameter algorithm parameterized by the number of input permutations would have to become hard already at four inputs.
The result sharpens the algorithmic contrast with edit distance: requiring the median to be a permutation, rather than an arbitrary string, is what makes the four-input case hard.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A natural testable extension is to determine the best polynomial-time approximation ratio achievable for four-permutation Ulam median, since the reduction's hard threshold leaves room for approximation algorithms.
The anchor-block lemma is stated for arbitrary permutations of the literal occurrence set, so the same construction may transfer to other median problems with an LCS-type formulation, such as weighted or constrained rank aggregation.
The reduction may also yield hardness for Ulam center and for clustering under the Ulam metric with a fixed number of clusters, although the paper does not pursue those consequences.
If the threshold gap is robust under perturbation, the construction could be adapted to prove hardness of approximation for four-permutation Ulam median, but that claim is not established in the paper.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The result is exactly what it claims: computing an Ulam median is NP-hard for four input permutations, closing the gap between the polynomial-time three-permutation case and the previous unbounded-permutation hardness. The construction is clean and the proof is careful. The anchor-block lemma (Lemma 3.4) is the real new idea, and it is proved properly. It lets the reduction force any optimal median to place literal symbols entirely on one side of the anchor block, so the clause gadget and variable-consistency gadget act independently. That separation is what makes four permutations suffice, and I have not seen it before.

The fixed-partition analysis in Lemma 3.5 is sound, including the use of the elementary identity (★) to optimize the internal orders. The converse direction in Proposition 3.6 is tight: because LCS lengths are integral, attaining the threshold forces both upper bounds to be tight, and the construction of the satisfying assignment from the partition works. I checked the inequalities and the threshold computation 5s/2 - m; they line up.

Soft spots are minor. The reduction relies on the NP-hardness of the balanced 3-SAT variant (each literal occurs exactly twice), cited to BKS03. That is a standard published result, so it is not a real risk, but a referee may want the citation verified rather than taken on faith. The paper also claims the reduction is polynomial-time without spelling out the sizes; that is obvious enough. I would not ask for more than a sentence.

One small note: the author is a co-author of the earlier FGHS25 unbounded hardness paper, but that result is not used in the reduction, so there is no circularity. The self-citation is context.

This paper is for anyone working on rank aggregation or the complexity of median problems under string metrics. It is short, readable, and the main lemma is reusable. I would take it seriously and send it to a good referee. My own verdict is accept; there is nothing here that needs major revision.

Referee Report

0 major / 6 minor

Summary. The paper proves that computing an Ulam median is NP-hard even when the input consists of exactly four permutations. The proof is a direct Karp-style reduction from a balanced variant of 3-SAT in which every variable has equally many positive and negative occurrences (in fact, every literal appears exactly twice). The construction encodes each literal occurrence as a distinct symbol and builds four permutations: two clause-witness permutations L1, L2 and two variable-consistency permutations R1, R2, separated by a long anchor block Z of length 2s+1. The main technical tool is Lemma 3.4, which shows that any candidate median can be transformed into a canonical permutation of the form tau_L Z tau_R without decreasing any of the four LCS scores. Lemma 3.5 then computes the optimal total LCS for a fixed partition of the literal-occurrence symbols into S_L and S_R. Combining the gadget lemmas with the threshold 5s/2 - m yields Proposition 3.6: the formula is satisfiable if and only if there is a median whose total Ulam distance to the four inputs is at most 5s/2 - m. Together with the known polynomial-time algorithm for three permutations, this closes the gap between three inputs and an unbounded number of inputs.

Significance. If correct, this is a tight and significant result: it establishes that four is the smallest number of input permutations for which computing an Ulam median is NP-hard, and it sharply separates the Ulam median problem from the edit median on arbitrary strings, where a fixed number of inputs is polynomial-time solvable. The paper's strengths include a general and reusable anchor-block lemma, elementary and complete proofs of all internal lemmas, and a reduction with no free parameters. I checked the anchor-block transformation, the fixed-partition optimum, the equality cases in Lemma 3.3, and the threshold computation in Proposition 3.6; all are consistent. The only external ingredient is the cited NP-hardness of balanced 3-SAT, which is a standard published result and does not undermine the proof. The manuscript is clearly written and the central claim is fully supported.

minor comments (6)

[Abstract/Introduction] The phrase 'an Ulam median' should read 'a Ulam median' wherever it appears, and the abstract contains 'Fischeret al.' without the intended space before 'et al.'.
[Section 3, Lemma 3.5] Identity (★) is used as a black box; please add the one-line derivation from the Ulam triangle inequality, namely that d_U(tau,gamma1)+d_U(tau,gamma2) is at least d_U(gamma1,gamma2), with equality at tau=gamma1.
[Section 3, reduction setup] The NP-hardness of the balanced 3-SAT variant is the only external ingredient, and the threshold in Proposition 3.6 depends on the equality |Sigma+_x|=|Sigma-_x|; please state explicitly which theorem or result in [BKS03] establishes the exact variant used.
[Section 4, Step 1] The phrase 'the symbols of Sigma remain in their original locations' is slightly ambiguous; saying 'the positions occupied by the symbols of Sigma are unchanged' would be clearer.
[Section 4, Step 2b] The proof of the symmetric identity (3) is compressed; it would benefit from explicitly saying that the first symbol of Sigma in a common subsequence determines the threshold t >= M-s.
[Section 3, Proposition 3.6] The decision version of the problem is not discussed; noting that it lies in NP follows immediately from polynomial-time LCS computation, so the result is NP-completeness for the decision version as well as NP-hardness for the optimization version.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: proof is a direct reduction from an external NP-hard 3-SAT variant.

full rationale

The central claim is that Ulam median is NP-hard for exactly four input permutations. The proof is a direct polynomial-time reduction from a balanced variant of 3-SAT, specifically (3,B2)-SAT where every literal occurs exactly twice, cited externally to Berman, Karpinski, and Scott [BKS03]. All of the reduction's correctness lemmas are proved from elementary LCS properties: Lemma 3.2 analyzes the clause-witness gadget, Lemma 3.3 analyzes the variable-consistency gadget, Lemma 3.4 (the anchor-block lemma) is proved in Section 4 from first principles with no dependence on the 3-SAT instance, and Lemma 3.5 derives the fixed-partition optimum from the Ulam distance identity d_U = n - LCS and the triangle inequality encoded in identity (★). The threshold 5s/2 - m is computed from these proved bounds rather than fitted to any data or to the desired conclusion. The paper's prior work [FGHS25] is cited only to contrast the previous unbounded-number NP-hardness result and is not used as a premise in the current reduction. The only external dependency, NP-hardness of balanced 3-SAT, is a standard published result from the literature and does not reduce to the theorem being proved. No parameter is fitted and later renamed a prediction, and no definition presupposes the target result. The paper is therefore self-contained apart from a legitimate external NP-hardness source, with no circular step identified.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The construction introduces an anchor block of auxiliary symbols, but this is a formal gadget rather than a new conceptual entity; M = 2s+1 is a design choice, not a fitted parameter. The load-bearing external input is the NP-hardness of balanced 3-SAT, cited to BKS03. No new physical or conceptual entities are postulated.

assumptions (3)

standard math d_U(pi, sigma) = |Sigma| - LCS(pi, sigma)
Standard identity used throughout the paper; stated as Equation (1) in Section 2.
domain assumption Balanced 3-SAT (each variable has an equal number of positive and negative occurrences, in particular (3,B2)-SAT where every literal occurs exactly twice) is NP-hard
Used to ensure the s/2 threshold in Lemma 3.3; cited from Berman, Karpinski, and Scott [BKS03] in Section 3.
standard math max_tau [LCS(tau, gamma1) + LCS(tau, gamma2)] = |S| + LCS(gamma1, gamma2) for permutations gamma1, gamma2 of S
This identity (star) is proved in Lemma 3.5 via the Ulam triangle inequality and is used to optimize internal orderings.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Ulam Median is NP-hard for Four Permutations." pith.science (2026). https://pith.science/paper/OKYCZO47

@misc{pith2026260805544,
  author       = {Pith},
  title        = {Pith review of: Ulam Median is NP-hard for Four Permutations},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OKYCZO47}},
  note         = {Machine review of arXiv:2608.05544}
}

read the original abstract

We show that computing a median under the Ulam distance is NP-hard even when the input consists of exactly four permutations. Previously, NP-hardness was known only for an unbounded number of input permutations (Fischer et al., ESA '25). Our result is tight, since an Ulam median of three permutations can be computed in polynomial time (Chakraborty--Das--Krauthgamer, SODA '21).

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

14 extracted references · 10 canonical work pages

[1]

Procaccia, editors

[BCE+16] Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D. Procaccia, editors. Handbook of Computational Social Choice. Cambridge University Press, 2016.doi:10.1017/ CBO9781107446984. 1 [BFG+26] Tian Bai, Fedor V. Fomin, Petr A. Golovach, Yash Hiren More, and Simon Wietheger. Clustering permutations under the ulam metric: A parameter...

work page 2016
[11]

2 [ODL+20] Samuel E

doi:10.1007/3-540-44888-8\_23. 2 [ODL+20] Samuel E. L. Oliveira, Victor Diniz, Anísio Lacerda, Luiz H. C. Merschmann, and Gisele L. Pappa. Is rank aggregation effective in recommender systems? an experimental analysis.ACM Trans. Intell. Syst. Technol., 11(2):16:1–16:26, 2020.doi:10.1145/3365375. 1 [Pet26] Dominik Peters. Kemeny rank aggregation is NP-hard...

work page doi:10.1007/3-540-44888-8
[1959]

Median strings.Pattern Recognit

1 [Koh85] Teuvo Kohonen. Median strings.Pattern Recognit. Lett., 3(5):309–313, 1985.doi:10.1016/ 0167-8655(85)90061-3. 2 [LLQ+07] Yuting Liu, Tie-Yan Liu, Tao Qin, Zhiming Ma, and Hang Li. Supervised rank aggregation. In Carey L. Williamson, Mary Ellen Zurko, Peter F. Patel-Schneider, and Prashant J. Shenoy, editors,Proceedings of the 16th International C...

arXiv 1985
[1997]

2 [JKY25] Ragesh Jaiswal, Amit Kumar, and Jatin Yadav

URL:https://doi.org/10.1017/ cbo9780511574931,doi:10.1017/CBO9780511574931. 2 [JKY25] Ragesh Jaiswal, Amit Kumar, and Jatin Yadav. Robust-sorting and applications to ulam-median. In52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025), vol- ume 334 ofLIPIcs, pages 100:1–100:19, 2025.doi:10.4230/LIPIcs.ICALP.2025.100. 3 [Kem59]...

doi:10.1017/cbo9780511574931
[2000]

Rácz, Siena Ang, Djordje Jevdjic, Sergey Yekhanin, Luis Ceze, and Karin Strauss

2 [RMR+17] Cyrus Rashtchian, Konstantin Makarychev, Miklós Z. Rácz, Siena Ang, Djordje Jevdjic, Sergey Yekhanin, Luis Ceze, and Karin Strauss. Clustering billions of reads for DNA data storage. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, editors,Advances in Neural Information ...

work page 2017
[2003]

Approximating the median under the ulam metric

4 [CDK21] Diptarka Chakraborty, Debarati Das, and Robert Krauthgamer. Approximating the median under the ulam metric. In Dániel Marx, editor,Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 761–775. SIAM, 2021.doi:10.1137/1.9781611976465.48. 2, 3 [CDK23] Diptarka Chakraborty, De...

work page doi:10.1137/1.9781611976465.48 2021
[2013]

2 [Gus97] Dan Gusfield.Algorithms on Strings, Trees, and Sequences - Computer Science and Com- putational Biology

URL:https://doi.org/10.1038/ nature11875,doi:10.1038/NATURE11875. 2 [Gus97] Dan Gusfield.Algorithms on Strings, Trees, and Sequences - Computer Science and Com- putational Biology. Cambridge University Press,

work page doi:10.1038/nature11875
[2017]

2 [YL78] H

URL:https://proceedings.neurips.cc/paper/ 2017/hash/ab7314887865c4265e896c6e209d1cd6-Abstract.html. 2 [YL78] H. Peyton Young and Arthur Levenglick. A consistent extension of condorcet’s election prin- ciple.SIAM Journal on applied Mathematics, 35(2):285–300,

work page 2017

Show all 14 references

[2019]

The complexity of kemeny aggregation with three rankings.CoRR, abs/2607.28588, 2026.arXiv:2607.28588

1 [Mad26] Péter Madarasi. The complexity of kemeny aggregation with three rankings.CoRR, abs/2607.28588, 2026.arXiv:2607.28588. 1 [MJC00] Carlos D. Martínez-Hinarejos, Alfons Juan, and Francisco Casacuberta. Use of median string for classification. In15th International Confere...

2026 arXiv
[2021]

2021.12,doi:10.4230/LIPICS.FSTTCS.2021.12

URL:https://doi.org/10.4230/LIPIcs.FSTTCS. 2021.12,doi:10.4230/LIPICS.FSTTCS.2021.12. 2 [CMS01] Graham Cormode, S. Muthukrishnan, and Süleyman Cenk Sahinalp. Permutation editing and matching via embeddings. In Fernando Orejas, Paul G. Spirakis, and Jan van Leeuwen, edi- tors,A...

2021
[2022]

2 [CDN26] Amir Carmel, Debarati Das, and Tien-Long Nguyen

URL:http://papers.nips.cc/paper_files/paper/2022/hash/ 974309ef51ebd89034adc64a57e304f2-Abstract-Conference.html. 2 [CDN26] Amir Carmel, Debarati Das, and Tien-Long Nguyen. A scalable and unified framework to weighted rank aggregation. In53rd International Colloquium on Automa...

2022 doi
[2023]

2, 3 [CDKS22] Diptarka Chakraborty, Syamantak Das, Arindam Khan, and Aditya Subramanian

URL:https://doi.org/10.4230/LIPIcs.ITCS.2023.31, doi:10.4230/LIPICS.ITCS.2023.31. 2, 3 [CDKS22] Diptarka Chakraborty, Syamantak Das, Arindam Khan, and Aditya Subramanian. Fair rank aggregation. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, edit...

2023 doi
[2025]

URL:https:// drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.111,doi:10.4230/ LIPIcs.ESA.2025.111

Schloss Dagstuhl – Leibniz-Zentrum für Informatik. URL:https:// drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.111,doi:10.4230/ LIPIcs.ESA.2025.111. 2 [FKS03] Ronald Fagin, Ravi Kumar, and D. Sivakumar. Efficient similarity search and classification via rank aggre...

2025
[2026]

1 [Pev00] Pavel A

URL:https: //arxiv.org/abs/2607.25540,arXiv:2607.25540. 1 [Pev00] Pavel A. Pevzner.Computational molecular biology - an algorithmic approach. MIT Press,

arXiv

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.

[1] [1]

Procaccia, editors

[BCE+16] Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D. Procaccia, editors. Handbook of Computational Social Choice. Cambridge University Press, 2016.doi:10.1017/ CBO9781107446984. 1 [BFG+26] Tian Bai, Fedor V. Fomin, Petr A. Golovach, Yash Hiren More, and Simon Wietheger. Clustering permutations under the ulam metric: A parameter...

work page 2016

[2] [11]

2 [ODL+20] Samuel E

doi:10.1007/3-540-44888-8\_23. 2 [ODL+20] Samuel E. L. Oliveira, Victor Diniz, Anísio Lacerda, Luiz H. C. Merschmann, and Gisele L. Pappa. Is rank aggregation effective in recommender systems? an experimental analysis.ACM Trans. Intell. Syst. Technol., 11(2):16:1–16:26, 2020.doi:10.1145/3365375. 1 [Pet26] Dominik Peters. Kemeny rank aggregation is NP-hard...

work page doi:10.1007/3-540-44888-8

[3] [1959]

Median strings.Pattern Recognit

1 [Koh85] Teuvo Kohonen. Median strings.Pattern Recognit. Lett., 3(5):309–313, 1985.doi:10.1016/ 0167-8655(85)90061-3. 2 [LLQ+07] Yuting Liu, Tie-Yan Liu, Tao Qin, Zhiming Ma, and Hang Li. Supervised rank aggregation. In Carey L. Williamson, Mary Ellen Zurko, Peter F. Patel-Schneider, and Prashant J. Shenoy, editors,Proceedings of the 16th International C...

arXiv 1985

[4] [1997]

2 [JKY25] Ragesh Jaiswal, Amit Kumar, and Jatin Yadav

URL:https://doi.org/10.1017/ cbo9780511574931,doi:10.1017/CBO9780511574931. 2 [JKY25] Ragesh Jaiswal, Amit Kumar, and Jatin Yadav. Robust-sorting and applications to ulam-median. In52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025), vol- ume 334 ofLIPIcs, pages 100:1–100:19, 2025.doi:10.4230/LIPIcs.ICALP.2025.100. 3 [Kem59]...

doi:10.1017/cbo9780511574931

[5] [2000]

Rácz, Siena Ang, Djordje Jevdjic, Sergey Yekhanin, Luis Ceze, and Karin Strauss

2 [RMR+17] Cyrus Rashtchian, Konstantin Makarychev, Miklós Z. Rácz, Siena Ang, Djordje Jevdjic, Sergey Yekhanin, Luis Ceze, and Karin Strauss. Clustering billions of reads for DNA data storage. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, editors,Advances in Neural Information ...

work page 2017

[6] [2003]

Approximating the median under the ulam metric

4 [CDK21] Diptarka Chakraborty, Debarati Das, and Robert Krauthgamer. Approximating the median under the ulam metric. In Dániel Marx, editor,Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 761–775. SIAM, 2021.doi:10.1137/1.9781611976465.48. 2, 3 [CDK23] Diptarka Chakraborty, De...

work page doi:10.1137/1.9781611976465.48 2021

[7] [2013]

2 [Gus97] Dan Gusfield.Algorithms on Strings, Trees, and Sequences - Computer Science and Com- putational Biology

URL:https://doi.org/10.1038/ nature11875,doi:10.1038/NATURE11875. 2 [Gus97] Dan Gusfield.Algorithms on Strings, Trees, and Sequences - Computer Science and Com- putational Biology. Cambridge University Press,

work page doi:10.1038/nature11875

[8] [2017]

2 [YL78] H

URL:https://proceedings.neurips.cc/paper/ 2017/hash/ab7314887865c4265e896c6e209d1cd6-Abstract.html. 2 [YL78] H. Peyton Young and Arthur Levenglick. A consistent extension of condorcet’s election prin- ciple.SIAM Journal on applied Mathematics, 35(2):285–300,

work page 2017