Improving Welfare in One-Sided Matchings using Simple Threshold Queries

Thomas Ma, Vijay Menon, Kate LarsonIJCAI 2021 · DOI

TL;DR

This paper explores how to improve the fairness and efficiency of matching systems (like assigning students to schools or workers to tasks) by asking agents for just a tiny bit of extra information beyond their basic preferences. They show that by using simple "yes/no" threshold queries, they can achieve matchings that are much better in terms of overall welfare, even when only a limited number of queries are allowed.

What Problem Does This Paper Address?

In many real-world scenarios, we need to match agents (e.g., students, workers) to objects (e.g., schools, tasks). A common approach is to ask agents for their preferences, often in the form of an ordered list of acceptable objects. However, this "ordinal" information doesn't capture how much an agent likes an object. Ignoring these "cardinal" preferences can lead to significant losses in overall welfare, meaning some agents might end up with objects they dislike much more than necessary, even if the matching satisfies basic fairness criteria like Pareto optimality. The challenge is to find a way to incorporate this crucial cardinal information without overwhelming agents with complex questions about their exact utility values.

Methods

The paper proposes using "binary threshold queries" as a middle ground. Instead of asking for precise utility values, these queries ask agents a simple "yes" or "no" question: "Is your utility for object X at least Y?" The authors develop algorithms that strategically ask these queries to gather just enough information to improve the welfare outcome.

They explore two main types of algorithms:

  • Adaptive Algorithms: These algorithms can adjust their subsequent queries based on the answers received. They show that with a small number of adaptive queries per agent (logarithmic in the number of agents and objects), they can achieve a (1+ε)-approximation to the optimal welfare for various matching properties (Pareto optimal, rank-maximal, etc.).
  • Non-Adaptive Algorithms: These algorithms ask a fixed set of queries upfront, without adapting to responses. This is considered more practical. They focus on algorithms that ask at most one query per (agent, object) pair. They develop algorithms for both "unit-sum" and "unit-range" valuation models (different ways agents might express their cardinal preferences) and provide upper and lower bounds on the welfare approximation they can achieve.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • The Power of "Just Enough" Information: The core insight is that you don't need full cardinal utility information to significantly improve matching outcomes. A few well-chosen binary threshold queries can bridge the gap between purely ordinal and fully cardinal approaches.
  • Non-Adaptive is Practical: While adaptive algorithms offer slightly better theoretical guarantees, the paper emphasizes the practical advantages of non-adaptive approaches, which are simpler to implement and less burdensome for agents.
  • Bridging the Gap: The work provides a principled way to select among multiple "good" matchings by incorporating welfare considerations, acting as a sophisticated tie-breaker.
  • Welfare vs. Distortion: The paper connects their work to the concept of "distortion" in matching literature, showing how their query-based approach can reduce welfare loss compared to purely ordinal methods.

Key Results

  • Adaptive Algorithms: Achieve a (1+ε)-approximation to optimal welfare using O(c log n) queries per agent, where 'c' depends on ε. This means a 2-approximation is possible with O(log n) queries per agent.
  • Non-Adaptive Algorithms (Unit-Sum Valuations):
    • Achieve an O(n²/³) approximation for priority-p matchings and Pareto optimal matchings using at most one query per (agent, object) pair.
  • Non-Adaptive Algorithms (Unit-Range Valuations):
    • Achieve an O(n) approximation for priority-p matchings.
  • Achieve an O(√n) approximation for Pareto optimal matchings.
  • Lower Bounds: For non-adaptive algorithms asking at most one query per (agent, object) pair, there's a lower bound of Ω(√n) on the achievable welfare approximation for both unit-sum and unit-range valuations.

Limitations and Future Work

  • Gap in Non-Adaptive Bounds: The paper notes a gap between the O(n²/³) upper bound and the Ω(√n) lower bound for non-adaptive algorithms with unit-sum valuations. Closing this gap is a direction for future research.
  • Generalizing Properties: The authors suggest expanding the set of matching properties considered, such as "popular matchings."
  • Two-Sided Matching: Applying these query-based approaches to two-sided matching problems (e.g., matching students to colleges where colleges also have preferences) is another promising avenue.
  • Interface Design: Understanding how to best design user interfaces for eliciting these simple queries is crucial for practical deployment.
  • Multi-Agent Assignment: Extending the work to scenarios where multiple agents can be assigned to the same object (e.g., course enrollment) is also mentioned.

Summary updated

BibTeX
@inproceedings{ma2021improving,
  author = {Thomas Ma and Vijay Menon and Kate Larson},
  title = {{Improving Welfare in One-Sided Matchings using Simple Threshold Queries}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/45},
}
Figure