Теория на игрите

Теория на игрите е дял от приложната математика за изследване на операциите, който изучава стратегически математически модели и взимането на решения в конфликтни ситуации.

Конфликтни са ситуациите, при които има две враждуващи страни с противоположни цели. При това, резултатът от всяко действие на едната страна зависи от начина на действие на противоположната страна. Примерите за конфликтни ситуации са многобройни. Класически пример в това отношение са военните действия. Редица ситуации в областта на икономиката (особено при наличие на свободна конкуренция) са конфликтни ситуации, в които играчите избират различни ходове, опитвайки се да максимизират възнаграждението си. Участващите в конфликта страни се наричат играчи. Ефективността на решенията на всеки играч зависи от неизвестните решения на останалите играчи и от други обстоятелства.

Видове игри

Според броя на участващите играчи, игрите са: с двама, с трима играчи и т.н. При игри с повече от двама играчи са възможни коалиции, които действат като един играч. Теорията на игрите изследва образуването на такива коалиции и разпределянето на общата печалба между тях.

Ако броят на различните действия, които играчите могат да предприемат, е краен, играта се нарича крайна; в противен случай тя е безкрайна.

Добре разработена е теорията на матричните игри. Под матрична игра се разбира крайна игра с двама играчи и нулева сума, където платежната функция е дадена във вид на матрица. Тези матрични игри се решават със средствата на линейното оптимиране.

Някои основни понятия

Основно понятие в теорията на игрите е печалбата на всеки играч. Загубата се приема за отрицателна печалба. Ако сумата от печалбите на всички играчи в една игра е постоянна (нула), говорим за игра с постоянна (нулева) сума.

Целта на играча и по-специално неговият начин на действие за постигането ѝ е стратегията на играча. Теорията на игрите доказва съществуването на оптимални стратегии и създава методи за намирането им.

За да може една игра да се подложи на математически анализ, трябва точно да се формулират правилата на играта. Те представляват система от условия, които определят възможните действия на играчите, обема на информацията на всяка страна за поведението на другата, редуването на ходовете, а също и резултата, до който довежда дадена съвкупност от ходове. Този резултат обикновено се изразява количествено – с число.

Ходовете на играчите са лични или случайни. За да бъде играта математически определена, в правилата на играта за всеки случаен ход трябва да бъде посочено разпределението на вероятностите за възможните изходи.

Мини-максна процедура

В рамките на теорията на игрите са разработени редица алгоритми или „стандартни решения“ за победа. Най-популярна е системата за победа при игра между двама играчи, наречена мини-максна процедура. Тя е базирана на идеята, че всеки играч играе най-добре. Ето накратко как се прилага тя: Да приемем, че всеки играч при всеки ход има краен брой избори за ход. След неговия ход, какъвто и да е той, противникът му също има краен брой избори. Да приемем също, което е вярно за повечето игри, че рано или късно играта винаги свършва с нечия победа. Тогава може да напишем всички възможни ходове на играта с всичките ѝ възможни изходи. Да приемем, че ние започваме и на всеки възможен краен изход слагаме оценка, показваща колко е печеливш за нас този резултат. Получава се дървовидна структура с нива – изборите на всеки играч, и листа – крайните оценки. Сега, тръгвайки от листата, може да оценим междинните състояния – ако на ход сме ние, текущото състояние има за оценка най-високата от оценките на следващите (защото ние искаме да спечелим), ако на ход е противникът, текущото състояние има за оценка най-ниската от следващите (защото той иска да спечели, т.е. ние да загубим). Така цялото развитие на играта е оценено. Оттук нататък стратегията за нас е да избираме винаги следващ ход с най-висока оценка.

Тази стратегия има редица критики и доводът, че играта може да не завърши никога, не е основателен. Такива игри са редки, неинтересни и често водят до алтернативни решения, за които подходът е принципно неприложим. Подобни „непечеливши стратегии“ са известни още като „политическо решение“ или „компромис“. Подобни резултати се получават и при патови игри с гарантиран непобедител. Най-популярната е tic-tac-toe („Хикс и о“). При такива игри математиката може да помогне малко – до чиста или някаква победа водят само преговори за реми или груба грешка на противника.

Основните критики на мини-максната процедура са огромното дърво на решенията, което повечето игри генерират, и сложният критерий за оценка на крайните състояния. Например, шахматът има много прост критерий за оценка на крайните състояния (победа, загуба и реми = 1, -1, 0), но толкова огромно и сложно дърво на изборите, че никой съвременен суперкомпютър не може да го изчисли. Повечето военни игри имат невероятно сложна система за оценка на крайните състояния.

За оценка на крайните състояния се прилагат различни евристични оценки и модели, докато за ограничаване размера на дървото на ходовете на практика се прилагат променени версии на алгоритъма, основно базирани на генериране на дървото, до някакво ниво и оценка на така получените крайни резултати. Естествено, оценката на тези крайни резултати не е лесна, защото те са междинни резултати в цялостното дърво на решенията.

Друг източник за критика на метода е „човешкият фактор“, т.е. доколко умишлено допуснати грешки на единия играч водят до стратегически важни грешки на другия играч. Този напълно безсмислен за абстрактната математика параметър винаги е бил основен в човешката история. Например Ханибал имитира пробив на центъра на войската си по време на битката при Кана, който подтиква римляните към бърза атака, в резултат на което те дори не забелязват, че са обкръжени, и след това унищожени.

Развитие

Как работи Wikipedia от гледна точка на теорията на игрите. Семинарна презентация на Thomas Koenig (2010, pdf, на немски език)

Развита първоначално като средство за обяснение на икономическото поведение, теорията на игрите сега се използва в много различни научни области от биология до философия. Тя се развива съществено и е формализирана за първи път от Джон фон Нойман и Оскар Моргенщерн преди и по време на Студената война, главно заради приложението си във военната стратегия, особено понятието за взаимно гарантирано унищожение. От 70-те години на миналия век теорията на игрите се прилага към поведението на животните, включително развитието на видовете чрез естествен отбор. Заради интересни игри като дилемата на затворника, при които взаимната корист е във вреда на всички, теорията на игрите е използвана в етиката и философията. Тя привлича вниманието на информатиците, поради прилагането ѝ в изкуствения интелект и кибернетиката.

Освен научния интерес, теорията на игрите е обект на внимание и в популярната култура. Животът на лауреата на Нобелова награда и специалист в областта на теорията на игрите Джон Наш е тема на игралния филм от 2001 г. „Красив ум“. Няколко телевизионни игри използват ситуации от теорията на игрите.