Applications such as employees sharing office spaces over
a workweek can be modeled as problems where agents are
matched to resources over multiple rounds. Agents’ require-
ments limit the set of compatible resources and the rounds in
which they want to be matched. Viewing such an application
as a multi-round matching problem on a bipartite compati-
bility graph between agents and resources, we show that a
solution can be found efficiently if one exists. To cope with
situations where a solution does not exist, we consider two
extensions. In the first extension, a benefit function is defined
for each agent and the objective is to find a solution to maxi-
mize the total benefit. For a general class of benefit functions
satisfying certain properties (including diminishing returns),
we show that this multi-round matching problem is efficiently
solvable. This class includes utilitarian and Rawlsian wel-
fare functions. For another benefit function, we show that the
maximization problem is NP-hard. In the second extension,
the objective is to generate advice to each agent (i.e., a subset
of requirements to be relaxed) subject to a budget constraint
so that the agent can be matched. We show that this budget-
constrained advice generation problem is NP-hard. For this
problem, we develop an integer linear programming formu-
lation as well as a heuristic based on local search. We exper-
imentally evaluate our algorithms on synthetic networks and
apply them to two real-world situations: shared office spaces
and matching courses to classrooms.

Resource Sharing Through Multi-Round Matchings

**Read paper on the following link:**

https://ifaamas.org/Proceedings/aamas2022/pdfs/p1738.pdf

**Abstract:**



Yohai Trabelsi

2

SHORT BIO

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES