Математика \ Теория игр и исследование операций

Теория игр и исследование операций. Модели, алгоритмы, сложность: Конспект лекций, страница 15

пары

m-пара

Z

положение Z и L

Удаляемые точки

(1,3), (2,6), (4,5)

(2,6)

{1}

Z слева

2, 4

(1,3), (5,6)

(5,6)

{5,6}

Z справа

6, 3

(1,5)

(1,5)

{1,5}

справа и слева

Решение = LÇ conv(Z)

Как считать углы?  Переход в Â3 – теорема Хелли.

№11. 2.2. Принятие решений в условиях неопределенности.

Функция f зависит от неизвестного y, избавиться от которого можно так:

a)Принцип пессимиста . Пример – при строительстве моста.

b) Принцип оптимиста . Пример – снятие вратаря в хоккее.

c) Принцип прагматика:

–информированный прагматик Þ , My-математич. ожидание;

-неинформированный прагматик Þ  или .

Пример: Лыжные соревнования. Пусть Xi – виды лыжной мази, Yi –состояния погоды. Для информированного прагматика вероятности состояний погоды известны: р1=0,3,  р2=0,6,  р3=0,1. Для каждого типа критерия считаем F(x).

 

погода

Тип критерия
 

Y1

Y2

Y3

Пессимист

Оптимист

Информ.прагматик

Неинформ.прагматик

X1

0,6

0,8

0,4

0,4

0,8

3*0,6+6*0,8+1*0,4 =7

0,6+0,8+0,4=1,8

X2

0,5

0,3

0,85

0,3

0,85

3*0,5+6*0,3+1*0,85=4,15

0,5+0,3+0,85=1,65

X3

0,6

0,7

0,5

0,5

0,7

3*0,6+6*0,7+1*0,5=6,5

0,6+0,7+0,5=1,8

X4

0,2

0,4

0,95

0,2

0,95

3*02+6*0,4+1*0,95=3,95

0,2+0,4+0,95=1,55

Так как чаще встречаются Х1 и Х3, то лучше использовать одну из этих мазей.

2.3. ИГРЫ.

Пусть есть n игроков, X1,X2,…,Xn-множества их стратегий, f1(x),…, fn(x) - их функции выигрыша, x=(x1,…,xn)-совокупная стратегия игроков и xjÎXi ,.

Принципы рационального поведения в играх:

1.  Принцип Парето            xy, если  "i  fi (x) >fi (y) & $ i0: fi0 (x) > fi0 (y).

2.  Принцип пессимиста: он считает, что цель соперников-навредить ему Þ . Стратегия называется максиминной.

3.  Принцип равновесия (Нэша): совокупная стратегия x*=(x1*,…,xn*) оптимальна по Нэшу (равновесна), если всем игрокам невыгодно отступать от своих частей совокупной стратегии, т.е. "i  fi (x*) > fi (x1*,…,xi,…,xn*).

Пример Гермейера: n-игроков, множества стратегий Xi=[0,1], функции выигрыша: . Оптимальной по Нэшу и максимину является стратегия, при которой все выбирают 1 и выигрывают 1. Оптимальными по Парето являются стратегии, когда все выбирают 0 и выигрывают n-1, или когда i-й игрок выбирает 1,а остальные – 0; при этом i-й получает n, а остальные – n-2.

№12. Биматричная игра

Число игроков = 2, множества стратегий конечны. Функции выигрыша = две матрицы. Один игрок выбирает номер строки матриц, другой - номер столбца.

Пример: Пусть. fxij=fx(xi,yj) – выигрыш игрока х, если он играет по xi ,а y по yj .

fx

y1

y2

miny

fy

y1

y2

maxy

x1

5

1

1

x1

3

3

x2

2

6

2

x2

4

5

x3

1

4

1

x3

8

2

maxx

=2

minx

3

2

=3

1)  максиминные стратегии существуют всегда: 

Скачать файл