ﻻ يوجد ملخص باللغة العربية
In the multidimensional stable roommate problem, agents have to be allocated to rooms and have preferences over sets of potential roommates. We study the complexity of finding good allocations of agents to rooms under the assumption that agents have diversity preferences [Bredereck et al., 2019]: each agent belongs to one of the two types (e.g., juniors and seniors, artists and engineers), and agents preferences over rooms depend solely on the fraction of agents of their own type among their potential roommates. We consider various solution concepts for this setting, such as core and exchange stability, Pareto optimality and envy-freeness. On the negative side, we prove that envy-free, core stable or (strongly) exchange stable outcomes may fail to exist and that the associated decision problems are NP-complete. On the positive side, we show that these problems are in FPT with respect to the room size, which is not the case for the general stable roommate problem. Moreover, for the classic setting with rooms of size two, we present a linear-time algorithm that computes an outcome that is core and exchange stable as well as Pareto optimal. Many of our results for the stable roommate problem extend to the stable marriage problem.
We study the three-dimensional stable matching problem with cyclic preferences. This model involves three types of agents, with an equal number of agents of each type. The types form a cyclic order such that each agent has a complete preference list
We describe our experience with designing and running a matching market for the Israeli Mechinot gap-year programs. The main conceptual challenge in the design of this market was the rich set of diversity considerations, which necessitated the develo
The Possible-Winner problem asks, given an election where the voters preferences over the set of candidates is partially specified, whether a distinguished candidate can become a winner. In this work, we consider the computational complexity of Possi
We consider the problem of committee selection from a fixed set of candidates where each candidate has multiple quantifiable attributes. To select the best possible committee, instead of voting for a candidate, a voter is allowed to approve the prefe
The problem of allocating scarce items to individuals is an important practical question in market design. An increasingly popular set of mechanisms for this task uses the concept of market equilibrium: individuals report their preferences, have a bu