2 citations · 5 across the 16 of their papers we have counts for
19 papers
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…
Fair Division by Contribution: A Shapley Value Perspective
Xiaohui Bei, Pinyan Lu, Xiaowei Wu +1
In many resource allocation problems, agents' valuations are best interpreted not as subjective preferences, but as the value they generate from receiving resources. Such valuation…
Allocating Chores with Restricted Additive Costs: Achieving EFX, MMS, and Efficiency Simultaneously
Zehan Lin, Xiaowei Wu, Shengwei Zhou
In a web-based review platform, papers from various research fields must be assigned to a group of reviewers. Each paper has an inherent cost, which represents the effort required…
An FPTAS for 7/9-Approximation to Maximin Share Allocations
Xin Huang, Shengwei Zhou
We present a new algorithm that achieves a -approximation for the \emph{maximin share (MMS)} allocation of indivisible goods under additive valuations, improving the c…
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…
Degree-bounded Online Bipartite Matching: OCS vs. Ranking
Yilong Feng, Haolong Li, Xiaowei Wu +1
We revisit the online bipartite matching problem on -regular graphs, for which Cohen and Wajc (SODA 2018) proposed an algorithm with a competitive ratio of $1-2\sqrt{H_d/d} = 1-…
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…
Approximately EFX and PO Allocations for Bivalued Chores
Zehan Lin, Xiaowei Wu, Shengwei Zhou
We consider the computation for allocations of indivisible chores that are approximately EFX and Pareto optimal (PO). Recently, Garg et al. (2024) show the existence of -EFX and…
Guaranteeing MMS for All but One Agent When Allocating Indivisible Chores
Jiawei Qiu, Xiaowei Wu, Cong Zhang +1
We study the problem of allocating indivisible chores to agents with additive cost functions under the fairness notion of maximin share (MMS). In this work, we propose a no…
Tree Splitting Based Rounding Scheme for Weighted Proportional Allocations with Subsidy
Xiaowei Wu, Shengwei Zhou
We consider the problem of allocating indivisible items to a set of heterogeneous agents, aiming at computing a proportional allocation by introducing subsidy (money). It h…
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…
One Quarter Each (on Average) Ensures Proportionality
Xiaowei Wu, Cong Zhang, Shengwei Zhou
We consider the problem of fair allocation of indivisible items to a group of agents with subsidy (money). Our work mainly focuses on the allocation of chores but most of o…
Improved Competitive Ratios for Online Bipartite Matching on Degree Bounded Graphs
Yilong Feng, Xiaowei Wu, Shengwei Zhou
We consider the online bipartite matching problem on -bounded graphs, where each online vertex has at most neighbors, each offline vertex has at least neighbors, and…
Multi-agent Online Scheduling: MMS Allocations for Indivisible Items
Shengwei Zhou, Rufan Bai, Xiaowei Wu
We consider the problem of fairly allocating a sequence of indivisible items that arrive online in an arbitrary order to a group of n agents with additive normalized valuation func…
Improved Competitive Ratio for Edge-Weighted Online Stochastic Matching
Yilong Feng, Guoliang Qiu, Xiaowei Wu +1
We consider the edge-weighted online stochastic matching problem, in which an edge-weighted bipartite graph G=(I\cup J, E) with offline vertices J and online vertex types I is give…
Weighted EF1 Allocations for Indivisible Chores
Xiaowei Wu, Cong Zhang, Shengwei Zhou
We study how to fairly allocate a set of indivisible chores to a group of agents, where each agent has a non-negative weight that represents its obligation for undertakin…
Approximately EFX Allocations for Indivisible Chores
Shengwei Zhou, Xiaowei Wu
In this paper, we study how to fairly allocate a set of m indivisible chores to a group of n agents, each of which has a general additive cost function on the items. Since envy-fre…