TY - GEN

T1 - Altruism, selfishness, and spite in traffic routing

AU - Chen, Po-An

AU - Kempe, David

PY - 2008

Y1 - 2008

N2 - In this paper, we study the price of anarchy of traffic routing, under the assumption that users are partially altruistic or spiteful. We model such behavior by positing that the "cost" perceived by a user is a linear combination of the actual latency of the route chosen (selfish component), and the increase in latency the user causes for others (altruistic component). We show that if all users have a coefficient of at least β > 0 for the altruistic component, then the price of anarchy is bounded by 1/β, for all network topologies, arbitrary commodities, and arbitrary semi-convex latency functions. We extend this result to give more precise bounds on the price of anarchy for specific classes of latency functions, even for β < 0 modeling spiteful behavior. In particular, we show that if all latency functions are linear, the price of anarchy is bounded by 4/(3 + 2β - β2). We next study non-uniform altruism distributions, where different users may have different coefficients β. We prove that all such games, even with infinitely many types of players, have a Nash Equilibrium. We show that if the average of the coefficients for the altruistic components of all users is β, then the price of anarchy is bounded by 1/β, for single commodity parallel link networks, and arbitrary convex latency functions. In particular, this result generalizes, albeit non-constructively, the Stackelberg routing results of Roughgarden and of Swamy. More generally, we bound the price of anarchy based on the class of allowable latency functions, and as a corollary obtain tighter bounds for Stackelberg routing than a recent result of Swamy.

AB - In this paper, we study the price of anarchy of traffic routing, under the assumption that users are partially altruistic or spiteful. We model such behavior by positing that the "cost" perceived by a user is a linear combination of the actual latency of the route chosen (selfish component), and the increase in latency the user causes for others (altruistic component). We show that if all users have a coefficient of at least β > 0 for the altruistic component, then the price of anarchy is bounded by 1/β, for all network topologies, arbitrary commodities, and arbitrary semi-convex latency functions. We extend this result to give more precise bounds on the price of anarchy for specific classes of latency functions, even for β < 0 modeling spiteful behavior. In particular, we show that if all latency functions are linear, the price of anarchy is bounded by 4/(3 + 2β - β2). We next study non-uniform altruism distributions, where different users may have different coefficients β. We prove that all such games, even with infinitely many types of players, have a Nash Equilibrium. We show that if the average of the coefficients for the altruistic components of all users is β, then the price of anarchy is bounded by 1/β, for single commodity parallel link networks, and arbitrary convex latency functions. In particular, this result generalizes, albeit non-constructively, the Stackelberg routing results of Roughgarden and of Swamy. More generally, we bound the price of anarchy based on the class of allowable latency functions, and as a corollary obtain tighter bounds for Stackelberg routing than a recent result of Swamy.

KW - Altruism

KW - Anarchy

KW - Routing

KW - Selfishness

KW - Spite

UR - http://www.scopus.com/inward/record.url?scp=77950908720&partnerID=8YFLogxK

U2 - 10.1145/1386790.1386816

DO - 10.1145/1386790.1386816

M3 - Conference contribution

AN - SCOPUS:77950908720

SN - 9781605581699

T3 - Proceedings of the ACM Conference on Electronic Commerce

SP - 140

EP - 149

BT - EC'08 - Proceedings of the 2008 ACM Conference on Electronic Commerce

T2 - 2008 ACM Conference on Electronic Commerce, EC'08

Y2 - 8 July 2008 through 12 July 2008

ER -