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 de tráfico, 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áfico 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: \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[editar | editar código-fonte]

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_ex + 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.

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 (em português) Universidade Federal do Rio de Janeiro. Visitado em 7 de agosto de 2009.
  2. von Ahn L (02-10-2008). Modeling Network Traffic Using Game Theory (em inglês) Carnegie Mellon University Science of the Web: Lecture 10. Visitado 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.