Research map / Learning theory and algorithms / Submodular and game algorithms
Information Design for Congestion Games with Unknown Demand
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.
Studies information design (public signaling) in single-commodity non-atomic congestion games with affine costs where demand is unknown, giving an FPTAS for two demand states, a series-parallel characterization of full information revelation, and an LP-based exact algorithm with computational study on real networks.
Problem
Optimal public signaling by a principal who observes realized demand so that the induced Wardrop equilibrium (under unknown, randomly active players) minimizes expected total cost in congestion games.
Approach
Models demand uncertainty as independent player participation with state-dependent probability, shows the equilibrium cost is piecewise linear and (for two states) monotone in the posterior, and uses these properties to get an FPTAS, a graph characterization of full revelation (series-parallel), and an LP over supports.
Key results
- For two demand states, an FPTAS computes near-optimal signaling with approximation ratio 1+epsilon, with running time polynomial in input and 1/epsilon.
- Full information revelation is optimal for all affine costs and priors if and only if the network is series-parallel.
- On real-world networks (40 instances each), the average number of distinct supports is about 4.7 to 5.3 and the maximum is 9 to 12, far below the number of edges.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use optimal partial signaling instead of no signal | Four-vertex, five-edge example with prior μ*θ₂=1/2 · Four-vertex, five-edge example | total expected cost: \tfrac{133}{200} -> \tfrac{131}{200} | Helped |
| Use optimal partial signaling instead of full information revelation | Four-vertex, five-edge example with prior μ*θ₂=1/2 · Four-vertex, five-edge example | total expected cost: \tfrac{134}{200} -> \tfrac{131}{200} | Helped |
| Reveal the realized demand instead of sending no signal | Two-parallel-edge congestion game · Two parallel edges, demands 1 and 1/2 (equal probabilities) | total expected cost: \tfrac 58 = 0.625 -> \tfrac{13}{24} \approx 0.542 | Helped |
Surprising findings
- Full information revelation is often not optimal on non-series-parallel graphs, yet in the real-world instances it is reported as ubiquitously optimal despite the networks not being series-parallel.
- Optimal schemes can strictly beat both full revelation and no signaling by using randomized, partially informative signals (in the two-example illustration).
Limitations
- Results for two states are an FPTAS; the general number of supports can be exponential (nested Braess instances), so the LP algorithm can be exponential in worst case.
- Model restricted to single-commodity networks with affine cost functions and public signals.
- Computational study uses only two demand states and a fixed rho=0.2.
Experimental setup
Datasets: Sioux Falls Eastern Massachusetts Berlin-Friedrichshain Berlin-Prenzlauer Berg-Center Berlin-Tiergarten Berlin-Mitte-Center
Benchmarks: Sioux Falls Eastern Massachusetts Berlin-Friedrichshain Berlin-Prenzlauer Berg-Center Berlin-Tiergarten Berlin-Mitte-Center
Metrics: number of distinct supports concavity and linearity of expected cost C(mu)
Baselines: no signaling full information revelation
Builds on: Bayesian persuasion Wardrop equilibrium Caratheodory's theorem
Closest papers by meaning
- Enhancing the Efficiency of Altruism and Taxes in Affine Congestion Games through Signalling (AAAI 2024 · similarity 0.87)
- The Complexity of Optimizing Atomic Congestion (AAAI 2024 · similarity 0.86)
- Network Intervention by Polling Strategic Agents (NeurIPS 2026 · similarity 0.85)
- Strategic Network Creation for Enabling Greedy Routing (AAAI 2025 · similarity 0.84)
- Multi-Sender Persuasion: A Computational Perspective (ICML 2024 · similarity 0.84)
- Trade-Offs Between Information and Crowding in Sequential Decisions (Student Abstract) (AAAI 2025 · similarity 0.83)
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.