PaperlayerView exact revision on arXiv

Source-linked AI summary

Improved Randomized Approximations for Strategic Obnoxious Facility Location

Hau Chan, Jianan Lin, Chenhao Wang

arXiv:2609.07261v1cs.GT

TL;DR

Strategic obnoxious facility location asks how to choose a facility on a segment when agents prefer it far away, while preserving truthful reporting and optimizing social or minimum utility. The paper develops randomized strategyproof mechanisms and improves upper and lower bounds for both objectives. Its results sharpen known guarantees, while leaving the true asymptotic order for minimum utility unresolved.

  • Problem

    The paper studies how randomized strategyproof mechanisms can optimize social and minimum utility when agents on a segment prefer the facility to be far away.

    Source: §1 · p. 2, §1.1 · p. 2

  • Method

    It designs a randomized social-utility mechanism and refines the uniform mechanism for minimum utility, with both mechanisms universally strategyproof.

    Source: §1.1 · p. 2

  • Results

    The social-utility upper bound is at most 1.47359 versus 3/2, the minimum-utility upper bound is √n + O(1) versus √2n + O(1), and the minimum-utility asymptotic lower bound rises from 3/2 to 2.

    Source: §1.1 · pp. 2–3

  • Takeaways & Limitations

    All four bounds considered in the paper strictly improve their corresponding previously known results.

    Source: §1.1 · p. 2

    The true asymptotic order for minimum utility remains unsettled: the paper suspects an Ω(√n) lower bound but proves only a constant lower bound.

    Source: §5 · p. 18

Abstract

from arXiv · show

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 possible and their utility is their distance from the facility, under the social utility and minimum utility objectives. For social utility, we propose a novel randomized mechanism that breaks the previously best known \(\frac32\)-approximation of [Cheng, Yu, and Zhang, TCS 2013], achieving an approximation ratio of at most \(1.47359\). We also raise the lower bound on the approximation ratio of randomized strategyproof mechanisms from \(\frac{2}{\sqrt{3}}\approx1.15470\) [Feigenbaum et al., JAAMAS 2020] to \(\frac{105}{88}\approx1.19318\). For minimum utility, following the profile-independent approach of [Chan, Lin and Wang, AAMAS 2026], we design a simple randomized mechanism that reduces the approximation guarantee from \(\sqrt{2n}+O(1)\) to \(\sqrt n+O(1)\), where \(n\) is the number of agents. Finally, we prove that no randomized strategyproof mechanism can achieve an asymptotic approximation ratio strictly smaller than \(2\), strengthening the previous asymptotic lower bound of \(\frac32\) [Feigenbaum et al., JAAMAS 2020]. Thus, all four bounds considered in this paper strictly improve upon the corresponding previously known results.

1 Introduction

The paper revisits randomized strategyproof mechanisms for obnoxious facility location on a segment, where agents prefer distance, under social- and minimum-utility objectives. It improves previously known bounds for both objectives.

1 Introduction

  • Strategic facility-location research designs strategyproof mechanisms that use agents’ reports to approximately optimize facility-location objectives; obnoxious settings instead favor distance from the facility.The paper studies the obnoxious variant on a segment.Source: §1 · pp. 1–2
  • Earlier work established a 3/2 randomized social-utility approximation, a tight deterministic bound of 3, and prior randomized lower bounds for social and minimum utility.The paper also builds on the uniform mechanism studied for minimum utility in.Source: §1 · p. 2

1.1 Our Results

  • At most 1.47359 beats the prior 3/2 social-utility approximation, and the paper also raises the randomized social-utility lower bound.Table 1 summarizes the improved upper and lower bounds.Source: §1.1 · pp. 2–3, §1 · p. 2, Table 1 · p. 3
  • √n + O(1) improves the minimum-utility upper bound from √2n + O(1), reducing the leading coefficient from 2 to 1.The refined uniform mechanism is universally strategyproof.Source: §1.1 · pp. 2–3, Table 1 · p. 3
  • An asymptotic lower bound of 2 strengthens the previous randomized minimum-utility lower bound of 3/2.Table 1 summarizes the lower bound as an impossibility result.Source: §1.1 · pp. 2–3, Table 1 · p. 3

1.2 Additional Related Work

  • Related work extends obnoxious facility location to tree networks and adds fairness, group-fairness, and prediction considerations; broader facility-location work also studies other spaces and facility counts.These variants retain the interaction between strategic behavior and performance or fairness objectives.Source: §1.2 · p. 3

2 Preliminaries

The preliminaries define the unit-segment setting, agents’ distance-based utility, randomized mechanisms, strategyproofness, and the two utility objectives used in the paper.

2 Preliminaries

  • The feasible region is the unit interval [0, 1], and each agent’s location is represented in a profile x = (x_1, ..., x_n).The notation x_-i denotes the profile with agent i removed.Source: §2 · p. 3
  • An agent at x_i receives utility |x_i − y| from a facility at y, so agents prefer the facility to be farther away.The facility location y is constrained to [0, 1].Source: §2 · p. 3
  • A randomized mechanism maps each reported profile to a distribution over facility locations, with utility measured by expected distance.It is strategyproof when no agent can improve expected utility by misreporting; it is universally strategyproof when it randomizes over deterministic strategyproof mechanisms.Source: §2 · p. 3
  • The paper evaluates social utility and minimum utility as expected objective values under the mechanism’s random facility location.An approximation compares the mechanism’s objective value with the optimum for every profile, and its ratio is at least 1.Source: §2 · p. 4

3 Social Utility

This section studies randomized strategyproof mechanisms for social utility, presenting a universally strategyproof mechanism with approximation ratio at most 1.47359 and establishing a lower bound of 105/88.

3.1 Upper Bound

  • Theorem 1 states that M93/100 is universally strategyproof and achieves a social-utility approximation ratio at most a quantity strictly smaller than 3.Source: §3.1 · pp. 5, 10

3.2 Lower Bound

  • 105/88≈1.19318 is a lower bound on randomized strategyproof mechanisms’ approximation ratio, improving on Feigenbaum et al.’s 2/√3≈1.15470 bound.Source: §3.2 · p. 10
  • Approximately 1.19318 is the social-utility lower bound established in this part.Source: §3.2 · p. 10
  • The proof scales the interval to [0, 8] and uses two agents, whose optimal social utility is max{a + b, 16 − a − b}.Source: §3.2 · p. 10
  • Four profiles’ welfare inequalities are weighted and combined with nonnegative strategyproofness constraints to form a certificate bounded independently of the mechanism’s output distributions.Source: §3.2 · p. 11
  • The certificate’s profile functions are piecewise linear, so their maxima on [0, 8] occur at integer points evaluated in Table 3.Source: §3.2 · pp. 11–12, Table 3 · p. 12

4 Minimum Utility

For minimum utility, the paper improves the randomized upper bound to √n + O(1) and proves an asymptotic lower bound of 2. The upper bound adds probability mass at the segment endpoints; the lower bound rules out every fixed approximation ratio below 2 for sufficiently many agents.

4.1 Upper Bound

  • √n + O(1) is the approximation ratio achieved for minimum utility by the Endpoint-Augmented Uniform Mechanism for every n ≥ 2.The mechanism is universally strategyproof and adds probability mass at both endpoints to a uniform draw.Source: §4.1 · p. 13
  • The upper-bound analysis separates profiles where the optimal empty interval is an internal gap from those where it is a boundary gap.The mechanism's expected minimum utility is bounded in both cases before the theorem combines them.Source: §4.1 · pp. 13–15

4.2 Lower Bound

  • For every ρ < 2, no randomized strategyproof mechanism is a ρ-approximation once n is sufficiently large, so the asymptotic lower bound is 2.The proof assumes a ρ-approximation and constructs profiles that yield contradictory bounds on the expected facility location.Source: §4.2 · pp. 16, 18
  • Strategyproofness implies that changing reports of agents at 0 cannot increase the expected facility location, while changing reports of agents at 1 cannot decrease it.This monotonicity applies when other reports are held fixed and is used in the lower-bound argument.Source: §4.2 · p. 16
  • The lower-bound construction starts from a finite grid profile and moves endpoint agents to create profiles with a unique largest empty interval at opposite ends.The resulting profiles are used to derive incompatible constraints under strategyproofness.Source: §4.2 · pp. 16–18

5 Conclusion

The paper improves randomized strategyproof bounds for obnoxious facility location under both social utility and minimum utility. It also identifies open questions on sharper social-utility guarantees and the asymptotic order of minimum utility.

5 Conclusion

  • The paper reports improved upper and lower bounds for social utility, a better leading constant in the O(√n) minimum-utility upper bound, and an asymptotic lower bound of 2.The authors state that several gaps remain open.Source: §5 · p. 18
  • For social utility, it remains open whether a sharper kernel certificate can improve the guarantee of the same random-threshold dictator mechanism.For minimum utility, the true asymptotic order remains unsettled; the authors suspect an Ω(√n) lower bound, while their current techniques prove only a constant lower bound.Source: §5 · p. 18

A Quadratic Certificate for the Social Utility Upper Bound

The appendix certifies the social-utility upper bound by reducing D(x,z) to quadratic polynomials on intersections of uniform and atom regions. Exhaustive minimization checks establish nonnegativity throughout the square.

A Quadratic Certificate for the Social Utility Upper Bound

Loading 2609.07261v1…