Расположение объекта (кооперативная игра) - 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) находятся в ядре.

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

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

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

  1. ^ Камаль Джайн и Мохаммад Махдиан, «Разделение затрат». Глава 15 в Вазирани, Виджай В.; Нисан, Ноам; Roughgarden, Тим; Тардос, Ива (2007). Алгоритмическая теория игр (PDF). Кембридж, Великобритания: Издательство Кембриджского университета. ISBN  0-521-87282-0.