Altruísmo, egoísmo e rancor na rota de tráfego

Neste artigo, estudamos o preço da anarquia na rota de tráfego, sob a suposição de que os usuários são parcialmente altruístas ou rancorosos. Modelamos esse comportamento postulando que o "custo" percebido por um usuário é uma combinação linear da latência real da rota escolhida (componente egoísta) e o aumento na latência que o usuário causa para os outros (componente altruísta). Mostramos que se todos os usuários têm um coeficiente de pelo menos β 0 para o componente altruísta, então o preço da anarquia está limitado a 1/β, para todas as topologias de rede, mercadorias arbitrárias e funções de latência semi-convexas arbitrárias. Estendemos esse resultado para fornecer limites mais precisos sobre o preço da anarquia para classes específicas de funções de latência, mesmo para β 0 modelando comportamento rancoroso. Em particular, mostramos que se todas as funções de latência são lineares, o preço da anarquia é limitado a 4/(3 + 2β − β 2). Em seguida, estudamos distribuições de altruísmo não uniformes, onde diferentes usuários podem ter coeficientes β diferentes. Provamos que todos esses jogos, mesmo com infinitos tipos de jogadores, têm um Equilíbrio de Nash. Mostramos que se a média dos coeficientes para os componentes altruístas de todos os usuários é ¯ β, então o preço da anarquia está limitado a 1 / ¯ β, para redes de link paralelo de mercadoria única e funções de latência convexas arbitrárias. Em particular, este resultado generaliza, embora de forma não construtiva, os resultados de roteamento de Stackelberg de Roughgarden e Swamy. De maneira mais geral, limitamos o preço da anarquia com base na classe de funções de latência permitidas e, como corolário, obtemos limites mais rigorosos para o roteamento de Stackelberg do que um resultado recente de Swamy.