🤖 AI

Your Recourse, My Loss? Algorithmic Recourse under Shared Constraints

This paper extends algorithmic recourse from individual-level recommendations to a many-to-many system with capacity constraints by modeling it as a capacitated weighted bipartite matching problem, proposing optimization layers that balance aggregate social welfare with distributive fairness while ensuring recourse validity in multi-stakeholder environments.

Original authors: Zahra Khotanlou, Kate Larson, Amir-Hossein Karimi

Published 2026-05-12

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Zahra Khotanlou, Kate Larson, Amir-Hossein Karimi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are applying for a loan, a job, or medical treatment, and an AI system says "No." Algorithmic recourse is the field that tries to tell you, "Here is exactly what you need to change to get a 'Yes'." For example, it might say, "If you pay off $500 of your debt, you will get approved."

Until now, most research has treated this like a one-on-one tutoring session: one person asking one teacher for help. The paper argues that this is unrealistic. In the real world, you aren't just talking to one teacher; you are one of many students trying to get into a limited number of classes, and those teachers have limited seats.

Here is a simple breakdown of the paper's ideas using everyday analogies:

1. The Problem: The "Too Many Students, Too Few Seats" Dilemma

Imagine a university with 100 students (seekers) and 5 professors (providers). Each professor has a specific list of requirements to accept a student.

The Old Way: Every student looks at all 5 professors and picks the one who asks for the easiest change (e.g., "Professor A only wants you to write one essay, while Professor B wants you to study for 10 hours"). Everyone rushes to Professor A.
The Reality: Professor A only has seats for 10 students. If 50 students all try to get in, 40 of them will be rejected, even though they found the "easiest" path. They are left with no recourse.
The Paper's Insight: You can't just tell everyone to pick the easiest path. You have to look at the whole system. If everyone rushes to the "easy" professor, the system breaks. We need a central planner (like a registrar) to assign students to professors in a way that gets the most people in with the least total effort.

2. The Solution: A Smart Seating Chart

The authors propose a new framework that acts like a smart seating chart for a crowded concert.

The Map: They create a map showing every student and every professor, drawing lines based on how "expensive" (difficult) it is for that student to get accepted by that professor.
The Goal: Instead of letting students fight for the best seats, the system calculates the best possible arrangement for the entire group. It asks: "How do we seat everyone so that the total amount of effort the crowd has to exert is minimized?"
The Result: This "Social Welfare" approach ensures that the limited seats go to the people who can get them with the least struggle, maximizing the number of successful outcomes for the group.

3. The "Welfare Gap": The Cost of Chaos

The paper defines a "Welfare Gap."

Imagine: If everyone acted alone, they would all run to the "easy" professor. Because that professor is full, many people get stuck.
The Gap: This is the difference between the "perfect world" (where everyone gets their ideal easy path) and the "real world" (where capacity is limited).
The Fix: The authors show that if you simply redistribute the seats (give more capacity to the professors who are popular and efficient), you can almost completely close this gap. You don't need more professors; you just need to move the existing seats to where they are needed most.

4. The "Moving Cost": Don't Break the System

You might ask, "Why not just move all the seats to the best professors immediately?"

The Catch: In the real world, moving seats costs money and effort. A professor can't instantly double their class size; it takes time and resources to hire more TAs or find a bigger room.
The Compromise: The authors add a third layer to their math. They ask: "How much can we improve the system without moving too many seats?"
The Result: They found that you don't need a massive overhaul. A small, targeted tweak to how many seats each professor has is often enough to get 99% of the benefits of a perfect system. It's like rearranging a few chairs in a crowded room to let everyone sit down, rather than building a new theater.

5. Fairness: Protecting the Most Vulnerable

Finally, the paper addresses fairness.

The Problem: A system that just tries to "save the most effort" might ignore the students who have a very hard time getting accepted (e.g., someone with a very poor credit history). The system might say, "It's too hard to help them, let's just help the easy cases."
The Fix: The authors introduce a "Fairness Mode." This is like a rule that says, "We must make sure the person having the hardest time gets some help, even if it costs the group a tiny bit more total effort."
The Trade-off: They show that you can significantly help the most disadvantaged people with only a very small drop in the overall efficiency of the system.

Summary

This paper argues that we need to stop thinking about AI advice as a private conversation between one person and one machine. Instead, we should view it as a public resource management problem.

By treating recourse like a bus schedule or a seating chart—where a central planner optimizes who goes where based on limited seats and varying difficulties—we can help more people succeed with less effort. The paper proves that we don't need perfect resources; we just need to stop letting people crowd the wrong doors and start distributing the available help where it works best.

Technical Summary: "Your Recourse, My Loss? Algorithmic Recourse under Shared Constraints"

Problem Statement

Current research on algorithmic recourse predominantly operates under a one-to-one assumption, where a single individual seeks a minimal-cost action to reverse an unfavorable decision from a single model. However, real-world decision-making systems often involve many-to-many interactions: multiple individuals (seekers) compete for limited resources from multiple decision-makers (providers).

In these settings, individually optimal recourse recommendations are not independent. When providers have capacity constraints (a limit on how many individuals they can accept), the validity of a recourse recommendation for one seeker depends on the actions of others. Optimizing for individual welfare in isolation ignores these interactions, leading to a welfare gap: the difference between the theoretically optimal outcome if every seeker could access their preferred provider and the realized outcome under capacity constraints. Existing literature has addressed multi-seeker scenarios but typically assumes a single provider or ignores the system-level allocation problem inherent in limited recourse capacity.

Methodology

The authors propose a framework that models multi-agent algorithmic recourse as a capacitated weighted bipartite matching problem.

Problem Formalization:
- Seekers ( $S$ ) and Providers ( $P$ ): Seekers are characterized by feature vectors; providers possess decision models (classifiers) and a matching capacity $k_j$ .
- Recourse Cost: For each seeker-provider pair $(i, j)$ , a recourse cost $c_{ij}$ is precomputed, representing the minimal effort to change the seeker's features to satisfy provider $j$ 's model.
- Weight Transformation: Costs are converted to edge weights $w_{ij} = e^{-\gamma \cdot c_{ij}}$ , where $\gamma$ is a scaling parameter. This transformation reflects Constant Absolute Risk Aversion (CARA), prioritizing low-cost interventions.
- Optimization Layers:
  - Layer 1 (Basic Matching): Solves a Mixed-Integer Linear Program (MILP) to maximize social welfare ( $\sum w_{ij}z_{ij}$ ) subject to individual and capacity constraints. This establishes the baseline social welfare under fixed capacities.
  - Layer 2 (Optimal Capacity Redistribution): Addresses the Welfare Gap by optimizing the distribution of a fixed total capacity $K$ across providers. The authors propose Algorithm 1, a greedy approach that assigns capacity to providers based on the frequency of their appearance in the top- $K$ individually preferred matches (highest weights). This avoids solving a full MILP for capacity allocation, offering a direct solution that recovers the optimal social welfare.
  - Layer 3 (Cost-Aware Optimization): Introduces a penalty for deviating from the initial capacity configuration ( $\hat{k}_j$ ). The objective function balances maximizing social welfare with minimizing the cost of capacity adjustments ( $\sum \beta_j |\Delta k_j|$ ), making the solution practical for real-world deployment where structural changes are costly.
- Inequality-Averse Extension: To address fairness, the linear utilitarian objective is replaced with a concave social welfare function ( $\sum u_i^\alpha$ ). This formulation prioritizes seekers with lower utilities (higher recourse costs), trading off aggregate efficiency for distributive equity. An Equity Metric ( $E$ ) is defined as the minimum utility attained by any successfully matched seeker.

Key Contributions

Many-to-Many Framework: The paper extends algorithmic recourse from isolated individual recommendations to a system-level design involving multiple seekers and multiple providers with capacity constraints.
Welfare Gap Quantification: It formally defines and quantifies the efficiency loss (welfare gap) that arises when individually optimal recommendations are infeasible at the system level due to capacity constraints.
Three-Layer Optimization:
1. A baseline capacitated matching formulation.
2. An efficient algorithm (Algorithm 1) to optimally redistribute fixed total capacity to minimize the welfare gap.
3. A cost-aware optimization that balances welfare gains against the operational costs of modifying provider capacities.
Inequality-Averse Formulation: The introduction of a concave welfare objective to explicitly prioritize disadvantaged seekers, demonstrating that significant equity gains can be achieved with marginal efficiency losses.

Experimental Results

The framework was validated on synthetic (Two-Moon) and real-world (Credit, COMPAS) datasets with varying numbers of seekers and providers.

Welfare Attainment: Under fixed, arbitrary capacity distributions, the system achieved only 83–93% of the theoretical individual welfare.
Impact of Redistribution: Applying the optimal capacity redistribution (Layer 2) restored social welfare to 100% of the individual welfare upper bound, proving that the welfare gap is primarily caused by misallocation rather than resource scarcity.
Cost-Aware Trade-offs: The cost-aware optimization (Layer 3) achieved near-optimal welfare (93–99% of the optimum) while requiring only minor adjustments to the initial capacity configuration, demonstrating practical feasibility.
Fairness-Efficiency Trade-off: In the inequality-averse experiments, reducing the parameter $\alpha$ (increasing aversion to inequality) doubled the minimum utility for the worst-off seekers (Equity Metric $E$ ) while incurring only a ~3.4% loss in total social welfare.
Hyperparameter Sensitivity: The study analyzed the scaling parameter $\gamma$ , identifying a "U-shaped" relationship between $\gamma$ and welfare attainment. It suggests an operating range (the "elbow" of the curve) where cost differences are meaningful without rendering non-optimal alternatives indistinguishable.

Significance and Claims

The paper claims to bridge the gap between individual algorithmic recourse and system-level design. Its primary significance lies in demonstrating that:

System-Level Coordination is Essential: Individually optimal recommendations are insufficient in resource-constrained environments; coordinated allocation is necessary to achieve near-optimal social welfare.
Efficiency is Achievable with Minimal Change: The welfare gap can be closed almost entirely by optimally redistributing existing resources, rather than requiring massive increases in total capacity.
Recourse is a Design Choice: The allocation of recourse is not merely a technical optimization problem but a value-laden system design decision. The framework provides a tractable path to balance aggregate efficiency with distributive fairness, allowing stakeholders to explicitly choose how to prioritize the most disadvantaged individuals when resources are scarce.

The authors conclude that their work provides a foundation for designing recourse systems that are not only actionable for individuals but also efficient and fair at the population level.