10 papers
Strategyproof Mechanisms for Connecting Impassable Regions
Hau Chan, Jianan Lin, Chenhao Wang
We study strategyproof mechanisms for building a pathway between two regions of a line segment separated by an obstacle. Each of the agents has a private location within its re…
Improved Randomized Approximations for Strategic Obnoxious Facility Location
Hau Chan, Jianan Lin, Chenhao Wang
We study randomized strategyproof mechanisms for strategic obnoxious facility location on a line segment, where agents wish the facility to be located as far away from them as poss…
Randomized Strategyproof Facility Location: Two Facilities and Beyond
Hau Chan, Jianan Lin, Chenhao Wang
We design and analyze randomized strategyproof mechanisms for multi-facility location under the utilitarian social-cost objective, the sum of the agents' distances to their nearest…
Improved Metric Distortion Bounds for Deterministic Weighted-Tournament Voting Rules
Hau Chan, Jianan Lin, Chenhao Wang
In metric social choice, voters and candidates lie in a common but unknown metric space, voters rank candidates by distance, and a voting rule seeks to minimize total distance to t…
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…
Strategyproof Mechanisms for Euclidean Facility Location Problems under -norm Social Cost
Hau Chan, Jianan Lin, Chenhao Wang
We study strategyproof mechanisms for eliciting agents' location preferences truthfully in the Euclidean plane and locating a facility so as to minimize the -nor…
Mechanism Design for Connecting Regions Under Disruptions
Hau Chan, Jianan Lin, Zining Qin +1
Man-made and natural disruptions such as planned constructions on roads, suspensions of bridges, and blocked roads by trees/mudslides/floods can often create obstacles that separat…
Obnoxious Facility Location Problems: Strategyproof Mechanisms Optimizing -Aggregated Utilities and Costs
Hau Chan, Jianan Lin, Chenhao Wang
We study the problem of locating a single obnoxious facility on the normalized line segment with strategic agents from a mechanism design perspective. Each agent has a pref…
Strategyproof Facility Location with Prediction: Minimizing the Maximum Cost
Hau Chan, Jianan Lin, Chenhao Wang
We study the mechanism design problem of facility location on a metric space in the learning-augmented framework, where mechanisms have access to imperfect predictions of the optim…
Mechanism Design for Extending the Accessibility of Facilities
Hau Chan, Jianan Lin, Chenhao Wang +1
We study a variation of facility location problems (FLPs) that aims to improve the accessibility of agents to the facility within the context of mechanism design without money. In…