Поиск кратчайшего пути. Элементы теории матричных игр. Игры в нормальной форме: определение, равновесие по Нэшу, доминирование стратегий

↑

⇐ ПредыдущаяСтр 8 из 28Следующая ⇒

Поиск кратчайшего пути

Пусть дан направленный граф (V, A), где V — множество вершин и A — множество ребер, с начальной вершиной обхода s, конечной t и весами w_ij для каждого ребра (i, j) в A. Вес каждого ребра соответствует переменной программы x_ij.

Тогда задача ставится следующим образом: найти минимум функции

при условии что для всех i и j выполняется следующее неравенство:

9. Элементы теории матричных игр

Игра состоит из последовательности действий (ходов). Ходы делятся на осмысленные и случайные.

Стратегия игрока – это набор правил при выборе хода. Цель игры нахождение оптимальной стратегии для каждого игрока т.е. такой стратегии при которой мат. ожидание максимально.

Матричная игра это парная игра, которая задаётся набором чистых стратегий n- стратегий первого игрока, m – стратегий второго игрока, а так же платёжной матрицей (a_ij), определяющая выигрыш 1-го игрока при выборе игроками стратегий i и j. Соответственно цель первого игрока максимизировать выигрыш, цель второго минимизация проигрыша.

Седловой точкой матрицы A называется такая пара (i₀,j₀), что " i=1,n, j=1,m выполняется неравенство a_ij0<=a_i0j0<=a_i0j. Элемент a_i0j0 в матрице А явл. одновременно максимумом из строк и минимумом из столбцов.

Цена игры – это выигрыш 1-го игрока и проигрыш 2-го игрока.

10. Игры в нормальной форме: определение, равновесие по Нэшу, доминирование стратегий

Постановка задачи. Пусть в некоторой операции участвуют n сторон. Пусть  – ход -го игрока, .  – множество ходов -го игрока, . Пусть каждый выбрал некоторый ход  – исход игры,   – мн-во всевозможных исходов игры. Число  – выигрыш (проигрыш) -го игрока.

 – мн-во выигрышей всех игроков.  – мн-во всевозм. исходов наз. игрой в нормальной форме. Каждый из игроков стремиться выбирать такую стратегию поведения, чтобы суммарный его выигрыш был наибольшим. Но сложность в том, что его выигрыш зависит не только от его хода, но и от хода других игроков.

Доминируемость. Пусть . Ходы 1 из игроков – , 2 игрока – ,  и Х– мн-во ходов.

 –отдельный исход. – выигрыш 1 игрока – выигрыш 2 игрока.

Опр. Говорят, что ход  доминирует ход , если , для любого  и существует хотя бы один ход второго игрока, что: .

Опр. Некоторый ход  является доминирующим для 1 игрока, если , , .

Обозначим через  – множество доминирующих ходов 1 игрока, через  –2 игрока.

Опр. Пусть сущ.  и , тогда пара  наз. точкой равновесия в доминирующих стратегиях.

Познавательные статьи:



Техника прыжка в длину с разбега

Тактические действия в защите

История Олимпийских игр

История развития права интеллектуальной собственности