From Individual to Multi-Agent Algorithmic Recourse: Minimizing the Welfare Gap via Capacitated Bipartite Matching

Zahra Khotanlou, Kate Larson, Amir - Hossein Karimi · 2025

Read From Individual to Multi-Agent Algorithmic Recourse: Minimizing the Welfare Gap via Capacitated Bipartite Matching by Zahra Khotanlou, Kate Larson, Amir - Hossein Karimi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-11070.txt.

Introduction

Zahra Khotanlou, Kate Larson, and Amir-Hossein Karimi ask what happens when many people seek recourse from the same limited providers. Their 2025 paper extends algorithmic recourse, the advice that tells someone how to flip an unfavorable AI decision. Classic work treats one person and one model, ignoring competition for scarce slots.

The authors model the crowd version as a matching problem between seekers and providers with capacity caps. Three optimization layers adjust matches, redistribute capacity, and weigh costs. A fairness-minded variant tilts help toward the worst-off seekers. Experiments reached near-best social welfare with small system changes. The paper reframes recourse as system design, not just personal advice.

Catalog record

CREATORZahra Khotanlou, Kate Larson, Amir - Hossein Karimi
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE39 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-11070

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

From Individual to Multi-Agent Algorithmic Recourse: Minimizing the Welfare Gap via Capacitated Bipartite Matching Zahra Khotanlou, Kate Larson, Amir - Hossein Karimi Abstract Decision makers are increasingly relying on machine learning in sensitive situations. In such settings, algorithmic recourse aims to provide individuals with actionable and minimally costly steps to reverse unfavorable AI-driven decisions. While existing research predominantly focuses on single-individual (i.e., seeker ) and single-model (i.e., provider ) scenarios, real-world applications often involve multiple interacting stakeholders. Optimizing outcomes for seekers under an individual welfare approach overlooks the inherently multi-agent nature of real-world systems, where individuals interact and compete for limited resources. To address this, we introduce a novel framework for multi-agent algorithmic recourse that accounts for multiple recourse seekers and recourse providers. We model this many-to-many interaction as a capacitated weighted bipartite matching problem , where matches are guided by both recourse cost and provider capacity. Edge weights, reflecting recourse costs, are optimized for social welfare while quantifying the welfare gap between individual welfare and this collectively feasible outcome. We propose a three-layer optimization framework: (1) basic capacitated matching, (2) optimal capacity redistribution to minimize the welfare gap, and (3) cost-aware optimization balancing welfare maximization with capacity adjustment costs. Experimental validation on synthetic and real-world datasets demonstrates that our framework enables the many-to-many algorithmic recourse to achieve near-optimal welfare with minimum modification in system settings. This work extends algorithmic recourse from individual recommendations to system-level design, providing a tractable path toward higher social welfare while maintaining individual actionability. 1 Introduction (a) One-to-one Recourse Matching (b) Many-to-many Recourse Matching Figure 1 : Various algorithmic recourse setups: (a) the classical one-to-one setting, where an individual s seeks recourse recommendations from a provider p with minimal cost required to reverse the output; (b) our proposed many-to-many framework generalizes prior settings by simultaneously optimizing for multiple recourse seekers and providers. AI decision-making systems rapidly apply predictive models to support individuals in various contexts, e.g., loan approvals, medical treatments, or bail decisions [ Voigt and Von Dem Bussche 2017 ] . The increasing reliance of humans on these algorithmic decision-making systems and their significant impact on areas such as finance, healthcare, and criminal justice have raised concerns regarding the transparency and fairness of these automated systems. Driven by AI policy regulations and the idea of a ”right to explanation,” algorithmic recourse is an emerging field that aims to provide individuals affected by negative, high-stakes algorithmic decisions with recommendations on how to reverse those outcomes [ GDPR 2016 , Verma et al. 2024 ] . Therefore, algorithmic recourse refers to the systematic process of reversing unfavorable decisions made by algorithms across various counterfactual scenarios [ Wachter et al. 2018 ] . It encompasses the necessary actions individuals must take to achieve a favorable outcome, serving as a foundation for temporally extended agency and trust in automated decision-making systems [ Karimi et al. 2021 ] . This concept is essential to ensure automated decisions are understandable and to enable individuals to engage with and contest these decisions [ Doshi-Velez and Kim 2017 , Gunning and Aha 2019 ] . Existing studies on algorithmic recourse predominantly address how the individual would need to change their attributes to achieve the desired outcome [ Karimi et al. 2022 ] . Such settings generally assume a single individual impacted by a single decision-making model as shown in Figure 1(a) . In real-world scenarios, however, AI decision-making systems (i.e., providers ) often interact with multiple individuals whose actions can influence outcomes and, consequently, recourse recommendations for others (Many-to-one setting). Furthermore, individuals seeking recourse (i.e., seekers ) may engage with multiple providers ( Figure 1(b) ) to choose the most suitable among given recommendations. The driving insight of this paper is that the effects of other stakeholders should not be ignored. Recent studies have explored recourse frameworks that consider more than one seeker. For instance, O’Brien and Kim 2022 modified the recourse optimization problem, introducing Social-Welfare-Efficient Recourse and Pareto-Efficient Recourse. Drawing upon game-theoretic principles, their illustrative use of the prisoner’s dilemma highlights potential misaligned benefits in conventional recourse recommendations and provides a compelling ethical rationale for reconsidering algorithmic interventions in a many-to-one setting. In similar vein, Fonseca et al. 2023 propose an agent-based simulation framework modeling multi-seeker-single-provider dynamic competition among recourse seekers over time, studying whether negatively classified instances will ever attain recourse in light of new individuals entering the seeker pool. Their work reveals that initially promising recourse recommendations may lose effectiveness due to continuous environmental changes. This emphasizes the importance of accounting for both competition and temporal shifts when formulating interventions. While these studies have extended the literature to settings with multiple recourse seekers, they continue to assume a single provider. There remains a gap regarding algorithmic recourse in situations involving multiple recourse providers each potentially impacting outcomes with their own decision models. Our Contributions We extend existing recourse frameworks to move past the unrealistic assumption of infinite provider capacity wherein seekers are able to match with any provider in absence of other simultaneous matches. Our proposed formulation includes multiple recourse seekers and multiple recourse providers and examines how individual recommendations in such settings affect the overall system. We formalize this interaction as a capacitated weighted bipartite matching problem and determine optimal recourse outcomes using a linear-programming approach, thereby maximizing social welfare under capacity constraints. Specifically, we evaluate the population cost or social welfare of recourse, summed over all individuals, under realistic capacity limits and contrast it with the case of unlimited provider capacity. Further, we identify a welfare gap between the socially optimal solution, computed by a central planner, and the unrealistic individually optimal outcome, where each seeker acts in isolation and selects the provider offering the lowest recourse cost, without coordination or consideration of provider capacity constraints. To minimize this gap, we introduce a second optimization layer that finds the best distribution for a total fixed capacity over providers. We propose a systematic procedure to find this optimal distribution and minimize the gap. Finally, since algorithmic recourse methods provide recommendations that minimally change the initial situation to reach the favourable outcome, we add the third optimization layer that minimizes the welfare gap while penalizing deviations from the initial capacity values. Solving this problem yields both the best provider capacities, accounting for the modification penalty, and the corresponding social welfare matching. 2 Many-to-Many Recourse Optimization In this section, we formalize the matching problem that serves as the foundation of our optimization framework. The problem is modeled as a bipartite graph as shown in Figure 1(b) , with loan seekers on one set and loan providers (e.g., banks) on the other, as follows: • Seekers \mathcal{S} : \{s_{i}~|~s_{i}\in\mathcal{S},~\forall~i\in[n]\} , each characterized by a feature vector x_{i} . • Providers \mathcal{P} : \{p_{j}~|~p_{j}\in\mathcal{P},~\forall~j\in[m]\} , each equipped with a classifier (w.l.o.g. binary model) h_{j} to accept or reject the seekers and a matching capacity k_{j} . All the seekers are initially rejected by all providers, i.e., h_{j}(x_{i})=-1~\forall~i,j, meaning that each seeker will have a recommendation from all providers. Furthermore, it is assumed that a central planner will coordinate matches between seekers and providers (i.e., Equation 1 ) and potentially redistribute existing capacity among providers (i.e., Equation 2 and Equation 3 ). Recourse

Read the complete text