Strategyproof bridge placement minimizes costs with optional preferences
Mechanism Design for Bridge Location with Optional Preferences
Computer Science and Game Theory
Summary
This paper studies how to place a bridge between two facilities so that people who want to use one or both facilities have the least travel cost possible. Each person has a private location and a preference for which facilities they care about. The challenge is to design a method that makes people honestly share their locations and preferences while placing the bridge at a location that keeps overall travel costs low. The authors give optimal and approximate methods for different ways of measuring travel costs and prove limits on how well any method can do.
What this means in practice
- •For urban planners: Optimize bridge locations connecting regions to minimize average or maximum travel times based on people’s facility preferences.
- •For transportation system designers: Design strategies ensuring truthful information about user locations and preferences when placing new transport links to improve service efficiency.
Authors
Xiaoshuang Geng, Wenjing Liu, Genjie Qin, Qizhi Fang
Abstract
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 preference specifying a nonempty subset of the two facilities in which she is interested. Her individual cost is measured by one of three natural variants: the maximum, the sum, or the minimum of her distances to the facilities in which she is interested. The social planner must design deterministic strategyproof mechanisms that elicit truthful reports, choose the location of a connecting bridge, and approximately minimize either the social cost or the maximum cost. Our main results are as follows. For the social cost objective, we design optimal mechanisms for the max-variant and sum-variant costs, and provide a 3-approximation mechanism for the min-variant cost, and establish a lower bound of 2 for the min-variant. For the maximum cost objective, we give 5/3-approximation mechanisms for the max-variant and sum-variant costs, and a 3-approximation mechanism for the min-variant cost; we also prove a common lower bound of 5/3 that applies to all three cost variants under the maximum cost objective.