Форум
Крутая задача по competition
Препод: Four merchants have been granted licenses to sell a certain line of products in Foodleshire, a flat perfectly square county in Ingland. Since they will sell exactly the same products at exactly the same prices, customers, who are uniformly distributed in the shire, will go to the nearest store. Successive merchants will place their stores so that they get the most selling territory. You are the first to establish a store. Where should you build it? (To avoid the problem of arbitrarily small distances, assume that Foodleshire is exactly 1000 furlongs square, and that stores may be placed only at integer coordinates. Also, assume that all 4 merchants know there are 4 of them, and the order in which they will build their stores.) задача с этого сайта
Ответов - 14
sniff: mojet bit dva magazin s odinakovimi koordinatimi? to est u magazinov kakaia ploshad?
1004: sniff Насколько я понял, магазин - это точка, то есть могут быть 2 магазина с одинаковыми координатами.
Препод: Я не решал эту задачу, но ее, по моему мнению, нужно решить в духе Стакельберга. Т.е., мы решаем задачу оптимизации 4 торговца, если известны координаты первых трех; решаем задачу оптимизации третьего торговца, если известны координаты первых двух и учитывая оптимизирующее поведение 4 торговца; затем решаем задачу оптимизации второго торговца при заданном поведении первого торговца и учитывая оптимизирующее поведение 3 и 4 торговцев; наконец, решаем задачу оптимизации 4 торговца, учитывая оптимизационное поведение 2, 3 и 4 торговцев... Вот только не знаю, какой ответ получается. :))
Kachkovski: Kinder Как-то слишком просто, чтобы быть правдой :)
Kinder: Kachkovski Сорри, стер ответ по ошибке
Kinder: У меня вот такая мысль еще появилась... Мы ищем равновесие под подыграм, которое есть одно из статических равновесий Нэша. Множество последних есть решения, предполагающие местоположения, симметричные относительно центра (500,500), т.к. фирмы во всем симметричны (и цены фиксированы). Поэтому решение должно быть симметричное. Сейчас тут порисовал немного и почему-то мне кажется, что расположение любой фирмы на своем ходе в центральной точке (500,500) не оптимально -- ее либо потом отожмут (например, ходами (499,500) и (501,500)) либо она сама себя накажет (если 4-я фирма). (Рекомендую рисовать в квадрате 4х4, смысл тот же, равновесие все равно будет у центра с минимальным шагом вокруг, т.е. 1 единица). Исходя из этих предположений мне кажется, что решением будет такое (в дельтах относительно точки (500, 500)) 1 = (-1,-1) 2 = (+1,-1) 3 = (-1,+1) 4 = (+1,+1) Может, и неверно, но ответ симметричный и весьма симпатишный З.Ы. Функции платежей тут есть линейная функция от площади потербителей, которые ходят в эту фирму.
LazyCrazy: а я бы поставил поцентру и ние***т)))
Петян: Препод пишет: You are the first to establish a store Джеффри, считать поведение всех четырех - ваше добавление к задаче?
Kachkovski: Петян Это подсказка.
Петян: Kachkovski, разумно))
Препод: Kinder пишет: Множество последних есть решения, предполагающие местоположения, симметричные относительно центра (500,500), т.к. фирмы во всем симметричны (и цены фиксированы). Поэтому решение должно быть симметричное. Нет я, не согласен! Фирмы НЕ симметричны - они ходят по очереди, у первого есть преимущество!
Kinder: Препод Мне кажется, что эффект first-mover advantage перекроется эффектом first-mover disadvantage. Действия первой фирмы ограничиваются тройным ходом потом.
Препод: Kinder Даже если ситуация первого игрока окажется в итоге хуже ситуации остальных трех (в чем я не уверен), это не отменяет вопроса - как следует поступать первому торговцу? Как и в случае даже двух игроков, никакого симметричного исхода ожидать не следует.
Kinder: Препод Ситуация с двумя кардинально отличается от этой. Даже в игре 4х4 с двумя игроками ходы такие -- первый ставит на (2,2) и получает не менее половины прибыли, а второй -- не более половины. (если ставить можно только в разные точки, то точно меньше половины для второго). Если три игрока, то первому ставить в точку (2,2) не оптимально, т.к. его тожмут справа и слева потом (останется лишь узкая полоска спроса посередине). Поэтому я думаю, что количество игроков важно для итогового решения. (Не знаю, насколько верно для 4-х). Тобишь first-mover advantage превращается в то, что он отхапает по крайней мере четверть всего спроса. (А ведь мог бы и меньше ).
полная версия страницы