Optimal Multi-Attribute Decision Making in Social Choice Problems

Sujoy SikdarIJCAI 2018 · DOI

TL;DR

This thesis tackles the challenge of making optimal decisions when choices have multiple attributes, a common but complex problem in areas like resource allocation and voting. The authors develop efficient mechanisms and theoretical guarantees for these scenarios by identifying and leveraging natural structures in agent preferences, making previously intractable problems solvable.

What Problem Does This Paper Address?

Making optimal decisions in real-world scenarios often involves evaluating alternatives that have multiple characteristics or attributes. Think about choosing a university (location, program, cost, campus life) or allocating resources (CPU, memory, storage). The complexity explodes as the number of attributes and alternatives grows. Furthermore, individual preferences over these multi-attribute alternatives can be incredibly intricate and difficult to model or elicit. This paper addresses the computational hardness and preference representation challenges in multi-attribute decision-making, particularly within the framework of social choice problems where collective decisions are made based on individual preferences.

Methods

The paper approaches multi-attribute decision making from two main directions:

  1. Decision Making Under Preferences: This direction focuses on designing mechanisms for specific social choice problems.
  2. Multi-type Resource Allocation: For housing markets, the authors extend the Top-Trading-Cycles (TTC) mechanism to handle multiple types of indivisible items. They propose a mechanism that is strict core selecting, non-bossy, and strong group strategyproof under certain conditions, running in polynomial time. They also prove theoretical limits on strategyproofness when agents can lie about preferences.
  3. Multi-issue Voting: For aggregating preferences over multiple issues (represented by CP-nets), the paper introduces a new class of voting rules. These rules handle potentially cyclic CP-nets and complex dependency structures by using a quantitative, loss-minimization framework.
  4. Learning Preferences from Data: This direction focuses on modeling and learning user preferences from real-world data.
  5. The authors develop models inspired by cognitive psychology, using natural language and semantic features.
  6. They employ "fast and frugal heuristic (FFH)" based decision models to learn from limited data, particularly in question answering settings.
  7. A case study on Reddit discussions demonstrates learning factors that drive user behavior and voting.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Structure is Key: The core insight is that by identifying and exploiting "natural structures" in agent preferences (which are often motivated by practical and cognitive considerations), complex multi-attribute decision problems can become tractable.
  • Beyond Simple Preferences: Traditional social choice theory often assumes simpler preference structures. This work extends these results to more realistic, complex, multi-attribute settings.
  • Trade-offs in Strategyproofness: For multi-type housing markets, the paper highlights a fundamental trade-off: it's impossible to satisfy both strict core selection and strategyproofness simultaneously if agents can misrepresent their preferences.
  • Quantitative Loss for Voting: Using a quantitative loss function to measure how "bad" an outcome is, based on preferred alternatives, offers a flexible way to aggregate preferences even when they are cyclic and lack common structure.
  • Leveraging Cognitive Models: Applying models from cognitive psychology (like FFH) can be effective for learning preferences from limited data, offering an alternative to data-hungry machine learning approaches.

Key Results

  • Multi-type Housing Markets: Development of a polynomial-time mechanism that is strict core selecting, non-bossy, and strong group strategyproof (under specific conditions) for multi-type housing markets.
  • Multi-issue Voting: A new class of voting rules for CP-nets that can handle cyclic preferences and complex dependencies, with computational complexity results provided.
  • Preference Learning: Models and methods for learning user preferences from noisy data and understanding factors driving online behavior, demonstrated through a Reddit case study.

Limitations and Future Work

Limitations:

  • The paper acknowledges that while their mechanisms offer desirable properties, they may not satisfy all desirable properties simultaneously (e.g., strategyproofness vs. core selection in housing markets).
  • The "natural structures" in preferences are key, and the effectiveness of the proposed mechanisms relies on these structures being present in real-world data.

Future Work:

  • Unified Approach: Develop a unified theory for mechanism design that bridges preference representations and practical modeling.
  • More General Settings: Extend housing market mechanisms to more general problem settings and expressive preference representations.
  • Local Mechanisms: Investigate properties of local mechanisms for multi-type resource allocation and how they contribute to desirable global allocations.
  • Online Communities: Build problem-specific models to better understand discussions in diverse online communities.

Summary updated

BibTeX
@inproceedings{sikdar2018optimal,
  author = {Sujoy Sikdar},
  title = {{Optimal Multi-Attribute Decision Making in Social Choice Problems}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/835},
}
Figure