3 papers
cs.GT2025
Non-Monotonicity in Fair Division of Graphs
Hadi Hosseini, Shraddha Pathak, Yu Zhou
We consider the problem of fairly allocating the vertices of a graph among agents, where the value of a bundle is determined by its cut value -- the number of edges with exactl…
cs.GT2025
Bin Packing and Covering: Pushing the Frontier on the Maximin Share Fairness
Bo Li, Ankang Sun, Zunyu Wang +1
We study a fundamental fair allocation problem, where the agent's value is determined by the number of bins either used to pack or cover the items allocated to them. Fairness is ev…
cs.GT2025
A Complete Landscape of EFX Allocations on Graphs: Goods, Chores and Mixed Manna
Bo Li, Minming Li, Tianze Wei +2
We study envy-free up to any item (EFX) allocations on simple graphs where vertices and edges represent agents and items respectively. An agent (vertex) is only interested in items…