Author name cluster

Ágnes Cseh

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

7 papers

1 author row

JAAMAS Journal 2024 Journal Article

Envy-freeness in 3D hedonic games

Michael McKay
Ágnes Cseh
David Manlove

Abstract We study the problem of fairly partitioning a set of agents into coalitions based on the agents’ additively separable preferences, which can also be viewed as a hedonic game. We study three successively weaker solution concepts, related to envy, weakly justified envy, and justified envy. In a model in which coalitions may have any size, trivial solutions exist for these concepts, which provides a strong motivation for placing restrictions on coalition size. In this paper, we require feasible coalitions to have size three. We study the existence of partitions that are envy-free, weakly justified envy-free, and justified envy-free, and the computational complexity of finding such partitions, if they exist. We impose various restrictions on the agents’ preferences and present a complete complexity classification in terms of these restrictions.

Details DOI

AAMAS Conference 2023 Conference Paper

The Swiss Gambit

Ágnes Cseh
Pascal Führlich
Pascal Lenzner

In each round of a Swiss-system tournament, players of similar score are paired against each other. An intentional early loss therefore might lead to weaker opponents in later rounds and thus to a better final tournament result—a phenomenon known as the Swiss Gambit. To the best of our knowledge it is an open question whether this strategy can actually work. This paper provides answers based on an empirical agent-based analysis for the most prominent application area of the Swisssystem format, namely chess tournaments. We simulate realistic tournaments by employing the official FIDE pairing system for computing the player pairings in each round. We show that even though gambits are widely possible in Swiss-system chess tournaments, profiting from them requires a high degree of predictability of match results. Moreover, even if a Swiss Gambit succeeds, the obtained improvement in the final ranking is limited. Our experiments prove that counting on a Swiss Gambit is indeed a lot more of a risky gambit than a reliable strategy to improve the final rank.

PDF

AAMAS Conference 2022 Conference Paper

Pareto Optimal and Popular House Allocation with Lower and Upper Quotas

Ágnes Cseh
Tobias Friedrich
Jannik Peters

In the house allocation problem with lower and upper quotas, we are given a set of applicants and a set of projects. Each applicant has a strictly ordered preference list over the projects she finds acceptable, while the projects are equipped with a lower and an upper quota. A feasible matching assigns the applicants to the projects in such a way that a project is either matched to no applicant or to a number of applicants between its lower and upper quota. In this model we study two classic optimality concepts: Pareto optimality and popularity. We show that finding a popular matching is hard even if the maximum lower quota is 2 and that finding a perfect Pareto optimal matching, verifying Pareto optimality, and verifying popularity are all NP-complete even if the maximum lower quota is 3. We complement the last three negative results by showing that the problems become polynomial-time solvable when the maximum lower quota is 2, thereby answering two open questions of Cechlárová and Fleiner [16]. Finally, we also study the parameterized complexity of all four mentioned problems.

PDF

AAMAS Conference 2022 Conference Paper

Three-Dimensional Popular Matching with Cyclic Preferences

Ágnes Cseh
Jannik Peters

Two actively researched problem settings in matchings under preferences are popular matchings and the three-dimensional stable matching problem with cyclic preferences. In this paper, we apply the optimality notion of the first topic to the input characteristics of the second one. We investigate the connection between stability, popularity, and their strict variants, strong stability and strong popularity in three-dimensional instances with cyclic preferences. Furthermore, we also derive results on the complexity of these problems when the preferences are derived from master lists.

PDF

AAMAS Conference 2021 Conference Paper

Multi-Robot Task Allocation-Complexity and Approximation

Haris Aziz
Hau Chan
Ágnes Cseh
Bo Li
Fahimeh Ramezani
Chenhao Wang

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.

PDF

AAMAS Conference 2021 Conference Paper

On Weakly and Strongly Popular Rankings

Sonja Kraiczy
Ágnes Cseh
David Manlove

Van Zuylen et al. [26] 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 π of the candidates is at least as good as any other ranking σ in the following sense: if we compare π to σ, at least half of all voters will always weakly prefer π. 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 π and σ to prefer π. In this paper, we derive structural and algorithmic results in both settings, also improving upon the results in [26]. We also point out connections to the famous open problem of finding a Kemeny consensus with 3 voters.

PDF

AAAI Conference 2021 Conference Paper

Optimal Kidney Exchange with Immunosuppressants

Haris Aziz
Ágnes Cseh
John P. Dickerson
Duncan C. McElfresh

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.

PDF Details