15 citations · 51 across the 31 of their papers we have counts for
39 papers
Logarithmic Comparison-Query Complexity for EF1 Allocations
Zehan Lin, Shengxin Liu, Biaoshuai Tao +1
We study the comparison-query complexity of computing allocations that are envy-free up to one item (EF1) for agents with heterogeneous additive preferences over indivisibl…
Fair and Efficient Allocations: Decision Problems in the Gap of Polynomial Hierarchy
Xiaolin Bu, Biaoshuai Tao
We consider the fair division problem with indivisible goods and study the following decision problem: given a fair division instance, does there exist an allocation that is envy-f…
Comparison-Based Fair Division of Indivisible Chores
Zehan Lin, Shengxin Liu, Biaoshuai Tao +1
We investigate the query complexity of fairly allocating indivisible chores among agents with additive cost functions. We depart from the standard cardinal model and assume…
Almost Envy-Freeness for Additive Mixed Manna with Entitlements: Deterministic and Randomized Guarantees
Zehan Lin, Shengxin Liu, Biaoshuai Tao +1
We investigate the fair allocation of indivisible items among agents with asymmetric entitlements in mixed manna settings, where the items consist of both goods and chores. For add…
Non-Existence of EFX Chore Allocations for Monotone Cost Functions with Binary Marginals
Zehan Lin, Shengxin Liu, Biaoshuai Tao +1
We study the existence of envy-free up to any item (EFX) allocations of indivisible chores when agents have monotone cost functions with binary marginals. For indivisible goods, th…
Bayesian Fair Division: Truthfulness in Picking Sequence with Correlated Valuations
Xiaolin Bu, Biaoshuai Tao
Sequential allocation mechanisms contain a class of widely studied mechanisms (e.g., round-robin) in the fair division of indivisible goods, where agents take turns picking items i…
Limitations of Best-of-Both-Worlds Solutions in Approval-Based Multiwinner Elections
Jiarong Jin, Xuanxuan Liu, Biaoshuai Tao
We study the best-of-both-worlds fairness in approval-based multi-winner elections, asking whether ex-ante guarantees for a fractional outcome can be implemented while every realiz…
Auctions with Contract Design
Xiaolin Bu, Jiarong Jin, Junzhu Ke +6
We consider a new auction model where the bidders' utilities and the auctioneer's revenue depend on a quality factor of the transaction determined by costly and strategic investmen…
Best-of-Both-Worlds Fairness for Mixed Goods and Chores
Haris Aziz, Xiaolin Bu, Xinhang Lu +4
We study the fundamental problem of fairly dividing indivisible items among agents with additive utilities. In our model, an item can be a good yielding non-negative utilities to s…
EFX for Additive Chores: Nonexistence, Pareto Incompatibility, and Bi-Valued Existence
Wentao He, Biaoshuai Tao
We consider the fair division problem of indivisible chores and resolve the long-standing open problem for the existence of EFX (envy-free up to any item) allocations with additive…
Incentive Analysis of Collusion in Fair Division
Haoqiang Huang, Biaoshuai Tao, Mingwei Yang +1
We study fair division problems with strategic agents capable of gaining advantages by manipulating their reported preferences. Although several impossibility results have revealed…
On Pareto-Optimal and Fair Allocations with Personalized Bi-Valued Utilities
Jiarong Jin, Biaoshuai Tao
We study the fair division problem of allocating indivisible goods to agents with additive personalized bi-valued utilities. Specifically, each agent assigns one of two…
Online MMS Allocation for Chores
Jiaxin Song, Biaoshuai Tao, Wenqian Wang +1
We study the problem of fair division of indivisible chores among agents in an online setting, where items arrive sequentially and must be allocated irrevocably upon arrival. T…
Aggregating Information and Preferences with Bounded-Size Deviations
Qishen Han, Grant Schoenebeck, Biaoshuai Tao +1
We investigate a voting scenario with two groups of agents whose preferences depend on a ground truth that cannot be directly observed. The majority's preferences align with the gr…
The Art of Two-Round Voting
Qishen Han, Grant Schoenebeck, Biaoshuai Tao +1
We study the voting problem with two alternatives where voters' preferences depend on a not-directly-observable state variable. While equilibria in the one-round voting mechanisms…
When is Truthfully Allocating Chores no Harder than Goods?
Bo Li, Biaoshuai Tao, Fangxiao Wang +3
We study the problem of fairly and efficiently allocating a set of items among strategic agents with additive valuations, where items are either all indivisible or all divisible. W…
Strong Equilibria in Bayesian Games with Bounded Group Size
Qishen Han, Grant Schoenebeck, Biaoshuai Tao +1
We study the group strategic behaviors in Bayesian games. Equilibria in previous work do not consider group strategic behaviors with bounded sizes and are too ``strong'' to exist i…
Best-of-Both-Worlds Fair Allocation of Indivisible and Mixed Goods
Xiaolin Bu, Zihao Li, Shengxin Liu +2
We study the problem of fairly allocating either a set of indivisible goods or a set of mixed divisible and indivisible goods (i.e., mixed goods) to agents with additive utilities,…
Truthful and Almost Envy-Free Mechanism of Allocating Indivisible Goods: the Power of Randomness
Xiaolin Bu, Biaoshuai Tao
We study the problem of fairly and truthfully allocating indivisible items to agents with additive preferences. Specifically, we consider truthful mechanisms outputting all…
Logarithmic Comparison-Based Query Complexity for Fair Division of Indivisible Goods
Xiaolin Bu, Zihao Li, Shengxin Liu +2
We study the problem of fairly allocating indivisible goods to agents, where agents may have different preferences over the goods. In the traditional setting, agents' valua…
A Complete Landscape for the Price of Envy-Freeness
Zihao Li, Shengxin Liu, Xinhang Lu +2
We study the efficiency of fair allocations using the well-studied price of fairness concept, which quantitatively measures the worst-case efficiency loss when imposing fairness co…
Fair Division with Allocator's Preference
Xiaolin Bu, Zihao Li, Shengxin Liu +2
We study the fair allocation of indivisible resources among agents. Most prior work focuses on fairness and/or efficiency among agents. However, the allocator, as the resource owne…
On the Existence of EFX (and Pareto-Optimal) Allocations for Binary Chores
Biaoshuai Tao, Xiaowei Wu, Ziqi Yu +1
We study the problem of allocating a group of indivisible chores among agents while each chore has a binary marginal. We focus on the fairness criteria of envy-freeness up to any i…
The Incentive Guarantees Behind Nash Welfare in Divisible Resources Allocation
Xiaohui Bei, Biaoshuai Tao, Jiajun Wu +1
We study the problem of allocating divisible resources among agents, hopefully in a fair and efficient manner. With the presence of strategic agents, additional incentive guara…