Proportionality Degree in Participatory Budgeting

This paper initiates the study of proportionality degree in participatory budgeting by establishing tight theoretical bounds for the Method of Equal Shares and Phragmen's Sequential Rule, demonstrating that despite their differing axiomatic properties, they achieve comparable quantitative proportionality, a finding further validated through extensive experiments on real-world datasets.

The Gist

Imagine a town hall meeting where the community has a pot of money (the budget) and a list of projects they want to fund, like a new park, a library renovation, or a community center. Everyone gets to vote for what they like. The big question is: How do we split the money so that different groups of people feel fairly represented?

This paper tackles that question by looking at two popular ways of doing the math: the Method of Equal Shares (MES) and Phragmén's Sequential Rule.

Here is the breakdown of what the researchers found, explained simply.

1. The Problem: "Fairness" is Hard to Measure

In the past, researchers asked a simple "Yes/No" question: Does this rule satisfy the "Fairness Rule"?

• Yes: Great, the rule is fair.
• No: Bad, the rule is unfair.

But life isn't binary. Sometimes a rule is mostly fair, or fair in some cases but not others. The authors wanted a better ruler. They invented a concept called "Proportionality Degree."

Think of it like a satisfaction score. If a group of voters represents 20% of the town, they should ideally get 20% of the "happiness" (or projects) from the budget. The "Proportionality Degree" measures how close a rule gets to that perfect 20% in the worst-case scenario.

2. The Contenders: Two Different Philosophies

The paper compares two famous methods for dividing the budget:

• Method of Equal Shares (MES): Imagine giving every voter an equal amount of "virtual cash" at the start. If a project costs $100 and 10 people want it, they chip in $10 each. If they run out of cash, they can't buy more. It's like a digital marketplace where everyone has a strict wallet.

  • Reputation: It's the "Gold Standard." It has very strong theoretical promises of fairness.

• Phragmén's Sequential Rule: Imagine a water tank filling up slowly. Every voter has a tank that fills with water (credits) at the same speed. As soon as a group of voters has enough water in their combined tanks to pay for a project, that project gets bought, and their tanks are emptied.

  • Reputation: It's a classic, older method. It's known to be fair, but it doesn't have the same "super-strong" theoretical promises as MES.

3. The Big Surprise: The "Tug-of-War" Result

The researchers expected MES to win easily because it has stronger theoretical rules. They thought it would give voters a much higher "satisfaction score."

But they were wrong.

When they did the heavy math (the "tight bounds"), they found that both rules are equally strong in terms of how well they protect groups of voters.

• The Analogy: Imagine two runners in a race. One runner (MES) is wearing a fancy, high-tech uniform that says they are faster. The other runner (Phragmén) is wearing a t-shirt. You'd expect the fancy uniform to win. But when they actually run the race, they cross the finish line at the exact same time.
• The Takeaway: Even though MES has stricter rules on paper, Phragmén's method is just as good at ensuring groups get their fair share of the budget in the real world.

4. The "Greedy" Rule (The Villain)

The paper also tested a third method called the Greedy Rule. This is the "common sense" approach: Just pick the projects that the most people voted for, one by one, until the money runs out.

• The Result: The Greedy rule was terrible at fairness. It ignored smaller groups. If 51% of the town wanted a huge stadium and 49% wanted a small community garden, the Greedy rule would fund the stadium and give the garden nothing.
• The Lesson: Both MES and Phragmén crushed the Greedy rule. They proved that you need a sophisticated algorithm to ensure minority groups aren't left out.

5. Real-World Testing

The authors didn't just do math on paper; they tested these rules on 100 real-world datasets from actual participatory budgeting events around the world.

• The Findings: The real-world data matched the math perfectly.
  • MES and Phragmén performed almost identically well.
  • Sometimes Phragmén was slightly better, sometimes MES was slightly better, but they were neck-and-neck.
  • The Greedy rule consistently underperformed.

6. What Does This Mean for You?

If you are a city council member or a community organizer trying to decide how to spend public money:

1. Don't just pick the most popular projects. That leaves people out.
2. You can choose either MES or Phragmén. You don't need to stress about picking the "perfect" one because they are mathematically equivalent in their ability to be fair.
3. The "Exhaustion" trick: The paper also looked at what happens when you have leftover money. If you use a "hybrid" approach (run the fair algorithm, then use the Greedy rule for whatever is left), you get the best of both worlds.

In a nutshell: This paper proves that two different mathematical approaches to fairness are actually twins in disguise. They both do a fantastic job of making sure that if a group of people stands together, they get a share of the budget that matches their size. And they both do it much better than just picking the "most popular" option.

Technical Summary

Here is a detailed technical summary of the paper "Proportionality Degree in Participatory Budgeting" by Filos-Ratsikas, Gogulapati, and Kalantzis.

1. Problem Statement

The paper addresses a gap in the literature regarding Participatory Budgeting (PB), a democratic process where citizens allocate public funds to projects. While PB rules are often evaluated using axiomatic properties (binary guarantees like whether a rule satisfies Extended Justified Representation (EJR) or Proportional Justified Representation (PJR)), these properties do not quantify how well a rule performs in terms of proportional representation.

The authors aim to study the Proportionality Degree, a quantitative metric that measures the worst-case average satisfaction a cohesive group of voters can achieve relative to their size and the cost of the projects they support. Specifically, the paper focuses on two prominent PB rules:

1. Method of Equal Shares (MES): Known for satisfying strong axiomatic guarantees (EJR).
2. Phragmén's Sequential Rule: Known for satisfying weaker axiomatic guarantees (PJR) but failing EJR.

The central research question is: Do the axiomatic differences between MES and Phragmén translate into quantitative differences in their proportionality degree?

2. Methodology

The authors employ a dual approach combining rigorous theoretical analysis with extensive empirical evaluation.

Theoretical Framework

• Definitions:
  • $\mathcal{T}$-Cohesive Group: A group of voters $V$ is cohesive for a set of projects $\mathcal{T}$ if they all approve every project in $\mathcal{T}$, and the cost of $\mathcal{T}$ is proportional to the group's size relative to the total budget ($cost(\mathcal{T})/B \le |V|/n$).
  • Proportionality Degree ($d_f(\mathcal{T})$): Defined as the largest lower bound $g(\mathcal{T})$ such that the average satisfaction of any $\mathcal{T}$-cohesive group is at least $\min(|\mathcal{T}|, g(\mathcal{T}))$.
• Analysis Techniques:
  • Lower Bounds: Proved using potential function arguments (for Phragmén) and payment ordering lemmas (for MES) to show the minimum satisfaction guaranteed to cohesive groups.
  • Upper Bounds: Constructed specific adversarial instances where the rules fail to achieve higher satisfaction, establishing tight bounds.
  • Generalization: Extended the analysis to any rule satisfying EJR under "ordinary" instances (where no single project is extremely cheap relative to the per-voter budget).

Experimental Evaluation

• Dataset: 100 real-world participatory budgeting instances from the Pabulib library.
• Rules Evaluated:
  1. Method of Equal Shares (MES)
  2. Sequential Phragmén
  3. MES with Exhaustion (greedy selection of remaining projects if budget remains)
  4. Phragmén with Exhaustion
  5. Greedy Approval (baseline: selects projects by highest approval count)
• Metric Calculation: Since calculating proportionality degree for all subsets is NP-hard (exponential in the number of projects), the authors used random sampling. For each dataset, they sampled 5,000 subsets of sizes $k \in \{1, \dots, 15\}$, identified the worst-case cohesive group for each subset, and computed the average proportionality degree.

3. Key Contributions

A. Theoretical Bounds

The paper derives tight bounds (up to small constant factors) for the proportionality degree of both rules.

• Main Result: Despite MES satisfying the stronger EJR axiom and Phragmén only satisfying PJR, both rules achieve the same proportionality degree.
• The Lower Bound: For a set of projects $\mathcal{T}$, the proportionality degree $d(\mathcal{T})$ is at least:
  $$\frac{1}{2} \left( \frac{cost(\mathcal{T})}{\max_{t \in \mathcal{T}} cost(t)} - 1 \right)$$
• The Upper Bound: There exist instances where the average satisfaction is at most:
  $$\frac{1}{2} \left( \frac{cost(\mathcal{T})}{\max_{t \in \mathcal{T}} cost(t)} \right) + 1$$
• General EJR Bound: The authors prove that any rule satisfying EJR in "ordinary" instances (where $cost(t) \cdot n \ge B$) achieves a proportionality degree of at least:
  $$\frac{\min_{t \in \mathcal{T}} cost(t)}{\max_{t \in \mathcal{T}} cost(t)} \cdot \frac{1}{2} \left( \frac{cost(\mathcal{T})}{\max_{t \in \mathcal{T}} cost(t)} - 1 \right)$$
  This implies that when project costs are similar (approaching the multi-winner voting setting), the guarantee for MES is shared by all EJR-satisfying rules.

B. Experimental Findings

• Performance: Both MES and Phragmén (with and without exhaustion) significantly outperform the widely used Greedy Approval rule.
• Comparison between Rules:
  • In practice, Phragmén with exhaustion often performs slightly better than MES with exhaustion.
  • Without exhaustion, Phragmén still performs very well, sometimes outperforming MES.
  • The greedy rule is consistently the worst performer regarding proportionality.
• Correlation with Theory: The experimental results closely mirror the theoretical findings, confirming that the two rules have comparable quantitative performance despite their different axiomatic profiles.

4. Results Summary

1. Equivalence in Quantitative Fairness: The most surprising finding is that the stronger axiomatic guarantee of MES (EJR) does not translate to a higher proportionality degree compared to Phragmén. Both rules offer the same worst-case quantitative guarantees.
2. Optimality Conjecture: The authors conjecture that these bounds are optimal, suggesting that no other rule can achieve a strictly better proportionality degree. They provide a theorem (Theorem 6) upper-bounding any PB rule's degree by $\frac{cost(\mathcal{T})}{\max_{t \in \mathcal{T}} cost(t)} - 1$.
3. Practical Superiority: Both rules are empirically superior to the greedy baseline, validating their use in real-world implementations.

5. Significance

• Bridging Axiomatic and Quantitative Gaps: The paper demonstrates that axiomatic properties (binary satisfaction) and quantitative performance (degree of satisfaction) are not always correlated. A rule failing a strong axiom (like Phragmén failing EJR) can still be quantitatively as fair as a rule that satisfies it (MES).
• Guidance for Practitioners: The results suggest that practitioners can choose between MES and Phragmén based on other factors (e.g., computational efficiency, specific implementation details) without sacrificing proportional fairness.
• Foundation for Future Research: By establishing tight bounds and identifying the gap between current bounds and the theoretical maximum, the paper sets a clear direction for future work in optimizing participatory budgeting mechanisms.

In conclusion, this work provides a comprehensive theoretical and empirical validation that Method of Equal Shares and Phragmén's Sequential Rule are equally effective in ensuring proportional representation in participatory budgeting, challenging the intuition that stronger axiomatic guarantees necessarily yield better quantitative outcomes.