Private Equilibrium Computation Is Quantal Response: Which Refinements Survive Differential Privacy Among Unequal Agents

When self-interested agents compute a joint plan together, for example robots deciding who yields at a crossing or energy hubs deciding how to split a dispatch, each agent usually wants to keep its own costs secret. Differential privacy (DP) is the standard tool. It gives a formal guarantee that an observer of the outputs cannot tell much about any one agent's private data, and it achieves this by adding calibrated randomness. The literature treats that randomness as a nuisance that costs accuracy. We argue it does something more specific in games. It acts as a permanent, agent-specific rate of "mistakes." Game theory has a precise vocabulary for such mistakes: equilibrium refinements, which are rules for discarding equilibria that rely on non-credible threats or on ignoring small errors. The main question is therefore not how much accuracy privacy costs. It is which equilibrium privacy selects, and whether that choice matches what the full-information game would prescribe.

The core observation is simple. If each agent chooses its action at each decision point with the exponential mechanism (the textbook DP rule that picks option $a$ with probability rising exponentially in its score), then private backward induction produces a quantal response equilibrium. That is an equilibrium in which each player picks better actions more often but never with certainty, and its "precision" is set by that agent's privacy budget and payoff sensitivity. Because unequal agents have unequal sensitivities, they end up with unequal precisions. A known impossibility result says the precision cannot be driven to infinity while privacy is kept. Two consequences follow, and we will test both. First, the private equilibrium can hand responsibility to the wrong agent, such as asking a heavy, slow-braking robot to yield. Second, the representation-invariance of refinements proven for exact solvers breaks under privacy, because the privacy cost depends on how many decision points a representation exposes.

Core Claim

Three results in the file frame the idea. Differentially Private Distributed Convex Optimization via Functional Perturbation proves a "stability trap." If a distributed solver converges when run without noise, then noise on its messages that fades over time cannot give DP. Privacy therefore requires perturbation that never vanishes, which leaves a permanent gap between the private solution and the true one. Equilibrium Refinements for Multi-Agent Influence Diagrams: Theory and Practice proves that subgame perfect equilibrium (no non-credible threats anywhere in the game tree) and trembling-hand perfect equilibrium (robust to vanishingly small mistake probabilities) are preserved between two representations. One is a compact graphical representation, the multi-agent influence diagram (MAID). The other is the full game tree. The paper solves the compact one by backward induction over strongly connected components. Trembling-hand perfection is defined as a limit in which mistakes go to zero. The stability trap forbids exactly that limit for any private solver.

We therefore propose to replace the vanishing-tremble target with a fixed-precision one and to analyze it directly. Let agent $i$ own decision point $h$, let $Q_i(h,a)$ be its private continuation payoff for action $a$, let $\Delta_i$ be the sensitivity of those payoffs to agent $i$'s private data, and let $\varepsilon_{i,h}$ be the privacy budget spent at $h$. The private choice rule is

$$ \Pr[a \mid h] \;\propto\; \exp\!\left(\lambda_{i,h}\, Q_i(h,a)\right), \qquad \lambda_{i,h} = \frac{\varepsilon_{i,h}}{2\Delta_i}, $$

which is a logit choice with precision $\lambda_{i,h}$. By basic composition, the agent's total budget satisfies $\varepsilon_i = \sum_h \varepsilon_{i,h}$. Once the precisions are fixed, the output of backward induction is a heterogeneous logit equilibrium of the true game. The tail bound of the exponential mechanism then gives the probability that $h$ departs from the subgame-perfect action. If $g_{i,h}$ is the gap between the best and second-best continuation payoffs and $n_h$ is the number of actions, that probability is at most $(n_h - 1)\exp(-\lambda_{i,h} g_{i,h})$. This yields three testable predictions. Refinement violations concentrate at decision points with small margin relative to sensitivity. The agent with the worst ratio of margin to sensitivity dominates the error, whatever the average budget. And the same game written with more exposed decision points, as a game tree rather than a MAID, pays more privacy per point and so selects worse.

What is new is treating privacy noise as a tremble structure that decides equilibrium selection, and using that view to design where privacy budget is spent. Prior private-optimization work does not do this. DP-ADMM: ADMM-Based Distributed Learning With Differential Privacy adds decreasing Gaussian noise to primal updates of a cooperative learning problem, and the functional-perturbation paper adds Laplace noise to basis coefficients of cooperative objectives. Both assume obedient agents with a shared objective. Neither asks which equilibrium of a general-sum game results.

Research Program

The first strand is analysis. We will formalize "privacy-induced perturbed games" for two mechanisms. The first is per-node exponential selection, as above. The second is one-shot functional perturbation of each agent's payoff function followed by an exact solver. Because the second is post-processing, it keeps DP, and it corresponds to a payoff perturbation rather than an action tremble. For each mechanism we will prove three things. The output is an equilibrium of an explicitly described perturbed game. Its distance from the subgame-perfect path is bounded by the margin expression. And as every $\varepsilon_i \to \infty$, its limit points are Nash equilibria of the true game. We will also check whether these limit points are trembling-hand perfect. We expect a counterexample in which unequal rates of approach across agents select a perfect equilibrium different from the one favoured by equal rates. This would be the private analogue of the known sensitivity of refinements to the ordering of trembles.

The second strand concerns representation. Hammond et al.'s equivalence holds for exact solving. We will study how per-node budget depends on the number of decision points each representation exposes. The goal is a condition under which solving on the MAID's components gives strictly better precision than the game tree at the same total privacy. We also want to characterize when the two private outputs differ as distributions. This extends the preservation question of Nash Equilibrium and Bisimulation Invariance, which shows that whether equilibria survive a change of model depends on what strategies are allowed to condition on. Here, what the strategy conditions on also determines how much privacy it costs.

The third strand is heterogeneity and a method. Safety Barrier Certificates for Collisions-Free Multirobot Systems shows that safe coordination among unequal robots requires splitting evasion responsibility in proportion to acceleration limits. Agile robots dodge while a heavy robot holds course. In game form, the heavy agent has a large margin for not yielding and the agile agent a small margin for yielding. Under equal budgets, the agile agent's small margin makes its decision point the error-prone one. We will build margin-aware budget allocation. Each agent spends a small share of its budget on privately estimating its own margins, using a noisy comparison of its top two actions. It then distributes the rest across its decision points to minimize the margin bound. We will prove the total privacy guarantee by composition. In continuous settings, the lower-level physical coupling will be solved by the decentralized ADMM of A Decentralized Algorithm for Coordination Between Economic Dispatch and Demand Response in Multi-Energy Systems, while the strategic upper stage is privatized as above.

Baselines

The naive reference point is exact, non-private generalized backward induction in the pycid library released with Equilibrium Refinements for Multi-Agent Influence Diagrams: Theory and Practice. It defines the true subgame-perfect path and the upper bound on welfare, and every private method is scored against it. A second reference point is the myopic, non-game-theoretic controller. We will run capability-aware barrier-function quadratic programs following Wang et al., with no strategic model and nothing released beyond positions. This shows what is lost or gained by computing an equilibrium at all.

The strongest existing competitor is one-shot functional perturbation of each agent's payoff function, in the manner of Nozari et al., followed by exact pycid backward induction on the privatized game. It is the strongest because it escapes the stability trap, spends each agent's whole budget in a single release, and inherits exact refinement computation by post-processing. Any gain we claim must come from where noise is placed, not from avoiding a bad baseline. A message-perturbation baseline will run DP-ADMM-style decreasing Gaussian noise on decentralized best-response dynamics. For its runtime and accuracy, we have only the Adult-dataset result that DP-ADMM took around 5.2 s for 100 iterations versus over 78 s for ADMM with primal variable perturbation. The file reports no equilibrium-selection metric for any of these methods on any game, so we have no reported result on Lacuna for subgame-perfect path recovery under privacy. All private methods get the same total per-agent $(\varepsilon, \delta)$, the same game instances, the same random seeds, and the same tuning budget for the basis truncation order and step sizes, fixed on held-out instances.

Two ablations isolate the key ingredient. Uniform budget splitting across decision points, with everything else held equal, isolates margin-aware allocation. Running the same private mechanism on the game-tree representation rather than the MAID isolates the representation effect. Beating the strongest baseline means a statistically significant drop in exploitability and in responsibility-inversion rate at equal $\varepsilon$ across the stated range, with welfare no worse.

Why not just…?

Why not just use a large privacy budget and treat the error as small? The margin bound says error is controlled by the smallest ratio of margin to sensitivity, not by the average. In heterogeneous games, a large budget can still leave one agent's near-tied decision flipped often. We will report the budget each method needs to reach 95% subgame-perfect path recovery. If uniform allocation reaches it at budgets that practitioners consider meaningful privacy, the heterogeneity argument is weak and we will say so.

Why not just privatize payoffs once and run an exact refinement solver? This is the real threat. It is also our strongest baseline, and it may match our method in games with uniformly large margins. Our claim is limited to games with uneven margins across agents or stages, where one payoff release wastes budget on irrelevant coefficients. The functional-perturbation paper itself notes that error falls with expansion order at higher cost. The experiments sweep margin heterogeneity explicitly. If the curves coincide across that sweep, we will reframe the contribution as analysis only, explaining which equilibrium the baseline selects.

Why not just centralize with encryption? Secure computation hides inputs but reveals the exact equilibrium, and in general-sum games that output can leak private preferences. It also inherits the scaling problems of central solving: the file reports several hours for a 25,000-state subgame-perfect computation in Multi-Robot Negotiation: Approximating the Set of Subgame Perfect Equilibria in General-Sum Stochastic Games. We treat it as orthogonal and do not benchmark it, but we note it gives no DP guarantee on the output.

Why not just run myopic barrier-function controllers and skip equilibria? Wang et al. document deadlocks when objectives conflict and infeasibility in crowds. The myopic reference baseline directly measures goal-completion and deadlock rates against the equilibrium methods.

Proposed Experiments

We will use the structured pycid games reported in Hammond et al. (the Road Example and Taxi Competition), in which exact solving achieved exponential speedups. We add a crossing game parameterized by the acceleration-limit ratio of the Khepera III and Magellan Pro robots from Wang et al. We also re-implement the two-truck supply-chain and joint-motion-planning games from the multi-robot negotiation paper at reduced scale; no code is given in the file. As a continuous stretch case, we use the modified IEEE 14-bus multi-energy system. There, hubs bid strategically in an upper stage, and Liu et al.'s ADMM performs the dispatch below with a penalty parameter safely under the reported divergence at $\rho = 5$.

Metrics are subgame-perfect path recovery, exploitability in the true game (the best gain any agent obtains by deviating), responsibility-inversion rate (the heavy agent assigned to yield), welfare, and success of a payoff-reconstruction attack as an empirical privacy check. The decisive checks are three. The first is whether per-node violation frequencies track $\exp(-\lambda_{i,h} g_{i,h})$ across decision points. If they do not, the core equivalence fails. The second is whether responsibility inversion under uniform budgets rises with the capability ratio, and whether margin-aware allocation removes it at equal privacy. The third is whether MAID-based private solving strictly beats game-tree private solving at equal budget, which would show that exact representation invariance does not survive privacy.