Paradoxo de Braess

O paradoxo de Braess, apresentado em 1968 pelo matemático alemão Dietrich Braess (n. 1938), é uma ilustração da ideia de que a oferta de um curso de ação adicional pode levar a uma piora da situação de todos os indivíduos, assumindo-se decisões individuais racionais. Trata-se de uma explicação para o caso em que uma alteração na rede viária, visando aumentar a fluidez do tráfego, tem o efeito exatamente oposto, reduzindo o desempenho de toda a rede. O trabalho original de Braess mostra uma situação paradoxal em que a construção de uma rodovia adicional (ou seja, um aumento na capacidade de uma rede viária congestionada), pode aumentar o tempo de percurso para todos os usuários da rede (ou seja, a capacidade da rede é reduzida), mantendo-se constante a demanda de tráfego e pressupondo-se que cada usuário da rede escolha o seu percurso de modo a minimizar o tempo de viagem (roteamento egoísta). Isto ocorre porque o equilíbrio de Nash no sistema não é necessariamente ideal. O paradoxo tem sido usado para explicar situações em que a fluidez do tráfego melhora quando as vias principais de uma rede são bloqueadas.

O paradoxo de Braess é uma ilustração de que a otimização racional dos interesses individuais associados a um bem público pode resultar em um estado sub-ótimo para cada indivíduo. O paradoxo pode ser enunciado da seguinte forma:

"Dada uma rede rodoviária e dados o ponto inicial do trajeto de um certo número de veículos e o ponto de destino deles, supondo-se que a preferência de cada motorista seja baseada não apenas na qualidade da estrada, mas também na densidade do fluxo, e que cada motorista escolha o caminho que mais o favorece (motoristas egoístas), o resultado do tempo de percurso não será necessariamente ótimo (no sentido de Pareto), sendo que uma extensão na rede rodoviária pode causar uma redistribuição do tráfego que resultará em maior duração dos percursos individuais."

A razão para isto é que, no equilíbrio de Nash, os motoristas não terão nenhum incentivo para mudar suas rotas. Se o sistema está neste equilíbrio, os motoristas egoístas deverão ser capazes de melhorar o tempo de suas viagens alterando as rotas que eles utilizam. No caso do paradoxo em questão, os motoristas irão continuar trocando até que ocorra o equilíbrio, mas, apesar disto, será reduzido o desempenho global da rede.

Se a latência é uma função linear, então, a adição de um trajeto nunca poderá fazer o tempo total no equilíbrio pior do que um fator de 4/3.

Exemplo

Exemplo do paradoxo de Braess

Considere uma rede rodoviária como mostrado no diagrama ao lado, onde 4.000 motoristas desejam viajar do ponto Início ao ponto Fim. O tempo em minutos de Início para A na estrada é calculado pelo número de viajantes (V) dividido por 100, e de Início para B é uma constante de 45 minutos. Se a estrada tracejada não existir, então o fluxo da rede terá 4 rodovias no total e o tempo necessário para percorrer a rota Início-A-Fim deverá ser de: ${\tfrac {A}{100}}+45$. O tempo necessário para dirigir Início-B-Fim será de ${\tfrac {B}{100}}+45$. Se uma rota for mais curta, então, pelo equilíbrio de Nash, o motorista racionalmente iria trocar sua rota para esta. Como há 4.000 pilotos, matematicamente teremos $A+B=4000$, que simplificando seria $A=B=2000$ e cada rota levará ${\tfrac {2000}{100}}+45=65$ minutos.

Agora supomos que a linha tracejada é uma estrada com um tempo de viagem menor, de aproximadamente 0 minutos. Nesta situação, todos os motoristas escolheriam o caminho Início-A-B, pois este caminho levará 40 minutos, enquanto simplesmente dirigir por Início-B levará 45 minutos. Ao chegar a A, cada motorista racionalmente escolherá a estrada "livre" para B e continuará ao Fim, porque de A-Fim demora 45 minutos para se atravessar, ao passo que de A-B-Fim não ultrapassará 40. Cada motorista levará o tempo de ${\tfrac {4000}{100}}+{\tfrac {4000}{100}}=80$ minutos para percorrer, exigindo um aumento de 15 minutos dos originais 65, de quando o atalho A-B não existia. Ninguém nesta situação será incentivado a trocar, pois ambas as rotas originais (Início-A-Fim e Início-B-Fim) levam agora 85 minutos. Se cada motorista aceitasse em não utilizar o caminho A-B, cada um seria beneficiado em 15 minutos de redução no tempo total de sua viagem. Mas, se cada motorista sempre quiser utilizar este atalho, a otimização da distribuição social não estará estável e então o paradoxo de Braess ocorrerá.

Existência de um equilíbrio

Seja $L_{e}(x)$ a fórmula para o custo do $x$ pessoas dirigindo na através da extensão $e$. Se o fluxo do grafo tiver extensões lineares (matematicamente: $L_{e}(x)=a_{e}x+b_{e}>0$, onde $a_{e}$ e $b_{e}$ são constantes), então o equilíbrio sempre existirá.

Supondo que haja um grafo de tráfico linear com $e_{x}$ pessoas dirigindo através da extensão $e$. Então a energia de e, $E(e)$ será:

$\sum _{i=1}^{e_{x}}L_{e}(i)=L_{e}(1)+L_{e}(2)+...+L_{e}(e_{x})$

(Se $x_{e}=0$, então $E(e)=0$). Com isso, a energia total do fluxo será a soma das energias de cada extensão no grafo.

Suponha agora que a distribuição do fluxo do grafo não esteja em equilíbrio. Deve haver pelo menos um condutor que possa alterar sua rota e melhorar o tempo total de viagem. Sua rota original é $x_{0},x_{1},...x_{n}$, ao passo que sua nova rota é $y_{0},y_{1},...y_{m}$. Podemos afirmar que $E$ é a energia total do fluxo e considere o que acontece quando a rota $x_{0},x_{1},...x_{n}$ é removida. A energia de cada extensão $x_{i}$ será reduzida por $L_{e}(i_{x})$ e então o $E$ será reduzido pela soma: $\sum _{i=0}^{n}L_{e}(i_{x})$. Note que este é simplesmente o tempo total de viagem necessária para pegar a rota original. Se for adicionada a nova rota, $y_{0},y_{1},...y_{m}$, $E$ acrescentará o tempo de viagem para compensar a utilização da nova rota. Porque a nova rota é mais curta que a original, $E$ deve diminuir. Repetindo o processo, $E$ continuará a diminuir. Como $E$ deve manter-se positivo, eventualmente um equilíbrio deverá ocorrer.

Ver também

• Anomalia de Bélády
• Bufferbloat
• Roteamento

Ligações externas

• Programas de Teste de Paradoxos (em inglês)
• Página Oficial de Braess (em inglês)
• Caracterizando o Paradoxo de Braess para Redes de Trânsito (em inglês)
• O Paradoxo da Rede Rodoviária (em inglês)