9 papers
Polynomial-Time Approximate EFX for Chores via Flow and Matching
Genjie Qin, Qizhi Fang, Minming Li +2
We study approximate EFX allocations of indivisible chores under nonnegative additive costs. Exact EFX allocations need not exist in general. We develop a polynomial-time algorithm…
Mechanism Design for Bridge Location with Optional Preferences
Xiaoshuang Geng, Wenjing Liu, Genjie Qin +1
We study the bridge location problem with optional preferences, where two separated regions each contain one prelocated facility. Each agent has a private location and a private pr…
Mechanism Design for Facility Location Games Under a Prelocated Facility
Genjie Qin, Qizhi Fang, Wenjing Liu
We study the problem of locating a new homogeneous facility under a prelocated facility. Here, a set of agents is located on a real line or a circle, each of whom has her locat…
Constrained Distributed Heterogeneous Two-Facility Location Problems with Max-Variant Cost
Xinru Xu, Wenjing Liu, Qizhi Fang +1
This paper investigates a constrained distributed heterogeneous two-facility location problem under the max-variant cost model. In this setting, a set of agents with private locati…
Mechanism Design for Locating a Bridge Between Regions with Prelocated Facilities
Genjie Qin, Chenhao Wang, Jianan Lin +2
In many urban planning projects, social planners require the construction of a bridge to connect two regions separated by obstacles such as rivers or highways. This paper studies t…
Facility Location Games for Multi-Location Agents with Satisfaction
Huanjun Wang, Qizhi Fang, Wenjing Liu
In this paper, we study mechanism design for single-facility location games where each agent has multiple private locations in [0, 1]. The individual objective is a satisfaction fu…
Constrained Distributed Heterogeneous Two-Facility Location Problems with Max-Variant Cost
Xinru Xu, Wenjing Liu, Qizhi Fang
We study a constrained distributed heterogeneous two-facility location problem, where a set of agents with private locations on the real line are divided into disjoint groups. The…
Truthful Two-Obnoxious-Facility Location Games with Optional Preferences and Minimum Distance Constraint
Xiaojia Han, Wenjing Liu, Qizhi Fang
In this paper, we study a truthful two-obnoxious-facility location problem, in which each agent has a private location in [0, 1] and a public optional preference over two obnoxious…
Constrained Heterogeneous Two-facility Location Games with Max-variant Cost
Qi Zhao, Wenjing Liu, Qizhi Fang +1
In this paper, we propose a constrained heterogeneous facility location model where a set of alternative locations are feasible for building facilities and the number of facilities…