Research map / Multi-agent systems and games / Games and equilibria
Mechanism Design for Connecting Regions Under Disruptions
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Designs strategyproof mechanisms that place a new pathway (edge) connecting two line-segment regions separated by an obstacle, given agents' private locations, for social and maximum cost objectives, with characterization, deterministic and randomized approximation bounds.
Problem
Choosing where to build a bypass/pathway connecting two regions separated by an obstacle when agents hold private locations and must reach the other region; objectives are social cost and maximum cost under strategyproofness.
Approach
Models the bridge-building problem as a mechanism design problem on a line with an obstacle, shows agent preferences are two-dimensional single-peaked (so strategyproof anonymous mechanisms are 2D generalized medians), gives an optimal group-strategyproof mechanism for social cost, and approximately optimal deterministic and randomized mechanisms for maximum cost.
Key results
- Social cost: OptSocCost is group strategyproof and optimal for social cost.
- Maximum cost: TwoExtreme is group strategyproof with approximation 2/(1+k) when L=0; deterministic lower bound 2/(1+sqrt(k)) for L=0.
- Randomized RandMaxCost achieves approximation max((4-2k)/(3-k),(1+k)/(1+k^2)) with randomized lower bound (6+6k)/(5+7k).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use TwoExtreme to connect the nearest-to-obstacle extreme agents | Maximum-cost pathway construction · Maximum cost (general obstacle length L) | approximation ratio: \frac{2 - 2(1 - k)L}{1 + k - (1 - k)L} | Helped |
| Use TwoExtreme when the obstacle has zero length | Maximum-cost pathway construction · Maximum cost (L=0) | approximation ratio: \frac{2}{1 + k} | Helped |
| Restrict the endpoints from getting too close to the obstacle (TwoExtremeRestrict) (ablation) | TwoExtreme · Maximum cost (L=0) | approximation ratio: \frac{2}{1+k} -> 2\cdot \max\left(\frac{1-(1-k)c}{1\!+\!k\!-(1-k)c}, \frac{k(2c-c^2)+1-c^2}{2-2c+2ck}, \frac{1+2ck}{2\! | Helped |
| Randomize between the extreme endpoints and midpoint endpoints using the specified probability | Maximum-cost pathway construction · Maximum cost (L=0) | approximation ratio: \max\left(\frac{4-2k}{3-k}, \frac{1+k}{1+k^2}\right) | Helped |
| Use the optimal maximum-cost solution | OptMaxCost · Maximum cost | optimality | Mixed |
| Set k=0 (ablation) | OptSocCost · Social cost | optimality | No clear effect |
Surprising findings
- The preference profile is two-dimensional but not one-dimensional single-peaked, so the standard one-dimensional median characterization does not apply directly.
- The optimal maximum-cost solution is not strategyproof.
Limitations
- Setting restricted to two line-segment regions with a single obstacle and a single pathway.
- Gap between deterministic and randomized upper and lower bounds remains (e.g., up to about 0.162 for randomized).
- Lower bound for deterministic L=0 case is computer-assisted with grid-based error estimates.
Experimental setup
Metrics: approximation ratio social cost maximum cost
Baselines: TwoExtreme Median mechanism OptMaxCost
Builds on: generalized median mechanism multi-dimensional single-peaked preferences bridge-building algorithms (Cai et al.)
Closest papers by meaning
- A Multiagent Path Search Algorithm for Large-Scale Coalition Structure Generation (AAAI 2025 · similarity 0.82)
- Exact Algorithms for Multiagent Path Finding with Communication Constraints on Tree-Like Structures (AAAI 2025 · similarity 0.81)
- Bidirectional Temporal Plan Graph: Enabling Switchable Passing Orders for More Efficient Multi-Agent Path Finding Plan Execution (AAAI 2024 · similarity 0.81)
- Solving Multiagent Path Finding on Highly Centralized Networks (AAAI 2025 · similarity 0.81)
- Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding (AAAI 2024 · similarity 0.81)
- Loosely Synchronized Rule-Based Planning for Multi-Agent Path Finding with Asynchronous Actions (AAAI 2025 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.