Fairness and Optimization in Dynamic Multiagent Allocation Problems

1 Motivation

Understanding the needs, wants, and tradeoffs of individual agents is important for solving many resource allocation problems, especially when resources are limited. In these problems, some agents receive the resources, some provide them, some allocate the resources, and some play the role of a facilitator in the allocation process. These problems become even more interesting when people play some or all of these roles. Some problems that come to mind in this context are the allocation of classes to classrooms ([Phillips et al., 2015]), of medical students to hospitals ([Roth, 1986]), hot desking or shared workspaces ([Cai and Khan, 2010]).

2 Definitions

We call the agent who allocates resources the principal. In general, the principal wants to maximize the size of the allocation and also wants the other agents to be satisfied with the allocation in order to keep their loyalty to the system. The agents who need the resources are simply referred to as agents. They have certain requirements and preferences regarding the properties of the desired resources. In some of the problems considered, the principal owns the resources. In other problems, the resources themselves (e.g., labor) or their owners may have their own interests, such as avoiding resource overuse. 1 . Finally, in some problems there is the role of a facilitator or mediator who may have its own interests and whose task it is to suggest or persuade other agents to follow its suggestions.

1 Please note that resources may be, for example, labor (e.g. doctors assigned to patients) or facilities. In the rest of the document, for simplicity, we refer to the preferences or satisfaction of the resources, referring to the constraints on the resources that may be set by their owners or by themselves.

To solve the above problems, we need to define a framework that allows agents to express their preferences and specify the desired resource properties. Sometimes the framework should also allow resources to specify their requirements. The framework should also define the roles of the principal and the facilitator/s if any.

3 Previous and Current Research

In my research, I have dealt with several problems in this context. In [Trabelsi et al., 2022] we have defined a framework in which the agents have restrictions and the resources have constraints. The principal's task is to allocate resources according to the agents' restrictions and resources constraints. In this work, an individual agent who is not satisfied with its chances of obtaining a resource approaches the principal. The principal then suggests to the agent which restrictions should be relaxed in order to improve the agent's chances of obtaining an allocation.

In [Trabelsi et al., 2023], we considered a repeated matching problem when an agent needs to be allocated in multiple rounds or days. In this paper, the principal approaches several agents and suggests they relax some of their restrictions to optimize the size of the allocation and, alternatively, the egalitarian fairness among the agents. Maximizing other types of utility, including leximinic fairness, has been considered in the problem of allocating water rights to farmers [Adiga et al., 2024]. We modeled the problems in all papers as matching in bipartite graphs and proposed several algorithmic solutions. The idea behind many of these algorithms is to construct a bipartite graph and/or assign weights to its edges smartly so that performing a simple maximum weighted or maximum cardinality matching yields the desired results.

In a work in progress, we consider an allocation problem in which a facilitator tries to maximize the matching size by advising some agents to relax their restrictions. Under certain conditions, the facilitator promises to allocate a resource to the agents that relax their restrictions, even though the facilitator itself has no control over the allocation process.

A dynamic environment in which agents (or tasks) arrive dynamically and delayed allocations are allowed can be found in our work [Ackerman Viden et al., 2023]. In this environment, the interests of both agents (tasks) and resources (workers) are important. In another (ongoing) work, we considered a situation where incoming tasks were allocated to workers without the possibility of rejecting a task. In this case, we sought to optimize egalitarian fairness for both agents and resources. In these works, we proposed several centralized LP-based algorithmic approaches.

In all mentioned papers, in addition to the proposed algorithms and proofs, we have conducted experiments with real datasets. In many cases where it was not possible to use existing datasets, we collected the data and created new datasets (e.g. in [Trabelsi et al., 2023] and [Ackerman Viden et al., 2023]). This work involved experiments with humans, which requires careful planning and analysis. The datasets were used to highlight the advantages of our algorithms on realworld problems and to illustrate their limitations.

4 Plans for Future Research

4.1 Challenges inMany toMany Allocation Problems

In [Trabelsi et al., 2022], the principal proposes to an agent to relax some restrictions in order to improve its chances of being matched. I would like to examine a scenario where several agents approach the principal. In this scenario, I would like to examine the promises made to the relaxing agents. Will it be possible to guarantee that they will be matched with a higher probability? What is the promised guarantee? How does it affect the promised improvement if some other agents will not follow the principal's advice? How can a solution be found in which fewer agents are affected by the rejection of others?

It is also interesting to examine the fairness between the approaching agents. Can we ensure egalitarian fairness? (e.g. is the least improvement maximised for an approaching agent). What is the cost of egalitarian fairness in terms of the size of the allocation? What about maximizing the leximin order?

4.2 Challenges in Different Principal Roles

While the principal in [Trabelsi et al., 2022] acts as a mediator and does not change the matching due to the changed restrictions, it is also interesting to examine the effects of a more proactive principal who changes the allocation procedure according to the given advice while maintaining some fairness criteria. We would like to answer the following questions: How could fairness be maintained in this scenario? Should the principal use some random process for retaining fairness? Should the principal improve the chances of the approaching agents at the cost of reducing the chances of those who do not approach?

Another direction to explore with respect to [Trabelsi et al., 2022] and [Trabelsi et al., 2023] is when the principal suggests to some agents to relax some of their restrictions, while some (probably other) agents ask the principal or mediator for tips on which restrictions they should relax to improve their chances of being allocated. In this scenario, the following questions should be asked: How should the principal balance between the interests of the approaching and approached agents? Should the principal prioritize the approached agents since their relaxations are in it's interests? Should the approaching agents be prioritized to keep them satisfied? If the resources have their interests, how should the principal balance them with it's interests and the interests of the approaching and approached agents? What happens when the resources approach the principal? More technically, we should also ask: How can we model these fairness issues? Is bipartite graph sufficient? Should we add weights to its edges or vertices? Which existing algorithms are relevant?

4.3 Challenges When Adding Intermediaries

In [Trabelsi et al., 2023], we consider a scenario where the matching is repeated for several days. In this paper, however, the entire allocation is calculated simultaneously. An interesting direction for future work is in scenarios where allocation is done in multiple rounds when agents and resources can negotiate between rounds. In this direction, what mechanism should the principal support for negotiation? How should the principal reflect the negotiation outcomes in the computed matching? Could a mediator that cannot affect the matching improve the agent satisfaction and allocation size? Which techniques should be utilized for the principal and mediator?