36 citations · 122 across the 33 of their papers we have counts for
21 papers · 1 filter
Multi-Winner Voting Games in TU and NTU: When is the Core Always Non-Empty?
Jiehua Chen, Christian Hatschka
Multi-winner approval voting selects a size- committee that aggregates voters' approval preferences over a set of alternatives. A central question is coalitional stability: No c…
Cutsets and EF1 Fair Division of Graphs
Jiehua Chen, William S. Zwicker
In fair division of a connected graph , each of agents receives a share of 's vertex set . These shares partition , with each share required to induce a co…
Algorithms and Complexity for Congested Assignments
Jiehua Chen, Jiong Guo, Yinghui Wen
We study the congested assignment problem as introduced by Bogomolnaia and Moulin (2023). We show that deciding whether a competitive assignment exists can be done in polynomial ti…
Optimal Seat Arrangement: What Are the Hard and Easy Cases?
Esra Ceylan, Jiehua Chen, Sanjukta Roy
We study four NP-hard optimal seat arrangement problems [Bodlaender et al., 2020a], which each have as input a set of n agents, where each agent has cardinal preferences over other…
Optimal Capacity Modification for Many-To-One Matching Problems
Jiehua Chen, Gergely Csáji
We consider many-to-one matching problems, where one side consists of students and the other side of schools with capacity constraints. We study how to optimally increase the capac…
Game Implementation: What Are the Obstructions?
Jiehua Chen, Sebastian Vincent Haydn, Negar Layegh Khavidaki +2
In many applications, we want to influence the decisions of independent agents by designing incentives for their actions. We revisit a fundamental problem in this area, called GAME…
2-Dimensional Euclidean Preferences
Laurent Bulteau, Jiehua Chen
A preference profile with m alternatives and n voters is 2-dimensional Euclidean if both the alternatives and the voters can be placed into a 2-dimensional space such that for each…
Hedonic Games With Friends, Enemies, and Neutrals: Resolving Open Questions and Fine-Grained Complexity
Jiehua Chen, Gergely Csáji, Sanjukta Roy +1
We investigate verification and existence problems for prominent stability concepts in hedonic games with friends, enemies, and optionally with neutrals [8, 16]. We resolve several…
Multi-Dimensional Stable Roommates in 2-Dimensional Euclidean Space
Jiehua Chen, Sanjukta Roy
We investigate the Euclidean -Dimensional Stable Roommates problem, which asks whether a given set~ of points from the 2-dimensional Euclidean space can be partit…
On (Coalitional) Exchange-Stable Matching
Jiehua Chen, Adrian Chmurovic, Fabian Jogl +1
We study (coalitional) exchange stability, which Alcalde [Economic Design, 1995] introduced as an alternative solution concept for matching markets involving property rights, such…
Fractional Matchings under Preferences: Stability and Optimality
Jiehua Chen, Sanjukta Roy, Manuel Sorge
We thoroughly study a generalized version of the classic Stable Marriage and Stable Roommates problems where agents may share partners. We consider two prominent stability concepts…
Stable Matchings with Diversity Constraints: Affirmative Action is beyond NP
Jiehua Chen, Robert Ganian, Thekla Hamm
We investigate the following many-to-one stable matching problem with diversity constraints (SMTI-Diverse): Given a set of students and a set of colleges which have preferences ove…
Adapting Stable Matchings to Evolving Preferences
Robert Bredereck, Jiehua Chen, Dušan Knop +2
Adaptivity to changing environments and constraints is key to success in modern society. We address this by proposing "incrementalized versions" of Stable Marriage and Stable Roomm…
Reaching Stable Marriage via Divorces is Hard
Jiehua Chen
We study the Reaching Stable Marriage via Divorces (DivorceSM) problem of deciding, given a Stable Marriage instance and an initial matching , whether there exists a stable mat…
Computational Complexity of Stable Marriage and Stable Roommates and Their Variants
Jiehua Chen
This paper gives an overview on and summarizes existing complexity and algorithmic results of some variants of the Stable Marriage and the Stable Roommates problems. The last secti…
Stable Roommates with Narcissistic, Single-Peaked, and Single-Crossing Preferences
Robert Bredereck, Jiehua Chen, Ugo Paavo Finnendahl +1
The classical Stable Roommates problem is to decide whether there exists a matching of an even number of agents such that no two agents which are not matched to each other would pr…
Matchings under Preferences: Strength of Stability and Trade-offs
Jiehua Chen, Piotr Skowron, Manuel Sorge
We propose two solution concepts for matchings under preferences: robustness and near stability. The former strengthens while the latter relaxes the classic definition of stability…
Small One-Dimensional Euclidean Preference Profiles
Jiehua Chen, Sven Grottke
We characterize one-dimensional Euclidean preference profiles with a small number of alternatives and voters. In particular, we show the following. 1. Every preference profile with…
Teams in Online Scheduling Polls: Game-Theoretic Aspects
Robert Bredereck, Jiehua Chen, Rolf Niedermeier +2
Consider an important meeting to be held in a team-based organization. Taking availability constraints into account, an online scheduling poll is being used in order to decide upon…
Parliamentary Voting Procedures: Agenda Control, Manipulation, and Uncertainty
Robert Bredereck, Jiehua Chen, Rolf Niedermeier +1
We study computational problems for two popular parliamentary voting procedures: the amendment procedure and the successive procedure. While finding successful manipulations or age…
The one-dimensional Euclidean domain: Finitely many obstructions are not enough
Jiehua Chen, Kirk Pruhs, Gerhard J. Woeginger
We show that one-dimensional Euclidean preference profiles can not be characterized in terms of finitely many forbidden substructures. This result is in strong contrast to the case…