💻 computer science

A General Theory of Proportionality with Additive Utilities

This paper extends axioms of proportionality from approval ballots to cardinal ballots within a general constrained selection model, proposing new rules that ensure proportional outcomes and generate proportional rankings for applications like participatory budgeting and public decision-making.

Original authors: Piotr Skowron

Published 2026-02-10

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Piotr Skowron

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are organizing a massive community festival. You have a list of potential activities (candidates), a group of neighbors (voters), and a limited budget (feasibility constraints). Some activities cost more than others, and some activities simply cannot happen together (like a loud rock concert and a quiet yoga session happening in the same tent).

The goal is to pick a set of activities that feels fair to everyone. If a group of neighbors represents 20% of the crowd and they all love a specific type of music, they should get roughly 20% of the festival's "music time."

This paper tackles a very tricky version of this problem: What if people don't just say "I like this" or "I don't"? What if they say, "I really like this, but I love that one even more"?

Here is a breakdown of the paper's ideas using simple analogies.

1. The Problem: The "Approval" vs. "Utility" Gap

Most previous rules for fair selection assumed voters only had a "Yes/No" button (Approval).

Approval: "I like the Rock Concert." (Value = 1)
Utility (The new challenge): "I like the Rock Concert a little, but the Jazz Band is my absolute favorite." (Rock = 0.2, Jazz = 1.0).

The paper argues that real life is full of these "Utility" preferences. Even if you vote "Yes" on a project, you might care about it more if it costs $100 than if it costs $10. The authors wanted to build rules that handle these nuanced feelings, not just simple "Yes/No" votes.

2. The Core Idea: Buying Candidates with "Virtual Money"

The authors propose a system where voters earn virtual money over time, like a faucet dripping coins into their pockets.

The Old Way (Phragmén's Rule): As soon as a group of people has enough coins to buy a candidate they like, they buy it immediately. It's a "greedy" approach.
The New Way (PropRank & Equal Shares): The authors realized that sometimes, buying a candidate now is a bad idea. Maybe if you wait 5 minutes, you'll have enough money to buy a better candidate that you love even more.

The Analogy: Imagine you are at an all-you-can-eat buffet, but you are paying by the minute.

Greedy: You see a burger you like, so you grab it immediately.
Smart (The Paper's Method): You see the burger, but you know a steak is coming out in 2 minutes. You wait. You calculate: "If I spend my money now on the burger, I might miss the steak. But if I wait, I can get the steak, which gives me more 'happiness' per dollar."

The paper introduces a mathematical "foresight" mechanism. It simulates the future to decide: Is it worth waiting for a better deal, or should I buy this now?

3. The Two Main Rules

A. PropRank (The "Time-Traveling" Selector)

This rule is designed to create a ranking (a list from 1st place to last place) rather than just a final list.

How it works: Voters earn money. The algorithm looks at every candidate and asks, "Who is willing to pay for this, and at what cost?"
The Twist: It doesn't just buy the cheapest thing. It calculates a "price per unit of happiness." If a candidate is expensive but gives a group of voters huge joy, it might be "cheaper" in terms of happiness than a cheap, boring candidate.
The Result: It produces a fair list where every top part of the list (the "prefix") is a fair committee on its own.

B. The Method of Equal Shares (The "Budget Allocator")

This is a more aggressive version. Instead of dripping money slowly, it gives everyone a big chunk of virtual money upfront and lets them spend it.

The Innovation: The authors took this method, which was previously only used for simple budgeting, and taught it how to handle complex constraints (like "we can't have both the rock concert and the yoga class").
How it handles constraints: If the algorithm tries to buy a set of candidates that breaks the rules (e.g., violates the budget or the "no rock/yoga together" rule), it stops, recalculates, and finds the best feasible subset to buy instead.

4. The "Heuristics" (The Smart Shortcuts)

The authors found that their perfect mathematical rules sometimes left money on the table (voters had money left over that they didn't spend). To fix this, they created "heuristic" (smart guess) versions:

PropRankRem: If a candidate gets removed from the list (because it's too expensive or conflicts with others), the algorithm hits "Reset." It tells the voters, "Okay, forget about that candidate. Let's restart the spending plan without it." This prevents voters from hoarding money waiting for a candidate that will never be picked.
Backtracking: This is like playing a video game. The algorithm tries a path. If it gets stuck, it goes back a few steps, changes its mind about which candidates to wait for, and tries again. It's slower but often finds a more perfect solution.

5. What Did They Find? (The Results)

The authors tested these rules on real-world data from Participatory Budgeting (where real cities let citizens vote on how to spend public money).

The "Wait" Factor: They found that setting the "wait" parameter (called $\kappa$ ) to 1 (meaning voters are very willing to wait for better deals) worked best for fairness.
Fairness vs. Happiness: Their new rules were incredibly fair. They rarely violated the "fairness" rules (called Extended Justified Representation).
Comparison:
- The Greedy method (just picking the most popular things) was efficient but unfair to smaller groups.
- The New Rules (PropRank and Equal Shares) were much fairer to diverse groups of voters, ensuring that minority preferences were actually represented, not just the majority's favorites.
- The Heuristic versions (with the "Reset" and "Backtrack" features) performed almost perfectly, creating outcomes with almost zero fairness violations.

Summary

The paper says: "We built a new way to make group decisions that respects how much people really like things, not just if they like them. By using a 'virtual money' system that encourages voters to wait for the best 'happiness-per-dollar' deals, we can create fairer outcomes for complex situations, like city budgets or committee selections, where not everything can be picked."

They proved mathematically that these rules are fair, and tested them on real data to show they work better than older methods.

Technical Summary: A General Theory of Proportionality with Additive Utilities

1. Problem Statement

The paper addresses the problem of selecting a feasible subset of candidates from a set $C$ based on voter preferences, subject to general feasibility constraints defined by a family of subsets $\mathcal{F} \subseteq 2^C$ . This framework generalizes several established models in social choice theory, including:

Committee elections: Selecting a fixed number of candidates.
Participatory budgeting (PB): Selecting projects within a total budget.
Public decision-making and judgment aggregation: Making decisions on multiple independent issues.
Diversity constraints: Ensuring specific structural properties (e.g., gender balance) in the selected set.

While axioms of proportionality (such as Justified Representation) have been defined for this general model, existing rules are primarily designed for approval ballots (where voters assign utility 0 or 1). The paper focuses on the more complex setting of additive utilities, where each voter $i$ assigns a numerical utility $u_i(c) \geq 0$ to every candidate $c$ . The goal is to design rules that ensure fair representation for cohesive groups of voters under these general constraints and cardinal utilities.

2. Methodology

The authors propose two primary algorithmic approaches inspired by the concept of voters "purchasing" candidates with virtual currency.

2.1 The PropRank Rule

PropRank is a sequential rule inspired by the Phragmén sequential rule but adapted for additive utilities.

Mechanism: Voters earn virtual money at a constant rate over time. The rule simulates a purchasing process where voters decide how much to spend on candidates.
Foresight Mechanism: Unlike standard greedy approaches, voters in PropRank anticipate future opportunities. They calculate a "scaling factor" $\lambda_i$ based on the best possible payment-to-utility ratio they could achieve if they waited for a more desirable candidate to become affordable.
Spending Function: A voter $i$ agrees to spend at most $x_i(c, r)$ on candidate $c$ in round $r$ , defined by a formula involving their current budget, the candidate's utility, and the scaling factor. This ensures the payment-to-utility ratio does not exceed the best fractional purchase available.
Ranking: The algorithm constructs a full ranking of candidates by their purchase timestamps. Since infeasible candidates are not removed during the process (only at the end of the ranking construction for specific committee sizes), every prefix of the ranking satisfies proportionality.

2.2 Generalized Method of Equal Shares (MES)

The authors extend the Method of Equal Shares (originally for PB) to general constraints.

Structure: The algorithm operates in rounds. In each round, it determines the maximum amount of money that can be allocated to voters such that the "Equal Shares" subroutine can purchase a set of candidates without violating feasibility constraints.
Foresight in MES: Similar to PropRank, the generalized MES incorporates a foresight mechanism. It computes upper bounds on spending ($capi$) to prevent voters from spending too early on candidates that might be less efficient than those available in future iterations.
Backtracking Heuristics: The paper introduces heuristic variants (PropRankRem, PropRankBacktrack) that restart the procedure or backtrack when candidates are removed, aiming to reduce unspent budgets and improve practical performance, though these lack the same theoretical guarantees as the base rules.
Bounded Overspending (BOS): An adaptation of the BOS method is proposed for general constraints, where the algorithm identifies the largest valid timestamp for purchasing before feasibility is violated.

3. Key Contributions

3.1 Theoretical Framework

Proportionality Axioms for Additive Utilities: The paper generalizes axioms like Extended Justified Representation (EJR) and Proportional Justified Representation (PJR) to the additive utility setting with general constraints.
Proportionality Degree: The authors define and analyze the "proportionality degree," quantifying the average satisfaction of a cohesive group. They establish the relationship between EJR and proportionality degree, showing that for general constraints, the guarantee depends on the size of the cohesive group ( $\gamma = |S|/n$ ).

3.2 Theoretical Guarantees

PropRank Guarantees:
- For Participatory Budgeting constraints, PropRank satisfies a proportionality degree of $d(\alpha) = (\alpha - u_{max})/2$ .
- For General constraints, it satisfies a degree of $d(\alpha) \geq \alpha \cdot \frac{1-\gamma}{2} - \frac{u_{max}}{2}$ .
- For Matroid constraints, it satisfies a weak proportionality degree of $(\alpha - u_{max})/2$ .
PJR Guarantees: The rules satisfy PJR degree guarantees of $d(\alpha) = (\alpha - u_{max})/(\kappa + 1)$ , where $\kappa$ is a parameter controlling the spending flexibility.

3.3 Algorithmic Extensions

The paper provides the first generalization of the Method of Equal Shares to arbitrary feasibility constraints with additive utilities.
It introduces heuristics (PropRankRem, PropRankBacktrack) to address the issue of unspent budgets in practical scenarios.

4. Experimental Results

The authors evaluated their rules on over 1,300 real-world participatory budgeting instances from the Pabulib dataset.

Metrics: Evaluation was based on EJR+ violations (proportionality), Exclusion Ratio (fraction of voters with zero utility), and Average Cost-Satisfaction (utilitarian efficiency).
Findings:
- $\kappa$ Parameter: The experiments indicate that PropRank with $\kappa = 1$ (allowing more flexible spending) performs significantly better in terms of proportionality (fewer EJR+ violations) than $\kappa = 0$ .
- Heuristics: The heuristic variants (PropRankRem, PropRankBacktrack) combined with $\kappa = 0$ showed very few EJR+ violations and favorable exclusion ratios, often outperforming the base PropRank in practical metrics despite lacking formal proofs for these specific heuristics.
- BOS Adaptation: The adapted Method of Equal Shares with Bounded Overspending performed exceptionally well, outperforming the original BOS-PB in EJR+ violations and matching it in exclusion ratio and utility. It was also noted as the most computationally efficient among the proposed techniques.
- Comparison: The proposed rules generally achieved cost-satisfaction comparable to or better than existing PB-specific rules (MES-PB, BOS-PB) while handling general constraints.

5. Significance and Claims

The paper claims to provide a general theory of proportionality that bridges the gap between specific models (like committee elections and PB) and the broader landscape of constrained selection problems.

Generalization: It demonstrates that established methods (Phragmén and Equal Shares) can be extended to arbitrary feasibility constraints and additive utilities without losing their core proportionality properties.
Ranking: A significant contribution is the ability to generate proportional rankings (where every prefix is a proportional committee) in the additive utility setting, addressing a gap in the literature.
Practicality: While the theoretical guarantees are strong, the authors modestly note that heuristic variants, which sacrifice some theoretical tractability for better practical performance (reducing unspent budgets), are highly effective in real-world instances.
Limitations: The paper acknowledges that the proof techniques for the base algorithms do not directly extend to the heuristic variants, and the computational complexity of the backtracking heuristics can be exponential (mitigated by a parameter $\sigma$ ).

In summary, the work establishes a robust theoretical foundation for proportional representation under general constraints and additive utilities, offering both provably fair algorithms and practical heuristics that perform well on real data.