TY - GEN
T1 - Social Cost Guarantees in Smart Route Guidance
AU - Serafino, Paolo
AU - Ventre, Carmine
AU - Tran-thanh, Long
AU - Zhang, Jie
AU - An, Bo
AU - Jennings, Nick
PY - 2019/8/23
Y1 - 2019/8/23
N2 - We model and study the problem of assigning traffic in an urban road network infrastructure. In our model, each driver submits their intended destination and is assigned a route to follow that minimizes the social cost (i.e., travel distance of all the drivers). We assume drivers are strategic and try to manipulate the system (i.e., misreport their intended destination and/or deviate from the assigned route) if they can reduce their travel distance by doing so. Such strategic behavior is highly undesirable as it can lead to an overall suboptimal traffic assignment and cause congestion. To alleviate this problem, we develop moneyless mechanisms that are resilient to manipulation by the agents and offer provable approximation guarantees on the social cost obtained by the solution. We then empirically test the mechanisms studied in the paper, showing that they can be effectively used in practice in order to compute manipulation resistant traffic allocations.
AB - We model and study the problem of assigning traffic in an urban road network infrastructure. In our model, each driver submits their intended destination and is assigned a route to follow that minimizes the social cost (i.e., travel distance of all the drivers). We assume drivers are strategic and try to manipulate the system (i.e., misreport their intended destination and/or deviate from the assigned route) if they can reduce their travel distance by doing so. Such strategic behavior is highly undesirable as it can lead to an overall suboptimal traffic assignment and cause congestion. To alleviate this problem, we develop moneyless mechanisms that are resilient to manipulation by the agents and offer provable approximation guarantees on the social cost obtained by the solution. We then empirically test the mechanisms studied in the paper, showing that they can be effectively used in practice in order to compute manipulation resistant traffic allocations.
UR - http://www.scopus.com/inward/record.url?scp=85072853293&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-29911-8_37
DO - 10.1007/978-3-030-29911-8_37
M3 - Conference contribution
SN - 9783030299101
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 482
EP - 495
BT - Pacific Rim International Conference on Artificial Intelligence
A2 - Nayak, Abhaya C.
A2 - Sharma, Alok
ER -
