Junjie Luo

EAAI Journal 2026 Journal Article

QFTD: An efficient quantum federated learning for transformer fault diagnosis with minimal gated unit in smart grid

• Guodong Li
• Junjie Luo
• Qingle Wang
• Lin Liu
• Chunyan Wei
• Huawei Wang
• Zhichao Zhang

AAMAS Conference 2025 Conference Paper

Computing Efficient Envy-Free Partial Allocations of Indivisible Goods

• Robert Bredereck
• Andrzej Kaczmarczyk
• Junjie Luo
• Bin Sun

Envy-freeness is one of the most prominent fairness concepts in the allocation of indivisible goods. Even though trivial envy-free allocations always exist, rich literature shows this is not true when one additionally requires some efficiency concept (e. g. , completeness, Pareto-efficiency, or social welfare maximization). In fact, in such case even deciding the existence of an efficient envy-free allocation is notoriously computationally hard. In this paper, we explore the limits of efficient computability by relaxing standard efficiency concepts and analyzing how this impacts the computational complexity of the respective problems. Specifically, we allow partial allocations (where not all goods are allocated) and impose only very mild efficiency constraints, such as ensuring each agent receives a bundle with positive utility. Surprisingly, even such seemingly weak efficiency requirements lead to a diverse computational complexity landscape. We identify several polynomial-time solvable or fixed-parameter tractable cases for binary utilities, yet we also find NP-hardness in very restricted scenarios involving ternary utilities.

JAAMAS Journal 2024 Journal Article

Multivariate algorithmics for eliminating envy by donating goods

• Niclas Boehmer
• Robert Bredereck
• Junjie Luo

Abstract Fairly dividing a set of indivisible resources to a set of agents is of utmost importance in some applications. However, after an allocation has been implemented the preferences of agents might change and envy might arise. We study the following problem to cope with such situations: given an allocation of indivisible resources to agents with additive utility-based preferences, is it possible to socially donate some of the resources (which means removing these resources from the allocation instance) such that the resulting modified allocation is envy-free (up to one good). We require that the number of deleted resources and/or the caused utilitarian welfare loss of the allocation are bounded. We conduct a thorough study of the (parameterized) computational complexity of this problem considering various natural and problem-specific parameters (e. g. , the number of agents, the number of deleted resources, or the maximum number of resources assigned to an agent in the initial allocation) and different preference models, including unary-encoded and 0/1-valuations. In our studies, we obtain a rich set of (parameterized) tractability and intractability results and discover several surprising contrasts, for instance, between the two closely related fairness concepts envy-freeness and envy-freeness up to one good and between the influence of the parameters maximum number and welfare of the deleted resources.

JAAMAS Journal 2023 Journal Article

Fine-grained view on bribery for group identification

• Niclas Boehmer
• Robert Bredereck
• Junjie Luo

Abstract Given a set of agents qualifying or disqualifying each other, group identification is the task of identifying a socially qualified subgroup of agents. Social qualification depends on the specific rule used to aggregate individual qualifications. The classical bribery problem in this context asks how many agents need to change their qualifications in order to change the outcome in a certain way. Complementing previous results showing polynomial-time solvability or NP-hardness of bribery for various social rules in the constructive (aiming at making specific agents socially qualified) or destructive (aiming at making specific agents socially disqualified) setting, we provide a comprehensive picture of the parameterized computational complexity landscape. Conceptually, we also consider a more fine-grained concept of bribery cost, where we ask how many single qualifications need to be changed, nonunit prices for different bribery actions, and a more general bribery goal that combines the constructive and destructive setting.

JAIR Journal 2023 Journal Article

Improving Resource Allocations by Sharing in Pairs

• Robert Bredereck
• Andrzej Kaczmarczyk
• Junjie Luo
• Rolf Niedermeier
• Florian Sachse

Given an initial resource allocation, where some agents may envy others or where a different distribution of resources might lead to a higher social welfare, our goal is to improve the allocation without reassigning resources. We consider a sharing concept allowing resources being shared with social network neighbors of the resource owners. More precisely, our model allows agents to form pairs which then may share a limited number of resources. Sharing a resource can come at some costs or loss in utility. To this end, we introduce a formal model that allows a central authority to compute an optimal sharing between neighbors based on an initial allocation. Advocating this point of view, we focus on the most basic scenario where each agent can participate in a bounded number of sharings. We present algorithms for optimizing utilitarian and egalitarian social welfare of allocations and for reducing the number of envious agents. In particular, we examine the computational complexity with respect to several natural parameters. Furthermore, we study cases with restricted social network structures and, among others, devise polynomial-time algorithms in path- and tree-like (hierarchical) social networks.

AAMAS Conference 2022 Conference Paper

Multivariate Algorithmics for Eliminating Envy by Donating Goods

• Niclas Boehmer
• Robert Bredereck
• Klaus Heeger
• Dušan Knop
• Junjie Luo

Fairly dividing a set of indivisible resources to a set of agents is of utmost importance in some applications. However, after an allocation has been implemented the preferences of agents might change and envy might arise. We study the following problem to cope with such situations: Given an allocation of indivisible resources to agents with additive utility-based preferences, is it possible to socially donate some of the resources (which means removing these resources from the allocation instance) such that the resulting modified allocation is envy-free (up to one good). We require that the number of deleted resources and/or the caused utilitarian welfare loss of the allocation are bounded. We conduct a thorough study of the (parameterized) computational complexity of this problem considering various natural and problem-specific parameters (e. g. , the number of agents, the number of deleted resources, or the maximum number of resources assigned to an agent in the initial allocation) and different preference models, including unary and 0/1-valuations. In our studies, we obtain a rich set of (parameterized) tractability and intractability results and discover several surprising contrasts, for instance, between the two closely related fairness concepts envy-freeness and envy-freeness up to one good and between the influence of the parameters maximum number and welfare of the deleted resources.

AAAI Conference 2022 Conference Paper

On Improving Resource Allocations by Sharing

• Robert Bredereck
• Andrzej Kaczmarczyk
• Junjie Luo
• Rolf Niedermeier
• Florian Sachse

Given an initial resource allocation, where some agents may envy others or where a different distribution of resources might lead to higher social welfare, our goal is to improve the allocation without reassigning resources. We consider a sharing concept allowing resources being shared with social network neighbors of the resource owners. To this end, we introduce a formal model that allows a central authority to compute an optimal sharing between neighbors based on an initial allocation. Advocating this point of view, we focus on the most basic scenario where a resource may be shared by two neighbors in a social network and each agent can participate in a bounded number of sharings. We present algorithms for optimizing utilitarian and egalitarian social welfare of allocations and for reducing the number of envious agents. In particular, we examine the computational complexity with respect to several natural parameters. Furthermore, we study cases with restricted social network structures and, among others, devise polynomial-time algorithms in path- and treelike (hierarchical) social networks.

AAAI Conference 2020 Conference Paper

Adapting Stable Matchings to Evolving Preferences

• Robert Bredereck
• Jiehua Chen
• Dušan Knop
• Junjie Luo
• Rolf Niedermeier

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 ROOMMATES. That is, we try to answer the following question: for both problems, what is the computational cost of adapting an existing stable matching after some of the preferences of the agents have changed. While doing so, we also model the constraint that the new stable matching shall be not too different from the old one. After formalizing these incremental versions, we provide a fairly comprehensive picture of the computational complexity landscape of INCREMENTAL STA- BLE MARRIAGE and INCREMENTAL STABLE ROOMMATES. To this end, we exploit the parameters “degree of change” both in the input (difference between old and new preference pro- file) and in the output (difference between old and new stable matching). We obtain both hardness and tractability results, in particular showing a fixed-parameter tractability result with respect to the parameter “distance between old and new stable matching”.

IJCAI Conference 2020 Conference Paper

Fine-Grained View on Bribery for Group Identification

• Niclas Boehmer
• Robert Bredereck
• Dušan Knop
• Junjie Luo

Given a set of individuals qualifying or disqualifying each other, group identification is the task of identifying a socially qualified subgroup of individuals. Social qualification depends on the specific rule used to aggregate individual qualifications. The bribery problem in this context asks how many agents need to change their qualifications in order to change the outcome. Complementing previous results showing polynomial-time solvability or NP-hardness of bribery for various social rules in the constructive (aiming at making specific individuals socially qualified) or destructive (aiming at making specific individuals socially disqualified) setting, we provide a comprehensive picture of the parameterized computational complexity landscape. Conceptually, we also consider a more fine-grained concept of bribery cost, where we ask how many single qualifications need to be changed, and a more general bribery goal that combines the constructive and destructive setting.

AAMAS Conference 2019 Conference Paper

Complexity of Manipulation in Premise-Based Judgment Aggregation with Simple Formulas

• Robert Bredereck
• Junjie Luo

Judgment aggregation is a framework to aggregate individual opinions on multiple, logically connected issues into a collective outcome. It is open to manipulative attacks such as Manipulation where judges cast their judgments strategically. Previous works have shown that most computational problems corresponding to these manipulative attacks are NP-hard. This desired computational barrier, however, often relies on formulas that are either of unbounded size or of complex structure. We revisit the computational complexity for a large class of Manipulation problems in judgment aggregation, now focusing on simple and realistic formulas. We restrict all formulas to be clauses that are (positive) monotone, Horn-clauses, or have bounded length. For basic variants of Manipulation, we show that these restrictions make several variants, which were in general known to be NP-hard, polynomial-time solvable. Moreover, we provide a P vs. NP dichotomy for a large class of clause restrictions (generalizing monotone and Horn clauses) by showing a close relationship between variants of Manipulation and variants of Satisfiability. For Hamming distance based Manipulation, we show that NPhardness even holds for positive monotone clauses of length three, but the problem becomes polynomial-time solvable for positive monotone clauses of length two.