Paradoxo de Braess

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

O Paradoxo de Braess, creditado ao matemático Dietrich Braess, afirma que a adição de capacidade extra para uma rede, quando os movimentos pela rota das entidades é feita de forma egoísta, pode, em alguns casos, reduzir o desempenho global. Isto ocorre porque o equilíbrio de Nash no sistema não é necessariamente ideal.[1]

O paradoxo enuncia o seguinte: "Para cada ponto de uma rede rodoviária, que seja considerado o local de partida dos carros e os destinos deles. Sob certas condições, cada um desejará estimar a distribuição do fluxo do tráfego, sendo que a preferência de uma rua qualquer não depende apenas da qualidade da estrada, mas também da densidade do fluxo. Se cada motorista tomar o caminho que considera mais favorável para ele, o resultado do tempo de percurso não será necessariamente reduzido. Além disso, o exemplo indica que uma extensão da rede pode causar a redistribuição do tráfico, que resultaria num maior tempo de tráfego individual."

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, apesar disto diminuir o desempenho global.

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.[1] [2]

Exemplo[editar | editar código-fonte]

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: . O tempo necessário para dirigir Início-B-Fim será de . 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 , que simplificando seria e cada rota levará 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 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[editar | editar código-fonte]

Seja a fórmula para o custo do pessoas dirigindo na através da extensão . Se o fluxo do grafo tiver extensões lineares (matematicamente: , onde e são constantes), então o equilíbrio sempre existirá.

Supondo que haja um grafo de tráfico linear com pessoas dirigindo através da extensão . Então a energia de e, será:

(Se , então ). 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 é , ao passo que sua nova rota é . Podemos afirmar que é a energia total do fluxo e considere o que acontece quando a rota é removida. A energia de cada extensão será reduzida por e então o será reduzido pela soma: . Note que este é simplesmente o tempo total de viagem necessária para pegar a rota original. Se for adicionada a nova rota, , acrescentará o tempo de viagem para compensar a utilização da nova rota. Porque a nova rota é mais curta que a original, deve diminuir. Repetindo o processo, continuará a diminuir. Como deve manter-se positivo, eventualmente um equilíbrio deverá ocorrer.

Ligações externas[editar | editar código-fonte]

Referências

  1. a b Figueiredo - de Souza e Silva. «Paradoxo de Braess, exercícios resolvidos e comentados» (PDF) (em português). Universidade Federal do Rio de Janeiro. Consultado em 7 de agosto de 2009. 
  2. von Ahn L (02-10-2008). «Modeling Network Traffic Using Game Theory» (PDF). Science of the Web: Lecture 10 (em inglês). Carnegie Mellon University. Consultado em 16 de novembro de 2008. 
Ícone de esboço Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o.