Reconciling selfish routing with social good

DOI10.1007/978-3-319-66700-3_12zbMath1403.91060arXiv1707.00208OpenAlexW2962911773MaRDI QIDQ681857

Thanasis Lianeas, Soumya Basu, Ger Yang, Yitao Chen, Evdokia Nikolova

Publication date: 13 February 2018

Abstract: Selfish routing is a central problem in algorithmic game theory, with one of the principal applications being that of routing in road networks. Inspired by the emergence of routing technologies and autonomous driving, we revisit selfish routing and consider three possible outcomes of it: (i) $heta$-Positive Nash Equilibrium flow, where every path that has non-zero flow on all of its edges has cost no greater than $heta$ times the cost of any other path, (ii) $heta$-Used Nash Equilibrium flow, where every used path that appears in the path flow decomposition has cost no greater than $heta$ times the cost of any other path, and (iii) $heta$-Envy Free flow, where every path that appears in the path flow decomposition has cost no greater than $heta$ times the cost of any other path in the path flow decomposition. We first examine the relations of these outcomes among each other and then measure their possible impact on the network's performance. Afterwards, we examine the computational complexity of finding such flows of minimum social cost and give a range for $heta$ for which this task is easy and a range for $heta$ for which this task is NP-hard. Finally, we propose deterministic strategies which, in a worst case approach, can be used by a central planner in order to provide good such flows, and further introduce a natural idea for randomly routing players after giving them specific guarantees about their costs in the randomized routing, as a tool for the central planner to implement a desired flow.

Full work available at URL: https://arxiv.org/abs/1707.00208

zbMATH Keywords

computational complexityselfish routingminimum social costNash equilibrium flow

Mathematics Subject Classification ID

Games involving graphs (91A43) Traffic problems in operations research (90B20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Software, source code, etc. for problems pertaining to game theory, economics, and finance (91-04)

This page was built for publication: Reconciling selfish routing with social good