Лекция 2 (545614)
Текст из файла
ПолезностьИ.В.Кацев (СПб ЭМИ)Полезность и антагонистические игры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 , ..., amna11 , a21 ,где aij = K1 (i, j).Поэтому конечные антагонистические игры называются матричными.И.В.Кацев (СПб ЭМИ)Полезность и антагонистические игры20126 / 13Пример120 −3 2 −1 −1 −1A=−2 001410 −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 −1A=−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 ...где aiia11000 ,... ann> 0, i = 1, . .
. , n.И.В.Кацев (СПб ЭМИ)Полезность и антагонистические игры201213 / 13Диагональные игрыДиагональные матричные игры:... 0 a22 . . .A= ... ... ...0 0 ...где aii.a11000 ,... ann> 0, i = 1, . . . , n.Утверждение..Любая диагональная игра является вполне смешанной.И.В.Кацев (СПб ЭМИ)Полезность и антагонистические игры201213 / 13.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.