Research map / Learning theory and algorithms / Submodular and game algorithms
Enhancing the Efficiency of Altruism and Taxes in Affine Congestion Games through Signalling
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 that publicly signalling each player's most preferred strategy (ideally a social optimum) improves the price of anarchy of affine congestion games with θ-altruistic players and personalized refundable/non-refundable taxes, via primal-dual analysis.
Problem
Worst-case efficiency (price of anarchy) of pure Nash equilibria in affine congestion games is degraded by selfish behaviour; altruism and non-refundable taxes have not improved it (PoA 5/2 and 2 respectively), and whether signalling can help was open.
Approach
Each player's most preferred (signalled) strategy is public; players' cost includes a θ-weighted term measuring the increase they cause to other players' signalled strategies. With a signalled social optimum, this yields tight PoA bounds as a function of θ (1 at θ=1/2) and equivalent personalized taxes.
Key results
- For θ=1/2 with a signalled social optimum, the price of anarchy drops to 1, so every pure Nash equilibrium is socially optimal.
- The PoA bound improves on 5/2 for selfish players whenever θ < 5/7 (≈0.714).
- With non-refundable taxes at θ=1/2, the price of anarchy is 2, the first improvement over the known bound for non-refundable taxes in affine congestion games.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Signal a social optimum and balance altruism and selfishness (θ = 1/2) | Affine congestion games with θ-altruistic players · Affine congestion games | price of anarchy: 5/2 -> one | Helped |
| Signal a social optimum with θ < 5/7 | Affine congestion games with θ-altruistic players · Affine congestion games | price of anarchy: 5/2 | Helped |
| Signal a ξ-approximation of the social optimum instead of the optimum | θ-altruistic affine congestion games · Affine congestion games | price of anarchy: ξ | Hurt |
| Use personalized refundable taxes derived from the signalled social optimum | Affine congestion games · Affine congestion games, θ = 1/2 | price of anarchy: 2 -> 1 | Helped |
| Use personalized non-refundable taxes from (5), with θ = 1/2 | Affine congestion games · Affine congestion games | price of anarchy: 2 | Helped |
Surprising findings
- Personalized taxes at θ=1/2 can force players to decentralizedly implement a social optimum, unlike non-personalized optimal-dependent taxes whose PoA stays at 2.
Limitations
- Results assume the signalled profile is a social optimum; a ξ-approximation degrades bounds by factor ξ.
- Upper bounds are existential; they do not yield polynomial-time implementable mechanisms, unlike the P≠NP-limited refundable tax lower bound.
- Computing the social optimum is hard in general, so signalled strategies may be impractical to obtain.
Experimental setup
Metrics: price of anarchy
Baselines: selfish players PoA 5/2 refundable taxes PoA 2 altruism without signalling (Caragiannis et al. 2010)
Builds on: congestion games (Rosenthal) primal-dual method for price of anarchy altruistic congestion games (Caragiannis et al. 2010) statical optimal-dependent taxes (Bilò and Vinci 2019)
Closest papers by meaning
- Signaling in Bayesian Network Congestion Games: the Subtle Power of Symmetry (AAAI 2021 · similarity 0.88)
- Information Design for Congestion Games with Unknown Demand (AAAI 2024 · similarity 0.87)
- Learning Optimal Tax Design in Nonatomic Congestion Games (NeurIPS 2024 · similarity 0.87)
- Computing Equilibria in Binary Networked Public Goods Games (AAAI 2020 · similarity 0.87)
- The Complexity of Optimizing Atomic Congestion (AAAI 2024 · similarity 0.85)
- Multi-Sender Persuasion: A Computational Perspective (ICML 2024 · similarity 0.85)
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.