PaperlayerView exact revision on arXiv

Source-linked AI summary

Mechanism Design for Bridge Location with Optional Preferences

Xiaoshuang Geng, Wenjing Liu, Genjie Qin, Qizhi Fang

arXiv:2609.39097v2cs.GT

TL;DR

The paper studies how to locate a bridge between two separated regions when agents privately report their locations and preferences over prelocated facilities. It designs deterministic strategyproof mechanisms for three individual-cost variants and two social objectives, obtaining optimal or approximation guarantees while leaving gaps for the min-variant.

  • Problem

    Bridge-location models considered in prior work do not capture agents who may prefer either or both of two facilities providing distinct services.

    Source: §1 · p. 2

  • Method

    The paper designs deterministic strategyproof bridge-location mechanisms for private locations and preferences, considering three individual-cost variants and social cost or maximum cost.

    Source: §2 · p. 4

  • Results

    The mechanisms are optimal for social cost under the max- and sum-variants, while the min-variant has a 3-approximation against a lower bound of 2; for maximum cost, max- and sum-variants attain 5/3, a lower bound applying to all three variants.

    Source: §3.3 · p. 9, §4 · p. 9, §5 · p. 10

  • Takeaways & Limitations

    Positive traversal costs are handled only in some settings: Mechanism 2 remains strategyproof and socially optimal for the sum-variant, whereas Mechanism 1 is no longer strategyproof for the max-variant.

    Source: §5 · p. 11

    Whether the remaining min-variant gaps under both social objectives can be closed remains open.

    Source: §5 · p. 11

Abstract

from arXiv · show

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.

1 Introduction

The paper extends bridge-location mechanism design to agents with private locations and preferences over facilities providing distinct services. It studies deterministic strategyproof mechanisms across three individual-cost variants and two social objectives.

1 Introduction

  • Agents may need one or both distinct-service facilities, motivating max-, sum-, and min-distance costs for bridge placement.The paper illustrates these variants with warehouse, school-and-kindergarten, and subway-station settings.Source: §1 · p. 2

1.1 Related Work

  • Earlier bridge models require crossing to the opposite-side facility or allow the nearer facility [16], but do not model optional preferences over distinct services.Source: §1 · p. 2, §1.1 · p. 3

1.2 Our Contributions

  • The paper studies deterministic strategyproof mechanisms with private locations and preferences, targeting social cost and maximum cost across three individual-cost variants.The results are summarized in Table 1.Source: §1.2 · pp. 3–4, Table 1 · p. 4

2 Preliminaries

The preliminaries model two separated regions with one prelocated facility each and a bridge position as the decision. They define agent costs and social objectives, then restrict the analysis to a bounded interval of bridge locations.

2 Preliminaries

  • Two parallel lines represent separated regions, each with one prelocated facility; a perpendicular, zero-traversal-cost bridge is described by one coordinate.The bridge endpoint has the same coordinate on both lines.Source: §2 · p. 4

Individual costs

  • An interested agent’s cost is the maximum, sum, or minimum of her distances to the facilities she prefers.Travel to the opposite region is measured via the bridge, while local travel is measured directly.Source: Individual costs · p. 5

Social objectives

  • Social cost sums agents’ costs, while maximum cost is the largest individual cost; strategyproofness requires truthful reporting to be no worse for any agent.Approximation compares the mechanism’s objective value with the optimum.Source: Social objectives · pp. 5–6
  • An optimal bridge position exists in [0, 1] for every cost variant and both objectives, so subsequent mechanisms need only output within that interval.Source: Social objectives · p. 6
  • Some agents’ costs are bridge-independent for outputs in [0, 1], and those agents cannot lower their true costs by misreporting.The paper identifies these agents by their preferences and locations relative to the facilities.Source: Social objectives · p. 7

3 Social Cost

For the social cost objective, the paper develops breakpoint-based mechanisms for three individual cost variants. They are optimal for the max- and sum-variants, while the min-variant mechanism is strategyproof and achieves a 3-approximation, with a lower bound of 2.

3 Social Cost

  • The analysis adapts a piecewise-linear social-cost balancing approach by introducing breakpoints for locations where costs change under optional preferences.Source: §3 · p. 7

3.1 Max-Variant

  • Mechanism 1 sorts agent breakpoints and selects the (|B|+1)th value, achieving strategyproofness and optimality for the social cost objective under the max-variant.Source: §3.1 · p. 8

3.2 Sum-Variant

  • Mechanism 2 uses the same breakpoint order-statistic rule and is strategyproof and optimal for the social cost objective under the sum-variant.Source: §3.2 · p. 8

3.3 Min-Variant

  • For the min-variant, Mechanism 3 excludes agents whose costs are bridge-independent and selects a crossing-cost breakpoint, achieving strategyproofness and a 3-approximation.Source: §3.3 · pp. 8–9
  • No deterministic strategyproof mechanism achieves an approximation ratio below 2 for the min-variant social cost objective.Source: §3.3 · p. 9

4 Maximum Cost

For the maximum cost objective, the paper gives a common 5/3 lower bound and uses Mechanism 4 across the three cost variants. The mechanism achieves 5/3-approximations for the max- and sum-variants and a 3-approximation for the min-variant.

4 Maximum Cost

  • A 5/3 lower bound applies to all three variants of the maximum cost objective; when agents want only the opposite-region facility, the variants coincide with the setting of Qin et al..Source: §4 · p. 9

4.1 Max-Variant

  • Mechanism 4 focuses on the minimum location in A and maximum location in B, and is strategyproof with a 5/3-approximation under the max-variant.Source: §4.1 · p. 10, §4 · p. 10

4.2 Sum-Variant

  • Under the sum-variant, Mechanism 4 is strategyproof and achieves a 5/3-approximation for the maximum cost objective.Source: §4.2 · p. 10

4.3 Min-Variant

  • Under the min-variant, Mechanism 4 is strategyproof and achieves a 3-approximation; the proof uses lower bounds on the optimum tied to agents’ positions relative to its output.Source: §4.3 · p. 10

5 Conclusion and Future Work

The paper establishes objective- and cost-variant-specific guarantees for deterministic strategyproof bridge mechanisms with optional preferences. It also identifies unresolved approximation gaps and complications from positive traversal costs, alongside directions for future work.

5 Conclusion and Future Work

  • For social cost, max- and sum-variant mechanisms are optimal, while the min-variant mechanism achieves a 3-approximation against a lower bound of 2.The gap between the min-variant upper and lower bounds remains open.Source: §5 · p. 10
  • For maximum cost, max- and sum-variant mechanisms attain the tight ratio of 5/3, while the min-variant has an upper bound of 3 and a lower bound of 5/3.Source: §5 · p. 10
  • With fixed public traversal cost τ > 0, Mechanism 2 remains strategyproof and socially optimal under sum-variant costs, while Mechanism 1 loses strategyproofness under max-variant costs.Source: §5 · pp. 10–11
  • With τ > 0, the nearest interested facility may change under the min-variant.Source: §5 · p. 11
  • Future work includes closing min-variant gaps, improving fully private maximum-cost guarantees, studying randomized mechanisms and fractional preferences, and extending positive traversal costs to remaining settings.Source: §5 · p. 11

A Appendix

The appendix provides proofs for the bridge-location mechanisms, establishing strategyproofness and their optimality or approximation properties. It also develops tight examples and lower-bound arguments, including bounds used in approximation analyses.

Proof of Lemma 1

  • An optimal bridge position can be chosen in [0, 1] without increasing any agent’s cost, social cost, or maximum cost.Moving any position below 0 to 0 or above 1 to 1 leaves local travel costs unchanged and does not increase crossing costs.Source: A Appendix · p. 13

Proof of Theorem 1

  • Mechanism 1 is strategyproof and minimizes social cost.The proof uses the mechanism’s selected breakpoint and a convex auxiliary objective.Source: A Appendix · pp. 13, 15

Proof of Theorem 2

  • Mechanism 2 is strategyproof and optimal for the social cost objective under the sum-variant individual cost.Its breakpoint selection and the cost functions’ shared form support the same strategyproofness and convexity arguments used for Mechanism 1.Source: A Appendix · p. 15

Proof of Theorem 3

  • SC(s0)/OPTSC(c) approaches 3 in a two-agent example for Mechanism 3, which the proof also establishes is strategyproof.The example uses an agent at x_i = 1/2 − ε and another at y_j = 1.Source: A Appendix · pp. 16–17

Proof of Theorem 4

  • 2 is a lower bound on the approximation ratio of every deterministic strategyproof mechanism for the social cost objective.The proof derives a contradiction from assuming a ratio below 2.Source: A Appendix · p. 18

Proof of Theorem 5

  • For the assumed ratio below 5/3, the proof derives that the mechanism’s output on instance c1 must satisfy −1/3 < h < 4/3.The provided portion ends at this constraint and does not show the remainder of the lower-bound proof.Source: A Appendix · pp. 18–19

A Appendix

  • 5/3 is a lower bound: no deterministic strategyproof mechanism for the maximum-cost objective can achieve a smaller approximation ratio.The proof derives a violating instance for locations in the stated range and handles the symmetric case by changing the other agent’s location.Source: A Appendix · p. 19
  • The max-variant mechanism is strategyproof because misreports cannot improve an agent’s cost, including reports that remove her from a set used by the median rule.The proof handles reports retaining or removing the agent from the relevant set and shows the output cannot move in a direction that benefits her.Source: A Appendix · pp. 19–20
  • 5/3 approximation bounds hold for both mechanisms, and the sum-variant mechanism also inherits the tight example.The case analysis establishes the bound for the max-variant mechanism; the sum-variant proof concludes the same bound and notes that the earlier tight example applies.Source: A Appendix · pp. 22, 26, 27
  • Under sum-variant costs, bridge-dependent costs retain the same monotonicity, so the median-rule strategyproofness argument applies, including reports that remove an agent from a set.The proof also establishes the 5/3 bound across its cases; outputs in several cases are optimal.Source: A Appendix · pp. 22, 27
  • For every bridge position s, the maximum cost is at least s0, so OPTMC(c) ≥ s0.Source: A Appendix · p. 27
  • Mechanism 4 is strategyproof, including reports that change an agent’s preference or specify a bridge-independent type while retaining her in the corresponding set.Bridge-independent agents cannot benefit from misreporting; the remaining agents’ monotone costs support the median-rule argument, with retained reports evaluated at their true location and preference.Source: A Appendix · pp. 27–28
  • Mechanism 4 is a 3-approximation for maximum cost, and a two-agent example attains ratio 3.In the example, the mechanism’s maximum cost is 3/2 while the optimum is 1/2.Source: A Appendix · p. 28

Positive Traversal Costs

With a fixed public crossing cost τ, the paper keeps the mechanisms’ selection rules unchanged. The effect depends on the cost variant: the sum-variant result persists, the max-variant mechanism loses strategyproofness, and the min-variant guarantees require further analysis.

Positive Traversal Costs

  • The extension adds a fixed public crossing cost τ ≥ 0, independent of bridge position and agents’ reports, while leaving the mechanisms’ selection rules unchanged.Source: Positive Traversal Costs · pp. 28–29
  • Mechanism 2 remains strategyproof and optimal for social cost under the sum-variant because the added term is independent of bridge position.The traversal-cost term is added to social cost without changing which bridge position minimizes it.Source: Positive Traversal Costs · p. 29
  • For every τ > 0, Mechanism 1 is not strategyproof under the max-variant.A two-agent example shows an agent can lower her true cost by misreporting her preference.Source: Positive Traversal Costs · p. 29
  • Under the extension, a positive traversal cost can change the nearest interested facility in the min-variant, so existing guarantees require further analysis.For 0 ≤ τ < 1, the travel costs are equal at s = (1−τ)/2; for τ ≥ 1, the local facility is always nearest.Source: Positive Traversal Costs · p. 29

Related papers

Loading 2609.39097v2…