Certified Price of Anarchy for Robots That Localize Each Other

Robots working without GPS or beacons often work out where they are relative to one another by measuring each other: the distance between two drones from radio ranging, or the direction from one robot to another from a camera. This only works if the team moves in informative ways. For example, two drones flying in parallel at a fixed distance cannot recover their relative pose from range measurements alone. Someone has to weave, turn a camera sideways, or take a detour. Each robot pays that cost personally, while much of the benefit goes to its teammates. Self-interested robots will therefore tend to free-ride, each waiting for another to do the informative motion. The price of anarchy, meaning the ratio of the team's total cost when every robot optimizes for itself to the cost under ideal central coordination, measures how much this free-riding costs. Nobody has measured it for this setting. We propose to compute, for concrete team geometries and tasks, a certified upper bound on that ratio.

The bound comes from two standard tools used together. First, we replace each robot's private planning problem with its first-order optimality conditions, the Karush-Kuhn-Tucker (KKT) conditions. This turns "the worst way the selfish team could settle" into one large optimization problem. Second, that problem is non-convex, so we "lift" it into a convex semidefinite program, an optimization over positive semidefinite matrices that a solver can handle globally. The lifted program is a relaxation: its solution can only overestimate the worst outcome. A similar relaxation of the coordinated problem can only underestimate the best outcome. The ratio of the two is therefore a guaranteed ceiling on the price of anarchy. Running local search on the same instance gives a matching floor.

Core Claim

For multi-robot relative localization games, an instance-level price of anarchy can be certified even when each robot's own planning problem is non-convex. The key observation concerns how KKT conditions fail. Applied to a non-convex follower, the KKT reduction is usually discarded as unsound because it admits stationary points that are not true best responses. For an upper bound on the worst equilibrium, this looseness points in the safe direction. Under a constraint qualification, every Nash equilibrium is a KKT point of every player's problem. Maximizing social cost over all KKT points therefore can only overestimate the worst equilibrium. Let $C(x)$ be the team's social cost for joint trajectories $x$, $\mathcal{K}$ the set of joint KKT points, and $\overline{\mathrm{SDR}}_{\mathcal{K}}$ and $\underline{\mathrm{SDR}}_{\mathrm{SO}}$ the optimal values of the semidefinite relaxations of the worst-KKT-point problem and of the system-optimum problem. Then

$$ \mathrm{PoA} \;=\; \frac{\max_{x \in \mathrm{NE}} C(x)}{\min_{x} C(x)} \;\le\; \frac{\max_{x\in\mathcal{K}} C(x)}{\min_x C(x)} \;\le\; \frac{\overline{\mathrm{SDR}}_{\mathcal{K}}}{\underline{\mathrm{SDR}}_{\mathrm{SO}}}. $$

The open empirical question is whether this ceiling is tight enough to be informative. The answer depends on the geometry, and the experiments are designed to measure it. If the bound is tight, it shows whether selfish behavior destroys localization in particular formations (parallel transit, crossing, convoy), and by how much. If it is loose, the program reports this and finds where the slack comes from: the KKT superset, the relaxation, or both.

The Game

We study planar robots with linear dynamics over a horizon of $T$ steps. Each robot chooses its own trajectory. A robot's private cost has two parts. The first is a quadratic penalty for deviating from its nominal path to goal. The second is a localization penalty that depends on its trajectory relative to the trajectories of its sensing partners. For range sensing, the localization term uses the scatter of the relative displacement between robots $i$ and $j$ over the horizon. This quantity is quadratic in positions, and it vanishes exactly when the relative position stays fixed. That is the degenerate case behind the constant-distance singularity reported by 3-D Inter-Robot Relative Localization via Semidefinite Optimization, which solves pairwise range-plus-odometry pose estimation as a semidefinite program but leaves trajectory generation outside its scope. A robot is penalized, through a slack variable, when this scatter falls below the level needed for reliable estimation. That keeps the social cost positive, which the ratio above requires.

For bearing sensing with a limited field of view, the analogous term charges the observer a yaw cost for turning toward a peer. In this variant the benefit mostly goes to the peer being observed. Preserving Relative Localization of FoV-Limited Drone Swarm via Active Mutual Observation identifies exactly this tension and resolves it with a central planner that commands each drone's yaw. We ask what happens when no such commander exists.

Every term is quadratic in the joint positions. Each player's problem is therefore a non-convex quadratic program, and its KKT system is polynomial with bilinear complementarity terms. Lifting the joint vector of positions, slacks, and multipliers into a matrix variable makes all of these conditions linear in the lifted variable, at the cost of one dropped rank-one constraint. We then add redundant products of constraints to tighten the relaxation. Wang et al. tighten their localization relaxation the same way in Certifiably Optimal Mutual Localization with Anonymous Bearing Measurements, which adds redundant rotation constraints to anonymous-bearing mutual localization.

Research Program

The prior work falls into three roles.

Prior work that motivates this program. Three groups of papers show that relative localization needs informative motion and that local solvers are fragile. The TU/e paper cited above documents the range singularity. The active-observation paper reports drift reductions from deliberate peer observation. Bearing-based Relative Localization for Robotic Swarm with Partially Mutual Observations relaxes swarm bearing localization to a semidefinite program with convex-iteration rank recovery, and names active planning for connectivity as future work. All three treat robots as cooperative or passive. None asks what self-interested robots would do.

Prior work that supplies the method. On the bilevel side, KKT reductions turn a follower's optimality into constraints. SICNav does this for crowd agents running reciprocal collision avoidance and solves the result locally at 10 Hz for 3 to 4 agents. Incentive-aware Electric Vehicle Routing linearizes complementarity with binary variables (the Big-M method) and solves the result exactly as a mixed-integer linear program. Both require convex followers to be exact, and neither certifies efficiency loss. We keep the KKT reduction. We drop the requirement that it be exact, and we replace both local solving and mixed-integer branching with a convex relaxation whose value is a bound by construction.

Prior work that constrains the design. On the efficiency side, Reconciling Selfish Routing with Social Good shows that optimizing under near-selfish fairness constraints is NP-hard. That rules out hoping for exact worst-equilibrium computation at scale and justifies settling for bounds. Demand-Independent Tolls shows that clean toll results depend on additive scalar edge costs. Our pairwise matrix-valued localization costs lie outside that class.

The program has three stages.

  1. Certify on synthetic instances. We build the lifted programs for teams of 2 to 8 robots and horizons of 10 to 30 steps. Instances cover three task families: parallel transit, crossing flows, and convoys with one well-equipped "shepherd" robot. This is an offline analysis tool, not a real-time controller. That sidesteps the runtime conflict between relaxations and control loops, where the cited estimators run at roughly 0.4 s per solve or 1 Hz.
  2. Test the localization proxy. We take the coordinated, worst-selfish, and typical-selfish trajectories from stage one. Along them we simulate range measurements and inertial odometry with noise, and run a reimplementation of the TU/e 28-constraint estimator. For the bearing variant, we run the Wang et al. and Guo et al. relaxations instead. This gives actual relative-pose errors to compare against what the proxy predicted.
  3. Design subsidies. A coordinator pays each robot for informative motion. Each payment enters that robot's private cost linearly, so it adds only a constant term to the robot's stationarity condition. As a result, the coordinator's choice of payments fits into the same lifted program without raising its polynomial degree. We then minimize the certified worst-equilibrium cost subject to a budget and to non-negative payments.

Baselines

Naive reference points. The first is selfish robots with no localization term at all: each flies its nominal path, and we record the resulting estimator failures. This shows how bad things get when nobody thinks about localization. The second is the fully cooperative team, which has a price of anarchy of 1 by definition. Its estimator error is the target. For context, Decentralized and Fully Onboard reports formation errors of around 0.05 m in simulation and 0.1 to 0.2 m on real micro aerial vehicles under cooperative range-aided localization. The active-observation paper reports up to 65% less drift than plain visual-inertial odometry.

Exact mixed-integer solving. This is the strongest existing competitor for computing the worst equilibrium. It follows the approach of the electric-vehicle routing paper: Big-M complementarity, with Gurobi's non-convex quadratic mode handling the quadratic player costs. On small instances it gives the true worst KKT-point value, which tells us exactly how much slack the relaxation adds. Yao et al. report an average of around 340 seconds for medium instances of their purely linear problem. Ours is harder, so we expect exact solving to stop scaling well before eight robots. Both methods get the same instances, the same machine, and the same time limit. Our method beats this baseline if it certifies a bound within a stated gap of the exact value on the instances both can solve, and keeps producing bounds where exact solving times out.

Local equilibrium search. The strongest method for finding equilibria from below combines best-response iteration with a SICNav-style local complementarity solver in CasADi/Acados, started from many random initializations. It yields an empirical lower bound on the price of anarchy, and we give it the same total compute as our relaxation. The local-solver failure rates reported by Wang et al., nearly 80% under random initialization, suggest this search will miss bad equilibria. Whether it does is measured, not assumed.

Ablations. The first removes the redundant product constraints, which isolates how much tightening they contribute. The second relaxes only the system optimum and replaces the worst-equilibrium relaxation with the best local equilibrium found. That shows what the KKT lifting itself contributes. No reported price-of-anarchy result for localization games was found on Lacuna, so there is no prior number to beat on the central quantity itself.

Why not just…?

Why not just simulate best-response dynamics and report the empirical price of anarchy? Simulation only finds equilibria that the dynamics happen to reach. It gives a floor on the price of anarchy, never a ceiling. Our free-riding games are non-convex, and in some of them each player's localization benefit is concave in its own motion, so we expect several equilibria. A ceiling is what answers "how bad can it get." This alternative is a real threat to the bound's usefulness: if the empirical floor and the certified ceiling coincide everywhere, the certificate adds rigor but no new insight. We will report the gap per task family and say so plainly if that happens.

Why not just apply a Pigouvian subsidy and skip the analysis? In the symmetric range game, the shared pairwise benefit makes the game an exact potential game. Paying each robot for the benefit it creates for its partner makes the coordinated solution an equilibrium. This is a serious alternative, and we include it as the reference mechanism. It still has three gaps. It does not rule out other, worse equilibria in a non-convex game. It needs each robot's private weights to be known. It ignores budget limits and asymmetric benefits, as in field-of-view-limited bearing sensing, where the observer pays and the observed robot benefits. If the Pigouvian subsidy matches our budget-constrained design on all instances, stage three adds nothing and we will report that.

Why not just command the robots centrally, as the active-observation and decentralized-localization systems do? Central command is the right design when robots comply. The price of anarchy measures what non-compliance costs. A small certified value is itself a useful result: it would say that, for that geometry, coordination infrastructure is not worth building.

Why not just use class-wide bounds from smoothness arguments? Intrinsic Robustness of the Price of Anarchy gives worst-case bounds over whole classes of games. Such bounds ignore the specific geometry that causes the localization singularities. We will derive the class bound where one applies and show, per instance, how much tighter the certified ratio is.

Proposed Experiments

Decisive check 1: tightness. On instances of up to four robots, compare the certified ceiling to the exact mixed-integer value and to the local-search floor. We also measure how close the lifted solution is to rank one, the condition under which a relaxation is exact. Wang et al. recover rank-one solutions up to bearing noise of about 0.4 rad. We expect the price-of-anarchy relaxation to be looser than such estimation relaxations, because complementarity products are harder to tighten.

Decisive check 2: does the proxy predict real error? In parallel transit, the worst selfish equilibrium should reproduce the constant-distance singularity, with a sharp rise in estimator error relative to the coordinated solution. Across all instances, the certified cost ratio should rank-correlate with the ratio of actual relative-pose errors produced by the estimators. If it does not, the quadratic proxy is the weak point. In that case we switch to the minimum-eigenvalue (E-optimal) information criterion, which becomes a small linear matrix inequality in the lifted variables, and repeat the check.

Decisive check 3: do subsidies pay off? On crossing and convoy tasks, compare the certified worst-equilibrium cost under no payments, under the Pigouvian subsidy, and under the budget-constrained subsidy designed in stage three. All three use matched budgets.

We report certified bounds, empirical floors, the gap between them, rank diagnostics, solve times, and pose errors in metres and radians, as functions of team size, horizon, and noise level.