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

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

• Есть несколько потребителей, которым нужна определенная услуга, например, подключение к электричеству.
• Есть несколько мест, где можно строить объекты (например, электростанции).
• Для каждой пары потребителей (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) находятся в ядре.

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

Смотрите также

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

Рекомендации