Author name cluster

Ankang Sun

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.

12 papers

2 author rows

AAMAS Conference 2026 Conference Paper

Fair Orientations: Proportionality and Equitability

Ankang Sun
Ruijie Wang
Bo Li

Westudythefairallocationofindivisibleitemsunderrelevanceconstraints, where each agent has a set of relevant items and can only receive items that are relevant to them. While the relevance constraint has been studied in recent years, existing work has largely focused on envy-freeness. Our work extends this study to other key fairness criteria — such as proportionality, equitability, and their relaxations — in settings where the items may be goods, chores, or a mixture of both. We complement the literature by presenting a picture of the existence and computational complexity of the considered criteria.

PDF

I&C Journal 2025 Journal Article

On the price of fairness of allocating contiguous blocks

Ankang Sun
Bo Li

Resource allocation is a fundamental problem in multi-agent systems, with two key factors to consider: fairness and efficiency. The concept of the “price of fairness” helps in the understanding of efficiency loss under fairness constraints. Among the diverse resource allocation settings, cake cutting stands out as a prominent model. Previous works by Suksompong [Discret. Appl. Math. , 2019] and Höhne and van Stee [Inf. Comput. , 2021] examined a variation of this model in which the cake represents indivisible items, with each agent requiring a contiguous block of items. These two works provided upper and lower bounds on the price of fairness when fairness is measured by envy-freeness and proportionality. However, in the case of indivisible items, achieving envy-free or proportional allocations is difficult, rendering these bounds insufficient for a comprehensive understanding of the true trade-off between fairness and efficiency. In this paper, we revisit the same problem and consider fairness notions that are satisfiable, including proportionality up to one item, and maximin share fairness. We investigate the efficiency loss under these fairness constraints and establish (almost) tight prices of fairness.

Details DOI

AAAI Conference 2025 Conference Paper

The (Exact) Price of Cardinality for Indivisible Goods: A Parametric Perspective

Alexander Lam
Bo Li
Ankang Sun

We adopt a parametric approach to analyze the worst-case degradation in social welfare when the allocation of indivisible goods is constrained to be fair. Specifically, we are concerned with cardinality-constrained allocations, which require that each agent has at most k items in their allocated bundle. We propose the notion of the price of cardinality, which captures the worst-case multiplicative loss of utilitarian or egalitarian social welfare resulting from imposing the cardinality constraint. We then characterize tight or almost-tight bounds on the price of cardinality as exact functions of the instance parameters, demonstrating how the social welfare improves as k is increased. In particular, one of our main results refines and generalizes the existing asymptotic bound of Θ(√n) on the price of balancedness. We also further extend our analysis to the problem where the items are partitioned into disjoint categories, and each category has its own cardinality constraint. Through a parametric study of the price of cardinality, we provide a framework which aids decision makers in choosing an ideal level of cardinality-based fairness, using their knowledge of the potential loss of utilitarian and egalitarian social welfare.

PDF Details DOI

AAMAS Conference 2024 Conference Paper

Allocating Contiguous Blocks of Indivisible Chores Fairly: Revisited

Ankang Sun
Bo Li

Resource allocation is a fundamental problem in multi-agent systems, with two key factors to consider: fairness and efficiency. The concept of the “price of fairness” helps in the understanding of efficiency loss under fairness constraints. Among the diverse resource allocation settings, cake cutting stands out as a prominent model. Recently, Höhne and van Stee [Inf. Comput. , 2021] examined a variation of this model in which the cake represents indivisible chores, with each agent requiring a connected piece of the chores. Höhne and van Stee provided upper and lower bounds on the price of fairness when fairness is measured by envy-freeness and proportionality. However, in the case of indivisible items, achieving envy-free and proportional allocations is difficult, rendering these bounds insufficient for a comprehensive understanding of the true trade-off between fairness and efficiency. In this paper, we revisit the same problem and consider fairness notions that are satisfiable, including proportionality up to one item, and maximin share fairness. By presenting tight bounds on the price of fairness with respect to these notions, we complete the picture of fairness and efficiency trade-off.

PDF

AAMAS Conference 2024 Conference Paper

Bounding the Incentive Ratio of the Probabilistic Serial Rule

Bo Li
Ankang Sun
Shiji Xing

Probabilistic Serial (PS) is a well-studied allocation rule used for distributing resources among multiple agents. Although it satisfies certain notable fairness and welfare properties, it is not truthful. This means that agents have incentives to misreport their preferences in order to influence the allocation in their favor. An interesting research question is to understand the extent to which an agent can gain from manipulation. A widely-accepted concept employed for this exploration is the incentive ratio, defined as the supreme ratio, across all instances of the problem, between the utility an agent obtains by employing an optimal manipulation strategy and the utility they receive when being truthful. Wang et al. [AAAI, 2020] examined the incentive ratio of PS for the setting when the number of items 𝑚 equals the number of agents 𝑛 and proved that the incentive ratio is 1. 5. In this paper, we study the general scenario in which 𝑚 and 𝑛 can be arbitrary. We prove that in this case, the tight incentive ratio of PS is 2 − 1 2𝑛−1.

PDF

AAAI Conference 2024 Conference Paper

Envy-Free House Allocation under Uncertain Preferences

Haris Aziz
Isaiah Iliffe
Bo Li
Angus Ritossa
Ankang Sun
Mashbat Suzuki

Envy-freeness is one of the most important fairness concerns when allocating items. We study envy-free house allocation when agents have uncertain preferences over items and consider several well-studied preference uncertainty models. The central problem that we focus on is computing an allocation that has the highest probability of being envy-free. We show that each model leads to a distinct set of algorithmic and complexity results, including detailed results on (in-)approximability. En route, we consider two related problems of checking whether there exists an allocation that is possibly or necessarily envy-free. We give a complete picture of the computational complexity of these two problems for all the uncertainty models we consider.

PDF Details DOI

AAMAS Conference 2023 Conference Paper

Equitability and Welfare Maximization for Allocating Indivisible Items

Ankang Sun
Bo Chen
Xuan Vinh Doan

We study fair allocations of indivisible goods and chores in conjunction with system efficiency, measured by two social welfare functions, namely utilitarian and egalitarian welfare. To model preference, each agent is associated with a cardinal and additive valuation function. The fairness criteria we are concerned with are equitability up to any item (EQX) and equitability up to one item (EQ1). For the trade-off between fairness and efficiency, we investigate efficiency loss under these fairness constraints and establish the price of fairness. From the computational perspective, we provide an almost complete picture of the computational complexity of (i) deciding the existence of an EQX/EQ1 and welfare-maximizing allocation; (ii) computing a welfare maximizer among all EQX/EQ1 allocations.

PDF

JAAMAS Journal 2023 Journal Article

Fairness criteria for allocating indivisible chores: connections and efficiencies

Ankang Sun
Bo Chen
Xuan Vinh Doan

Abstract We study several fairness notions in allocating indivisible chores (i. e. , items with disutilities) to agents who have additive and submodular cost functions. The fairness criteria we are concerned with are envy-free up to any item, envy-free up to one item, maximin share (MMS), and pairwise maximin share (PMMS), which are proposed as relaxations of envy-freeness in the setting of additive cost functions. For allocations under each fairness criterion, we establish their approximation guarantee for other fairness criteria. Under the additive setting, our results show strong connections between these fairness criteria and, at the same time, reveal intrinsic differences between goods allocation and chores allocation. However, such strong relationships cannot be inherited by the submodular setting, under which PMMS and MMS are no longer relaxations of envy-freeness and, even worse, few non-trivial guarantees exist. We also investigate efficiency loss under these fairness constraints and establish their prices of fairness.

Details DOI

ECAI Conference 2023 Conference Paper

On the Price of Fairness in the Connected Discrete Cake Cutting Problem

Ankang Sun
Bo Li 0037

Discrete cake cutting is a fundamental model in fair resource allocation where the indivisible resources are located on a path. It is well motivated that, in reality, each agent is interested in receiving a contiguous block of items. An important question therein is to understand the economic efficiency loss by restricting the allocations to be fair, which is quantified as price of fairness (PoF). Informally, PoF is the worst-case ratio between the unconstrained optimal welfare and the optimal welfare achieved by fair allocations. Suksompong [Discret. Appl. Math. , 2019] has studied this problem, where fairness is measured by the ideal criteria such as proportionality (PROP). A PROP allocation, however, may not exist in discrete cake cutting settings. Therefore, in this work, we revisit this problem and focus on the relaxed notions whose existence is guaranteed. We study both utilitarian and egalitarian welfare, and our results show significant differences between the PoF of guaranteed fairness notions and that of the ideal notions.

Details

JAAMAS Journal 2022 Journal Article

Equitability and welfare maximization for allocating indivisible items

Ankang Sun
Bo Chen
Xuan Vinh Doan

Abstract We study fair allocations of indivisible goods and chores in conjunction with system efficiency, measured by two social welfare functions, namely utilitarian and egalitarian welfare. To model preference, each agent is associated with a cardinal and additive valuation function. The fairness criteria we are concerned with are equitability up to any item (EQX) and equitability up to one item (EQ1). For the trade-off between fairness and efficiency, we investigate efficiency loss under these fairness constraints and establish the price of fairness. From the computational perspective, we provide a complete picture of the computational complexity of (i) deciding the existence of an EQX/EQ1 and welfare-maximizing allocation; (ii) computing a welfare maximizer among all EQX/EQ1 allocations.

Details DOI

ICML Conference 2021 Conference Paper

Approximate Group Fairness for Clustering

Bo Li 0037
Lijun Li
Ankang Sun
Chenhao Wang 0001
Yingfan Wang

We incorporate group fairness into the algorithmic centroid clustering problem, where $k$ centers are to be located to serve $n$ agents distributed in a metric space. We refine the notion of proportional fairness proposed in [Chen et al. , ICML 2019] as {\em core fairness}. A $k$-clustering is in the core if no coalition containing at least $n/k$ agents can strictly decrease their total distance by deviating to a new center together. Our solution concept is motivated by the situation where agents are able to coordinate and utilities are transferable. A string of existence, hardness and approximability results is provided. Particularly, we propose two dimensions to relax core requirements: one is on the degree of distance improvement, and the other is on the size of deviating coalition. For both relaxations and their combination, we study the extent to which relaxed core fairness can be satisfied in metric spaces including line, tree and general metric space, and design approximation algorithms accordingly. We also conduct experiments on synthetic and real-world data to examine the performance of our algorithms.

Details

AAMAS Conference 2021 Conference Paper

Connections between Fairness Criteria and Efficiency for Allocating Indivisible Chores

Ankang Sun
Bo Chen
Xuan Vinh Doan

We study several fairness notions in allocating indivisible chores (i. e. , items with non-positive values): envy-freeness and its relaxations. For allocations under each fairness criterion, we establish their approximation guarantees for other fairness criteria. Under the setting of additive cost functions, our results show strong connections between these fairness criteria and, at the same time, reveal intrinsic differences between goods allocation and chores allocation. Furthermore, we investigate the efficiency loss under these fairness constraints and establish their prices of fairness.

PDF