Теория игр : моделирование и решение конфликтных ситуаций Ольга Дмитриевна Кичмаренко канд. физ.- мат. наук, доцент заведующая кафедрой Оптимального управления и экономической кибернетики Одесского национального университета имени И. И. Мечникова

Теория игр. Введение – Что наша жизнь? – Игра! " Пиковая дама », М. И. Чайковский Как победить конкурента? Как преуспеть в политике? Как выиграть в азартную игру? Как выиграть в войне? Как справедливо поделить деньги? 2 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций

Теория игр. Введение Теория игр – раздел прикладной математики, относящийся к системам и методам принятия решений, который предоставляет средства моделирования, анализа и решения конфликтных ситуаций 3 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций

Теория игр. Введение Конфликтная ситуация: заинтересованные стороны интересы (цели) сторон возможные действия каждой из сторон Конфликт интересов порождает столкновение людей. 4 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций

Теория игр. Примеры « Два начальника » У двух начальников один подчиненный. Каждый из начальников, давая подчиненному задание, может разрешить выполнять свое задание совместно с заданием другого начальника или потребовать выполнения своего задания в первую очередь. Если задания выполняются совместно, то каждый из начальников получает по 10 единиц выигрыша. Если только один шеф потребовал первоочередного выполнения своего задания, он получает 15 единиц выигрыша, времени на выполнение задания второго начальника у подчиненного не остается и второй начальник несет убытки в размере 5 единиц. Если оба шефа потребовали выполнения своего задания в первую очередь, подчиненный отказывается работать вообще, и начальники получают нулевые выигрыши. 5 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций

Теория игр. Примеры « Фермеры на общем поле » Два фермера намерены выпасать коров на общем поле. Количество молока x, которое приносит корова, зависит от общего числа коров на поле : x = 120 – n ( литров ), где n = n1 + n2 – общее количество коров на поле. Доход фермера определяется количеством молока, приносимым его коровами : П 1 = n1 (120 – n1 – n2), П 2 = n2 (120 – n1 –n2). Сколько коров выпустят на поле фермеры ? 6 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций

Теория игр. Примеры « Аукцион » На аукционе на продажу выставлен предмет. Есть один продавец и один покупатель. Цена предмета для продавца ( минимальная цена, по которой продавец готов продать предмет ) rs, цена для покупателя ( максимальная цена, по которой покупатель готов купить предмет ) – rb. Оба игрока знают свою цену, но не знают цену противника. Они делают заявки ps и pb. Если заявка покупателя выше заявки продавца, то предмет продается по средней стоимости p = (ps + pb) / 2. Если заявка продавца выше заявки покупателя, то сделка не состоится. Какую цену должен выставить каждый из участников аукциона ? 7 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций

« Распределения затрат между членами кооператива » N перевозчиков намерены построить хранилища для жидкого топлива. Потребности потребителя i в топливе в моменты времени t 1, t 2,…, tm заданны функцией. Принимать топливо в хранилища можно в промежутках между потреблением. Тогда объем хранилищ, удовлетворяющий всех потребителей, равен. Расходы на строительство – некоторая функция F от объема хранилища. Каждый потребитель топлива может объединиться с любым другим для построения общего хранилища. Если образуется коалиция К, то объем хранилища составит, а затраты на его строительство составят.. Нужно определить количество хранилищ и коалиции, которые их будут строить, а также распределить затраты на сооружение хранилищ между членами коалиции. 8 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций Теория игр. Примеры

Васин А. А., Морозов В. В. Теорія игр и модели математической экономики. – М., 2005 г. – 272 с. ВоробьевН. Н. Теория игр : Лекции для экономистов - кибернетиков. – Л.: ЛГУ, – 272 с. Дюбин Г. Н., Суздаль В. Г. Введение в прикладную теорию игр - М.: Наука, с. Карлин С. Математические методы в теории игр, программировании и экономике М.: Мир, – 838 с. Крушевский А. В. Терия игр. – К.: Вища школа, – 216 с. Розенмюллер И. Кооперативные игры и рынки. - М.: Мир, 1974 Оуен Г. Теорія игр. – М., – 216 с. Мулен Э. Теория игр с примерами из математической экономики. – М., Мир, – 200 с. Gibbons R. Game theory for applied economists. – Princeton university press, – 267 p. 9 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций Теория игр. Литература

Теория игр. Предыстория VI-V в. до н. э. – Сунь Цзы « Искусство войны » Если набор возможных действий известен обоим противникам, то можно просчитать, кому достанется победа, а собственно саму войну не затевать. Наилучшая победа – бескровная, когда противник предпочитает добровольно сдаться Непобедимость заключена в себе самом, возможность победы заключена в противнике Все люди знают ту форму, посредством которой я победил, но не знают той формы, посредством которой я организовал победу. Поэтому победа в бою не повторяется в том же виде, она соответствует неисчерпаемости самой формы. 10 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций

Теория игр. Предыстория II в. до н. э.-VI в. н. э. - Талмуд : Что делать, если умерший человек остался должен больше, чем у него было ? По брачному контракту одной его жене в случае его смерти должно достаться 100 шекелей, другой – 200, а третьей – 300. Если все его наследство составит 100 шекелей, то его нужно разделить поровну между всеми тремя женами. Если наследство составило 200 шекелей, то первой – 50, двум другим – по 75. Если же осталось 300 шекелей, то первой – 50, второй 100, а третьей – 150. Как поступать с другими суммами ? 11 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций

Теория игр. Предыстория Библия. Задача царя Соломона о двух женщинах. 12 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций

Теория игр. Предыстория Библия. Задача царя Соломона о двух женщинах. Если бы женщины знали, каким будет результат их слов, то и притворная мать также попросила бы отдать ребенка другой женщине 13 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций

Теория игр. Предыстория Библия. Задача царя Соломона о двух женщинах. Если бы женщины знали, каким будет результат их слов, то и притворная мать также попросила бы отдать ребенка другой женщине Мудрость Соломона состояла не в предложении правильного механизма, а в сокрытии его деталей от заинтересованных сторон. 14 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций

Теория игр. История в XVII в. – оптимальные стратегии в математическом моделировании (Bachet de Mezirak, Lyon, 1612) в XVIII в. - теория противоречий в экономической науке - Даниил Бернулли – о вероятности в игре ( переписка графа Уолдгрейва и Д. Бернулли об игре Le Her) Механизмы справедливого формирования общественного выбора 15 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций

Теория игр. История XIX в. - задачи производства и ценообразования в условиях олигополии олигополии Антуан Огюстен Курно (Cournot, ) Антуан Огюстен Курно (Cournot, ) 16 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций

Теория игр. История XIX в. - задачи производства и ценообразования в условиях олигополии олигополии Жозеф Луи Франсуа Бертран Жозеф Луи Франсуа Бертран (Bertrand, ) (Bertrand, ) 17 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций

Теория игр. История XIX в. - задачи производства и ценообразования в условиях олигополии олигополии Генрих фон Штакельберг Генрих фон Штакельберг ( Heinrich von Stackelberg ; ) ( Heinrich von Stackelberg ; ) 18 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций

Теория игр. История XIX в. - задачи производства и ценообразования в условиях олигополии олигополии Френсис Исидор Эджуорт Френсис Исидор Эджуорт (Edgeworth, ) (Edgeworth, ) 19 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций

Теория игр. История Нач. XX в. – идея математической теории конфликта интересов Эрнст Фридрих Фердинанд Цермело, (Ernst Friedrich Ferdinand Zermelo, ) 20 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций

Теория игр. История Нач. XX в. – идея математической теории конфликта интересов Эрнст Фридрих Фердинанд Цермело, (Ernst Friedrich Ferdinand Zermelo, ) « О применении теории множеств к шахматной игре », 1912: В каждой позиции шахматной партии один из игроков может форсированной выиграть или обеспечить себе ничью, выбирая « правильные » ответы на любой ход противника. 21 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций

Теория игр. История Нач. XX в. – идея математической теории конфликта интересов Эрнст Фридрих Фердинанд Цермело, (Ernst Friedrich Ferdinand Zermelo, ) Эмануэль Ласкер Эмануэль Ласкер ( ) чемпион мира по шахматам с 1894 по 1921, 1906 г. – брошюра «Kampf» - видение игры, с распространением её на различные сферы человеческой деятельности 22 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций

Теория игр. История Джон фон Нейман (John von Neumann, ) Джон фон Нейман 23 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций

Теория игр. История Джон фон Нейман (John von Neumann, ) Джон фон Нейман Оскар Моргенштерн Оскар Моргенштерн (Oskar Morgenstern, ) » 24 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций

Теория игр. История Джон фон Нейман (John von Neumann, ) Джон фон Нейман Оскар Моргенштерн Оскар Моргенштерн (Oskar Morgenstern, ) Математическая теория игр г. « Теория игр и экономическое поведение » 1944 г. 25 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций

Теория игр. История Джон Нэш Джон Нэш (John Forbes Nash, 1928) 26 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций

Теория игр. История Джон Нэш Ллойд Шепли Джон Нэш Ллойд Шепли (John Forbes Nash, 1928)(John Forbes Nash, 1928) (Lloyd Stowell Shapley,1923)(Lloyd Stowell Shapley,1923) 27 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций

Теория игр. Основные определения. Игра - это система правил, определяющих количество игроков, их возможные действия и распределение выигрышей в зависимости от поведения игроков и исходов. Игрок – это один участник или несколько участников, имеющих одни общие для них интересы, не совпадающие с интересами других групп. Множество игроков : Пример. Три производителя завоевывают рынок сбыта, при этом ни один из производителей не имеет полного влияния на этом рынке, поэтому выгода каждого производителя на рынке зависит от действий других производителей. Какие варианты взаимодействия производителей можно допустить ? 28 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций

Стратегии – возможные действия игрока, определяемые правилами игры. Сделать ход – сделать выбор из имеющихся возможностей, т. е. выбрать стратегию. Ситуация игры – совокупность выбранных стратегий всеми игроками. Выигрыш – это мера эффекта для игрока ( баллы, деньги, моральное удовлетворение ). В теории игр рассматриваются только такие игры, в которых выигрыш измеряется количественно. Выигрыш каждого игрока зависит не только от выбранной им стратегии, но и от стратегий, выбранных другими игроками, т. е. от ситуации игры : 29 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций Теория игр. Основные определения.

Какими бывают игры ? 30 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций Теория игр. Классификация игр.

По количеству игроков игры одного игрока игры двух игроков игры N игроков По количеству стратегий конечные бесконечные 31 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций Теория игр. Классификация игр.

По количеству игроков игры одного игрока игры двух игроков игры N игроков По количеству стратегий конечные бесконечные 32 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций Теория игр. Классификация игр.

По количеству игроков игры одного игрока игры двух игроков игры N игроков По количеству стратегий 33 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций Теория игр. Классификация игр.

По количеству игроков игры одного игрока игры двух игроков игры N игроков ( менее изучены из - за возникающих принципиальных трудностей и технических возможностей получения решения ) По количеству стратегий 34 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций Теория игр. Классификация игр.

По количеству игроков игры одного игрока игры двух игроков игры N игроков По количеству стратегий конечные бесконечные 35 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций Теория игр. Классификация игр.

По количеству игроков игры одного игрока игры двух игроков игры N игроков По количеству стратегий конечные бесконечные 36 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций Теория игр. Классификация игр.

По количеству игроков игры одного игрока игры двух игроков игры N игроков По количеству стратегий конечные бесконечные 37 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций Теория игр. Классификация игр.

По характеру взаимоотношений игроков бескоалиционные коалиционные кооперативные По характеру выигрышей игры с нулевой суммой антагонистические игры с ненулевой суммой 38 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций Теория игр. Классификация игр.

По виду функции выигрышей матричные биматричные непрерывные 39 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций Теория игр. Классификация игр.

Матричные игры Решение конфликта в условиях антагонизма : кто кого победит ? Биматричные игры Решение конфликта : кто выиграет больше ? Кооперативные игры Решение вопроса : как поделить деньги или как поделить власть ? 40 О. Д. Кичмаренко Теория игр : моделирование и решение конфликтных ситуаций Теория игр. Введение.

Спасибо за внимание !