Решение по переговорам Калаи-Смородинского
Решение теории игр

Решение торга Калаи–Смородинского (КС) является решением проблемы торга . Оно было предложено Эхудом Калаи и Меиром Смородинским [1] как альтернатива решению торга Нэша, предложенному 25 лет назад. Главное различие между двумя решениями заключается в том, что решение Нэша удовлетворяет независимости нерелевантных альтернатив , тогда как решение КС вместо этого удовлетворяет ресурсной монотонности .

Параметр

Задача о сделке для двух человек состоит из пары : ( Ф , г ) {\displaystyle (F,d)}

  • Допустимое множество соглашений . Это замкнутое выпуклое подмножество . Каждый элемент представляет возможное соглашение между игроками. Координаты соглашения — это полезности игроков, если это соглашение реализуется. Предположение о том, что является выпуклым , имеет смысл, например, когда можно комбинировать соглашения путем рандомизации. Ф {\displaystyle F} Р 2 {\displaystyle \mathbb {R} ^{2}} Ф {\displaystyle F} Ф {\displaystyle F}
  • Точка разногласия , где и — соответствующие выигрыши игрока 1 и игрока 2, когда торги заканчиваются без достижения соглашения. г = ( г 1 , г 2 ) {\displaystyle d=(d_{1},d_{2})} г 1 {\displaystyle d_{1}} г 2 {\displaystyle d_{2}}

Предполагается, что проблема нетривиальна, т.е. соглашения по ней лучше для обеих сторон, чем разногласия. Ф {\displaystyle F}

Решение переговоров — это функция , которая берет задачу переговоров и возвращает точку в ее наборе возможных соглашений, . ф {\displaystyle f} ( Ф , г ) {\displaystyle (F,d)} ф ( Ф , г ) ∈ Ф {\displaystyle f(F,d)\in F}

Требования к переговорным решениям

Решения Нэша и KS согласуются по следующим трем требованиям:

Оптимальность по Парето является необходимым условием. Для каждой проблемы торга возвращенное соглашение должно быть эффективным по Парето. ф ( Ф , г ) {\displaystyle f(F,d)}

Симметрия также необходима. Имена игроков не должны иметь значения: если игрок 1 и игрок 2 меняют свои утилиты, то соглашение должно быть изменено соответствующим образом.

Инвариантность к положительным аффинным преобразованиям также кажется необходимым условием: если функция полезности одного или нескольких игроков преобразуется линейной функцией, то соглашение также должно быть преобразовано той же линейной функцией. Это имеет смысл, если мы предположим, что функции полезности являются лишь представлениями отношения предпочтения и не имеют реального числового значения.

В дополнение к этим требованиям Нэш требует независимости нерелевантных альтернатив (IIA). Это означает, что если набор возможных соглашений растет (больше соглашений становится возможным), но решение по переговорам выбирает соглашение, которое содержалось в меньшем наборе, то это соглашение должно быть таким же, как соглашение, достигнутое, когда был доступен только меньший набор, поскольку новые соглашения нерелевантны. Например, предположим, что в воскресенье мы можем договориться о варианте A или варианте B, и мы выбираем вариант A. Затем, в понедельник мы можем договориться о варианте A или B или C, но мы не выбираем вариант C. Затем Нэш говорит, что мы должны выбрать вариант A. Новый вариант C нерелевантен, поскольку мы его все равно не выбираем.

Калай и Смородинский расходятся с Нэшем по этому вопросу. Они утверждают, что весь набор альтернатив должен влиять на достигнутое соглашение. В приведенном выше примере предположим, что отношение предпочтений игрока 2: C>>B>A (C намного лучше, чем B, который несколько лучше, чем A), в то время как отношение предпочтений игрока 1 обратное: A>>B>>C. Тот факт, что становится доступным вариант C, позволяет игроку 2 сказать: «если я откажусь от своего лучшего варианта — C, я имею право требовать, чтобы был выбран, по крайней мере, мой второй лучший вариант».

Поэтому KS удаляют требование IIA. Вместо этого они добавляют требование монотонности . Это требование гласит, что для каждого игрока, если полезность, достижимая этим игроком для каждой полезности другого игрока, слабо больше, то полезность, которую этот игрок получает в выбранном соглашении, также должна быть слабо больше. Другими словами, игрок с лучшими вариантами должен получить слабо-лучшее соглашение.

Формальное определение монотонности основано на следующих определениях.

  • Б е с т я ( Ф ) {\displaystyle Best_{i}(F)} - наилучшая ценность, которую я могу получить от игрока в рамках возможного соглашения.
  • Б е с т я ( Ф , ты ) {\displaystyle Best_{i}(F,u)} - наилучшая ценность, которую игрок i может получить в осуществимом соглашении, в котором полезность другого игрока составляет (если другой игрок никогда не сможет получить полезность , то определяется как ). ты {\displaystyle u} ты {\displaystyle u} Б е с т я ( Ф , ты ) {\displaystyle Best_{i}(F,u)} Б е с т я ( Ф ) {\displaystyle Best_{i}(F)}

Требование монотонности гласит, что если и — две проблемы торга, такие, что: ( Ф , г ) {\displaystyle (F,d)} ( Ф ′ , г ) {\displaystyle (F',d)}

  • Б е с т 1 ( Ф ) = Б е с т 1 ( Ф ′ ) {\displaystyle Лучший_{1}(F)=Лучший_{1}(F')}
  • Для каждого u , Б е с т 2 ( Ф , ты ) ≤ Б е с т 2 ( Ф ′ , ты ) {\displaystyle Best_{2}(F,u)\leq Best_{2}(F',u)}

Тогда решение f должно удовлетворять:

  • ф 2 ( Ф , г ) ≤ ф 2 ( Ф ′ , г ) {\displaystyle f_{2}(F,d)\leq f_{2}(F',d)}

По словам КС:

«Если для каждого уровня полезности, который может потребовать игрок 1, максимально возможный уровень полезности, которого может одновременно достичь игрок 2, увеличивается, то уровень полезности, назначенный игроку 2 в соответствии с решением, также должен быть увеличен».

По симметрии то же самое требование выполняется, если поменять местами игроков 1 и 2.

Решение КС

Решение КС можно рассчитать геометрически следующим образом.

Пусть будет точкой наилучшей полезности . Проведите линию от (точки несогласия) до (точки наилучшей полезности). б ( Ф ) {\displaystyle b(F)} ( Б е с т 1 ( Ф ) , Б е с т 2 ( Ф ) ) {\displaystyle (Лучший_{1}(F),Лучший_{2}(F))} Л {\displaystyle L} г {\displaystyle д} б {\displaystyle б}

По предположению нетривиальности, линия имеет положительный наклон. По выпуклости пересечение с множеством является интервалом. Решение KS является верхней правой точкой этого интервала. Л {\displaystyle L} Ф {\displaystyle F} Л {\displaystyle L} Ф {\displaystyle F}

Математически решение KS — это максимальная точка, которая сохраняет соотношения выигрышей. То есть, это точка на границе Парето , такая, что: μ {\displaystyle \мю} Ф {\displaystyle F}

μ 1 − г 1 μ 2 − г 2 = Б е с т 1 ( Ф ) − г 1 Б е с т 2 ( Ф ) − г 2 {\displaystyle {\mu _{1}-d_{1} \over \mu _{2}-d_{2}}={Лучшее_{1}(F)-d_{1} \over Лучшее_{2}(F)-d_{2}}}

Примеры

Алисе и Джорджу нужно выбрать один из трех вариантов, которые дадут им следующие суммы денег: [2] : 88–92  Предположим для целей примера, что полезность линейна по деньгам и что деньги не могут быть переданы от одной стороны другой.

абс
Элис605030
Джордж80110150

Они также могут смешивать эти варианты в произвольных долях. Например, они могут выбрать вариант a для доли x времени, вариант b для доли y и вариант c для доли z, так что: . Следовательно, множество допустимых соглашений представляет собой выпуклую оболочку a(60,80) и b(50,110) и c(30,150). х + у + з = 1 {\displaystyle x+y+z=1} Ф {\displaystyle F}

Точка несогласия определяется как точка минимальной полезности: это 30 для Алисы и 80 для Джорджа, поэтому d=(30,80).

Для обоих решений Нэша и KS нам необходимо нормализовать полезности агентов, вычитая значения несогласия, поскольку нас интересуют только выгоды, которые игроки могут получить выше этой точки несогласия. Следовательно, нормализованные значения следующие:

абс
Элис30200
Джордж03070

Решение Нэша по торгам максимизирует произведение нормализованных полезностей:

макс л о г ( 30 х + 20 у ) + л о г ( 30 у + 70 з ) {\displaystyle \max log(30x+20y)+log(30y+70z)}

Максимум достигается, когда и и (т.е. вариант b используется 87,5% времени, а вариант c используется в оставшееся время). Выигрыш полезности Алисы составляет 17,5 долларов, а Джорджа — 35 долларов. х = 0 {\displaystyle x=0} у = 7 / 8 {\displaystyle у=7/8} з = 1 / 8 {\displaystyle z=1/8}

Решение КС по торгам уравнивает относительные выгоды — выгоды каждого игрока относительно его максимально возможной выгоды — и максимизирует это равное значение:

макс 30 х + 20 у 30 = 30 у + 70 з 70 {\displaystyle \max {30x+20y \более 30}={30y+70z \более 70}}

Здесь максимум достигается, когда и и . Выигрыш полезности Алисы составляет 16,1 доллара, а Джорджа — 37,7 доллара. х = 0 {\displaystyle x=0} у = 21 / 26 {\displaystyle у=21/26} з = 5 / 26 {\displaystyle z=5/26}

Обратите внимание, что оба решения являются Парето-превосходящими решение "случайно-диктаторское" - решение, которое выбирает диктатора случайным образом и позволяет ему/ей выбрать свой лучший вариант. Это решение эквивалентно тому, чтобы позволить и и , что дает выигрыш полезности всего в $15 для Алисы и $35 для Джорджа. х = 1 / 2 {\displaystyle x=1/2} у = 0 {\displaystyle у=0} з = 1 / 2 {\displaystyle z=1/2}

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

Ссылки

  1. ^ Калай, Эхуд и Смородинский, Меир (1975). «Другие решения проблемы торга Нэша». Econometrica . 43 (3): 513– 518. doi :10.2307/1914280. JSTOR  1914280.
  2. ^ Эрве Мулен (2004). Справедливое разделение и коллективное благосостояние . Кембридж, Массачусетс: MIT Press. ISBN 9780262134231.
Взято с "https://en.wikipedia.org/w/index.php?title=Решение_торговли_Калай–Смородинским&oldid=1245945894"