Matchings under One-Sided Preferences with Soft Quotas

Santhini K. A., Raghu Raman Ravi, Meghana NasreIJCAI 2023 · DOI

TL;DR

This paper introduces "soft quotas" for assignment problems, moving beyond rigid limits to allow for flexible ranges of acceptable assignments. They develop efficient algorithms to find assignments that balance minimizing deviations from these soft quotas with optimizing applicant preferences, offering a practical trade-off for real-world scenarios.

What Problem Does This Paper Address?

In many real-world assignment scenarios, like allocating students to courses or residents to hospitals, there are often constraints on how many individuals can be assigned to a particular "post" (e.g., a course, a hospital department). Traditionally, these constraints are treated as fixed upper bounds (e.g., a course can take at most 30 students). However, in practice, these limits are often more flexible. For instance, a hospital might prefer to have at least 5 residents for a department to function smoothly, but could still operate with 4, albeit with reduced service levels. Similarly, a course might have a target of 30 students but could accommodate 32.

This paper addresses the limitations of fixed quotas by introducing "soft quotas." Instead of a single upper bound, each post is associated with a range defined by a lower target and an upper target. Assignments can fall outside this range, but doing so incurs a "deviation." The core challenge is to find assignments that are optimal in two potentially conflicting ways: minimizing these deviations and satisfying applicant preferences (like rank-maximality or fairness). The paper explores how the order in which these two objectives are prioritized leads to different problem formulations and requires distinct algorithmic approaches.

Methods

The paper proposes algorithms for two main scenarios:

  1. Deviation First, Preference Optimality Next: Here, the primary goal is to minimize deviation from soft quotas, and among those assignments with minimal deviation, the best one according to applicant preferences is chosen.
  2. Minimizing Total Deviation (OPT-MIN-TOT): This is tackled using a novel flow network construction. The network is designed to encode the costs associated with deviations. By finding a minimum cost flow, they can determine the minimum total deviation. The preference optimality is then achieved by selecting the best matching from the set of those with minimum total deviation.
  3. Minimizing Maximum Deviation (OPT-MIN-MAX): This problem is reduced to a fixed quota setting. By introducing a parameter $\Delta$ representing the maximum allowed deviation, they transform the soft quota problem into a fixed quota problem where quotas are adjusted by $\pm \Delta$. A binary search on $\Delta$ is used to find the minimum possible maximum deviation.
  4. Preference Optimality First, Deviation Next: In this scenario, a certain level of preference optimality (defined by a "signature requirement") must be met first, and then deviation is minimized.
  5. Signature Requirement: An additional input, a "signature requirement," is introduced. This requirement specifies a minimum level of preference satisfaction (e.g., a minimum number of applicants matched to their top-ranked posts).
  6. Algorithm for RMM-SIGN-MIN-TOT: This problem is solved using a sophisticated flow network that incorporates costs for deviations and demands for satisfying the signature. The network is constructed such that a feasible flow corresponds to a matching that meets the signature and has minimum total deviation.
  7. Algorithm for RMM-SIGN-MIN-MAX: Similar to the deviation-first case, this involves guessing the maximum deviation $\Delta$ and solving a rank-maximal matching problem in a fixed quota setting derived from the soft quotas and $\Delta$.

The core algorithmic technique across these problems is the use of flow networks, a standard tool in matching theory, but adapted here to handle the novel soft quota constraints and dual optimization objectives. They leverage concepts like min-cost max-flow and network transformations to solve these complex assignment problems.

Datasets

Not discussed in the paper. The paper focuses on theoretical problem formulation and algorithmic design, using a small illustrative example (Figure 1) rather than empirical evaluation on datasets.

Key Insights and Ideas

  • Soft Quotas as a Practical Extension: The introduction of soft quotas is a significant conceptual shift, moving beyond rigid constraints to model more realistic scenarios where deviations are permissible and quantifiable.
  • Orthogonal Optimization Objectives: The paper highlights that the order of optimization (deviation first vs. preference first) leads to fundamentally different problem formulations and algorithmic strategies, demonstrating a clear trade-off.
  • Flow Networks as a Versatile Tool: The paper showcases the power of flow networks in handling complex assignment problems with dual objectives, even when dealing with novel constraints like soft quotas.
  • Bridging Soft and Fixed Quotas: The reduction of soft quota problems to fixed quota problems (especially for minimizing maximum deviation) is a clever technique that leverages existing algorithmic machinery.
  • Signature as a Control Mechanism: The introduction of a "signature requirement" provides a mechanism to enforce a minimum level of preference satisfaction when preference optimality is prioritized.

Key Results

The paper presents theoretical results establishing the existence of polynomial-time algorithms for the defined problems:

  • Theorem 1: Polynomial-time algorithms exist for OPT-SIGN-MIN-MAX and OPT-SIGN-MIN-TOT, where OPT can be rank-maximality or fairness.
  • Theorem 2: Polynomial-time algorithms exist for OPT-MIN-MAX and OPT-MIN-TOT, where OPT can be rank-maximality or fairness.

The paper also provides detailed constructions of flow networks and outlines the algorithmic steps for solving these problems, demonstrating their computational feasibility. An example instance (Figure 1) and a table of optimal matchings illustrate the concepts and trade-offs involved.

Limitations and Future Work

  • Exponential Weights: The authors note that their flow network constructions sometimes require "exponential weights on the edges." They suggest that designing algorithms that avoid such large weights would be an interesting direction for future work.
  • Generalization: While the paper focuses on rank-maximality and fairness for preference optimality, it mentions that analogous results for fairness can be obtained with minor modifications. However, exploring other preference notions or more complex preference structures could be a future avenue.
  • Empirical Evaluation: The paper is primarily theoretical. Empirical evaluation of the proposed algorithms on real-world or synthetic datasets would be valuable to assess their practical performance and compare them against existing methods.
  • Other Soft Quota Models: The paper introduces one specific way to model soft quotas. Exploring alternative definitions or more nuanced ways to penalize deviations could be a direction for future research.

Summary updated

BibTeX
@inproceedings{a2023matchings,
  author = {Santhini K. A. and Raghu Raman Ravi and Meghana Nasre},
  title = {{Matchings under One-Sided Preferences with Soft Quotas}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/309},
}
Figure