Пусть в районе проживают 10 человек, каждый из которых хочет весело провести пятничный вечер. Каждый может либо остаться дома, либо пойти в гости к любому из 9 своих сожителей по району. Как действовать каждому жителю, если доехать до любого дома стоит 2 единицы, а выигрыш от вечера равен количеству людей, с которыми он его провел. Учесть, что если кто-то пришел к пустой двери (хозяин сам ушел в гости), то все пришедшие получают 0. Можно ли обобщить это на случай произвольной стоимости за проезд и произвольной пользы от вечера?

задан 17 Июн '18 22:21

Совершенно очевидно, что нужно всем собраться у кого-то дома.
Что-то вы нам недоговариваете

(18 Июн '18 17:20) spades

@spades, ну они же не могут заранее договориться, каждый принимает решение независимо.

(18 Июн '18 17:56) mr_kin

Что значит, не могут договариваться?
Проясните этот момент. Например, все думают, а давайте соберемся у кого-нибудь. У кого же собраться? Может у того, кто живет ближе всех (суммарная длина расстояний до остальных наименьшая)? Это договор? Да, нет, почему?

(18 Июн '18 18:42) spades

@spades, давайте считать, что стоимость добраться до дома от любого жителя к любому одинаковая.

(18 Июн '18 18:53) mr_kin

@spades: в случае возможности явного или неявного договора задача становится неинтересной. Я понимаю так, что решение идти или не идти принимается с некоторой вероятностью (всё независимо), и если идти, то с равной вероятностью выбирается тот, к кому идти. Задача получается вполне содержательная.

(18 Июн '18 18:53) falcao

@falcao, содержательность по моему также отсутствует. Чтобы вечеринка была выгодной, необходимо присутствие на ней 4-х человек. Что при случайном выборе места посещения весьма маловероятно. Поправьте, если ошибаюсь

(18 Июн '18 18:59) spades

@spades: Вы правы в том смысле, что при тех конкретных данных (-2 балла за посещение), выгоднее всего сидеть дома. И это совсем легко показать. Но общий случай достаточно интересен. Или даже случай 10 домов с платой 1 балл вместо 2.

(18 Июн '18 19:22) falcao

А я так понимаю, что тут не про решение спрашивается, а про описание игры в нормальной форме...

(18 Июн '18 23:03) all_exist

@all_exist, можно с описания начать, у меня вообще никаких идей, что делать в общем виде

(18 Июн '18 23:31) mr_kin
показано 5 из 9 показать еще 4
10|600 символов нужно символов осталось
2

Рассмотрим следующую формальную общую версию задачи. Пусть имеется $%n$% домов, и за посещение другого дома мы расходуем $%a$% баллов. Все участники при этом равноправны, и ни о чём заранее не договаривались. Тогда их стратегии должны быть одинаковыми. Под этим мы понимаем то, что каждый из них с вероятностью $%p$% идёт в гости, и с вероятностью $%1-p$% остаётся дома. Идя в гости, он наудачу выбирает один из $%n-1$% домов, в который надо идти.

Для начала можно заметить, что при $%a=2$% выгоднее всего сидеть дома. При этом средний выигрыш равен нулю, а при $%p > 0$% он будет отрицателен. В самом деле, представим себе, что мы пришли к кому-то в гости, и он наверняка остался дома (этим мы завышаем значение матожидания). Тогда, даже если все остальные $%n-2$% участника наверняка пойдут в гости (снова завышение!), то в нужном нам месте в среднем соберутся (n-2)/(n-1) из них. И тогда с учётом хозяина, мы проведём вечеринку со средним числом участников $%2-\frac1{n-1} < 2$%.

Таким образом, далее можно считать, что $%0\le a < 2$%, и при таком условии найдём оптимальное значение вероятности $%p$%. Если мы идём в гости (с вероятностью $%p$%), то с вероятностью $%1-p$% хозяин окажется дома, и к нему помимо нас придут в среднем $%(n-2)p/(n-1)$% других участников. (Все эти усреднения корректны, и легко могут быть обоснованы через свойства матожидания суммы и произведения.) На таком посещении мы теряем $%a$% баллов, приобретая в среднем $%1+\frac{n-2}{n-1}p$%. Если мы остаёмся дома (с вероятностью $%1-p$%), то к нам в среднем придёт $%p$% гостей (каждый из $%n-1$% приходит с вероятностью $%p/(n-1)$%, то есть это следует из аддитивности матожидания.

Итого, с учётом формулы полной вероятности, мы имеем средний выигрыш, равный $%F(p)=p((1-p)(1+\frac{n-2}{n-1}p)-a)+(1-p)p=p(1-p)(2+\frac{(n-2)p}{n-1})-ap$%. Это кубический многочлен; требуется найти максимум функции на отрезке $%p\in[0,1]$%.

Производная здесь равна $%F'(p)=2-a-\frac{2pn+3p^2(n-2)}{n-1}$%. В точке $%p=0$% производная положительна, поэтому наибольшее значение функции получается или при $%p=1$%, или в критической точке. Квадратное уравнение здесь имеет два корня разных знаков; нас интересует положительный, равный $%p_0=\frac{\sqrt{(7-3a)n^2+9(a-2)n+6(2-a)}-n}{3(n-2)}$%. Нетрудно проверить, что эта величина всегда меньше 1.

Таким образом, при $%a < 2$% в гости идти выгодно, и делать это следует с вероятностью $%p_0$%. В частности, при $%n=10$% получается $%p_0=\frac{\sqrt{133-54a}-5}{12}$%.

ссылка

отвечен 19 Июн '18 2:15

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×78

задан
17 Июн '18 22:21

показан
413 раз

обновлен
19 Июн '18 2:15

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru