Speaker: Aaron Roth Title: The Price of Malice in Linear Congestion Games Abstract: The price of anarchy has proven to be a useful measure for quantifying the degradation of performance in a system that is populated by selfish agents. However, it is a brittle measure, because it assumes that all users of the system are perfectly rational and adeptly seek to minimize their own cost. In actual networks, this is not always the case! Users may be oblivious to congestion, may be unable to calculate optimal routes, or may be explicitly malicious (consider, for example, denial of service attacks and worms). In this talk, we study the price of malice in traffic routing games, in which users must choose paths on a network to route their flow, and incur traffic dependent latency costs. We quantify by how much Byzantine (possibly malicious) users can degrade social cost. We provide bounds on two measures of the price of malice that have been proposed in the literature, by bounding the price of total anarchy. Bounding the price of malice using the price of total anarchy has the advantage that our bounds on social cost can be plausibly achieved by computationally efficient, decentralized agents who may only be aware of their own costs.