Державна освітня установа вищої професійної освіти
«Тюменського державного нафтогазового університету»
ІНСТИТУТ КІБЕРНЕТИКИ, ІНФОРМАТИКИ І ЗВ'ЯЗКУ
ВІДДІЛЕННЯ ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ ТА ОБЧИСЛЮВАЛЬНОЇ ТЕХНІКИ
Завдання на курсовий проект
Тема курсового проекту: Кооперативні гри
Перелік питань підлягають дослідженню і розробці:
1 Арбітражні схеми.
2 Класичні кооперативні ігри
3 Кооперативні гри з нескінченним числом гравців
Керівник курсового проекту _____________________________
Зав. відділенням ІТВТ _____________________________
Завдання прийняв до виконання _____________________________
АРБІТРАЖНА СХЕМА - правило, за яким кожній грі з діленнями ставиться у відповідність єдиний поділ цієї гри, називається арбітражним рішенням. Спочатку А. с. були розглянуті Дж. Нешем для випадку гри двох осіб. нехай
u = 1. un)> - безліч поділів, d = (d1. dn) - точка status quo, тобто. е. точка, відповідна нагоди, коли ніякої поділ не здійснюється, [R, d] - гра з діленнями, u - її арбітражне рішення. Поділ u * зв. рішенням Неша, якщо
Рішення Неша і тільки воно задовольняє наступним аксіомам:
1) якщо f - лінійне неубутних перетворення, то fu¯ є арбітражне рішення гри [fR, fd] (інваріантність щодо перетворень корисності); 2) u¯ ≥ d, u¯ ∈ R і немає такого u ∈ R, щоб u ≥ u¯ (Оптимальність по Парето); 3) якщо R '⊂ R, d' = d, u¯ ∈ R ', то u¯ '= U¯ (Незалежність непов'язаних альтернатив); 4) якщо di = dj. i, j = 1. n і R симетрична, то u¯i = u¯j. i, j = 1. n (симетрія).
Іншу А. с. з типовий. функцією v (S), S ⊂ N = (1. n) для ігор n осіб дав Л. С. Шеплі [2]. рішення Шеплі # 966; (V) = (# 966; 1 (v). # 966; n (v)), де
# 947; n (s) = (s - 1)! (N - s)! / N. s - число елементів множини S, також задовольняє аксіомі симетрії, крім того, Σi # 966; i (v) = v (N) і для будь-яких двох ігор u і v виконується # 966; (U + v) = # 966; (U) + # 966; (V). Були також розглянуті А. с. для випадку порівнянних індивідуальних виграшів (див. [3]).
Арбітражні схеми Дж. Неша і Л. С. Шеплі узагальнив Дж. Харшані [4]. Рішення Харшані, крім відповідних чотирьох аксіом Неша, задовольняє ще двом аксіомам: 1) рішення монотонно залежить від обґрунтованих вимог гравця, 2) якщо u * і u ** - рішення, то рішенням буде і u¯,
якщо тільки u¯ належить кордоні безлічі R.
А. с. безперервно залежать від параметрів гри, якщо в R є кращі поділи, ніж точка status quo.
Отже, математик зробив свою справу і йде в бік, а гравці торгуються. Чим закінчиться торг - невідомо. Добре, якщо вони люди згідливі і поступливі. На жаль, зустрічаються люди (і не тільки люди, а цілі держави), які, бажаючи отримає собі щонайбільше, торгуються дуже наполегливо, пускаючи в хід все, навіть погрози. В результаті переговори закінчуються нічим, загрози приводяться у виконання ... Чим це закінчується можна дуже часто спостерігати в житті.
Одним з виходів з цієї ситуації є запрошення з боку деякого арбітра, який би однаково ставився до обох сторін, і запропонувати йому вказати спільну стратегію "по справедливості". Якщо арбітр дійсно "справедливий" і "неупереджений", він може винести яке влаштовує обох гравців рішення. Але що означає "справедливий" і "неупереджений"?
Досить очевидно, що до такого арбітра повинні бути пред'явлені такі вимоги.
1. Арбітражне рішення повинно бути елементом переговорного безлічі.
2. Арбітражна схема повинна бути незалежною від імен або позначень гравців.
3. Якщо дві гри близькі між собою в якомусь сенсі, то і арбітражні рішення повинні бути близькі.
4. Арбітражне рішення повинно відображати дієвість загроз гравців.
У теорії ігор для вирішення подібних завдань часто використовують аксіоматичний метод, коли подібні вимоги намагаються формалізувати у вигляді математичних аксіом. Нижче ми викладемо систему таких аксіом, що належить Дж. Неша. Надалі вважається, що гравець № 1 має ходів, гравець номер 2 - ходів, платіжна матриця має вигляд,,. Через ми будемо позначати опуклу оболонку точок, - переговорний безліч, - точка status quo, - рішення арбітра.
Аксіома 1. (Оптимальність за Парето). Точка повинна бути елементом переговорного безлічі, тобто