The Complexity of Sequential Routing Games
We study routing games where every agent sequentially decides her next edge when she obtains the green light at each vertex. Because every edge only has capacity to let out one agent per round, an edge acts as a FIFO waiting queue that causes congestion on agents who enter. Given $n$ agents over $|V|$ vertices, we show that for one agent, approximating a winning strategy within $n^{1-\varepsilon}$ of the optimum for any $\varepsilon>0$, or within any polynomial of $|V|$, are PSPACE-hard. Under perfect information, computing a subgame perfect equilibrium (SPE) is PSPACE-hard and in FPSPACE. Under imperfect information, deciding SPE existence is PSPACE-complete.
NurtureToken New!

Token crowdsale for this paper ends in

Author

Are you an author of this paper? Check the Twitter handle we have for you is correct.

Subcategory

#1. Which part of the paper did you read?

#2. The paper contains new data or analyses that is openly accessible?
#3. The conclusion is supported by the data and analyses?
#4. The conclusion is of scientific interest?
#5. The result is likely to lead to future research?

User:
Repo:
Stargazers:
0
Forks:
0
Open Issues:
0
Network:
0
Subscribers:
0
Language:
None
Views:
0
Likes:
0
Dislikes:
0
Favorites:
0
0
Other
Sample Sizes (N=):
Inserted:
Words Total:
Words Unique:
Source:
Abstract:
None
08/05/18 05:52PM
7,611
2,016
Tweets
WhalezEye: RT @DO: The Complexity of Sequential Routing Games. https://t.co/p9gCI3lRRa