# Competitive Perimeter Defense on a Line

arXiv: https://arxiv.org/abs/2103.11787 · HTML: https://mlsanity.com/paper/2103.11787/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Mar 2021.

## Built on by (most cited first, 1 of 1)

- [Embedded Mean Field Reinforcement Learning for Perimeter-defense Game](https://mlsanity.com/paper/2505.14209/) (2025)

## Abstract (arXiv)

We consider a perimeter defense problem in which a single vehicle seeks to defend a compact region from intruders in a one-dimensional environment parameterized by the perimeter size and the intruder-to-vehicle speed ratio. The intruders move inward with fixed speed and direction to reach the perimeter. We provide both positive and negative worst-case performance results over the parameter space using competitive analysis. We first establish fundamental limits by identifying the most difficult parameter combinations that admit no c-competitive algorithms for any constant c≥ 1 and slightly easier parameter combinations in which every algorithm is at best 2-competitive. We then design three classes of algorithms and prove they are 1, 2, and 4-competitive, respectively, for increasingly difficult parameter combinations. Finally, we present numerical studies that provide insights into the performance of these algorithms against stochastically generated intruders.