Dynamic Social Choice with Evolving Preferences

David C. Parkes, Ariel D. ProcacciaAAAI 2013 · OpenReview

Abstract

Social choice theory provides insights into a variety of collective decision making settings, but nowadays some of its tenets are challenged by internet environments, which call for dynamic decision making under constantly changing preferences. In this paper we model the problem via Markov decision processes (MDP), where the states of the MDP coincide with preference profiles and a (deterministic, stationary) policy corresponds to a social choice function. We can therefore employ the axioms studied in the social choice literature as guidelines in the design of socially desirable policies. We present tractable algorithms that compute optimal policies under different prominent social choice constraints. Our machinery relies on techniques for exploiting symmetries and isomorphisms between MDPs.

Introduction

Traditional social choice theory—the study of collective decision-making through mechanisms like voting—has historically focused on static environments. In these settings, agents have fixed preferences, a single vote is conducted, and an outcome is selected. However, modern online platforms, such as advocacy groups or collaborative filtering systems, require sequential decision-making where today’s choice can fundamentally alter tomorrow’s preferences.

This dynamic nature introduces two primary challenges:

  1. Dynamics: Decisions must account for how current choices influence future preference profiles.
  2. Scalability: The state space of such systems is massive. With $n$ agents and $m$ alternatives, there are $(m!)^n$ possible preference profiles, making standard MDP solvers computationally infeasible.

The Social Choice MDP

The authors bridge the gap between social choice and reinforcement learning by representing the problem as a Social Choice MDP. In this framework, states represent every possible preference profile, actions correspond to the alternatives available for selection, and transitions are stochastic models describing how agent preferences evolve after a specific alternative is chosen.

Transition models for individual agent types (left) and the resulting MDP transition model (right).

A key insight of this work is that a deterministic, stationary policy in this MDP is mathematically equivalent to a social choice function. This allows for the direct application of classical social choice axioms—mathematical "fairness" guidelines—to the design of optimal policies.

Symmetry and Scalability

To overcome the astronomical state space, the authors employ Symmetry Exploitation. They assume agents can be categorized into a small number of "types" who share identical transition models. By focusing on anonymity—the principle that the identity of a voter shouldn't matter, only the distribution of votes—the state space can be contracted. Instead of tracking individual rankings, the model only tracks the count of agents of each type holding specific rankings. This collapses the complexity from exponential to polynomial relative to the number of agents $n$.

Axiomatic Constraints and Results

The paper categorizes social choice axioms into two groups: local axioms, where decisions in one state do not depend on others (e.g., Pareto optimality), and nonlocal axioms, which describe global properties of the policy (e.g., being "onto" or "non-dictatorial").

The authors demonstrate that optimal policies satisfying these axioms can be computed efficiently:

  • Theorem 4.10: For a constant number of alternatives and agent types, an optimal policy satisfying any local, anonymous axiom can be found in polynomial time in $n$.
  • Theorem 5.1: Even for nonlocal axioms, a "guided search" approach allows for polynomial-time optimization.

The complexity bottleneck shifts from the number of agents ($n$) to the number of alternatives ($m$). While $n$ can be very large, $m$ must remain relatively small for the algorithms to remain tractable.

Limitations and Future Work

While the paper provides a robust theoretical foundation, it faces several limitations. The algorithms are exponential in $m!$, meaning they struggle as the number of alternatives grows. Additionally, the model assumes transition probabilities are known, whereas in practice, these would need to be learned from data. Future work remains to address axioms like monotonicity and to adapt the model for dynamic populations where members join and leave over time.

Summary updated

Abstract

Social choice theory provides insights into a variety of collective decision making settings, but nowadays some of its tenets are challenged by internet environments, which call for dynamic decision making under constantly changing preferences. In this paper we model the problem via Markov decision processes (MDP), where the states of the MDP coincide with preference profiles and a (deterministic, stationary) policy corresponds to a social choice function. We can therefore employ the axioms studied in the social choice literature as guidelines in the design of socially desirable policies. We present tractable algorithms that compute optimal policies under different prominent social choice constraints. Our machinery relies on techniques for exploiting symmetries and isomorphisms between MDPs.
BibTeX
@inproceedings{parkes2013dynamic,
  author = {David C. Parkes and Ariel D. Procaccia},
  title = {{Dynamic Social Choice with Evolving Preferences}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2013},
  url = {https://openreview.net/forum?id=rJWcd6ed-H},
}
Figure