2018/08/03 by Anisse Ismaïli, Anisse Ismaili, Ismaili, Anisse
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Game Theory and Applications #Game Theory and Voting Systems #cs.GT
paper · pdf · doi:10.48550/arxiv.1808.01080
Submitted to WINE2018 on July 28th, 2018. Rejected (reviews included here). No major flaws are known. Additional (positive) results would be welcome
openalex publication_date 2018/08/03 · arxiv created 2018/10/26 · arxiv updated 2018/10/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 n1-ε of the optimum for any ε>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.