PaperlayerView exact revision on arXiv

Source-linked AI summary

Large player classes and approximately weighted voting

Ezra Einy, Ori Haimanko

arXiv:2610.08968v1econ.THcs.GTmath.OC

TL;DR

C-completeness alone does not ensure a weighted-majority representation for a finite simple game. The paper defines approximate weightedness and bounds its threshold in C-complete games. As player classes grow, the threshold vanishes under stated conditions, with a tight rate for bounded class count, while coalition misclassification also vanishes in that case.

  • Problem

    C-completeness of a simple game does not guarantee that the game has a weighted-majority representation.

    Source: §1.1 · p. 2

  • Method

    The paper defines ε-weightedness through a bound on the excess of losing-coalition weight over winning-coalition weight and studies its minimum threshold ε*.

    Source: §1.2 · p. 3

  • Results

    ε* tends to zero when n_min grows and the number of classes is subexponential in n_min; with bounded class count, ε*=O(1/n_min), and the rate is tight.

    Source: §7 · p. 24

  • Takeaways & Limitations

    With bounded player-class count, the minimum fraction δ of coalitions mislabeled by weighting also tends to zero as player classes grow.

    Source: §7 · p. 25

    The asymptotic result does not determine the sign of ε*, which may remain positive along an entire sequence of games.

    Source: §7.2 · p. 25

Abstract

from arXiv · show

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 $\delta$ 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 $\delta=O(1/\sqrt{n_{\min}})$.

1 Introduction

C-completeness does not guarantee full weightedness in finite simple games, but the paper shows it supports approximate weightedness as player classes grow. It also studies when this approximation corresponds to fewer coalition misclassifications.

1.1 The background

  • C-completeness is necessary but not sufficient for weightedness in finite simple games, motivating an asymptotic route to approximate weightedness.The paper contrasts this with the continuum result of Einy and Neyman (1990), which obtains weightedness under continuity assumptions.Source: §1.1 · p. 2

1.2 Approximate weightedness and the main results

  • For a C-complete game, ε* is bounded above by (log2 d + 2)/n_min; with subexponential d it tends to zero as n_min grows, and with bounded d its O(1/n_min) rate is tight.Here d is the number of player classes and n_min is the size of the smallest class.Source: §1.2 · p. 3

1.3 Alternative approaches

  • The paper distinguishes ε-weightedness, which minimizes a normalized weight difference, from α-rough weightedness, which minimizes a ratio; their thresholds are closely linked under stated qualifications.The convergence of ε* to zero is equivalent to convergence of μ to 1 when minimal winning coalitions do not become negligible under an optimal weight vector.Source: §1.3 · pp. 4–5

1.4 Misclassification measure

  • The misclassification measure δ is the minimum fraction of coalitions assigned the wrong status by a weighted-majority representation, and it vanishes alongside ε* in the bounded-class asymptotic case.The paper presents δ as a normalized form of the outlier value defined in earlier work.Source: §1.4 · p. 5

1.5 This paper’s structure

  • The paper develops the framework and threshold in Section 2, proves general bounds and asymptotic convergence in Section 3, and studies tightness, alternative measures, and misclassification in later sections.Proofs are deferred to the Appendix except for main steps in the proof of Theorem 10 and the proof of [truncated].Source: §1.5 · pp. 5–6

2 Preliminaries and basic notions

The preliminaries define simple games and desirability relations, characterize C-completeness through 2-trade robustness, and represent player classes by coalition profiles. They then define approximate weightedness and its threshold.

2.1 Simple games and desirability relations

  • A game is C-complete exactly when it is 2-trade robust: no two winning and two losing coalitions can form a 2-trade.A 2-trade balances each player's membership count across the two winning and two losing coalitions.Source: §2.1 · p. 7

2.2 Player classes

  • In an I-complete game, players form an ordered chain of equivalence classes, and a coalition profile counts its members in each class.Winning and losing profiles are respectively up-closed and down-closed in the coordinatewise order.Source: §2.2 · p. 8

Proposition 5 (Equivalence classes are symmetry classes). If G is I-complete,

  • For I-complete games, equivalence classes are symmetry classes, so permutations preserving each player class capture the game's symmetries.The proposition frames C-completeness as a profile counterpart to the preceding 2-trade characterization.Source: Proposition 5 (Equivalence classes are… · p. 8

2.3 Weightedness, ε-weightedness and the loss-win-excess threshold

  • A game is ε-weighted when some normalized player weights and quota limit how much a losing coalition can outweigh a winning one; ε* is the least achievable excess.The threshold is a minimax value: the game is ε-weighted exactly when ε is at least ε*, and it is fully weighted exactly when ε* is negative.Source: §2.3 · pp. 9–10
  • For I-complete games, ε* can be computed through a minimax formula over convex hulls of winning and losing profiles, with an optimal weight vector constant within each player class.The stated formula uses the convex hulls of the winning and losing profile sets.Source: §2.3 · p. 10

3 The main results

For C-complete games, the paper bounds the loss-win-excess threshold and shows how profile structure yields that bound. When player classes grow and their number is controlled, the threshold vanishes at a tight rate.

3.1 Bounds on the loss-win-excess threshold

  • For a C-complete game with d player classes and smallest class size n_min, ε* has the uniform upper bound (log2 d + 2)/n_min.The theorem also gives a lower bound, which applies to I-complete games generally; the supplied passage does not state its value.Source: §3.1 · p. 11

3.2 Proof of Theorem 10

  • C-completeness implies approximate midpoint convexity of winning and losing profile sets, enabling a convex-analysis proof of the threshold bound.The proof uses the profile version of 2-trade robustness to derive these properties.Source: §3.2.1 · p. 12

3.2.1 Approximate midpoint convexity

  • Rounded midpoints preserve status: rounding winning-profile averages upward and losing-profile averages downward yields profiles with the same status.This is the finite-profile substitute for exact midpoint convexity.Source: §3.2.1 · pp. 12–13

3.2.2 Approximating convex combinations by pure profiles

  • Approximate midpoint convexity extends to convex combinations: a winning or losing pure profile can be found within a bounded coordinate error.The error is bounded using the approximation result of Dilworth et al. (1999).Source: §3.2.2 · p. 13

3.2.3 Conclusion of the proof

  • The proof applies bounded-error profile approximations to maximizing winning and losing profiles, then uses up-closedness to derive a contradiction and bound ε*.A losing profile forced into the winning set would contradict the disjointness of winning and losing profiles.Source: §3.2.3 · p. 14

3.3 Asymptotics with large player classes

  • If n_min grows while the number of classes is subexponential in n_min, ε* tends to zero; with bounded class count, its O(1/n_min) rate is tight.The player classes need not be comparable in size; a fixed positive fraction of the electorate in each class automatically bounds their number.Source: §3.3 · p. 15
  • Nonweightedness among the highlighted C-complete cases requires at least three player classes and at least two shift-minimal winning profiles.For two classes or a single shift-minimal winning profile, the stated C-complete cases are weighted.Source: §3.3 · pp. 15–16

4 Asymptotic tightness of the ε∗convergence rate

This section constructs C-complete games showing that the O(1/n_min) upper bound on ε∗ is asymptotically tight. It also shows that C-completeness and acyclicity of strict C-desirability do not ensure rough weightedness, even in a constant-sum example.

4.1 Flip games

  • Flip games reverse the weight-indicated winning status at the quota and one level below it, while other coalition weights determine status by weight.The construction uses this near-quota reversal to build games close to a weighted-game structure.Source: §4 · p. 16

Definition 17 (Three-class games

  • For every m ≥ 5, eG_m with q = 60 is a C-complete flip game whose three player classes each have size m (n_min = m), and Proposition 18 gives ε* = Θ(1/n_min).The classes have integer weights 20, 15, and 12, respectively.Source: Definition 17 (Three-class games · p. 17

Corollary 19 (Asymptotic tightness of the convergence rate in Theorem

4.3 Acyclicity of ≻C does not imply (any of our notions of) weightedness

  • Acyclic strict C-desirability does not guarantee rough weightedness, even as the number of players grows: eG_m is acyclic but not roughly weighted.For m = 5, eG_5 has 15 players and is not ε-weighted for any ε < 1/235.Source: §4.3 · p. 19
  • A 14-player alternative is constant-sum and C-complete, with acyclic strict C-desirability and ε∗ = 1/307 > 0.This provides a smaller constant-sum example of the same failure of acyclicity to ensure weightedness.Source: §4.3 · p. 20

5 Asymptotic α-rough weightedness

The section relates the loss-win-excess threshold ε∗ to the critical threshold µ used for α-rough weightedness. For proper C-complete games, their asymptotic behavior is linked; for some improper games, µ can miss convergence of ε∗.

5 Asymptotic α-rough weightedness

  • For proper C-complete games, ε∗ tending to zero is equivalent to µ tending to 1; when the games are strong, the relation between the thresholds holds with equality.With uniformly bounded class count, the stated asymptotic bound is µ(G_n) = 1 + O(1/n_min).Source: §5 · p. 20, Definition 21 (α-rough weightedness… · p. 21

Definition 21 (α-rough weightedness and threshold µ; Freixas and Kurz

  • ε∗ measures the maximal losing-versus-winning weight difference, whereas µ is the least maximal-losing to minimal-winning weight ratio.The optimal weight vectors for the two thresholds may differ, even after rescaling.Source: Definition 21 (α-rough weightedness… · p. 21
  • For improper games, ε∗ can converge to zero without µ converging to 1: eG_m has µ(eG_m) = 60/59 > 1 while ε∗(eG_m) tends to zero.The paper notes that the two thresholds may therefore decouple outside the proper-game setting.Source: Definition 21 (α-rough weightedness… · pp. 21–22
  • In the eG_m example, the decoupling is tied to optimal winning-coalition weight tending to zero; all coalitions with at least six players are automatically winning.The authors characterize this as an isolated phenomenon.Source: Definition 21 (α-rough weightedness… · p. 22

6 Misclassification measure reflects approximate

A small loss-win-excess threshold does not itself correct coalitions mislabeled by a weighting rule. However, when player classes grow and their number is bounded, both the threshold and the least misclassified fraction vanish, at rates O(1/nmin) and O(1/√nmin), respectively.

weightedness

  • A coalition mislabeled by an ε*-optimal weighting remains ε*-close in weight to its correct status, but this closeness does not fix the mislabeling.Source: §6 · p. 22

Definition 26 (Misclassification measure). For G = (N, W), let

  • The misclassification measure δ(G) is the least fraction of coalitions mislabeled by a weight system, equivalently the error probability for a uniformly random coalition.Source: Definition 26 (Misclassification… · p. 23
  • For sufficiently large M, δ(G) equals the normalized outlier value, the minimal fraction declared outliers so the remaining coalitions can be weighted.Source: Definition 26 (Misclassification… · p. 23
  • Both δ and ε* tend to zero under the stated slower-growth condition (log2 dn + 2)√dn = o(√nmin), even when the class count is not bounded.The corollary assumes nmin tends to infinity.Source: Definition 26 (Misclassification… · p. 24
  • With a bounded number of player classes, ε* = O(1/nmin) and δ = O(1/√nmin), and both measures tend to zero as nmin grows.The paper also states that the ε* rate is asymptotically tight.Source: Definition 26 (Misclassification… · p. 24

7 Concluding remarks

C-completeness yields quantitative approximate weightedness, with convergence controlled by the smallest player class and the number of classes. The concluding discussion qualifies the bound, distinguishes approximate from full weightedness, and raises an open question for constant-sum games.

7 Concluding remarks

  • For any C-complete game with d classes, ε* ≤ (log2 d + 2)/n_min, independently of the total player count and largest class size.The bound requires only completeness of the coalitional desirability relation; the strict part need not be acyclic.Source: §7 · p. 24
  • When n_min grows and d is subexponential in n_min, ε* tends to 0; for bounded d, convergence is O(1/n_min) and the order is tight.The tightness statement is supported by a sequence with three player classes and ε* = Θ(1/n_min).Source: §7 · pp. 24–25
  • The concluding discussion also relates the fall of ε* to δ, the minimal fraction of coalitions mislabeled by a weighted representation.The cited passage states this relation for growing n_min and a bounded number of classes.Source: §7 · p. 25

7.1 How overestimating is the constant factor in the bound?

  • The bound’s log2 d + 2 factor comes from rounding midpoint convexity and converting approximate midpoint convexity to general convexity.The authors note that this factor could in principle be reducible because the winning and losing profile sets have special structure.Source: §7.1 · p. 25

7.2 Is full weightedness ever obtainable in the limit?

  • Convergence of ε* to zero does not establish eventual full weightedness: ε* may remain positive along an entire sequence.The authors ask whether a natural strengthening of the large-class assumption would guarantee that ε* eventually falls below zero.Source: §7.2 · p. 25

7.3 Does ε* converge to zero faster in constant-sum games?

  • Whether a quadratic-in-1/n_min bound holds asymptotically for general C-complete constant-sum games remains unknown.The authors suggest the quadratic rate seen in flip games may be relevant to the general constant-sum case.Source: §7.3 · p. 26

8 Appendix

The appendix supplies proof components linking C-completeness to trade robustness and player-class symmetry. It also reduces the weight optimization to class-constant vectors.

8.1 Proof of Proposition 4

  • The appendix proves both directions of the equivalence between C-completeness and 2-trade robustness for coalition profiles.A failed completeness condition yields the relevant opposing winning and losing coalitions; the reverse construction produces C-incomparability from a violating trade.Source: §8.1 · p. 26

8.2 Proof of Proposition 5

  • The game’s automorphisms are precisely permutations preserving each I-desirability class, and every within-class permutation is an automorphism.The proof establishes this by showing that automorphisms preserve the desirability ranking and that within-class transpositions are automorphisms.Source: §8.2 · p. 27

8.3 Proof of Proposition 6

  • C-completeness is characterized by the absence of equal-sum pairs of winning and losing profiles.The proof constructs coalitions realizing the profiles and shows that such a pair would make two coalitions C-incomparable.Source: §8.3 · pp. 27–28

8.4 Proof of Proposition 9

  • A minimizer of the loss-win-excess objective can be averaged over game automorphisms, yielding a minimizer constant on each player class.The proof uses invariance of the objective under automorphisms and the characterization of automorphisms as class-preserving permutations.Source: §8.4 · p. 29

8.5 Proof components of Theorem 10 that are missing in Section 3.2

These appendix proofs establish profile-level midpoint properties, derive a distance bound, and verify lower-bound and constructed-game claims. They also constrain how desirability cycles could behave in the flip game.

8.5.1 Proof of Lemma 11

  • For C-complete games, the midpoint of two winning profiles cannot be a losing profile when that midpoint is an allowed profile.The proof applies the profile characterization of C-completeness to the two winning profiles and their midpoint.Source: §8.5.1 · p. 29

8.5.2 Proof of Lemma 12

  • Rounded midpoints of winning profiles remain winning, and the symmetric rounded-midpoint property holds for losing profiles.The proof adjusts coordinates with odd sums by one and uses the up-closedness of winning profiles and down-closedness of losing profiles.Source: §8.5.2 · p. 30

8.5.3 Proof of Lemma 13

  • A midpoint-distance condition yields sup-norm proximity to the winning and losing profile sets from their convex hulls.The proof applies the Dilworth et al. result to convert approximate midpoint convexity into a distance bound.Source: §8.5.3 · pp. 30–31

8.5.4 Proof of the lower bound in inequality (8) of Theorem 10

  • In establishing the lower bound for ε∗(G), the argument obtains minA∈W w∗(A) = 0 ≤ maxB∈L w∗(B), and therefore ε∗(G) ≥0.Source: §8.5.4 · p. 31

8.6 Proof of Proposition 16

  • The flip-game construction is C-complete and admits weights giving ε* ≤ 1/W(N).The proof verifies the required unattained weight levels and uses attained weights q − 1 and q to obtain the bound.Source: §8.6 · p. 32

8.7 Proof of Proposition 18

  • The constructed three-class sequence has C-complete games with ε* ≤ 1/(47m) for class size m ≥ 5.The three class sizes are (m, m, m), so n_min = m.Source: §8.7 · p. 32

8.8 Proof of Proposition 20

  • In the flip-game cycle argument, rises cannot be consecutive, while the total weight change would require at least twice as many rises as drops.Since every rise must be followed by a drop, the two count constraints rule out a presumed cycle.Source: §8.8 · p. 34

8.9 Proof of the claims made in Remark 5 on the 14-player game (a sketch)

The appendix verifies claims about a 14-player example, proves a bound equality, and establishes the rough-weightedness ratio for a constructed game.

8.9 Proof of the claims made in Remark 5 on the 14-player game (a sketch)

  • For the 14-player game, the proof obtains ε* = 1/307 and sketches why the strict C-desirability relation is acyclic.The equality follows from the exhibited profile difference; the acyclicity argument tracks permitted weight rises and drops.Source: §8.9 · pp. 34–35

8.10 Proof of Proposition 22

  • The proof establishes equality in the stated bound (19) for μ(G).The displayed expression in the proof is (1 + ε*(G))/(1 − ε*(G)).Source: §8.10 · p. 37

8.11 Proof of Proposition 24

  • For the constructed game, the proof matches the lower and upper bounds at a rough-weighting ratio of 60/59.It derives α ≥ 60/59 for any rough weighting and exhibits a weight vector achieving that ratio.Source: §8.11 · p. 38

8.12 Proof of Proposition 25

The proof establishes convergence of the critical threshold when the approximation error tends to zero, with an O(1/n_min) bound. It also develops a class-normalized weighting argument and interprets misclassification probability over uniformly random coalitions.

8.12 Proof of Proposition 25

  • µ(G_n) tends to 1 whenever ε*(G_n) tends to 0, and µ(G_n) = 1 + O(1/n_min).Source: §8.12 · p. 38

8.13 Proof of Proposition 27

  • The minimum misclassification probability δ(G) is the probability that a weighting misclassifies a uniformly random coalition, with each player independently included with probability 1/2.Source: §8.13 · p. 38
  • For a random coalition, the proof writes its weight as a sum of independent random variables and applies the Berry–Esseen theorem.Source: §8.13 · p. 39
  • The proof considers weights constant within each player class and normalized by the sum of representative class weights.Source: §8.13 · p. 40
  • A weight system based on W* classifies every winning coalition correctly; any misclassified losing coalition has weight between q* and q* + τ(G).Source: §8.13 · p. 40

8.14 Proof of Proposition 29

The proof uses constant-sum structure and profile transformations to establish a middle-third tie profile under a bound on class sizes relative to the largest individual weight. It also gives an upper bound on ε*(G) for C-complete games.

8.14 Proof of Proposition 29

  • In both cases, exactly one coalition from each complementary pair is winning, so the game is constant-sum.Source: §8.14 · p. 41
  • For a C-complete game, ε*(G) ≤ 1/W(N).Source: §8.14 · p. 41
  • The proof also considers the reverse regime n_min < 6W_max after establishing the middle-third profile result.Source: §8.14 · pp. 41–42
  • When n_min ≥ 6W_max, there is a profile x with each class coordinate between one-third and two-thirds of that class size.Source: §8.14 · p. 42
  • The profile argument starts from a coalition weighing q − 1 and shifts players between classes while preserving the profile’s weighted total until every coordinate lies in the middle third.Source: §8.14 · p. 42
Loading 2610.08968v1…