Dynamic Proportional Rankings

Jonas Israel, Markus BrillIJCAI 2021 · DOI

TL;DR

This paper tackles the challenge of maintaining fair representation in dynamic ranking systems, like live Q&A platforms, where items are selected sequentially. The authors introduce and analyze novel "dynamic" and "myopic" versions of established proportional ranking rules, demonstrating how to adapt them to scenarios where the ranking must be updated after each selection.

What Problem Does This Paper Address?

In many interactive settings, such as live Q&A sessions, panel discussions, or town halls, an audience submits questions, and a moderator selects them for discussion. While simple popularity-based ranking (e.g., by upvotes) is common, it can lead to the "tyranny of the majority," where minority opinions are completely unrepresented. This paper addresses the need for ranking systems that ensure proportional representation of different groups within the audience, even as questions are selected and removed from consideration one by one. The core problem is how to dynamically update a ranking to maintain fairness as the set of available items shrinks.

Methods

The authors extend two well-known proportional ranking rules, sequential Phragmén and sequential PAV, to a dynamic setting. They propose two paradigms for this dynamization:

  • Dynamic Rules: These rules aim to maintain proportional representation of voter interests at each individual time step. They recompute the ranking based on the remaining candidates and the history of implemented candidates, ensuring that the current ranking itself is representative.
  • Myopic Rules: These rules focus on making the set of implemented candidates as representative as possible. They prioritize candidates that, if selected, would best contribute to overall proportionality, often by considering only the immediate impact on representation.

They also introduce "satisfaction monotonicity" as a desirable property, where the satisfaction of voters with the ranking doesn't decrease when a non-approved candidate is implemented.

Datasets

Not discussed in the paper. The authors use synthetic approval profiles generated according to specific probabilistic models (blurred parties and spatial models) for their experimental evaluation.

Key Insights and Ideas

  • The "tyranny of the majority" is a real problem: Even with significant minority representation (e.g., 40%), unpopular topics can be entirely overlooked if rankings are purely popularity-based.
  • Dynamic adaptation is crucial: Simply removing selected items from a static proportional ranking isn't enough. The ranking needs to be recomputed to reflect the changing landscape and ensure continued fairness.
  • Two distinct approaches to dynamism: The "dynamic" rules focus on the current ranking's fairness, while "myopic" rules focus on the fairness of the sequence of selected items. These lead to different trade-offs.
  • Monotonicity is surprisingly hard to achieve: Even simple rules can violate satisfaction monotonicity, where a voter's satisfaction decreases when a candidate they don't approve of is selected. This suggests that achieving fairness often involves complex trade-offs.
  • Myopic rules can offer stronger selection guarantees: While dynamic rules ensure the ranking is fair at each step, myopic rules can provide better guarantees about the set of selected items being representative over time.

Key Results

  • Theoretical Guarantees: The paper provides theoretical bounds for the proportional representation offered by the dynamic rules, specifically for "k-group representation" (how far down a ranking one needs to look to find representation for a group) and "proportional justified selection" (ensuring that if a group has enough support for a candidate, they will eventually get representation).
  • Monotonicity Failures: Dynamic seqPAV and dynamic Phragmén fail to satisfy (h, a)-monotonicity for small groups. Myopic rules also fail this property unless the group is very large.
  • Experimental Validation: Experiments with generated approval profiles show that AV (Approval Voting) performs poorly in terms of proportional representation, while the proposed dynamic and myopic rules (except AV) yield proportionally increasing satisfaction values as minority group sizes grow. The dynamic rules maintain more stable satisfaction over iterations compared to the myopic rules, which exhibit more volatile jumps.

Limitations and Future Work

  • Adversarial DM: The analysis of proportional justified selection relies on assumptions about the decision-maker's behavior (depth-restricted selection and candidate "clones"). Without these, adversarial DMs could undermine proportionality.
  • Static Electorate/Candidates: The current model assumes a fixed set of voters and candidates. Future work could explore scenarios with voters joining/leaving and new questions appearing dynamically.
  • Changing Preferences: Participants might change their approval preferences over time, which is not modeled here but could be incorporated.
  • Computational Complexity: While the paper states rules are computable in polynomial time, a detailed analysis is deferred to a full version.
  • Real-world Applicability: The authors suggest extensions to real-world scenarios like committee elections and human-in-the-loop decision support systems.

Summary updated

BibTeX
@inproceedings{israel2021dynamic,
  author = {Jonas Israel and Markus Brill},
  title = {{Dynamic Proportional Rankings}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/37},
}
Figure