Отправлено: 05.03.07 13:04. Заголовок: Крутая задача по 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.)

задача с этого сайта

 Отправлено: 05.03.07 15:56. Заголовок: Re:

mojet bit dva magazin s odinakovimi koordinatimi? to est u magazinov kakaia ploshad?

 Отправлено: 05.03.07 16:15. Заголовок: Re:

sniff
Насколько я понял, магазин - это точка, то есть могут быть 2 магазина с одинаковыми координатами.

 Отправлено: 05.03.07 19:08. Заголовок: Re:

Я не решал эту задачу, но ее, по моему мнению, нужно решить в духе Стакельберга. Т.е., мы решаем задачу оптимизации 4 торговца, если известны координаты первых трех; решаем задачу оптимизации третьего торговца, если известны координаты первых двух и учитывая оптимизирующее поведение 4 торговца; затем решаем задачу оптимизации второго торговца при заданном поведении первого торговца и учитывая оптимизирующее поведение 3 и 4 торговцев; наконец, решаем задачу оптимизации 4 торговца, учитывая оптимизационное поведение 2, 3 и 4 торговцев... Вот только не знаю, какой ответ получается. :))

 Отправлено: 05.03.07 20:13. Заголовок: Re:

Kinder
Как-то слишком просто, чтобы быть правдой :)

 Отправлено: 05.03.07 20:28. Заголовок: Re:

Kachkovski
Сорри, стер ответ по ошибке

 Отправлено: 05.03.07 20:50. Заголовок: Re:

У меня вот такая мысль еще появилась... Мы ищем равновесие под подыграм, которое есть одно из статических равновесий Нэша. Множество последних есть решения, предполагающие местоположения, симметричные относительно центра (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)
Может, и неверно, но ответ симметричный и весьма симпатишный

З.Ы. Функции платежей тут есть линейная функция от площади потербителей, которые ходят в эту фирму.

 Отправлено: 05.03.07 21:25. Заголовок: Re:

а я бы поставил поцентру и ние***т)))

 Отправлено: 05.03.07 21:47. Заголовок: Re:

Препод пишет:

цитата:

You are the first to establish a store

Джеффри, считать поведение всех четырех - ваше добавление к задаче?

 Отправлено: 05.03.07 21:49. Заголовок: Re:

Петян
Это подсказка.

 Отправлено: 05.03.07 22:04. Заголовок: Re:

Kachkovski, разумно))

 Отправлено: 06.03.07 14:20. Заголовок: Re:

Kinder пишет:

цитата:

Множество последних есть решения, предполагающие местоположения, симметричные относительно центра (500,500), т.к. фирмы во всем симметричны (и цены фиксированы). Поэтому решение должно быть симметричное.

Нет я, не согласен! Фирмы НЕ симметричны - они ходят по очереди, у первого есть преимущество!

 Отправлено: 06.03.07 15:47. Заголовок: Re:

Препод
Мне кажется, что эффект first-mover advantage перекроется эффектом first-mover disadvantage. Действия первой фирмы ограничиваются тройным ходом потом.

 Отправлено: 07.03.07 18:57. Заголовок: Re:

Kinder

Даже если ситуация первого игрока окажется в итоге хуже ситуации остальных трех (в чем я не уверен), это не отменяет вопроса - как следует поступать первому торговцу?

Как и в случае даже двух игроков, никакого симметричного исхода ожидать не следует.

 Отправлено: 07.03.07 20:40. Заголовок: Re:

Препод
Ситуация с двумя кардинально отличается от этой. Даже в игре 4х4 с двумя игроками ходы такие -- первый ставит на (2,2) и получает не менее половины прибыли, а второй -- не более половины. (если ставить можно только в разные точки, то точно меньше половины для второго).
Если три игрока, то первому ставить в точку (2,2) не оптимально, т.к. его тожмут справа и слева потом (останется лишь узкая полоска спроса посередине).
Поэтому я думаю, что количество игроков важно для итогового решения. (Не знаю, насколько верно для 4-х).
Тобишь first-mover advantage превращается в то, что он отхапает по крайней мере четверть всего спроса. (А ведь мог бы и меньше ).