Research map / Multi-agent systems and games / Games and equilibria
Data Poisoning to Fake a Nash Equilibria for Markov Games
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Characterizes offline reward data poisoning attacks that install a fictitious unique Markov-perfect Nash equilibrium in two-player zero-sum Markov games, and solves the attack cost minimization via a linear program.
Problem
Offline data poisoning against multi-agent RL: an attacker modifies a training dataset so that victim learners in a two-player zero-sum Markov game converge to an attacker-chosen pure Nash equilibrium, at minimal cost.
Approach
Defines the unique Nash set (Q functions for which a target pure joint policy is the unique Markov perfect NE), shows it is a polytope via strict inequalities with an iota gap, models victims' theory-of-mind as a hypercube outer approximation of plausible Q functions, and reduces the attack to a linear program with L1 cost.
Key results
- On the RPS toy example with iota=0.01 and rho=0, the optimal attack cost is 2.02 versus 4 for the feasible attack construction (b=1).
- In matching pennies with n=100 episodes, the proposed attack costs 99.47 on average versus 198.38 for the DSE attack of Wu et al. 2023 (and 250.46 for the feasible attack).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use the proposed attack instead of the feasible attack | Matching pennies · Matching pennies, n=1 | average cost: 2.12 -> 1.06 | Helped |
| use the proposed attack instead of the DSE attack | Matching pennies · Matching pennies, n=1 | average cost: 2.06 -> 1.06 | Helped |
| use the proposed attack instead of the feasible attack | Matching pennies · Matching pennies, n=10 | average cost: 16.08 -> 9.09 | Helped |
| use the proposed attack instead of the DSE attack | Matching pennies · Matching pennies, n=10 | average cost: 18.31 -> 9.09 | Helped |
| use the proposed attack instead of the feasible attack | Matching pennies · Matching pennies, n=100 | average cost: 250.46 -> 99.47 | Helped |
| use the proposed attack instead of the DSE attack | Matching pennies · Matching pennies, n=100 | average cost: 198.38 -> 99.47 | Helped |
| use the proposed attack instead of the feasible attack | Rock Paper Scissors · Rock Paper Scissors | attack cost: 4 -> 2.02 | Helped |
Limitations
- Only pure-strategy target equilibria; faking mixed NE is impossible if theory-of-mind set has nonzero volume.
- Requires full-coverage-free but relies on ToM approximation; optimality depends on tightness of outer approximation.
- Only experiments on small toy games (RPS and matching pennies).
Experimental setup
Datasets: synthetic Rock Paper Scissors dataset (5 entries) synthetic stochastic matching pennies datasets (uniform distributions)
Metrics: L1 attack cost
Baselines: DSE attack (Wu et al. 2023) feasible attack (Table 1 construction)
Builds on: Wu et al. 2023 offline reward poisoning against MARL Cui and Du 2022 pessimism/optimism offline MARL
Closest papers by meaning
- Reward Poisoning Attacks on Offline Multi-Agent Reinforcement Learning (AAAI 2023 · similarity 0.92)
- When Can You Poison Rewards? A Tight Characterization of Reward Poisoning in Linear MDPs (ICML 2026 · similarity 0.89)
- Policy Poisoning in Batch Reinforcement Learning and Control (NeurIPS 2019 · similarity 0.89)
- Optimal Attack and Defense for Reinforcement Learning (AAAI 2024 · similarity 0.87)
- Multi-level Certified Defense Against Poisoning Attacks in Offline Reinforcement Learning (ICLR 2025 · similarity 0.87)
- Learning Equilibria from Data: Provably Efficient Multi-Agent Imitation Learning (NeurIPS 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.