Cseh, Ágnes; Juhos, Attila Pairwise Preferences in the Stable Marriage ProblemACM Transactions on Economics and Computation (TEAC) 2021: 1–28
We study the classical, two-sided stable marriage problem under pairwise preferences. In the most general setting, agents are allowed to express their preferences as comparisons of any two of their edges and they also have the right to declare a draw or even withdraw from such a comparison. This freedom is then gradually restricted as we specify six stages of orderedness in the preferences, ending with the classical case of strictly ordered lists. We study all cases occurring when combining the three known notions of stability—weak, strong and super-stability—under the assumption that each side of the bipartite market obtains one of the six degrees of orderedness. By designing three polynomial algorithms and two NP-completeness proofs we determine the complexity of all cases not yet known, and thus give an exact boundary in terms of preference structure between tractable and intractable cases.
Cseh, Ágnes; Kavitha, Telikepalli Popular matchings in complete graphsAlgorithmica 2021: 1–31
Our input is a complete graph \(G = (V,E)\) on n vertices where each vertex has a strict ranking of all other vertices in \(G\). The goal is to construct a matching in \(G\) that is "globally stable" or popular. A matching \(M\) is popular if \(M\) does not lose a head-to-head election against any matching \(M'\): here each vertex casts a vote for the matching in \(\{M,M'\}\) where it gets a better assignment. Popular matchings need not exist in the given instance \(G\) and the popular matching problem is to decide whether one exists or not. The popular matching problem in \(G\) is easy to solve for odd \(n\). Surprisingly, the problem becomes NP-hard for even n, as we show here.
Andersson, Tommy; Cseh, Ágnes; Ehlers, Lars; Erlanson, Albin Organizing time exchanges: Lessons from matching marketsAmerican Economic Journal: Microeconomics 2021: 338–73
This paper considers time exchanges via a common platform (e.g. , markets for exchanging time units, positions at education institutions, and tuition waivers). There are several problems associated with such markets, e.g., imbalanced outcomes, coordination problems, and inefficiencies. We model time exchanges as matching markets and construct a non-manipulable mec hanism that selects an individually rational and balanced allocation that maximizes exchanges among the participating agents (and those allocations are efficient). This mechanism works on a preference domain whereby agents classify the goods provided by other participating agents as either unacceptable or acceptable, and for goods classified as acceptable, agents have specific upper quotas representing their maximum needs.
Aziz, Haris; Cseh, Agnes; Dickerson, John; McElfresh, Duncan Optimal Kidney Exchange with ImmunosuppressantsConference on Artificial Intelligence (AAAI) 2021: 21–29
Algorithms for exchange of kidneys is one of the key successful applications in market design, artificial intelligence, and operations research. Potent immunosuppressant drugs suppress the body's ability to reject a transplanted organ up to the point that a transplant across blood- or tissue-type incompatibility becomes possible. In contrast to the standard kidney exchange problem, we consider a setting that also involves the decision about which recipients receive from the limited supply of immunosuppressants that make them compatible with originally incompatible kidneys. We firstly present a general computational framework to model this problem. Our main contribution is a range of efficient algorithms that provide flexibility in terms of meeting meaningful objectives. Motivated by the current reality of kidney exchanges using sophisticated mathematical-programming-based clearing algorithms, we then present a general but scalable approach to optimal clearing with immunosuppression; we validate our approach on realistic data from a large fielded exchange.
Aziz, Haris; Chan, Hau; Cseh, Ágnes; Li, Bo; Ramezani, Fahimeh; Wang, Chenhao Multi-Robot Task Allocation—Complexity and ApproximationAutonomous Agents and Multiagent Systems (AAMAS) 2021: 133–141
Multi-robot task allocation is one of the most fundamental classes of problems in robotics and is crucial for various real-world robotic applications such as search, rescue and area exploration. We consider the Single-Task robots and Multi-Robot tasks Instantaneous Assignment (ST-MR-IA) setting where each task requires at least a certain number of robots and each robot can work on at most one task and incurs an operational cost for each task. Our aim is to consider a natural computational problem of allocating robots to complete the maximum number of tasks subject to budget constraints. We consider budget constraints of three different kinds: (1) total budget, (2) task budget, and (3) robot budget. We provide a detailed complexity analysis including results on approximations as well as polynomial-time algorithms for the general setting and important restricted settings.
Kraiczy, Sonja; Cseh, Ágnes; Manlove, David On Weakly and Strongly Popular RankingsAutonomous Agents and Multiagent Systems (AAMAS) 2021: 1563–1565
Van Zuylen et al. introduced the notion of a popular ranking in a voting context, where each voter submits a strictly-ordered list of all candidates. A popular ranking pi of the candidates is at least as good as any other ranking sigma in the following sense: if we compare pi to sigma, at least half of all voters will always weakly prefer pi. Whether a voter prefers one ranking to another is calculated based on the Kendall distance. A more traditional definition of popularity---as applied to popular matchings, a well-established topic in computational social choice---is stricter, because it requires at least half of the voters who are not indifferent between pi and sigma to prefer pi. In this paper, we derive structural and algorithmic results in both settings, also improving upon the results by van Zylen et al. We also point out connections to the famous open problem of finding a Kemeny consensus with 3 voters.