Research map / Learning theory and algorithms / Submodular and game algorithms
Mediator Interpretation and Faster Learning Algorithms for Linear Correlated Equilibria in General Sequential 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.
Shows untimed communication deviations equal linear deviations in extensive-form games, and uses CFR-based scaled-extension representation to get faster linear-swap regret minimizers and linear correlated equilibrium computation.
Problem
Linear-swap regret / linear correlated equilibria in extensive-form games lack a game-theoretic interpretation and existing algorithms (quadratic-program projections) are computationally expensive.
Approach
Characterizes linear deviations as untimed communication deviations, where a deviator may query a mediator any number of times per decision point; this representation is a scaled extension enabling CFR-based regret minimization with only a fixed-point computation per iteration.
Key results
- Per-iteration time speedups of 35x to 442x over the prior linear-swap method across four games (e.g., 442x on Sheriff of Nottingham).
- Time to reach the prior method's final gap is 595x (Kuhn poker) to 10800x (Sheriff) faster.
- Theoretical per-iteration complexity improves from QP to fixed-point (LP-based, tilde O(d^omega)) with O(d^2 sqrt(T)) regret.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the UTC-based algorithm instead of the prior algorithm | Linear correlated equilibrium learning · 4-Player Kuhn poker | average time per iteration: 195ms -> 5.65ms | Helped |
| Use the UTC-based algorithm instead of the prior algorithm | Linear correlated equilibrium learning · Ridesharing game | average time per iteration: 160ms -> 676μs | Helped |
| Use the UTC-based algorithm instead of the prior algorithm | Linear correlated equilibrium learning · 3-Player Leduc poker | average time per iteration: 12.1s -> 42.0ms | Helped |
| Use the UTC-based algorithm instead of the prior algorithm | Linear correlated equilibrium learning · Sheriff of Nottingham | average time per iteration: 50.2s -> 114ms | Helped |
| Use the UTC-based algorithm instead of the prior algorithm | Linear correlated equilibrium learning · 4-Player Kuhn poker | time to target gap 7 × 10⁻⁴: 5h 25m -> 32.8s | Helped |
| Use the UTC-based algorithm instead of the prior algorithm | Linear correlated equilibrium learning · Ridesharing game | time to target gap 9 × 10⁻⁵: 4h 07m -> 8.89s | Helped |
| Use the UTC-based algorithm instead of the prior algorithm | Linear correlated equilibrium learning · 3-Player Leduc poker | time to target gap 0.224: 6h 00m -> 2.12s | Helped |
| Use the UTC-based algorithm instead of the prior algorithm | Linear correlated equilibrium learning · Sheriff of Nottingham | time to target gap 2.06: 6h 00m -> 2.00s | Helped |
Surprising findings
- Untimed communication deviations can be profitable where timed communication deviations cannot, so communication equilibria are not closed under untimed deviation.
Limitations
- Untimed private communication equilibrium concept is not defined without privacy restriction; open questions remain for non-private versions.
- Swap regret poly(d)T^c remains open; the method achieves only O(d^2 sqrt(T)) regret against linear deviations.
- Power iteration used instead of LP for fixed points in experiments, so theoretical guarantees differ from practice.
Experimental setup
Datasets: 4-player Kuhn poker ridesharing game 3-player Leduc poker Sheriff of Nottingham
Benchmarks: 4-player Kuhn poker ridesharing game 3-player Leduc poker Sheriff of Nottingham
Metrics: time per iteration linear swap equilibrium gap wall-clock time to target gap
Baselines: Farina and Pipis 2023 linear-swap dynamics
Builds on: Farina and Pipis 2023 linear-swap regret communication deviations counterfactual regret minimization regret matching+
Closest papers by meaning
- Polynomial-Time Linear-Swap Regret Minimization in Imperfect-Information Sequential Games (NeurIPS 2023 · similarity 0.94)
- No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium (NeurIPS 2020 · similarity 0.92)
- Convergence of No-Swap-Regret Dynamics in Self-Play (NeurIPS 2024 · similarity 0.90)
- Efficient $\Phi$-Regret Minimization with Low-Degree Swap Deviations in Extensive-Form Games (NeurIPS 2024 · similarity 0.90)
- Impact of Decentralized Learning on Player Utilities in Stackelberg Games (ICML 2024 · similarity 0.89)
- Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games (ICLR 2025 · similarity 0.89)
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.