Лекція 2 Теорія ігор (продовження)
жүктеу/скачать 453.14 Kb.
|
|
Лекція 2 Теорія ігор (продовження) Отже, на 1-й лекції ми ознайомились із основами теорії ігор. Нехай матрична гра представлена платіжною матрицею з елементами a ij , де i = 1,2, ... , m - стратегії першого гравця, j = 1,2, ..., n - стратегії другого гравця. Дані стратегії гравців, які застосовуються з ймовірностями 1, ми домовилися називати чистими стратегіями . На попередній лекції ми показали, що рішення матричної гри в чистих стратегіях (тобто при виборі кожним гравцем однієї і лише однієї стратегії із заданої множини його стратегій) існує тоді і тільки тоді, коли платіжна матриця має сідлову точку. Розглянемо вибір стратегій у грі без сідлової точки. Якщо гравець може передбачити, яку з чистих стратегій вибере супротивник, він може знайти найкращу у відповідь хід противника. Таким чином, кожен гравець зацікавлений у тому, щоб його ходи були непередбачувані. Для цього необхідно запровадити у вибір стратегій елемент випадковості. Однак, відсутність логіки при виборі стратегій погіршить становище кожного з гравців. Компроміс полягає в тому, що гравці чергують (змішують) свої стратегії випадково, але за певною розумною схемою. Цій схемі має відповідати комбінація чистих стратегій. Введемо такі зміни правил гри: кожен гравець поряд з окремими стратегіями зі своєї множини стратегій може застосовувати їх комбінації, в яких стратегії представлені в певних пропорціях. Розглянемо матричну гру, представлену таблицею.
де - частота (імовірність) з якою перший гравець збирається використовувати свою стратегію 1; - частота (імовірність) з якою перший гравець збирається використовувати свою стратегію 2; - частота (імовірність) з якою перший гравець збирається використовувати свою стратегію m . Вектор називають змішаною стратегією першого гравця. З визначення ймовірності: . Аналогічно другий гравець чергує (змішує) свої стратегії так, щоб: Стратегія 1 мала частоту (імовірність) ; Стратегія 2 мала частоту (імовірність) ; Стратегія n має частоту (імовірність) . Вектор називається змішаною стратегією другого гравця. Очевидно, що . Можливість застосовувати поряд зі стратегіями та , які ми називатимемо чистими стратегіями 1-го та 2-го гравців відповідно, змішаних стратегій x та y, змінює умови гри, розширює їх. Тому перехід від чистих стратегій до змішаних стратегій називають змішаним. розширенням гри . Множина змішаних стратегій 1-го і 2-го гравців є відповідно: – множина m - мірних векторів, координати яких задовольняють умовам: ; – множина n - мірних векторів, координати яких задовольняють умовам: . Очевидно, що чисті стратегії гравців входять як елементи до множини їх змішаних стратегій. Для гравця, у якого три чисті стратегії, змішані стратегії записуються векторами з трьох елементів, наприклад : (0,2; 0,3; 0,5), (0,1; 0,8; 0,1), (0, 3; 0,3; 0,4). Взагалі, способів розподілу одиничної вірогідності за декількома стратегіями може бути безліч. Усі безліч змішаних стратегій можна зобразити графічно. Залежно кількості чистих стратегій безліч змішаних стратегій виглядає, як у рис. 1. Рис. 1. Вид множини змішаних стратегій Якщо лише одна чиста стратегія, то може бути лише одна змішана стратегія, яка збігається з чистою (рис. 1.2, а). Якщо чистих стратегій дві, то множина змішаних стратегій є відрізком (рис. 1.2, б). Якщо три чисті стратегії, то множина змішаних стратегій є площею трикутника (рис. 1.2, в). Якщо в нас чотири чисті стратегії, то зобразити чотиривимірний простір важко, але множина змішаних стратегій буде обсягом піраміди (рис. 1.2, г). Якщо в загальному випадку маємо n чистих стратегій, то матимемо справу з n-мірним простором, але множина змішаних стратегій буде оболонкою, натягнутою на n вершин, що знаходяться в одиницях на кожній осі, що також іноді називають (n-1) - мірним симплексом. "Фізичний сенс" поняття змішаних стратегій наступний. Нехай у кожного гравця є генератор випадкових чисел, що визначає йому, яку зі стратегій йому слід грати. Так, за наявності двох стратегій людина може підкидати монетку: ймовірність того, що вона зіграє кожну стратегію, дорівнює 50%. Якщо стратегій, наприклад, рівно шість, то гравцеві зручно вдатися до кидання кісток і так далі. Іншим гравцям відома можливість випадання тієї чи іншої стратегії, проте спостерігати конкретну реалізацію на момент прийняття рішення вони не можуть. Нехай перший гравець вибрав деяку змішану стратегію x , а другий – y . Тоді кожен елемент платіжної матриці стає випадковою подією. Знайдемо ймовірність цієї події. Для того, щоб здійснився результат , перший гравець вибирає стратегію i з ймовірністю , а другий гравець вибирає стратегію j з ймовірністю . Через незалежність вибору ймовірність результату дорівнює ймовірності спільних наступів двох незалежних подій, тобто. твору їх ймовірностей . Для кожної пари змішаних стратегій можна знайти середнє значення виграшу , яке ми позначимо . Це середнє значення дорівнює математичному очікуванню платежу. Оскільки платіж здійснюється з ймовірністю , то математичне очікування визначається за формулою. У випадку, коли матрична гра має сідлову точку, оптимальна змішана стратегія першого гравця матиме вигляд . І оптимальна змішана стратегія 2-го гравця матиме вигляд . Таким чином, рівноваги в чистих стратегіях є окремим випадком рівноваги в змішаних стратегіях. Стратегія i першого гравця називається його активною стратегією , якщо в оптимальній стратегії ймовірність . Аналогічно стратегія j гравця 2 називається його активною стратегією , якщо в оптимальній стратегії ймовірність . Матричну гру можна вирішити: – у чистих стратегіях, якщо в ній є одна або кілька сідлових точок; – у домінуючих стратегіях, якщо гру можна редукувати до однієї точки; приведенням гри до завдання лінійного програмування і далі вирішити: – графічно (у якому разі?). - симплекс-методом; - методом Лагранжа; - ітераційним методом Брауна-Робінсон. жүктеу/скачать 453.14 Kb. Достарыңызбен бөлісу:
|