Дилемата на затворника

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

По начало разработена, за да може да се прецени оптималната стратегия на играч в една или друга (хазартна) игра, тя се оказва математическият инструмент за определяне на начините за максимална изгода при взаимодействия между хора или юридически лица. Иначе казано, тя се оказва оптималният математически инструмент за описване на взаимодействията в обществото.

(Теорията на игрите има разширения, които работят с големи, статистически групи от хора. Класиката й обаче се използва за ситуации с ограничен брой хора. В противен случай сигурно другото й име щеше да е психоистория. 😉 )

Едно от интересните “уравнения” в теорията на игрите е така наречената “дилема на затворника”. Тя е най-известният пример за ситуации, в които, ако всеки от участниците действа както е най-изгодно за него, крайният резултат е неизгоден за всички. Или, иначе казано, е възможно сътрудничеството на участниците да не е в интерес на всеки от тях, въпреки че е в интерес на всички. На езика на теорията, такива ситуации се наричат “Парето-субоптимални”.

Ситуацита е описана преди двайсетина години от Албърт Тъкър, и гласи (в един от вариантите й) следното:

Полицейски патрул е арестувал двама души, заподозрени в разбиване на витрината на златарски магазин и обирането му. Има свидетели, които са ги видели да чупят витрината. Никой обаче не ги е видял да вземат нещо от магазина.

В тази ситуация следователят ги изолира един от друг, и казва на всеки следното:

– За теб има четири варианта. Ако и двамата с колегата ти си мълчите, ще получите по шест месеца присъда за чупене на витрина. Ако той мълчи, но ти кажеш, че той е взел златото, ще те пуснем, защото съдействаш на следствието. Ако колегата ти каже, че ти си го взел, а ти не го натопиш, отнасяш десет години затвор. Обаче ако и ти кажеш, че и той е взимал, ще получиш само пет години, понеже сътрудничиш на следствието… В твой интерес е да го натопиш. Ако той мълчи, излизаш веднага, вместо да лежиш шест месеца. Ако той проговори, лежиш пет години вместо десет. И в двата случая си на печалба. Решавай си.

Очевидно всеки от двамата има изгода да натопи другия, че е вземал от златото. Така и двамата ще получат по пет години затвор. И ще пропуснат много по-добрия вариант, когато ще получат само по шест месеца.

В английската Уикипедия има разкошна статия по темата. Струва си човек да похаби няколко часа, за да изчете всичко около нея – огромно ограмотяване е. Извън това обаче, дилемата на затворника демонстрира сложността на създаването на Парето-оптимални системи – иначе казано, на свестни общества и държави.

Колкото по-малко са хората в една общност, колкото по-сходни са, и колкото по-кратко време съществува общността, с толкова по-малко Парето-неоптимални проблеми се сблъсква. Иначе казано, толкова по-малко ядове и грижи от обществен характер създава животът в нея. В реалните ситуации обаче хората в общностите са много, много различни са, и общностите съществуват дълго. (Което е чудесно – дейността на повече хора води до печалба заради икономиите от размер; разнообразието на хората в общността е най-голямото й богатство, а дългото й съществуване е предусловие за намаляване на проблемите.) Това ще рече, че в една общност с размер на типична държава обикновено съществуват огромен брой Парето-неоптимални ситуации.

Законодателството в по-свестните държави служи именно за разрешаването на тези ситуации. Например, то предвижда мерки срещу престъпността. (Да крадеш от другите като правило е по-изгодно, отколкото да изработваш сам; да живееш в общност от бандити обаче е много по-неизгодно, отколкото в общност от честно работещи хора.) Предвижда набиране на войници в случай на война. Дава на правителството властта да взима непопулярни, но необходими решения. И т.н.

Интересна ми се струва ситуацията, в която любители-математици се опитват да намерят най-оптималния постижим Парето-баланс за голяма общност, примерно цяла държава. Вероятно може да бъде създаден софтуер, който да подпомага тази работа, с необходимите изчисления и сравнения. Не бих се учудил, ако той изисква мощността на сериозен суперкомпютър. Но мисля, че ако се реализира на послойно-хибридна структура, ще е по силите на една сериозна софтуерна компания да го напише. Описването на интеракторите ще е много по-сериозно количество работа, но смятам, че също ще е посилно.

Сериозен въпрос е дали ще има държава, която да поиска да приложи продукта. Но си мисля, че навлизането на информатиката и на някои други технологии може в значителна степен да освободи обществото от закрепостеността на хората. Тогава те ще могат по-лесно да образуват общности, в които да прекарват значителен процент от съществуването си. Реално е някои от тези общности да опитат така създадените модели. Вероятно първите опити никак няма да са сполучливи. Но с изчистването на грешките… кой знае, нищо чудно да се стигне и до вършещи работа модели.

18 thoughts on “Дилемата на затворника

  1. Нора Найденова

    Чудесен пост! Смятам, че би бил изключително полезен на всеки, който иска да схване същественото по темата. Колкото до създаването на софтуер, който ще помага за достигането до ефективни общества… смятам, че хората, които биха работили по него, биха си изгубили времето и ресурсите за нещо напразно. Няма универсална математическа формула за постигането на оптимално функционираща държава или социално-икономическа среда. Нито пък някога ще бъде измислен софтуер, който да изготвя специфична формула за всяка отделна държава. Това се дължи на факта, че в цялото математическо уравнение има прекалено много неизмерими величини, а освен това има и едно неконтролируемо и непредвидимо неизвестно – човекът.

    Reply
  2. Itilon

    Теорията на игрите винаги ми е била адски интересна :).

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

    Мисълта ми е, че Дилемата на затворника в най-добрия случай е само статистически валидна. Тя взима за условие напълно чисти ситуации, в които хората реагират съвършено рационално, без да са придружени от какъвто и да е background или емоционален багаж (изобщо каквото и да е извън условието). Един математически модел от типа на психоисторията, според мен, ще се сблъска със същия проблем – впрочем и в икономиката, и в социологията, и в други науки има подобни модели и не случайно учените, работещи в съответните области, от време на време се оказват крайно изненадани. Така че дори да бъде разработен съвършено балансиран продукт от типа на описания от теб, според мен той няма да работи добре.

    Та си мисля, че най-добрите модели са описателни – като този на капитализма например. Те не са създадени предварително от учените с цел да подобрят живота ни. Просто отразяват общества, появили се в опита на всеки от нас да направи съществуването си възможно най-добро. Затова нито Капиталът, нито Държавата и революцията (а и Маркс, и Ленин са били безспорно много ерудирани хора) не донесоха нищо добро. Но Богатството на народите още е настолна книга на всеки, който иска да разбере икономиката, свободата и обществото.

    Reply
  3. Григор Post author

    @Нора Найденова: Теорията на игрите (и по-точно анализът на оптималността на Парето-решенията за дадени случаи) според мен би могла да е от голяма полза при оптимизирането на нормативната база на едно общество. Когато се касае до прости ситуации (напр. доколко може да се разчита на служителя, който има изгода работодателят му да го осигурява на пълна работна заплата, да го изтропа, че не го осигурява), те могат да се преценят и чрез опит и логика. Когато обаче има огромен набор взаимодействащи си ситуации, софтуер за оптимизиране на уравнения по Парето би могъл да бъде много полезен. Ще позволи издирването на “дупки” в системата, например в нормативната база.

    @Itilon: Такъв продукт винаги би бил само инструмент, и винаги би бил недовършен инструмент. Дори в един момент да бъде доведен до съвършенство, обществото се развива – в следващия момент той отново ще е непълен, или дори грешен.

    Интересното обаче става, когато се хибридизират теорията на игрите (оптимално работеща при преценка на краен брой субекти), и статистическият анализ (“психоисторията”), работещ оптимално при статистически големи групи. Разширена версия на теорията на игрите би помогнала за прилично предсказване на лидерства, където хората са малко. Статистическият анализ би бил добър при предсказване на поведението на масите. (Реално, за да работят прилично, и двете трябва да инкорпорират по малко от другото.) За “средните слоеве” би била подходяща комбинация от двата подхода. Където единият е слаб, другият е силен. Така че нищо чудно да може да се постигне резултат – сигурно не съвършен, но при достатъчно доизкусуряване забележимо ефективен.

    Затова и чопля подобни теми. 🙂

    Reply
  4. Николай Василев

    Принципът на Парето не водеше ли до равновесието на Наш (Nash equilibrium)?

    Аз си мисля, че може би ако се въведат някакви примери в обществото, които провокират кооперативното мислене в хората, може би модела ще сработи.

    Като пример се сещам една случка, която или Григор беше описал или някой в коментарите към някои пост: тъй като в Ню Йорк хората рисували много графити навсякъде и официалните забрани за рисуване не вършели работа, кметът издал заповед всички стени, които са нарисувани, да се варосат (или боядисат, това е без значение). След като това станало, процента на рисуващите рязко спаднал, просто хората не се решавали да рисуват върху чистите повърхности.

    Та, ако се използват такива психологически подходи и се опита да се приложи модела, който Григор описа, кой знае… може пък някой да изнамери психоисторията на Хари Селдън по този начин 🙂

    Reply
  5. Itilon

    @ Николай Василев, говориш за нещо съвсем различно, което се нарича Теория на счупения прозорец. Тя поначало е доста спорна, де, въпреки че аз съм склонен да вярвам в нея. Изобщо не виждам как може да се инкорпорира в Теорията на игрите, обаче, тъй като е строго психологическа, и макар да има опитни потвърждения, не може да се докаже по категоричен начин, че те са следствие от нея (да не говорим за случаи, в които просто не сработва). Може и да греша, естествено.

    Reply
  6. Николай Василев

    Извинявам се. След като публикувах коментара и аз се замислих, че може би наистина се отклоних малко от темата поставена от Григор.

    Това е което имах в предвид – теория на счупения прозорец. Но струва ми се, че макар неявно, теорията за счупения прозорец е свързана с теория на игрите… макар и косвено.

    Ако хората са стимулирани да се противопоставят на малките нередности в обществото (мръсни улици, грубост, вандалство, кражби и т.н.), то те ще развият нетърпимост и към големите (по подобие на идеята да се ограничи престъпността в Ню Йорк, започвайки с чистенето на вагоните). Което, според мен, се вписва в принципа на Парето по следния начин: ако се изследват факторите, които провокират хората да мислят в полза на обществото, въпреки временното неудобство, но в дългосрочен план, това би оптимизирало благоденствието на обществото, защо не тези фактори да бъдат включени в софтуерния модел, за който Григор говори?

    Не знам дали теорията на счупения прозорец е доказана или не, не съм специалист по психология. Просто спонтанна асоциация между двете теории и ми стори интересно като идея.

    Reply
  7. Николай Василев

    “Просто спонтанна асоциация между двете теории и ми стори интересно като идея.” да се чете: “Просто направих спонтанна асоциация между двете теории и ми стори интересно като идея.”

    Reply
  8. Любо Николов

    Според една апокрифна съвременна легенда големите акули от Уолстрийт неведнъж са разигравали дилемата на затворника в различни варианти, използвайки секретарките си. И се оказало, че практическите резултати в огромното мнозинство от случаите противоречат на теорията.
    Много големият проблем в съвременния тюрлю-гювеч от икономика, математика и психология е там, че взима за модел някаква абстрактна личност, напълно лишена от съвест. Така по модела излиза, че в горния случай престъпниците ще се накиснат взаимно, от което уж печелят, а всъщност губят и двамата.
    На практика по всяка вероятност ще мълчат, от което уж губят, а всъщност печелят.
    Морално-етичните норми са логични в по-висш смисъл, но подхождането към тях от позициите на елементарната логика (и егоизма) е дълбоко погрешно.

    Reply
  9. Григор Post author

    @Николай Василев: Точно така, принципът на Парето води до еквилибриум на Наш. Историята с графитите илюстрира механизмите на Парето косвено (демонстрира изместване на еквилибриума при промяна на условията). Анализирана е не-математически в “теорията за единия счупен прозорец”.

    @Itilon: Инкорпорирането е елементарно. Докато стените са изрисувани, всяка нова рисунка прибавя само една рисунка към многото (процентно променя ситуацията с твърде малко). Анализът на Парето в такъв случай предполага присъединяване към отговорност, споделена от много други – тоест, прагът на действие е нисък. Ако стените бъдат боядисани, първата рисунка поема еднолично отговорността – тоест, прагът на действие се покачва. Нещата могат да бъдат изчислени математически сравнително просто, като се отчетат тежестта на наказанието по критериите на общността на потенциалните нарушители, и перцепцията им за вероятността да бъдат хванати и да го получат. (Тези фактори могат да бъдат и динамични, например когато перцепцията е погрешна, и се коригира с първите заловени или незаловени; това следва да се отчита в модел, който трябва да поддържа адекватност за значимо по критериите на динамиката на факторите време.)

    @Любо Николов: “Дилемата на затворника” не винаги е вярна в реалния случай, защото той включва и много други фактори. (В дадения пример – най-вече фактора “женска логика”. 😉 )Целта й обаче е не да предскаже реалния живот (това би изисквало тя да стане сложна до степен да не е лесно обяснима), а да покаже лесно и разбираемо, че има ситуации, в които Парето-решенията са субоптимални. Надпреварата във въоръжаването например е класическа такава ситуация, която е работила “изправно” в течение на десетки години, и ако едната от страните не беше се сринала икономически, щеше да работи и още дълго време…

    Иначе, морално-етичните норми почти без изключение са именно опити за Парето-оптимизация, която чрез налагане на външен фактор (морал, етика, норма) принуждава участниците да търсят Парето-оптимално решение, като пренебрегнат логически изгодното Парето-субоптимално.)

    Reply
  10. Апостол Дянков

    Препоръчвам ти една книга Critical Mass – how one things lead to another, на Philip Ball, където затворническата дилема и компютърните симулации са описани много информативно и увлекателно. Ако си навътре в математиката ще ти е по-интересна отколкото на мен. Ако не си я намериш в pdf с удоволствие ще ти заема печатно копие.

    Reply
  11. Verena

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

    По-точно, имам предвид книгата “Звездни рейнджъри” на Хайнлайн. Ключов момент в модела е обвързването на правата и отговорностите с “усилия”, които трябва да бъдат положени, за да се получи право на глас, или власт. В момента последната световна мода – раздаване на права на всички, понеже “им се полага по право” – направо е превърнала думата “права” в подигравка 🙁

    Неслучайно “Звездни рейнджъри” и “Луната е наставница сурова” ги изучават във военните училища в САЩ…

    Reply
  12. skoklyo

    А може би пък тази дилема показва единствено колко важна е информираността при вземането на решения, нищо друго. Ограничи подаването на информация и дори суперкомпютърът ти с всичките му съвършени алгоритми няма да твори нищо освен ирационални глупости.

    Reply
  13. Христо Томов

    Гледайки засегнатите теми си мисля, че вероятно ще представлява интерес за вас един конкретен раздел от теорията на игрите – теорията за дизайн на механизми – Mechanism design theory (според Wikipedia уместно наричана понякога и reverse game theory). За разлика от класическата теория на игрите, която се занимава основно с поведението на „играчите” при зададени правила, при дизайна на механизми се разглежда какви да бъдат правилата, за да се постигнат (максимизират) желани цели при зададено поведение/мотивация на играчите. За труда си върху тази теория Leonid Hurwicz, Eric S. Maskin, Roger B. Myerson получиха колективно Нобелова награда за икономика през 2007г. Постиженията в областта са приложими реално както при дизайна на локални „игри”, като например правила за търгове и вътрешно фирмени политики, така и при определянето на правила за обществото, на местно и държавно ниво.
    От известно време се интересувам активно от теорията и ако някой проявява интерес мога да го насоча към интересни ресурси по темата. За събуждане на любопитството може да разгледате например Braess’s paradox (http://en.wikipedia.org/wiki/Braess_paradox), който илюстрира как пренебрегването на принципите и може да превърне искрените усилия на някой да подобри една система в негативен фактор. Някъде четох за реално затваряне на новооткрити пътища, за да се избегнат описаните последици.

    Reply
  14. Григор Post author

    @Апостол Дянков: Благодаря!

    @Verena: И на мен често най ми допадат модели от фантастични модели. 🙂

    (Апропо, никът ти комплимент към Ники Теллалов ли е? 🙂 )

    @skoklyo: Наистина показва колко важна е информираността. (Например информираността, че теорията също е важна. 🙂 )

    @Христо Томов: Благодаря за идеите и линка!

    Reply
  15. skoklyo

    Да, разбира се, че теориите са важно нещо. Но в дадената дилема ключов момент е изолацията на двамата затворника, също както в едно общество индивидите не се познават лично и не общуват директно. Никой не знае какво се върти в главата на другия, доколко запознат със ситуацията е, доколко я оценява правилно, а дори самият психологически натиск от страна на следователя (и хилядите му нюанси и форми в обществото, съответно) е достатъчен да обърка логиката на вземане на решения.
    И какво се получава накрая – чист хазарт. Затваряш очите, дърпаш спусъка и се надяваш да извадиш късмет, много научно, няма що. Също като комунизма – хайде всички да се жертваме за общото благо, надявайки се, че сред нас няма нито един, който да ни развали къщичката от карти. И за да сме сигурни, че такъв няма да остане скрит, нека всеки да шпионира всеки. И като по-напреднали с техниката от 1984 насам, можем да тръснем един голям суперкомпютър, който да решава вместо нас – какви да бъдат оптималните ни закони, какво да бъде оптималното ни меню, с кой партньор ще постигнем оптимален брак, какви да бъдат оптималните ни сънища, професионална реализация и прочие дреболии.
    Ами, аз просто не съм съгласен, извинявам се. Самото споменаване за планово моделиране и оптимизиране на обществото ми намирисва на тоталитаризъм и антиутопия, с всичките неизбежни извращения на системата рано или късно. Човешкото общество винаги се е крепяло на баланса между егоизъм и саможертва, като за второто разчитаме най-вече на възвишени емоции или откровен натиск. Затова и намирам математическият елемент в дилемата за ненадежден и маловажен – двамата арестанти в нея могат да изберат да мълчат или отричат просто защото се познават добре, имат предварително координирана история, или си чакат адвоката, който ще им даде допълнителна информация и съвет. А ако се натопят, може да е просто защото са били държани 24 часа без сън при постоянни разпити и вече просто искат всичко да свърши. Така че, какво изобщо доказва дилемата, освен необходимостта от повече информация и общуване, и от по-малко репресии също, включително от страна на математици и програмисти? 🙂

    Reply
  16. Григор Post author

    @skoklyo: Доказва няколко неща.

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

    И като продължение, че познаването на този факт (и други около теорията на игрите), и използването на това познание за добро, може да ни даде много по-свястно общество, отколкото имаме сега. И че това общество ще е проектирано с научни средства, само ме радва. Да, гаранции за качество няма. Но аз предпочитам да живея в проектирана къща, отколкото в построена чрез случайно хвърляне на камъни през рамо. Най-малкото защото ако проектът се окаже лош, винаги мога да го изхвърля и да отчета грешките му в следващия. Звучи гадно, но цялото развитие на обществото е по такъв механизъм. С единствената разлика, че обикновено научен подход и анализ на грешките липсва, и обикновено се почва от каквото падне… Всъщност, единственото общество, започнато да се строи чрез наистина сериозен анализ на грешките на предишните, е американското. Не че и то не се е изкривило впоследствие, но определено е било след създаването си три нива над всички околни. И и досега остава по-добро в доста отношения (макар и да, не във всички – но пък на практика всички други общества, които са по-добри от него в каквото и да е, са силно повлияни от него).

    Иначе казано, математическият елемент в смятането на траектория е маловажен до степен да е излишен. Къде камъкът ще бъде метнат с не точно предвидената сила и/или посока, къде ще духне вятър… Но иди да убеждаваш артилеристите, че тая работа става без математика. Или примерно ракетно-космическите инженери. Така че не подценявай нещата. 🙂

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *