---
title: "How Much Can Approximate Equilibria Change the Social Cost of Selfish Routing?"
source: "arXiv AI/CL/LG（论文）"
source_tier: "t2"
url: "https://arxiv.org/abs/2611.01234v1"
permalink: "https://feed.astralor.com/items/itm_1b1adf6e1eb209a949dbe8e2"
published: "2026-10-31T20:01:59.000Z"
score: 56
channel: "tech"
tags: ["How Much Can","Approximate Equilibria Change","Social Cost","Selfish Routing","Nash"]
---

# How Much Can Approximate Equilibria Change the Social Cost of Selfish Routing?

## 速览

We study approximate Nash equilibria in nonatomic congestion games, with the goal of understanding how much the social cost can change when the equilibrium condition is relaxed. We consider $ε$-approximate Nash equilibr…

## 关键点

- We study approximate Nash equilibria in nonatomic congestion games, with the goal of understanding how much the social cost can change when the equilibrium condition is relaxed.
- We consider $ε$-approximate Nash equilibria ($ε$-NE), in which each player uses a strategy whose cost is at most $1 + ε$ times the minimum available cost.
- We compare the social costs of $ε$-NE and exact Nash equilibria.

## 全文

We study approximate Nash equilibria in nonatomic congestion games, with the goal of understanding how much the social cost can change when the equilibrium condition is relaxed. We consider $ε$-approximate Nash equilibria ($ε$-NE), in which each player uses a strategy whose cost is at most $1 + ε$ times the minimum available cost. We compare the social costs of $ε$-NE and exact Nash equilibria. This lets us quantify, for example, how much a navigation app can reduce total travel time when drivers tolerate routes slightly slower than the fastest available route. For degree-$d$ polynomial latencies in both general nonatomic congestion games and single-commodity routing games on series-parallel networks, we give tight lower and upper bounds on the relative change in social cost from an exact Nash equilibrium to any $ε$-NE, with matching instances for every $ε$. For small $ε$, the largest possible relative reduction and increase in general congestion games are both $Θ(\sqrt{dε})$, independently of the number of resources and populations. In contrast, on series-parallel networks of depth $h$, the largest possible relative reduction is $Θ(hε)$, while the largest possible relative increase is known to be $ε$. For the classes of games we study, these results give a tight and quantitative characterization of the possible changes in social cost and establish a separation between general and series-parallel networks.

---

引用前请核对原文;本文由星际流动整理:https://feed.astralor.com/items/itm_1b1adf6e1eb209a949dbe8e2