Цойтенская стратегия - Zeuthen strategy

В Цойтенская стратегия это стратегия переговоров, используемая некоторыми искусственные агенты. Его цель - измерить готовность рискнуть конфликтом.^[1] Агент будет более склонен рисковать конфликтом, если ему нечего терять в случае неудачи переговоров. Напротив, агент менее склонен рисковать конфликтом, когда ему есть что терять. Стоимость сделки выражается в ее полезности. Агент может многое потерять, если разница между полезностью его текущего предложения и конфликтной сделкой высока.

Когда оба агента используют монотонный протокол концессии, стратегия Цойтена приводит их к соглашению о сделке в ходе переговоров. В этот набор входят все бесконфликтные сделки, которые индивидуально рациональный и Оптимальный по Парето, и соглашение о конфликте, которое максимизирует Наш продукт.

Стратегия была представлена ​​в 1930 году датским экономистом. Фредерик Цойтен.^[2]

Три ключевых вопроса

Стратегия Zeuthen отвечает на три открытых вопроса, которые возникают при использовании монотонный протокол концессии, а именно:

1. Какую сделку предложить в первую очередь?
2. Кто должен уступить в любом раунде?
3. В случае уступки, какую сумму должен уступить агент?

Ответ на первый вопрос заключается в том, что любой агент должен начинать с наиболее предпочтительной сделки, потому что эта сделка имеет наибольшую пользу для этого агента.^[3] Второй ответ: агент с наименьшим значением Риск (i, t) уступает, потому что агент с наименьшей полезностью для конфликтной сделки больше всего выигрывает от избегания конфликта. На третий вопрос стратегия Цойтена предполагает, что уступающий агент должен уступить ровно настолько, чтобы повысить свою ценность Риск (i, t) чуть выше, чем у другого агента. Это предотвращает повторную уступку уступающего агента в следующем раунде.

Риск

${displaystyle { ext{Risk}}(i,t)={egin{cases}1&U_{i}(delta (i,t))=0{frac {U_{i}(delta (i,t))-U_{i}(delta (j,t))}{U_{i}(delta (i,t))}}&{ ext{otherwise}}end{cases}}}$

Риск (i, t) мера агента яготовность рискнуть конфликтом. Функция риска формализует представление о том, что готовность агента рискнуть конфликтом - это отношение полезности, которую агент потеряет, приняв предложение другого агента, к полезности, которую агент потеряет, вызвав конфликт. Агент я считается, что использует рациональную стратегию переговоров, если на любом этапе т + 1 этот агент я придерживается своего последнего предложения, Риск (i, t)> Риск (j, t).

Достаточная уступка

Если агент я делает достаточную уступку на следующем этапе, тогда, предполагая, что агент j использует рациональную стратегию переговоров, если агент j не уступает на следующем шаге, он должен сделать это на следующем шаге. Набор всех достаточных уступок агента я на шаге т обозначается SC (i, t).

Минимальная достаточная уступка

${displaystyle delta '=arg max _{delta in {SC(A,t)}}{U_{A}(delta )}}$

- минимальная достаточная уступка агента A на шаге т.

Агент А начинает переговоры с предложения

${displaystyle delta (A,0)=arg max _{delta in {NS}}U_{A}(delta )}$

и сделает минимально достаточную уступку в шаге т + 1 если и только если Риск (A, t) ≤ риск (B, t).

ТеоремаЕсли оба агента используют стратегии Цойтен, то они согласятся

${displaystyle delta =arg max _{delta 'in {NS}}{pi (delta ')},}$

то есть сделка, которая максимизирует продукт Нэша.^[4]

ДоказательствоПусть δ_А = δ (A, t). Пусть δ_B = δ (B, t). Согласно стратегии Цойтена, агент А уступит на шаге ${displaystyle t}$ если и только если

${displaystyle Risk(A,t)leq Risk(B,t).}$

То есть, если и только если

${displaystyle {frac {U_{A}(delta _{A})-U_{A}(delta _{B})}{U_{A}(delta _{A})}}leq {frac {U_{B}(delta _{B})-U_{B}(delta _{A})}{U_{B}(delta _{B})}}}$

${displaystyle U_{B}(delta _{B})(U_{A}(delta _{A})-U_{A}(delta _{B}))leq U_{A}(delta _{A})(U_{B}(delta _{B})-U_{B}(delta _{A}))}$

${displaystyle U_{A}(delta _{A})U_{B}(delta _{B})-U_{A}(delta _{B})U_{B}(delta _{B})leq U_{A}(delta _{A})U_{B}(delta _{B})-U_{A}(delta _{A})U_{B}(delta _{A})}$

${displaystyle -U_{A}(delta _{B})U_{B}(delta _{B})leq -U_{A}(delta _{A})U_{B}(delta _{A})}$

${displaystyle U_{A}(delta _{A})U_{B}(delta _{A})leq U_{A}(delta _{B})U_{B}(delta _{B})}$

${displaystyle pi (delta _{A})leq pi (delta _{B})}$

Таким образом, агент А уступит тогда и только тогда, когда ${displaystyle delta _{A}}$ не дает большего продукта коммунальных услуг.

Следовательно, стратегия Zeuthen гарантирует окончательное соглашение, которое максимизирует продукт Нэша.

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

1. Вулдридж, Майкл (2009). Введение в мультиагентные системы (2-е изд.). John Wiley & Sons Ltd., стр. 327–329. ISBN  9780470519462.
2. Фатима, Шахин; Краус, Сарит; Вулдридж, Майкл (2014). Принципы автоматизированных переговоров. Издательство Кембриджского университета. С. 14–15. ISBN  9781316060582.
3. Rosenschein, Jeffrey S .; Злоткин, Гилад (осень 1994). «Проектирование соглашений для автоматизированных переговоров». Журнал AI. AAAI. 15: 29–46. Дои:10.1609 / aimag.v15i3.1098.
4. Харшани, Джон К. (апрель 1956 г.). «Подходы к проблеме переговоров до и после теории игр: критическое обсуждение теорий Цойтена, Хикса и Нэша». Econometrica. 24 (2): 144–157. Дои:10.2307/1905748. JSTOR  1905748.