Ordinal Hedonic Seat Arrangement under Restricted Preference Domains: Swap Stability and Popularity

Anaëlle WilczynskiIJCAI 2023 · DOI

TL;DR

This paper explores how to assign agents to positions in a network (like seats at a table or offices in a building) such that everyone is as happy as possible, considering only their preferences for individual agents. They investigate two fairness criteria: "swap stability" (no two agents can improve their situation by swapping places) and "popularity" (no other arrangement is preferred by more agents). The key contribution is a comprehensive analysis of when these fair arrangements are guaranteed to exist under various restrictions on agent preferences and network structures.

What Problem Does This Paper Address?

Imagine you're organizing a conference dinner or assigning office spaces. You want to arrange people (agents) in a way that makes them happy, but not necessarily by forming strict groups. Instead, each person cares about the people they are "connected" to – their neighbors in the arrangement. This is the core of "hedonic seat arrangements." The challenge is that people have complex preferences, and it's hard to guarantee fairness.

This paper tackles two main fairness concepts:

  1. Swap Stability: If two agents can swap their positions and both end up happier (or at least no worse off, and one is strictly better off), the arrangement isn't "swap-stable." This is like a local fairness check – can a small change fix things?
  2. Popularity: An arrangement is "popular" if no other arrangement is preferred by a majority of agents. This is a global optimality concept – is this arrangement the "people's choice"?

The paper's main goal is to figure out under what conditions (specific types of agent preferences and network structures like paths, cycles, or clusters) we can guarantee that such fair arrangements exist. This is crucial for practical applications where simply finding an arrangement isn't enough; it needs to be demonstrably fair and stable.

Methods

The authors use a combination of theoretical analysis and constructive proofs. They define "preference extensions" to translate individual agent preferences into preferences over sets of neighbors. Key preference restrictions studied include:

  • Single-peaked (SP): Agents have a most preferred agent, and preferences decrease as you move away from that agent along a specific ordering.
  • Narcissistically single-peaked (narSP): A stricter version of SP where the most preferred agent is directly adjacent in the ordering.
  • Iteratively mutual best (IMB): Agents can be paired up based on mutual highest preferences, and this process is repeated.
  • Globally-ranked (GR): Agents have a global ranking of all possible pairs of agents.
  • 1-Euclidean (1-D): Agents are placed on a line, and preferences are based on distance.

They then analyze the existence of swap-stable and popular arrangements for these preference types on different graph structures:

  • Path graphs: Linear arrangements (e.g., a street).
  • Cycle graphs: Circular arrangements (e.g., a round table).
  • Cluster graphs: Groups of agents forming cliques (e.g., distinct teams).

The proofs often involve constructing specific arrangements and demonstrating that they satisfy the desired properties under certain conditions. They also use counterexamples to show when such arrangements cannot be guaranteed.

Datasets

Not discussed in the paper. The paper focuses on theoretical models and proofs rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Preference restrictions are key: The existence of swap-stable and popular arrangements is highly sensitive to how agents' preferences are structured. Simple restrictions like single-peakedness are often insufficient, while more complex ones like globally-ranked preferences provide stronger guarantees.
  • Graph structure matters: The shape of the network significantly impacts fairness guarantees. For instance, what works for a path graph might not work for a cycle graph, especially concerning certain preference extensions.
  • Swap stability dynamics can cycle: Even with seemingly reasonable preferences (like narcissistically single-peaked), the process of agents swapping positions can get stuck in cycles, meaning a stable state might not be reached. This highlights the complexity of local stability.
  • Globally-ranked preferences are powerful for swap stability: When agents have a global ranking of all pairs, swap dynamics are guaranteed to converge for any graph and most preference extensions. This is a strong positive result.
  • Narcissistically single-peaked preferences offer good results for popularity: This preference type, combined with specific graph structures and preference extensions, often guarantees the existence of popular arrangements.

Key Results

The paper presents a detailed landscape of existence results, summarized in tables. Some highlights include:

  • Swap Stability:
    • Guaranteed to exist for globally-ranked preferences on any graph.
  • Guaranteed for iteratively mutual best preferences on path graphs (with Fishburn's extension) and 2-cluster graphs.
  • Guaranteed for narcissistically single-peaked preferences on path graphs (with Gärdenfors' extension) and cluster graphs (with best compatibility).
  • No guarantee for swap stability in cycle graphs under strict simple independence, or in path graphs under simple dominance, even with single-peaked preferences.
  • Popularity:
    • Guaranteed for narcissistically single-peaked preferences on path graphs (with Fishburn's extension).
  • Guaranteed for narcissistically single-peaked and globally-ranked preferences on path graphs (with responsive set extension) and cycle graphs (with Gärdenfors' or responsive set extension).
  • No guarantee for popularity in cycle graphs under narcissistically single-peaked preferences (with Gärdenfors' or responsive set extension), and in 3-cluster graphs under 1-Euclidean preferences.

Limitations and Future Work

  • Open Questions: Several "question marks" remain in the summary tables, indicating areas where the existence of swap-stable or popular arrangements is still an open problem, particularly for certain combinations of preference restrictions, graph types, and preference extensions (e.g., path graphs with >RS for swap stability, or cycle graphs with narSP for swap stability).
  • Computational Complexity: While the paper establishes existence, it doesn't always delve into the computational complexity of finding these arrangements, though some constructive proofs imply polynomial-time computability. Future work could focus on efficient algorithms for constructing these arrangements.
  • General Cluster Graphs: The positive results for swap stability in cluster graphs are limited to those with at most one odd clique. Extending these results to general cluster graphs remains an open problem.
  • Preference Restrictions: The paper explores several common restrictions. Investigating other known preference restrictions from the literature could yield further insights.

Summary updated

BibTeX
@inproceedings{wilczynski2023ordinal,
  author = {Anaëlle Wilczynski},
  title = {{Ordinal Hedonic Seat Arrangement under Restricted Preference Domains: Swap Stability and Popularity}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/324},
}
Figure