CS Paper Radar

Lexicographic Social Ranking on Monotonic Coalitional Rankings

Felix Fritz, Stefano Moretti

cs.GT ·submitted 2026-08-25 14:19 UTC · v1
published

Abstract

Recent studies on social rankings in coalitional settings have introduced methods that rank individuals by lexicographically comparing vectors of their occurrences across coalitions ordered according to their strength. In this work, we focus on two such solutions: the lexicographical excellence (lex-cel) solution, which disregards coalition size, and the L^(1) solution, which additionally prioritizes smaller coalitions through a double lexicographic comparison. We investigate the combinatorial connections between these two solutions on monotonic coalitional rankings, where equivalence classes are compactly represented through sets of minimal (with respect to set inclusion) coalitions. After introducing general formulas for computing the lex-cel and L^(1) parameter vectors from these minimal coalitions, we also present worst-case running time results. Finally, to further explore the behavior of the two solutions through simulations designed to assess the distance of the rankings they produce, we show that the monotonicity assumption does not lead to actual redundancy in the rankings produced by the two solutions.

Comment
18 pages, 1 figure, slightly modified version to be published in ADT 2026 - 9th International conference on Algorithmic Decision Theory

Closest papers

Nearest neighbours by meaning across the whole index.

Proportionality in Ranking Compression

cs.GT cs.LGecon.TH ·2026-10-16 ·Daniel Halpern, Xinyu Liu, Evi Micha, Yu Peng Ng, Warut Suksompong
top venuetheory similarity 0.61
Abstract · Appears in the 40th Annual Conference on Neural Information Processing Systems (NeurIPS), 2026

Motivated by applications in reinforcement learning from human feedback, we consider a setting where a given collection of rankings needs to be compressed into a smaller collection of rankings. This can also be seen as a combination of two fundamental social choice frameworks: ranking aggregation and multiwinner voting. We propose three proportionality notions that capture different types of representation in this setting: positional proportionality, pairwise proportionality, and proportionality for solid coalitions (PSC). On the one hand, we show that positional proportionality and PSC are always satisfiable for any input rankings and target compression size, and a desired output can be found in polynomial time. On the other hand, we prove that pairwise proportionality cannot be satisfied in general, but can nevertheless be attained when the input rankings are single-peaked or single-crossing.

0.33

Sampford Apportionment Satisfies Threshold Monotonicity

cs.GT ·2026-08-24 ·Haris Aziz, Simon Mackenzie, Mashbat Suzuki
theory similarity 0.59
Abstract

Apportionment distributes a fixed number of legislative seats among political parties in proportion to their vote shares. Randomization can satisfy quota in every realization and exact proportionality in expectation, but these requirements determine only the parties' marginal seat distributions. We study threshold monotonicity, which requires that when every standard quota inside a coalition weakly increases and every standard quota outside it weakly decreases, the coalition's new seat total stochastically dominates its old one. We prove that Sampford apportionment satisfies threshold monotonicity, resolving the threshold-monotonicity conjecture of Correa et al. (2024). Complementing this result, we prove that no quota-respecting, ex-ante proportional method satisfies pairwise threshold monotonicity even for disjoint coalitions when there are at least seven parties. This impossibility applies whether or not the method has full support.

0.28

Pair Difficulty Matters: Rethinking Pairwise LLM-as-a-Judge Evaluation and Consistency

cs.CL ·2026-09-29 ·Bruno Brocai, Maria Becker
top venuepositioncode/data similarity 0.56
Abstract · Accepted as an EMNLP Main 2026 short paper (2676). v2: Improve graph labels. v3: Correct theoretical argument

Large Language Model judges are widely used to rank texts and text-generating systems through pairwise comparison, and their reliability is typically assessed via three proxies: position bias, transitivity, and pairwise agreement (self- or human-labeled). Because these proxies drive judge selection and benchmarking, a substantial literature reporting that judges perform poorly on them risks steering practitioners away from otherwise capable evaluators. We argue this assessment is misleading. Under the Bradley--Terry geometry underlying pairwise aggregation, each proxy is dominated by close-rank-gap pairs, where inconsistency is expected and errors cost little aggregate ranking accuracy; far-gap pairs determine the ranking accuracy but barely move the proxies. We formalize this argument and validate it in a controlled simulation and on two human-rated corpora: the proxies correlate only weakly with ranking accuracy against gold, and their predictive component concentrates in the far-gap regime. Judges should therefore be assessed on rank-gap-conditional metrics, ideally against human rankings. Code at https://github.com/brunobrocai/PairDifficulty

0.73

Large player classes and approximately weighted voting

cs.GT econ.THmath.OC ·2026-10-06 ·Ezra Einy, Ori Haimanko
theory similarity 0.56
Abstract

It is known that completeness of the coalitional ($C$-)desirability relation in a simple game does not imply the existence of a weighted-majority representation. We show that weightedness is implied in an approximate sense. Call an $n$-player simple game $\varepsilon$-weighted if, for some weight vector in the $(n-1)$-simplex, any losing coalition weight exceeds any winning coalition weight by at most $\varepsilon$; let $\varepsilon^{\ast}$ be the smallest such $\varepsilon$. We establish an upper bound on $\varepsilon^{\ast}$ in a general $C$-complete game, and deduce that, if all classes of equally desirable players become large asymptotically but the number of classes is bounded, then $\varepsilon^{\ast}=O(1/n_{\min})$ for the minimal player class size $n_{\min}$, and the bound is tight. Importantly, the minimal attainable fraction $δ$ of coalitions mislabeled by a weighting rule also tends to $0$ when $n_{\min}\rightarrow\infty$ and the number of player classes is bounded, with $δ=O(1/\sqrt{n_{\min}})$.

0.12

Metric Distortion of Social Welfare Functions

cs.GT cs.MA ·2026-08-22 ·Fatih Erdem Kizilkaya, Aaryaman Aggarwal, Evi Micha
similarity 0.55
Abstract · 11 pages, 1 table

Metric distortion has primarily been studied for social choice functions, which select a single winner from ordinal preferences. We extend this framework to social welfare functions, which output a ranking of $m$ candidates. We associate each voter $v$ with a monotone weight vector $\mathbf{w}_v = (w_{v1},\ldots,w_{vm})$, specifying the importance of the $i$-th position for voter $v$, and define the cost of a ranking as the position-weighted sum of their distances to the ranked candidates. This model generalizes both single-winner voting and committee selection. We consider three information regimes. First, we study the setting where the positional weight vectors are known. A natural approach recursively applies a single-winner rule with distortion $β$ to construct the ranking one position at a time. We show that this yields distortion at most $3β$ in general. This gap is not merely an artifact of the analysis: we show that no analysis based solely on per-round guarantees can certify a bound better than $2β$. By exploiting structural properties specific to Fractional Veto of Kizilkaya and Kempe, we show that its recursive extension achieves the optimal distortion of 3. Second, when all voters share the same unknown weight vector, recursively applying any social choice function with distortion $β$ achieves distortion at most $1+(β-1)\text{range}(\mathbf{w})$, where $\text{range}(\mathbf{w})=(w_1-w_m)/w_1$ denotes the normalized range of the common weight vector $\mathbf{w}$. Finally, we study unknown heterogeneous weights. Without further assumptions, every rule has unbounded distortion. We therefore consider two natural normalizations: unit-sum, where each voter distributes one unit of value across the ranking, and unit-top, where every voter assigns unit value to the first position. Under both models, we show that the optimal distortion is $Θ(m)$.

0.40

Condorcet-type properties of the linear ordering problem with ties

cs.GT math.COmath.OC ·2026-09-17 ·Daichi Kawashima, Noriyoshi Sukegawa
similarity 0.55
Abstract

The Kemeny rule aggregates multiple strict rankings into a single strict ranking that minimizes the sum of its distances from the input rankings. The resulting optimization problem, called the Kemeny problem (\texttt{KP}), is a special case of the linear ordering problem (\texttt{LOP}). The Kemeny rule satisfies several desirable properties in social choice theory, including the extended Condorcet criterion (\texttt{XCC}). Ando et al. strengthened this result by introducing the strong Condorcet criterion (\texttt{SCC}) and showing that it holds for every optimal solution to an arbitrary \texttt{LOP} instance. Yoo and Escobedo extended the Kemeny rule to rankings with ties and showed that the resulting rule satisfies the non-strict extended Condorcet criterion (\texttt{NXCC}). This criterion gives a condition under which one candidate must be ranked strictly above another in every optimal solution. In this paper, we introduce the non-strict strong Condorcet criterion (\texttt{NSCC}), a counterpart of the \texttt{SCC} for rankings with ties, and show that it holds for every optimal solution to an arbitrary instance of the linear ordering problem with ties (\texttt{LOPT}). We also establish a complementary structural property that gives conditions under which two candidates must be tied in every optimal solution to an arbitrary \texttt{LOPT} instance.

0.13

Coalitions, Stability, and Majority Jackpots: Frameworks for Unifying Majoritarian and Proportional Allocation in Multiwinner Elections

cs.GT ·2026-11-02 ·Kit Scriven, Nitin Kohli
similarity 0.55
Abstract

Social choice literature on multiwinner elections tends to focus on characterizing two distinct tasks: majoritarian representation and proportional representation. However, many real world systems can be viewed as operating between these two extremes, such as majority jackpot systems used in several countries throughout history. Towards the goal of better understanding these systems from a social choice perspective, we introduce two frameworks that encompass existing desiderata for majoritarian and proportional settings: coalitions, which encompasses properties such as fixed majority and solid coalitions; and stability, which encompasses various generalizations of Condorcet's criterion for single-winner elections, such as Gehrlein stability and local stability, among others. We develop theory and tools that characterize the mathematical and computational aspects of both frameworks across a wide array of preference structures (such as the unrestricted domain over candidates and the restricted domain of party lists). Building on this foundation, we shed new light on majority jackpot electoral systems, which to date have received limited mathematical analysis in the social choice literature.

0.14

Knowing Which, Not How Much: Language Models Order Party Positions They Cannot Place

cs.CL cs.CY ·2026-11-16 ·Yousef Attia, Jarosław A. Chudziak
publishedbenchmark similarity 0.53
Abstract · Accepted at the 40th Pacific Asia Conference on Language, Information and Computation (PACLIC 40)

Language models are increasingly asked where real actors stand: what a party's platform prioritises, what an institution has committed to. Such judgments are gradable, carrying both an order and a magnitude. Nearly every benchmark that tests them asks about one entity at a time, then reads that score as the model's knowledge of the domain. Order and magnitude, however, need not be acquired together. Text about social entities carries far more comparison than measurement, so a model may hold a dependable ordering with no anchored scale beneath it. We ask whether a model can place a documented social position on a scale or only order the actors it compares, and what that means for how such knowledge is measured. We test this on party positions in Japan and South Korea, where the Comparative Manifesto Project's coded data supplies a rare external answer key. Asked to order four parties, models beat the strongest fixed-answer baseline by more than a factor of two; asked to place one party on the same scale, they fall below it. The ordering survives inside those failed placements, and supplying the coded values lifts placement to near ceiling. Comparative and absolute questions about the same fact therefore measure different things here, and for party issue salience a benchmark built from one cannot speak for the other.

0.33