Project Highlights

Summary of our project's main achievements so far:

• Flow-free selfish routing: We consider a time-based selfish routing model in which an agent traversing a link can only cause delays to agents who use the link at a later time. In particular, we assume that traffic is made up of discrete "packets'' rather than continuous "flows'' as in the classical selfish routing model studied by Roughgarden and Tardos. The
  structural properties that lead to inefficiencies in routing choices appear different in this "flow-free'' model compared to the flow-based model. In particular, in single commodity networks, with non-atomic agents, the price of anarchy is exactly one in the flow-free model; that is, selfish behaviour leads to optimal routings. In contrast, in the flow-based model simple parallel link (single commodity) networks are the worst networks from a price of anarchy perspective. For multi-commodity networks, selfish routing does lead to inefficiencies in the flow-free model. We present bounds on the price of anarchy for such networks. Specifically, in the non-atomic case the worst-case price of anarchy is exactly 4 for linear latency functions. For atomic games, the price of anarchy is between 4 and 5.83 (or 5 in the case of equal weight agents).  Our framework also extends to include more complex games, for example what is called the sub-contractor game.
• Equilibria for networks with malicious users: We consider the problem of characterizing user equilibria and optimal solutions for selfish routing in a given network. We extend the known models by considering malicious behaviour. While selfish users follow a strategy that minimizes their individual cost, a malicious user will use his flow through the network in an effort to cause the maximum possible damage to this cost. We define a generalized model, present characterizations of flows at equilibrium and prove bounds for the ratio of the social cost of a flow at equilibrium over the cost when centralized coordination among users is allowed. This is an expanded version of work presented at ISAAC 2003, that simplifies the assumptions needed for our results and generalizes these results to more general latency functions using results by Roughgarden.