Лекция 2 (Лекции (4))

ПолезностьИ.В.Кацев (СПб ЭМИ)Полезность и антагонистические игры20121 / 13ПолезностьПолезность - мера удовлетворенности агента.И.В.Кацев (СПб ЭМИ)Полезность и антагонистические игры20121 / 13ПолезностьПолезность - мера удовлетворенности агента.Предположение - для каждого агента существует функция полезности и онстремится максимизировать ее мат. ожидание.И.В.Кацев (СПб ЭМИ)Полезность и антагонистические игры20121 / 13Отношение предпочтенияЕсть множество альтернатив X, замкнутое относительно следующей операции:x, y ∈ X ⇒ αx + (1 − α)y ∈ X.У агента есть отношение предпочтения ” > ” на множестве X.

Аксиомы:И.В.Кацев (СПб ЭМИ)Полезность и антагонистические игры20122 / 13Отношение предпочтенияЕсть множество альтернатив X, замкнутое относительно следующей операции:x, y ∈ X ⇒ αx + (1 − α)y ∈ X.У агента есть отношение предпочтения ” > ” на множестве X. Аксиомы:.Аксиома (Полнота).Длялюбых альтернатив x, y верно одно из трех: x.И.В.Кацев (СПб ЭМИ)Полезность и антагонистические игры> y, x < y, x = y.20122 / 13Отношение предпочтенияЕсть множество альтернатив X, замкнутое относительно следующей операции:x, y ∈ X ⇒ αx + (1 − α)y ∈ X.У агента есть отношение предпочтения ” > ” на множестве X. Аксиомы:.Аксиома (Полнота).Длялюбых альтернатив x, y верно одно из трех: x.> y, x < y, x = y..Аксиома (Транзитивность).Еслиx.> y, y > z, то x > z.И.В.Кацев (СПб ЭМИ)Полезность и антагонистические игры20122 / 13Отношение предпочтенияЕсть множество альтернатив X, замкнутое относительно следующей операции:x, y ∈ X ⇒ αx + (1 − α)y ∈ X.У агента есть отношение предпочтения ” > ” на множестве X.

Аксиомы:.Аксиома (Полнота).Длялюбых альтернатив x, y верно одно из трех: x.> y, x < y, x = y..Аксиома (Транзитивность).Еслиx.> y, y > z, то x > z..Аксиома (Непрерывность).Если x> y > z, то существует такое число α ∈ (0, 1), чтоαx + (1 − α)z > y..И.В.Кацев (СПб ЭМИ)Полезность и антагонистические игры20122 / 13Отношение предпочтенияЕсть множество альтернатив X, замкнутое относительно следующей операции:x, y ∈ X ⇒ αx + (1 − α)y ∈ X.У агента есть отношение предпочтения ” > ” на множестве X. Аксиомы:.Аксиома (Полнота).Длялюбых альтернатив x, y верно одно из трех: x.> y, x < y, x = y..Аксиома (Транзитивность).Еслиx.> y, y > z, то x > z..Аксиома (Непрерывность).Если x> y > z, то существует такое число α ∈ (0, 1), чтоαx + (1 − α)z > y...Аксиома (Независимость от несущественных альтернатив).Еслиx.> y, то для любого z верно αx + (1 − α)z > αy + (1 − α)z.И.В.Кацев (СПб ЭМИ)Полезность и антагонистические игры20122 / 13Теорема об ожидаемой полезности.Теорема.Если отношение предпочтения удовлетворяет аксиомам (1)-(4), тосуществует такая функция U : X → R, что для любых x, yx.И.В.Кацев (СПб ЭМИ)> y ⇔ EU(x) > EU(y).Полезность и антагонистические игры20123 / 13План доказательства1.

Для u < v строим отображение ”интервала” между ними на (0, 1) идоказываем, что оно - биекцияИ.В.Кацев (СПб ЭМИ)Полезность и антагонистические игры20124 / 13План доказательства1. Для u < v строим отображение ”интервала” между ними на (0, 1) идоказываем, что оно - биекция2. Доказываем единственность такого отображения с фиксированнымиграницами и аддитивностью с одного края (тут уже границы уже не обязательно 0и 1)И.В.Кацев (СПб ЭМИ)Полезность и антагонистические игры20124 / 13План доказательства1.

Для u < v строим отображение ”интервала” между ними на (0, 1) идоказываем, что оно - биекция2. Доказываем единственность такого отображения с фиксированнымиграницами и аддитивностью с одного края (тут уже границы уже не обязательно 0и 1)3. При наложении функции совпадаютИ.В.Кацев (СПб ЭМИ)Полезность и антагонистические игры20124 / 13План доказательства1. Для u < v строим отображение ”интервала” между ними на (0, 1) идоказываем, что оно - биекция2. Доказываем единственность такого отображения с фиксированнымиграницами и аддитивностью с одного края (тут уже границы уже не обязательно 0и 1)3.

При наложении функции совпадают4. Определяем функцию в данной точке как значения всех таких функций,которые в данных двух точках принимают значения 0 и 1. Показываем, что этоодно и то же числоИ.В.Кацев (СПб ЭМИ)Полезность и антагонистические игры20124 / 13План доказательства1.

Для u < v строим отображение ”интервала” между ними на (0, 1) идоказываем, что оно - биекция2. Доказываем единственность такого отображения с фиксированнымиграницами и аддитивностью с одного края (тут уже границы уже не обязательно 0и 1)3. При наложении функции совпадают4. Определяем функцию в данной точке как значения всех таких функций,которые в данных двух точках принимают значения 0 и 1.

Показываем, что этоодно и то же число5. Доказываем, что построенная функция нам подходитИ.В.Кацев (СПб ЭМИ)Полезность и антагонистические игры20124 / 13Антагонистические игрыБескоалиционная игра (в нормальной форме)Γ = {N, {Xi }i∈N , {Ki }i∈N }.Здесь N - конечное множество игроков,Xi , i ∈ N− множество стратегий игрока i ∈ N,∏Ki : i∈N Xi → R− функция выигрыша игрока iИ.В.Кацев (СПб ЭМИ)∈ N,Полезность и антагонистические игры20125 / 13Антагонистические игрыБескоалиционная игра (в нормальной форме)Γ = {N, {Xi }i∈N , {Ki }i∈N }.Здесь N - конечное множество игроков,Xi , i ∈ N− множество стратегий игрока i ∈ N,∏Ki : i∈N Xi → R− функция выигрыша игрока i∈ N,Конечная антагонистическая игра: |N| = 2, N = {1, 2}, X1 , X2 конечны,K1 (x1 , x2 ) + K2 (x1 , x2 ) = 0(const) для всех x1 ∈ X1 , x2 ∈ X2 .И.В.Кацев (СПб ЭМИ)Полезность и антагонистические игры20125 / 13Антагонистические игрыКаждая конечная антагонистическая игра с X1полностью задается m × n матрицей= {1, ..., m}, X2 = {1, ..., n}..., a1n..., a2n ,A=...

... ... am1 , ..., amna11 , a21 ,где aij = K1 (i, j).Поэтому конечные антагонистические игры называются матричными.И.В.Кацев (СПб ЭМИ)Полезность и антагонистические игры20126 / 13Пример120 −3 2 −1 −1 −1A=−2 001410 −2И.В.Кацев (СПб ЭМИ)Полезность и антагонистические игры20127 / 13Седловые точки.Упражнение.Покажите, что для произвольных i, jmax min aiji.И.В.Кацев (СПб ЭМИ)j≤ min max aijjiПолезность и антагонистические игры20128 / 13Седловые точки.Упражнение.Покажите, что для произвольных i, jmax min aiji.j≤ min max aijjiСедловой точкой называется пара (i∗ , j∗ ), для которой выполняется равенство (вточках i∗ ,j∗ достигаются внешние экстремумы)max min aijiИ.В.Кацев (СПб ЭМИ)j= min max aijjiПолезность и антагонистические игры20128 / 13Смешанные стратегииСмешанной стратегией игрока называется вероятностное распределение намножестве его первоначальных, чистых стратегий.

В матричной игре смешаннойстратегией игрока 1 является векторx= (x1 , . . . , xm ), xi ≥ 0,m∑xi= 1,yj= 1.i=1а смешанной стратегией игрока 2 – векторy= (y1 , . . . , yn ), yj ≥ 0,n∑j=1Если игрок 1 применяет смешанную стратегию x, а игрок 2 – смешаннуюстратегию y, то ожидаемый выигрыш игрока 1 равенA(x, y)= xAyT =m ∑n∑aij xi yj .i=1 j=1И.В.Кацев (СПб ЭМИ)Полезность и антагонистические игры20129 / 13Теорема о минимаксе.Теорема (Теорема о минимаксе, фон Нейман (1928)).max min xAyTx.И.В.Кацев (СПб ЭМИ)y= min max xAyTyxПолезность и антагонистические игры201210 / 13Пример1 −2 0 −3 2 −1 1 −1A=−2 0 0 1 41 0 −2И.В.Кацев (СПб ЭМИ)Полезность и антагонистические игры201211 / 13Вполне смешанные игрыОптимальные стратегии (x∗ , y∗ ) называются вполне смешанными, еслиx∗i > 0, y∗j > 0 для всех i, j.

Игра, у которой любые оптимальные стратегииигроков вполне смешанные, называется вполне смешанной..Утверждение.Если матричная игра вполне смешанная, то mстратегииигроков x∗ , y∗ единственные..И.В.Кацев (СПб ЭМИ)= n, а оптимальныеПолезность и антагонистические игры201212 / 13Диагональные игрыДиагональные матричные игры:... 0 a22 . . .A= ... ... ...0 0 ...где aiia11000 ,... ann> 0, i = 1, . .

. , n.И.В.Кацев (СПб ЭМИ)Полезность и антагонистические игры201213 / 13Диагональные игрыДиагональные матричные игры:... 0 a22 . . .A= ... ... ...0 0 ...где aii.a11000 ,... ann> 0, i = 1, . . . , n.Утверждение..Любая диагональная игра является вполне смешанной.И.В.Кацев (СПб ЭМИ)Полезность и антагонистические игры201213 / 13.