дорога с благими намерениями

[109]

пару недель назад ходил на лекцию по теории игр, давно хотел этот постинг написать, но всё руки не доходили.

представим себе два альтернативных способа попасть из города A в город D:



цифры означают время; 1 = константа, 0..1 = пропорционально доле общего трафика, проходящего по ребру.

очевидно, пути через В и С равноценны, через каждый пойдёт половина трафика, и попасть из A в D можно будет за время 1 + 0.5 = 1.5

если на каком-то из путей окажется трафика меньше чем половина, то предельно рациональные водители, решающие, по какому пути поехать, выберут меньший трафик. то есть система стабильна.

теперь следим за руками: правительство штата объявило о плане разгрузить дороги и уменьшить трафик путём построения скоростной супермагистрали, такой быстрой, что время прохождения практически равно нулю.

обстоятельства сложились так, что по политическим причинам супермагистраль пришлось построить между B и С:



теперь рациональные водители даже не задумываются, как им ехать; путь [A]->[B]->[C]->[D] всегда гарантированно быстрее, чем какой-либо другой, поэтому весь трафик идёт по этому пути; время в пути = 1 + 1 = 2.

то есть, строительство дополнительной дороги ухудшило положение вещей.

Comments

[squadette.livejournal.com]

я не очень понял, что значит "константа 1" -- в смысле что дорога так себе?

если оба все рациональные водители поедут A-B, то наверное дорога A-C будет разгружаться, нет? и константа станет типа 0.5?

[109.livejournal.com]

нет, это значит, что скорость не зависит от трафика и время всегда = 1. представь широкую просёлочную дорогу с грязью и ухабами.

[msh.livejournal.com]

То есть "рациональный водитель" - это тупой лемминг, который продолжает ездить через B-C, даже когда уже заметил, что все остальные маршруты дают тоже самое время 2, потому что ему сказали, что там супермагистраль

[plakhov.livejournal.com]

замените 0..1 на 0..0,99

[ivanvr.livejournal.com]

Если все уже едут через B->C, то рациональный водитель будет оставаться на A->B->C->D, потому что если найдется хоть кто-то кто поедет A->C->D или A->B->D, то тогда он точно проедет за <2.

Если никто не едет через B->C и трафик распределен 50/50, то водитель проехавший A->B за (х), оказавщийсь в [B] думает: езать по B->D за (1) или ехать по B->C->D за (1-x). Трафик перераспределиться и народ перестанет ездить по A->C и В->D, что по условиям задачи не ускорит проезд по ним.

[109.livejournal.com]

рациональный водитель - это тот, кто едет туда, где быстрее во всех случаях, кроме вырожденного. поскольку в вырожденном случае время тоже не хуже, то ехать туда никакого смысла нет никогда.

[109.livejournal.com]

естественно, ехать туда следует читать как не ехать туда