Discrete Mathematics and Optimization Seminar

McGill University
Monday November 6th at 4.30pm
Burnside 1205

Title. The Price of Anarchy and a Priority-Based Model of Routing.

Abstract. In this talk, I will begin by reviewing previous work on selfish routing, where the behaviour of traffic and
communication networks are analysed from a game-theoretic perspective. There are a number of network users, each
requiring something (a car, a data packet) to be routed between two points in the network. However, the network
suffers from congestion effects - the more a link is used, the longer it takes to traverse. I will concentrate on
the so called "price of anarchy", which quantitatively measures the inefficiency that can occur if there is no
central authority, and individual users aim to do the best they can for themselves.

I will then discuss some new results, in particular a new model for routing that introduces priorities. This will
enable us to model the idea that a car can cause congestion to cars behind it, but not in front of it. We have tight
bounds on the price of anarchy for a number of variations of our model, and make some comparisons to the standard
routing model.

The work is joint with Adrian Vetta and Babak Farzad.