Стратегия Зойтена

Стратегия Зойтена используется в переговорах в рамках протокола монотонных уступок, при котором участники по очереди делают предложения, и каждое последующее предложение должно быть выгоднее предыдущего. Если агент получает предложение, которое приносит ему бóльшую выгоду, чем его собственное, переговоры считаются успешными. В противном случае, если ни один из агентов не сделает нового предложения, переговоры завершаются неудачей^[3].

Стратегия предполагает, что агенты знают свои собственные функции полезности.

В ходе анализа стратегии обычно рассматриваются три вопроса^[2]:

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

Ответ на первый вопрос прост: первым предложением должно быть наиболее предпочтительное для агента решение с точки зрения его полезности. Агент i выбирает такое предложение ${\displaystyle \delta }$, которое максимизирует его функцию полезности U:

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

Второй вопрос раскрывается в стратегии Зойтена через оценку «готовности агента рисковать конфликтом». Интуитивно, агент будет более готов рисковать конфликтом, если разница между полезностью его текущего предложения и конфликтным решением мала. Если же эта разница велика — агент ожидает большие потери и склонен уступить^[2].

Готовность агента i рисковать конфликтом в раунде t вычисляется как

${\displaystyle {\text{Риск}}(i,t)={\frac {\mbox{потеря полезности агента (i) при уступке и принятии предложения агента (j)}}{\mbox{потеря полезности агента (i) при отказе уступить, ведущем к конфликту}}}}$

Числитель определён как разность полезности текущего предложения агента i и предложения агента j, знаменатель — как полезность текущего предложения i. До достижения соглашения значение риска изменяется от 0 до 1. Чем выше риск (ближе к 1), тем меньше потери от конфликта, агент менее склонен уступать. Чем ниже риск (ближе к 0), тем выше потери, агент меньше хочет рисковать^[2].

Формула:

${\displaystyle {\text{Риск}}(i,t)={\begin{cases}1&U_{i}(\delta (i,t))=0\\{\frac {U_{i}(\delta (i,t))-U_{i}(\delta (j,t))}{U_{i}(\delta (i,t))}}&{\text{иначе}}\end{cases}}}$

Присвоение риска равным 1, если полезность хода агента i равна нулю, означает, что выгода агента от собственного и конфликтного решений совпадают, и он полностью готов пойти на конфликт.

В ходе переговоров склонность к риску уменьшается. Тот, чей риск меньше, должен уступить так, чтобы баланс риска сместился на второго агента.

Стратегия утверждает: в раунде t должен уступить тот агент, чья оценка риска ниже^[2]. Остаётся вопрос — насколько должен уступить агент.

Если оба используют стратегию Зойтена, будет достигнуто равновесие Нэша, причём в следующей точке:^[1]

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

Если агент уступает недостаточно, в следующем раунде соотношение риска по-прежнему будет показывать высокую потенциальную потерю от конфликта. Поэтому необходим минимальная уступка, при которой меняется баланс риска, после чего другой агент вынужден уступить^[2].

Если агент A делает достаточный уступок, а агент B действует рационально, тот также уступит либо в этом, либо в следующем ходе. Множество всех достаточных уступков агента A на шаге t обозначается как ${\displaystyle {\text{SC}}(A,t)}$^[1]. Минимальным уступком будет тот, который принадлежит этому множеству и приносит максимальную полезность.

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

Пусть δ_A = δ(A,t), δ_B = δ(B,t).

Согласно стратегии Зойтена, агент A уступает на шаге t при условии^[1]:

${\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})}$

Агент A уступит (или согласится на предложение), если его собственное предложение (${\displaystyle \delta _{A}}$) не принесёт большего выигрыша, чем предложение B.

Таким образом, стратегия гарантирует достижение соглашения и максимизацию продукта Нэша.

Стратегия Зойтена, реализованная в протоколе монотонных уступок, может быть описана следующим псевдокодом^[4] (ход переговоров описан со стороны агента A):

1. ${\displaystyle \delta _{A}\gets \arg \max _{\delta }U_{A}(\delta )}$
2. ${\displaystyle {\mbox{Сделать предложение}}~\delta _{A}}$
3. ${\displaystyle {\mbox{Получить предложение}}~\delta _{B}}$
4. ${\displaystyle {\mbox{если}}~U_{A}(\delta _{B})\geq U_{A}(\delta _{A})}$

   ${\displaystyle {\mbox{тогда}}~{\mbox{Принять}}~\delta _{B}}$

5. ${\displaystyle {\mbox{Риск}}_{A}\gets {\frac {U_{A}(\delta _{A})-U_{A}(\delta _{B})}{U_{A}(\delta _{A})}}}$
6. ${\displaystyle {\mbox{Риск}}_{B}\gets {\frac {U_{B}(\delta _{B})-U_{B}(\delta _{A})}{U_{B}(\delta _{B})}}}$
7. ${\displaystyle {\mbox{если}}~{\mbox{Риск}}_{A}<{\mbox{Риск}}_{B}}$

   ${\displaystyle {\mbox{тогда}}~\delta _{A}\gets \delta _{A}'{\mbox{такое, что}}~{\mbox{Риск}}_{A}(\delta _{A}')>{\mbox{Риск}}_{B}(\delta _{B}')}$

   ${\displaystyle {\mbox{перейти к}}~2}$

8. ${\displaystyle {\mbox{перейти к}}~3}$

На иллюстрации показан графический ход переговоров между агентами i и j^[4]. По оси x — полезность U, по оси y — множество предложений ${\displaystyle \delta }$. Начальные предложения (шаг 0): ${\displaystyle \delta (i,0)=0}$ для i, ${\displaystyle \delta (j,0)=6}$ для j.

Видно, что агент j имеет меньший риск и должен сделать уступку. Новое предложение выбирается так, чтобы в следующем раунде j не пришлось снова уступать

То есть ${\displaystyle \delta _{j}<5}$.

Соответственно, агент j выбирает ${\displaystyle \delta (j,1)=4{,}9}$.

Предположим, что в последнем раунде у обоих агентов одинаковые значения риска^[2]:

В этом случае по алгоритму оба должны уступить, однако возникает потенциальная проблема: если один из агентов нарушит стратегию, не уступив, он получит большую выгоду за счёт другого. Если оба будут упрямы, возникнет конфликт — типичная игра в цыплят, анализируемая теорией игр. Предложения делаются одновременно, договорённости невозможны; выгоду приносит противодействие уступке, но если оба не уступают — конфликт невыгоден всем. Это некооперативная и антикоординационная ситуация.

Например, при следующих полезностях:

На практике решением может быть добавление элементарной рандомизации — «подбрасывание монеты» или иной механизм, который случайным образом распределяет, кто уступает; только при этом стратегия становится устойчивой и удовлетворяет требованию равновесия Нэша^[2].

Второй существенный недостаток — сложность применения для большого числа задач: множество решений растёт экспоненциально, что сильно ограничивает возможность применения стратегии Зойтена в реальных задачах^[2].

Вычислительная сложность = ${\displaystyle O(2^{|T|})}$