2 citations · 5 across the 16 of their papers we have counts for
5 papers · 1 filter
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…