36 citations · 122 across the 33 of their papers we have counts for
40 papers
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…
Efficient Algorithms for Monroe and CC Rules in Multi-Winner Elections with (Nearly) Structured Preferences
Jiehua Chen, Christian Hatschka, Sofia Simola
We investigate winner determination for two popular proportional representation systems: the Monroe and Chamberlin-Courant (abbrv. CC) systems. Our study focuses on (nearly) single…
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…
Parameterized Intractability for Multi-Winner Election under the Chamberlin-Courant Rule and the Monroe Rule
Jiehua Chen, Sanjukta Roy
Answering an open question by Betzler et al. [Betzler et al., JAIR'13], we resolve the parameterized complexity of the multi-winner determination problem under two famous represent…
Multidimensional Manhattan Preferences
Jiehua Chen, Martin Nöllenburg, Sofia Simola +2
A preference profile (i.e., a collection of linear preference orders of the voters over a set of alternatives) with alternatives and voters is -Manhattan (resp. -Eucl…
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…
Participatory Budgeting with Donations and Diversity Constraints
Jiehua Chen, Martin Lackner, Jan Maly
Participatory budgeting (PB) is a democratic process where citizens jointly decide on how to allocate public funds to indivisible projects. This paper focuses on PB processes where…
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…
Efficient fully dynamic elimination forests with applications to detecting long paths and cycles
Jiehua Chen, Wojciech Czerwiński, Yann Disser +8
We present a data structure that in a dynamic graph of treedepth at most , which is modified over time by edge insertions and deletions, maintains an optimum-height elimination…
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…
Good Things Come to Those Who Swap Objects on Paths
Matthias Bentert, Jiehua Chen, Vincent Froese +1
We study a simple exchange market, introduced by Gourvés, Lesca and Wilczynski (IJCAI-17), where every agent initially holds a single object. The agents have preferences over the o…
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…