Расположение объекта (кооперативная игра)

Совместная игра определения местоположения объекта - это совместная игра с разделением затрат. Цель состоит в том, чтобы разделить стоимость открытия новых объектов между клиентами, пользующимися этими удобствами. В игре есть следующие компоненты:

• Есть несколько потребителей, которым нужна определенная услуга, например, подключение к электросети.
• Есть несколько мест, где можно построить объекты (например, электростанции).
• Для каждой пары потребителей (C) и местоположения (L) существует фиксированная стоимость обслуживания C из L (например, в зависимости от расстояния между электростанцией и домом потребителя). Эта стоимость обозначается как Стоимость [C, L].
• Стоимость обслуживания группы потребителей ниже, чем сумма затрат на обслуживание каждого потребителя в отдельности.

ПРИМЕР:

• Есть два Стоимость услуг F1 составляет 2, а стоимость F2 - 2.
• Есть три потребителя, Алиса Боб и Карл.
• Алиса может обслуживаться только из F1 при стоимости 2. Таким образом, стоимость обслуживания обслуживание только ее составляет 2 + 2 = 4.
• Боба можно обслужить из F1 за 2 или из F2 за 1. Таким образом, стоимость обслуживания одного составляет 2 + 1 = 3.
• Карла можно обслужить только из F2, с ценой 1. Таким образом, стоимость обслуживания только его составляет 2 + 1 = 3.
• Стоимость обслуживания Алисы и Боба составляет 2 + 2 + 2 = 6 ( построив только F1).
• Стоимость обслуживания Боба и Карла составляет 2 + 1 + 1 = 4 (построив только F2).
• Стоимость обслуживания Алисы и Карла составляет 2+ 2 + 2 + 1 = 7 (построив F1 и F2).
• Стоимость обслуживания всех агентов составляет 2 + 2 + 2 + 1 + 1 = 8.

Наиболее социально желаемый результат игра в том, что все агенты обслуживаются. Стоимость этого результата (8 в приведенном выше примере) может быть разделена между агентами. Распределение затрат хорошо, если ни одна подгруппа агентов не может отклониться и получить более низкую стоимость для себя (такое распределение затрат, как говорят, находится в ядре игры). В приведенном выше примере:

• Вектор затрат (5,2,1) не находится в ядре, так как Алиса может отклониться и получить стоимость только 4. Точно так же вектор (3,3,2) не является в ядре, поскольку Боб и Карл могут отклониться вместе и получить общую стоимость только 4.
• Векторы затрат (4,2,2) и (4,1,3) находятся в ядре.

Классический результат теории игр, теорема Бондаревой – Шепли, дает необходимые и достаточные условия для того, чтобы игра имела непустое ядро.

См. Также

• Расположение объекта (проблема оптимизации)
• Расположение объекта (соревновательная игра)
• Механизм разделения затрат

Ссылки