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' requirements 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 compatibility graph between agents and
resources, we show that a solution (i.e., a set of matchings, with one matching
per round) 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 multi-round matching to maximize 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 welfare 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 formulation as well as a heuristic based on local search. We
experimentally evaluate our algorithms on synthetic networks and apply them to
two real-world situations: shared office spaces and matching courses to
classrooms.

针对多轮匹配问题，我们在普遍应用实践中探究了解决资源与代理人之间的配对问题的方法，并研究了不同类型的收益函数的解决策略，同时针对不同的场景，我们提出了整数线性规划和基于局部搜索的启发式算法。