Facilitating Matches on Allocation Platforms

Yohai Trabelsi, Abhijin Adiga, Yonatan Aumann, Sarit Kraus, S. S. Ravi · 2025

Read Facilitating Matches on Allocation Platforms by Yohai Trabelsi, Abhijin Adiga, Yonatan Aumann, Sarit Kraus, S. S. Ravi (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-18325.txt.

Introduction

Yohai Trabelsi and co-authors study a matchmaker who improves allocations by politely asking people to bend in a 2025 paper. On allocation platforms, rigid restrictions leave good matches unmade. A facilitator can plead with some agents to relax some limits, raising total social good. Two rules bind the pleading: nobody who takes the advice may end up worse off, and a budget caps how many relaxations can be requested.

The paper defines the facilitator's problem formally, including a ladder of participation guarantees an agent might demand before listening. Several social-good yardsticks get considered. Polynomial-time algorithms then solve the optimization across one-to-one and many-to-one matching settings. Experiments on three real-world datasets show facilitation paying off, and they chart how stronger guarantees change what a facilitator can achieve. The work speaks to organ exchanges, school choice, and refugee placement alike.

Catalog record

CREATORYohai Trabelsi, Abhijin Adiga, Yonatan Aumann, Sarit Kraus, S. S. Ravi
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE76 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Browse the full library · About the Tower of Babel

Full text

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

Facilitating Matches on Allocation Platforms Yohai Trabelsi, Abhijin Adiga, Yonatan Aumann, Sarit Kraus, S. S. Ravi Abstract We consider a setting where goods are allocated to agents by way of an allocation platform (e.g., a matching platform). An “allocation facilitator” aims to increase the overall utility/social-good of the allocation by encouraging (some of the) agents to relax (some of) their restrictions. At the same time, the advice must not hurt agents who would otherwise be better off. Additionally, the facilitator may be constrained by a “bound” (a.k.a. ‘budget’), limiting the number and/or type of restrictions it may seek to relax. We consider the facilitator’s optimization problem of choosing an optimal set of restrictions to request to relax under the aforementioned constraints. Our contributions are three-fold: (i) We provide a formal definition of the problem, including the participation guarantees to which the facilitator should adhere. We define a hierarchy of participation guarantees and also consider several social-good functions. (ii) We provide polynomial algorithms for solving various versions of the associated optimization problems, including one-to-one and many-to-one allocation settings. (iii) We demonstrate the benefits of such facilitation and relaxation, and the implications of the different participation guarantees, using extensive experimentation on three real-world datasets. † † paperid: 9712 1 Introduction Recently, allocation-platforms/matching-platforms, which allocate resources of one sort or another to users, are being deployed for a variety of applications in both the public and private sectors, including in welfare and social services ( Huang et al. 2023 ; Pan et al. 2023 ; Aguma 2022 ) . Some examples are allocating home healthcare demand with service providers ( Lin et al. 2021 ) , on-demand housekeeping platforms ( Yu et al. 2022 ) , government platforms for providing housing assistance to homeless individuals ( Sharam et al. 2018 ) , ride-sharing platforms ( Bao et al. 2023 ) , sharing parking spaces ( Tang et al. 2023 ) , and volunteer matching platforms ( Slingerland et al. 2018 ) . In these platforms, users specify their resource requirements and constraints, and the platforms aim to optimize the allocation of resources to users where resources can be shared among several users. The key stakeholders in the resultant allocation are clearly the users. In many cases, however, there may be additional stakeholders. For example, local welfare authorities are justifiably interested in increasing the number of homeless individuals awarded housing assistance (see e.g., Chan et al. 2018 ), and university administration is interested in maximizing the number of courses for which classrooms have been successfully allocated (see e.g., Frimpong and Owusu 2015 ). At times, these stakeholders may be able to directly determine, or make changes to the allocation, but more often than not, the allocation procedure itself is fixed - for regulatory, commercial, or technical reasons (see e.g., Trabelsi et al. 2022 ). For example, New York City offers affordable housing opportunities through the Housing Connect portal nyc , which serves as an allocation and matching platform. The algorithm used for this allocation is governed by multiple laws and regulations, including: (i) the federal Fair Housing Act, (ii) the NYC Human Rights Law, (iii)NYC HPD regulations, and (iv) NYC HDC rules. These regulations determine the allocation, which does not change. At the same time, the NYC Department of Housing Preservation and Development (HPD) established an advisory initiative, called the Housing Ambassadors Program hpd , to help people navigate and use the allocation platform effectively. In their website, they emphasize that the Housing Ambassadors do not provide housing directly, and they cannot guarantee that an applicant will receive an affordable unit through the lottery. In such cases, interested parties – which from now on we term facilitators – can still shape the resulting allocation by assisting and advising users in selecting the priorities and constraints they enter into the allocation platform. It is important to stress that such advice need not be viewed as a form of manipulation, neither of the platform nor of the users. Indeed, users frequently do not know how best to express their true constraints, and such interventions – if done right – can benefit all Slaugh et al. 2016 . As such, we only consider impartial facilitators whose priorities are aligned with the overall social good, without any preference for one user or another. In this paper, we study advice provisioning with such impartial facilitators: what advice should they provide? What guarantees should/can be offered to the users, both those following the advice and those who do not? In this paper, we assume that with appropriate guarantees, agents are willing to accept the advice. Providing them knowledge about whether they have been, or are currently, guaranteed a resource— either through the facilitator to ease constraints or the allocator as an act of transparency— further enhances their receptiveness. For concreteness, we consider the following stylized model (see Figure 1 for an example). There is an allocation platform that, given (i) a set X of agents - each agent x_{i} with demand level d_{i} for the number of resources it needs, (ii) a set Y of resources, and (iii) a binary compatibility relation E between agents and resources, outputs a maximum allocation of resources to agents (where the maximum is in the sense of resource utilization). The compatibility relation E represents the compatibility as provided to the platform by the agents . The facilitator can advise agents to add additional compatibilities \hat{E} , thereby enlarging the input compatibility relation to E^{+}=E\cup\hat{E} . If offered no advice, then E^{+}=E . Adding any such new compatibility e\in\hat{E} is associated with some discomfort level \rho(e) . We consider a class of problems where the facilitator’s objective is to maximize resource allocation with the constraint that the aggregate cost does not exceed a specified bound. Here, the aggregate cost is some function of all \rho(e) s, such as sum of all \rho(e) s or the count of strictly positive \rho(e) values (which is the number of proposed relaxations). Figure 1 shows solutions for different functions. The incompatibility between a course and a classroom in Figure 1 can arise due to various factors such as seating capacity, commute distance, and accessibility issues. Optimal solutions for various scenarios (bound type and value—participation guarantee) are shown, all of which can be achieved by our framework. Expansions of the acronyms used in these scenarios are given under “Summary of Contributions”. Formal definitions of the guarantees are provided in Section 3 . Note that even for such a simple example, the solutions can be very different for different scenarios. We propose the following two requirements to ensure that the proposed relaxation does not harm the agents while encouraging cooperation among them: (i) No agent is harmed: Any agent that was guaranteed to be granted an allocation prior to the facilitator’s actions, is also guaranteed so following the facilitator’s actions. (ii) Participating agents benefit: Any agent that is asked by the facilitator to add a compatibility (and does so) is guaranteed to be granted an allocation. Figure 1: An example of a course–classroom allocation platform where every course needs to be matched to one classroom. Solid edges represent a compatible pair of a course and a classroom, dashed edges indicate an

Read the complete text