Discrete Mathematics and Optimization Seminar

McMaster University
Monday March 21st at 4.30pm
Burnside 1205

Title. The Good, the Bad, and the Rich: Routing selfish, class-conscious, and malicious users on traffic networks.

Abstract. Recently there has been great interest in the Computer Science community for the study of selfish routing on a
network. "Selfish" means that the users (the Good) of the network are uncoordinated; instead, they try to minimize their routing
cost, without caring about the effect their decisions may have on the overall performance or on the other players. This
setting is game-theoretic in nature, and it may eventually lead to an equilibrium. Such `traffic equilibria' have been
studied for a long time in the OR community, but we are particularly interested in the comparison between a coordinated
vs. an uncoordinated network. We will present a classic formulation of traffic equilibria as solutions to a complementarity
problem by Aashtiani & Magnianti, and then we will show how one can extend this formulation to model malicious users (the Bad),
and how to use taxation (class warfare) to lure the users towards a prescribed flow pattern. This is joint work with Anastasios
Viglas, and Stavros Kolliopoulos.