Mechanism Design for Connecting Regions Under Disruptions
For researchers in algorithmic game theory and mechanism design, this paper introduces a new problem domain (connecting regions under disruptions) and provides foundational theoretical results.
This paper initiates the study of mechanism design for connecting two regions separated by disruptions, where agents have private locations and the goal is to design strategyproof mechanisms that approximately minimize social or maximum cost. The authors characterize all strategyproof and anonymous mechanisms and provide upper and lower bounds on approximation ratios for social and maximum costs.
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 separate two connected regions. As a result, the traveling and reachability of agents from their respective regions to other regions can be affected. To minimize the impact of the obstacles and maintain agent accessibility, we initiate the problem of constructing a new pathway (e.g., a detour or new bridge) connecting the regions disconnected by obstacles from the mechanism design perspective. In the problem, each agent in their region has a private location and is required to access the other region. The cost of an agent is the distance from their location to the other region via the pathway. Our goal is to design strategyproof mechanisms that elicit truthful locations from the agents and approximately optimize the social or maximum cost of agents by determining locations in the regions for building a pathway. We provide a characterization of all strategyproof and anonymous mechanisms. For the social and maximum costs, we provide upper and lower bounds on the approximation ratios of strategyproof mechanisms.