Introduction
Generalized Scoring Rules (GSRs) represent a significant class of voting systems that encompass nearly all common methods, including Single Transferable Vote (STV), Copeland, and Maximin. While GSRs were introduced to study the frequency of election manipulability, they initially lacked a formal axiomatic characterization. This research fills that gap by identifying the fundamental properties that define the GSR family.
The Problem: Defining the GSR Class
In computational social choice, researchers often rely on the computational hardness of calculating winners to deter strategic manipulation. To evaluate the effectiveness of this approach, it is crucial to understand how frequently a rule can be manipulated. Previous work by Xia and Conitzer (2008) suggested that most common rules are GSRs, but without a mathematical definition of what constitutes a GSR, it was impossible to determine if all natural voting rules were covered or if significant exceptions existed.
Finite Local Consistency (FLC)
The key innovation of this work is the introduction of Finite Local Consistency (FLC). This axiom serves as a relaxation of the classic consistency property.
- Standard Consistency: If two disjoint groups of voters both elect candidate $A$, their union must also elect candidate $A$. This is a very restrictive property, typically satisfied only by simple positional scoring rules like the Borda count.
- Finite Local Consistency: A rule satisfies FLC if the space of all possible voting profiles can be partitioned into a finite number of regions such that the rule behaves consistently within each region.
The authors demonstrate that while most rules are not globally consistent, they exhibit "local" consistency. For instance, in a Bucklin election, if two groups both elect candidate $c$ at the same round $k$, their union will also elect $c$ at round $k$.
The Characterization Theorem
The central result of the paper is the Characterization Theorem: A voting rule is a GSR if and only if it is anonymous and satisfies finite local consistency.
The proof utilizes a geometric representation of voting profiles. By treating profiles as points in a high-dimensional space and employing hyperplanes to separate different outcomes, the authors show that any rule satisfying FLC can be represented as a GSR where the winner is determined by comparing components of a summed score vector.
Quantifying Complexity: The Degree of Consistency
The paper introduces the "degree of consistency" as a quantitative measure of a rule's complexity, defined as the minimum number of parts needed to partition the profile space to achieve consistency. A rule with a degree of 1 is a standard scoring rule, whereas a higher degree indicates a more complex system to summarize or elicit.
As shown in the table above, the degree of consistency varies significantly across rules. While positional scoring rules have a degree of 1, rules like STV and Maximin exhibit exponential growth in their degree of consistency relative to the number of candidates $m$. The "order" of a GSR—the dimension of the score vector required to represent it—is directly linked to this degree of consistency. This has practical implications for preference elicitation, as it determines how much data is needed to summarize an ongoing election.
Limitations and Future Work
Future research directions include tightening the bounds for complex rules like Copeland and Ranked Pairs, where a significant gap remains between lower and upper bounds. Additionally, while this characterization assumes a fixed number of alternatives $m$, future work could explore settings where the number of candidates scales alongside the number of voters. The authors also suggest that GSRs could be used for more efficient preference elicitation algorithms, leaving specific implementations for future study.
Summary updated