Применение методов теории игр при исследовании систем управления

Введение
1 Общенаучные методы исследования систем управления. Метод деловой игры
2 Элементы теории игр
3 Модели теории игр: кооперативные, иерархичекие и рефлексивные
Заключение
Список литературы

Применение методов теории игр при исследовании систем управления

Плох такой принцип принятия решений тем, что игрок забывает про то, что у остальных есть свои интересы, и, наверное, цель каждого игрока – максимизировать свою целевую функцию, а не «напакостить» оппоненту (это может быть частным случаем целевой функции, но, к счастью, не всегда в жизни так бывает). Определенный выше вектор действий игроков называется максиминным, или гарантирующим равновесием. Это один из вариантов определения исхода игры. То есть, можно предполагать, что возможный вариант поведения игроков – выбор всеми гарантирующих стратегий, что реализует максиминное равновесие. Но этот вариант не единственен. И основная проблема теории игр на сегодняшний день заключается в том, что не существует единой универсальной концепции решения игры – ее устойчивого в том или ином смысле исхода. В разных моделях используются разные предположения, которые приводят к различным концепциям равновесия. Поэтому рассмотрим некоторые другие варианты. 2) Представим себе такую ситуацию, что целевая функция i-го игрока fi(y) достигает максимума по его действию в точке, которая не зависит от действий других игроков. Это оптимальное действие, не зависящее от обстановки, называется доминантной стратегией агента. Формально: стратегия yid будет доминантной стратегией, если какая бы обстановка не складывалась, его выигрыш будет максимальным при выборе именно доминантной стратегии: Vyi ϵ Ai, Vy-i ϵ A-i, fi(yid, y-i) ≥ fi(yi, y-i).Отметим, что в обеих частях неравенства фигурирует произвольная, но одна и та же обстановка. Если у каждого игрока существует доминантная стратегия, то совокупность доминантных стратегий называется равновесием в доминантных стратегиях (РДС) {yid}iϵN. Это – идеальная ситуация для исследователя, описывающего математическую модель. Если существует равновесие в доминантных стратегиях, то каждый из игроков принимает решение независимо. А описывать независимое принятие решений гораздо проще. Но такая ситуация встречается очень редко.3) Гораздо чаще существует равновесие Нэша (РН). Джон Нэш, американский математик, в начале 50-х годов XX века предложил следующее: устойчивым исходом взаимодействия агентов можно считать такой вектор их действий, от которого в одиночку никому не выгодно отклоняться. Это значит, что ни один из агентов, в одиночку меняя свою стратегию на другую, не может увеличить свой выигрыш при условии, что остальные своих стратегий не меняют.Формальное определение равновесия Нэша yN ϵ A' таково: Vi ϵ N Vyi ϵ Ai, fi(yin, y-in) ≥ fi(yi, y-in), то есть для любого агента и для любого допустимого его действия выбор им равновесного по Нэшу действия дает ему выигрыш не меньший, чем при выборе любого другого действия при условии, что остальные игроки выбирают равновесные по Нэшу стратегии.Равновесие Нэша хорошо тем, что в большинстве моделей оно существует. Недостатком его является то, что оно не всегда единственно. Представьте, если есть два равновесия, то как предсказать, в каком из них окажутся агенты? Нужны дополнительные предположения. Кроме того, равновесие Нэша не устойчиво к отклонению двух и более игроков. По определению одному агенту не выгодно отклоняться, но это не значит, что если два агента договорились и одновременно отклонились, то они не смогут оба выиграть. То есть равновесие Нэша – существенно некооперативная концепция равновесия. 4) Помимо вышесказанного, необходимо ввести понятие точки Парето. Вектор действий агентов yP ϵ A' , принадлежащий множеству A' допустимых векторов действий, будет эффективным по Парето, если для любого другого вектора действий найдется агент такой, что значение его целевой функции будет строго меньше, чем в точке Парето Vy ≠ yP Эi ϵ N fi(y)< fi (yP).То есть точка Парето – такая точка, отклоняясь от которой, нельзя одновременно увеличить значения целевых функций всех игроков. Идея хороша тем, что позволяет утверждать, что если мы можем сделать лучше всем, то это надо делать. Любая разумная модель должна удовлетворять эффективности по Парето. Вопрос заключается в том, как соотносятся все вышеперечисленные стратегии с эффективностью по Парето, так как хочется, чтобы результат, соответствующий индивидуальным максимумам, был бы еще эффективным для общества в целом. Оказывается, что эффективность по Парето, к сожалению, никак не соотносится ни с одной из трех концепций решения игры, изложенных выше.3 Модели теории игр: кооперативные, иерархичекие и рефлексивныеКооперативная игра задается множеством игроков N = {1, …, n} и характеристической функцией v: 2N→ R, ставящей в соответствие каждой коалиции игроков ее выигрыш. Дележом игры (N, v) называется вектор x = (x1, …, xn), для которого iϵNxi=v(N) (свойство эффективности), xi ≥ v ({i}), i ϵ N (свойство индивидуальной рациональности). Решением кооперативной игры обычно считается множество дележей, которые реализуемы при рациональном поведении игроков. Различные концепции решения кооперативных игр отличаются предположениями о рациональном поведении игроков. Иерархические игры. Если в рассматриваемых до сих пор моделях игровой неопределенности предполагалось, что игроки (агенты) выбирают свои стратегии одновременно и однократно (модели повторяющихся и дифференциальных игр в настоящей работе не рассматриваются), то в иерархических играх существует фиксированный порядок ходов – первый ход делает центр, затем свои стратегии выбирают агенты. С этой точки зрения иерархические игры являются наиболее адекватным аппаратом описания задач управления организационными системами. Для иерархических игр характерно использование максимального гарантированного результата (МГР) в качестве базовой концепции решения игры. При этом «пессимистичность» МГР (взятие минимума по множеству неопределенных параметров) компенсируется возможностью передачи информации между игроками, что, очевидно, снижает неопределенность при принятии решения. Критерии эффективности (целевые функции) первого и второго игроков обозначим w1 = f1 (x1, x2) и w2 = f2 (x1, x2) соответственно. Выигрыши игроков зависят от их действий x1 и x2 из множеств действий X10, X20.Во всех моделях иерархических игр считается, что первый игрок (центр) имеет право первого хода. Его ход состоит в выборе стратегии x1. Понятие стратегии существенно отличается от понятия действия и тесно связано с информированностью первого игрока о поведении второго игрока – агента. Под стратегией игрока здесь и далее понимается правило его поведения, то есть правило выбора конкретного действия в зависимости от содержания и конкретного значения той информации, которую он получит в процессе игры. Выбирать же собственно действие центр может и после выбора действия агентом. Самая простая стратегия центра состоит в выборе непосредственно действия x1 (если поступления дополнительной информации о действии агента в процессе игры не ожидается), более сложная – в выборе функции x1 (x2) (если в процессе игры ожидается информация о действии агента). Стратегия центра может также состоять в сообщении агенту некоторой информации, например, о планах своего поведения в зависимости от выбора агентом действия. При этом агент должен быть уверен, что первый игрок может реализовать эту стратегию, то есть что первый игрок будет точно знать реализацию действия x2 на момент выбора своего действия x1. Например, если агент (выбирающий стратегию вторым) не ожидает информации о действии центра, то реализация права первого хода центра может состоять в сообщении центром агенту функции x1 (x2). Такое сообщение может рассматриваться, как обещание выбрать действие x1 = x1 (x2) при выборе агентом действия x2. Тогда стратегия агента состоит в выборе действия в зависимости от сообщения центра, x2 = x2 (x1(.)). Если при этом агент доверяет сообщению центра, он должен выбрать действие x2*, реализующееmax f2 (x1 (x2), x2).Игра с описанным выше порядком функционирования называется для краткости игрой Г2 (примером такой игры служит как раз задача стимулирования в условиях информированности центра о действии агента). Если центр не ожидает информации о действии агента и это известно агенту, то стратегия центра состоит, как уже было сказано, просто из выбора некоторого действия x1*. Стратегия агента состоит в выборе x2 = x2(x1*) (он делает ход вторым, уже зная действие центра). Такая игра называется игрой Г1 (это, например, та же задача стимулирования, но уже в условиях отсутствия у центра информации о действии агента). Рефлексивные игры. Рассмотрим игру, в которой участвуют агенты из множества N = {1, 2, …, n}. Если в ситуации присутствует неопределенный параметр Ɵ ϵ Ω, то структура информированности Ii (как синоним будем употреблять термины «информационная структура» и «иерархия представлений») i-го агента включает в себя следующие элементы. Во-первых, представление i-го агента о параметре Ɵ – обозначим его Ɵi, Ɵi ϵ Ω. Во-вторых, представления i-го агента о представлениях других агентов о параметре Ɵ – обозначим их Ɵij, Ɵij ϵ Ω, j ϵ N. В третьих, представления i-го агента о представлении j-го агента о представлении k-го агента – обозначим их Ɵijk, Ɵijk ϵ Ω, j,k ϵ N. И так далее. Таким образом, структура информированности Ii i-го агента задается набором всевозможных значений вида Ɵij1…j1, где l пробегает множество целых неотрицательных чисел, j1, …, jl ϵ N, а Ɵij1…j1 ϵ Ω.Аналогично задается структура информированности I игры в целом – набором значений Ɵij1…jl, где l пробегает множество целых неотрицательных чисел, j1, …, jl ϵ N, а Ɵij1…jl ϵ Ω.Подчеркнем, что структура информированности I «недоступна» наблюдению агентов, каждому из которых известна лишь некоторая ее часть (а именно – Ii). Таким образом, структура информированности – бесконечное n-дерево (то есть тип структуры постоянен и является n-деревом), вершинам которого соответствует конкретная информированность реальных и фантомных агентов. Рефлексивной игрой ГI называется игра, описываемая следующим кортежем: ГI = {N, (Xi)i ϵ N, fi (∙)i ϵ N, Ω, I},где N – множество реальных агентов, Xi – множество допустимых действий i-го агента, fi (∙): Ω × X′ → R1 – его целевая функция, i ϵ N, Ω – множество возможных значений неопределенного параметра, I – структура информированности. Подчеркнем, что все элементы рефлексивной игры кроме структуры информированности являются общим знанием среди агентов, то есть 1) эти элементы известны всем агентам; 2) всем агентам известно 1); 3) всем агентом известно 2) и так далее до бесконечности. Далее для формулировки некоторых определений и свойств нам понадобятся следующие обозначения: Ʃ+ – множество всевозможных конечных последовательностей индексов из N; Ʃ – объединение Ʃ+ с пустой последовательностью; |σ| – количество индексов в последовательности σ (для пустой последовательности принимается равным нулю), которое выше было названо длиной последовательности индексов. Если Ɵi – представления i-го агента о неопределенном параметре, а Ɵij – представления i-го агента о собственном представлении, то естественно считать, что Ɵij = Ɵi.