Teorya ng laro

Anyong ekstensibo

Ang anyong ekstensibo ay maaaring gamitin upang ipormalisa ang mga laro na may pagsesekwensiya ng panahon ng mga galaw. Ang mga laro rito ay nilalarawan sa mga mga puno (gaya ng inilalarawan sa kaliwa). Dito, ang bawat berteks (o nodo) ay kumakatawan sa isang punto ng pagpipilian para sa isang manlalaro. Ang manlalaro ay tinutukoy ng isang bilang na itinala ng berteks. Ang linya sa berteks ay kumakatawan sa isang posibleng aksiyon para sa manlalarong ito. Ang mga kabayaran ay tinutukoy sa ilalim ng puno. Ang anyong ekstensibo ay maaaring makita bilang maraming manlalarong paglalaro ng isang desisyong puno.
Sa larong inilarawan sa kaliwa, mayroong dalawang mga manlalaro. Ang Manlalarong 1 ang unang gumalaw at pumipili ng F o U. Nakikita ng Manlalarong 2 ang galaw ng Manlalarong 1 at pagkatapos ay pumili ng A o R. Ipagpalagay na pinili ng Manlalarong 1 ang U at pinili ng Manlalarong 2 ang A, kung gayon, ang Manlalarong 1 ay kukuha ng 8 at ang Manlalarong 2 ay kukuha ng 2.
Ang anyong ekstensibo ay maaaring bumihag ng mga larong sabay na galaw at mga larong may hindi-perpektong impormasyon. Upang ikatawan ito, ang isang tinuldukang linya ay kumokonekta sa iba't ibang mga berteks upang ikatawan ang mga ito bilang bahagi ng parehong hanay ng impormasyon (i.e. hindi alam ng mga manlalaro kung saan punto sila) o ang isang saradong linya ay iginuhit sa palibot nito.

Anyong karakteristikong punsiyon

Sa mga larong nag-aangkin ng maaalis na utilidad, ang magkahiwalay na mga gantimpala ay hindi ibinibigay. Bagkus, ang punsiyong karakteristiko ay nagpapasya ng kabayaran sa bawat pagkakaisa. Ang ideya ay ang pagkakaisa na 'walang laman' ay hindi tumatanggap ng isang gantimpala. Ang pinagmulan ng anyong ito ay matatagpuan sa aklat nina John von Neumann at Oskar Morgenstern. Kung titingnan ang mga instansiyang ito, kanilang hinulaan na kapag ang pagkakaisang C ay lumilitaw, ito ay gumagawang laban sa praksiyon (N/C) kung paanog ang dalawang mga indibidwal ay naglalarao ng isang larong normal. Ang nakabalanseng kabayarang C ay isang basikong punsiyon. Bagaman may iba't ibang mga halimbawa na nakatutulong sa pagtukoy ng koalisyonal na mga halaga mula sa mga larong normal, hindi lahat ay lumilitaw na sa kanilang punsiyon ay maaaring mahango mula sa gayon. Sa pormal na paglalarawan, ang isang punsiyong karakteristiko ay nakikita bilang: (N,v), kung saan ang N ay kumakatawan sa pangkat ng mga tao at ang v:2^N-->R ay isang normal na utilidad. Ang gayong mga punsiyong karakteristiko ay lumawig upang ilarawan ang mga laro kung saan ay walang maaalis na utilidad.

Anyong punsiyong partisyon

Ang anyong punsiyong karakteristiko ay hindi pumapansin sa posibleng mga eksternalidad ng pormasyong koalisyon. Sa anyong punsiyong partisyon, ang kabayaran ng koalisyon ay hindi lamang nakabatay sa mga kasapi nito kundi pati sa paraang ang natitira ng mga manlalaro ay pinapartisyon o hinahati.

Pakikipagtulungan o hindi-pakikipagtulungan

Ang isang laro ay isang pakikipagtulungan kung ang mga manlalaro ay may kakayahang bumuo ng nagtataling mga pangako. Halimbawa, ang sistemang legal ay nag-aatas sa mga ito na sumunod sa kanilang mga pangkat. Sa mga larong hindi pakikipagtulungan, ito ay hindi posible. Kadalasan, ipinagpapalagay na ang komunikasyon sa mga manlalaro ay pinapayagan sa mga larong pakikipagtulungan ngunit hindi sa mga larong hindi pakikipagtulungan. Gayunpaman, ang klasipikasyong ito sa dalawang binaryong mga kriterya ay kinuwestiyon at minsang itinakwil. Sa dalawang mga uri ng mga laro, ang mga larong hindi pakikipagtulungan ay may kakayahang magmodelo ng mga sitwasyon sa pinakamaliit na detalye na lumilikha ng mga tiyak na resulta. Ang mga larong pakikipagtulungan ay pumopokus sa laro sa pangkalahatan. Ang malaking mga pagsisikap ay ginawa upang iugnay ang dalawang mga pakikitungo. Ang tinatawag na programang Nash ay nagpatunay na maraming mga solusyong pakikipagtulungan bilang ekwilibriang hindi pakikipagtulungan. Ang mga larong hybrid ay naglalaman ng mga elementong pakikipagtulungan at hindi pakikipagtulungan. Halimbawa, ang mga koalisyon ng mga manlalaro ay nabubuo sa isang larong pakikipagtulungan ngunit ang mga ito ay naglalaro sa isang anyong hindi pakikipagtulungan.

Larong sabay at sunod sunod

Ang mga larong sabay ang mga laro kung saan ang parehong mga manlalaro ay sabay na gumagalaw o kung ang mga ito ay hindi gumagalaw ng sabay, ang kalaunang mga manlalaro ay walang kamalayan sa mga aksiyon ng mas naunang mga manlalaro (na gumagawa sa mga itong epektibong sabay). Ang mga larong sekwensiyal (o larong dinamiko) ang mga laro kung saan ang mga kalaunang manlalaro ay may ilang kaalaman tungkol sa mga mas naunang aksiyon. Ito ay hindi kinakailangang isang perpektong impormasyon tungkol sa bawat aksiyon ng mga mas naunang manlalaro. Ito ay maaaring labis na kaunting kaalaman. Halimbawa, ang isang manlalaro ay maaaring makaalam na ang mas naunang manlalaro ay hindi gumanap ng isang partikular na aksiyon samantalang hindi nito alam kung alin sa mga ibang makukuhang aksiyon ng unang manlalaro ay aktuwal na naganap. Ang pagkakaiba sa pagitan ng sabay at sekwensiyal na mga laro ay nabibihag sa iba't ibang mga representasyong tinatalakay sa itaas. Sa kadalasan, ang anyong normal ay ginagamit upang ikatawan ang mga larong sabay at ang anyong ekstensibo ay ginagamit upang ikatawan ang mga larong sekwensiyal. Ang transpormasyon ng ekstensibong laro tungo sa anyong normal ay isang daan na ang ibig sabihin ang maraming mga larong anyong ekstensibo ay tumutugon sa parehong anyong normal. Dahil dito, ang mga nosyon ng ekwilibrium para sa mga larong sabay ay hindi sapat sa pangangatwiran tungo sa mga larong sekwensiyal.

Perpektong impormasyon at hindi perpektong impormasyon

Ang isang mahalagang pang-ilalim na hanay ng mga larong sekwensiyal ay binubuo ng mga laro ng perpektong impormasyon. Ang isang laro ay isang perpektong impormasyon kung alam ng lahat ng mga manlalaro ang mga galaw na nakaraang ginawa ng ibang lahat na mga manlalaro. Kaya, ang tanging mga larong sekwensiyal ang mga laro ng perpektong impormasyon dahil ang mga manlalaro sa mga larong sabay ay walang alam sa mga aksiyon ng ibang mga manlalaro. Ang karamihang mga laro na pinag-aaralan sa teoriya ng laro ang mga larong hindi perpektong impormasyon. Ang mga interesanteng halimbawa ng mga larong perpektong impormasyon ay kinabibilangan ng larong ultimatum at larong centipede. Ang mga larong paglilibang ng perpektong impormasyon ay kinabibilangan ng chess, go, at mancala. Maraming mga laro ng kard ay mga laro ng hindi perpektong impormasyon gaya halimbawa ng poker at tulay na kontrata. Ang perpektong impormasyon ay kadalasang ikinalilito sa kompletong impormasyon na isang parehong konsepto. Ang kompletong impormasyon ay nag-aatas na alam ng bawat manlalaro ang mga stratehiya at kabayarang makukuha sa ibang mga manlalaro ngunit hindi kinakailangang mga aksiyong kinuha. Ang mga laro ng hindi kompletong impormasyon ay maaaring mapaliit gayunpaman sa mga laro ng hindi perpektong impormasyon sa pamamagitan ng pagpapakilala ng mga galaw sa kalikasan.

Mga larong kombinatoryal

Ang mga laro kung saan ang kahirapan sa paghahanap ng stratehiyang optimal ay nagmumula mula sa pagiging marami ng mga posibleng galaw na tinatawag na mga larong kombinatoryal. Ang mga halimbawa nito ay kinabibilangan ng chess at go. Ang mga larong kinasasangkutan ng hindi perpekto o hindi kompletong impormasyon ay maaari ring magkaroon ng isang malakas na katangiang kombinatoryal halimbawa sa larong backgammon. Walang teoriyang nagkakaisa sa pagsagot mga elementong kombinaoryal sa mga laro. Gayunpaman, mayroon mga kasangkapang matematikal na maaaring lumutas ng mga problemang partikular at sumagot sa ilang mga pangkalahatang tanong.
Ang mga laro ng perpektong impormasyon ay pinag-aaralan sa teoriyang laro na kombinatoryal na umunlad sa mga nobelang representasyon, e.g. mga bilang na surreal gayundin din ang kombinatoryal at alhebraikong (at stratehiyang nagnanakaw ng argumento) mga paraang pagpapatunay upang lutasin ang mga ilang uri kabilang ang mga paikot ikot na mga laro na maaaring magresulta sa walang hangganang mahabang mga sekwensiya ng mga galaw. Ang mga pamamaraang ito ay sumasagot sa mga laro na mas mataas na kompleksidad na kombinatoryal kesa sa mga karaniwang itinuturing na tradisyonal o ekonomikong teoriya ng laro. Ang isang karaniwang laro na nalutas sa paraang ito ang hex. Ang isang kaugnay na larangan ng pag-aaral na humahango sa teoriyang komputasyonal na kompleksidad ang kompleksidad ng laro na nauukol sa pagtatantiya ng kahirapang komputasyonal ng paghahanap ng mga optimal na stratehiya.
Ang pagsasaliksik sa Intelihensiyang Artipisyal ay sumagot sa parehong perpekto at hindi perpektong (o hindi kompletong) mga larong impormasyon na may labis na masalimuot na mga istrakturang kombinatoryal (tulad ng chess, go o backgammon) kung saan walang mapapatunayang mga stratehiyang optimal ang natagpuan. Ang mga praktikal na solusyon ay kinasasangkutan ng mga komputsasyonal na heuristika tulad ng pagtatabas na alpha-beta o paggamit ng artipisyal na neural network na sinanay ng pagpapapalakas na pagkatuto (reinforcement learning) na gumagawa sa mga larong mas mapangasisiwaan sa pagsasanay na pagkukuwenta.

Walang hangganang mahabang mga laro

Ang mga laro kung paanong pinag-aaralan ng mga ekonomista at mga manlalaro ng larong tunay na daigdig ay pangkalahatang nagtatapos sa may hangganang maraming mga galaw. Ang purong matematika ay hindi labis na tinatakdaan at ang mga teorista ng hanay sa partikular ay nag-aaral ng mga laro na tumatagal sa walang hangganang maraming mga galaw na ang ang nanalo (o iba pang kabayaran) ay hindi alam hanggang pagkatapos na lahat na ang mga galaw ay nakumpleto. Ang pokus ng atensiyon ay karaniwang hindi labis sa kung ano ang pinakamahusay na paraan na maglaro ng gayong laro ngunit simpleng kung ang isa o iba pang manlalaro ay may mananalong stratehiya. Maaaring patunayan gamit ang aksiyoma ng pagpili na mayroong mga laro kahit sa perpektong impormasyon at kung ang tanging mga kalalabasan ay panalo o talo kung saan wala sa mga manlalaro ang may stratehiyang mananalo. Ang pag-iral ng gayong mga stratehiya para sa matalinong dinisenyong mga laro ay mahalagang mga konsekwensiya sa teoriyang deskriptibong hanay.

Mga larong diskreto at tuloy tuloy

Ang karamihan ng teoriya ng laro ay nauukol sa may hangganan, diskretong mga laro na may hangganan bilang ng mga manlalaro, galaw, pangyayari, kalalabasan etc. Gayunpaman, maraming mga konsepto ay maaaring palawigin. Ang mga larong tuloy tuloy ay pumapayag sa mga manlalaro na pumili ng isang stratehiya mula sa isang hanay ng tuloy tuloy na stratehiya. Halimbawa, ang kompetisyong Cournot ay karaniwang minomodelo na ang mga stratehiya ng mga manlalaro ay anumang hindi negatibong mga kantidad kabilang ang mga praksiyonal na kantidad.

Mga larong diperensiyal

Ang mga larong diperensiyal gaya ng tuloy tuloy na larong pagpupursige at pagtakas ay mga larong tuloy tuloy kung saan ang ebolusyon ng mga bariabulo ng estado ng mga manlalaro ay pinangangasiwaan ng mga ekwasyong diperensiyal. Ang problema ng paghahanap ng optimal na stratehiya sa isang larong diperensiyal ay malapit na kaugnay ng teoriyang optimal na kontrol. Sa partikular, mayroon dalawang uri ng mga stratehiya: ang stratehiyang bukas na loop ay matatagpuan gamit ang prinsipyong maksimum ni Pontryagin samantalang ang mga stratehiyang saradong loop ay matatagpuan gamit ang paraang ekwasyong Hamilton-Jacobi-Bellman.
Ang isang partikular na kaso ng mga larong diperensiyal ang mga laro na may randomang horison ng panahon. Sa gayong mga laro, ang terminal na panahon ay isang randomang bariabulo na may ibinigay na punsiyong distribusyong probabilidad. Kaya ang mga manlalaro ay nagmamaksima ng ekpektansiyang matematikal ng punsiyong gastos. Ipinakita na ang binagong problemang optimisasyon ay maaaring muling ipormula bilang isang diniskwentong larong diperensiyal sa loob ng isang walang hangganang panahong interbal.

Mga larong maraming-manlalaro at populasyon

Ang mga larong may arbitraryo ngunit may hangganang bilang ng mga manlalaro ay kadalasang tinatawag na mga larong n-tao. Ang teoriyang evolusyonaryong laro ay tumuturing sa mga larong kinsasangkutan ng isang populasyon ng mga tagagawa ng desisyon kung saan ang prekwensiya kung saan ang isang partikular na desisyon ay ginawa ay maaaring magbago sa loob ng panahon bilang tugon sa mga desisyong ginawa ng lahat ng mga indibiwal sa populasyon. Sa biolohiya, ito ay nilalayon mag-modelo ng biolohikal na ebolusyon kung saan ang ang nakaprogramang henetikong organismo ay nagpapasa kasama ng kanilang mga pagpoprogramang stratehiya sa kanilang mga supling. Sa ekonomika, ang parehong teoriya ay nilalayon na bumihag ng mga pagbabago sa populasyon dahil ang mga tao ay gumagampan ng papel sa laro ng maraming mga beses sa loob ng kanilang panahon ng buhay at may kamalayang (at marahila ay makatwiran) na naglilipat ng mga stratehiya.

Mga kalalabasang stokastiko (at relasyon sa ibang mga larangan)

Ang mga problema ng indibidwal na desiyon na may mga kalalabasang stokastiko ay minsang itinuturing na mga larong isang manlalaro. Ang mga sitwasyong ito ay hindi itinuturing na larong teoretikal ng ilang mga may akda. Ang mga ito ay maaaring imodelo gamit ang mga parehong kasangkapan sa loob ng mga kaugnay na disiplina ng teoriyang desisyon, mga operasyong pagsasaliksik, at mga area ng Intelihensiyang Artipisyal, partikular na ang pagpaplanong AI (na may kawalang katiyakan) at sistemang maraming ahente. Bagaman ang mga larangang ito ay may iba't ibang mga motibator, ang matematika na nasasangkot ay malaking pareho, e.g, gamit ang mga prosesong desisyong Markov (MDP). Ang mga kalalabasang stokastiko ay maaari ring imodelo sa mga termino ng teoriya ng laro sa pamamagitan ng pagdaragdag ng isang randomang umaasal na manlalaro na gumagawa ng mga "galaw na tsansa" na tinatawag ring galaw sa kalikasan. Ang manlalarong ito ay hindi karaniwang itinuturing na ikatlong manlalaro na kundi isang larong dalawang manlalaro ngunit tanging nagsisilbi upang magbigay ng pagikot ng dice kung inaatasan ng laro. Para sa ilang mga problema, ang ilang mga pakikitungo sa pagmomodelo ng mga kalalabasang stokastiko ay maaaring tumungo sa iba't ibang mga solusyon. Halimbawa, ang pagkakaiba sa pakikitungo sa pagitan ng MDP at solusyong minimaks ay ang huli ay tumuturing sa kasong masahol kesa sa hanay ng mga galaw adbersaryal kesa sa pangangatwiran sa ekspektasyon tungkol sa mga galaw na ito sa ibinigay na nakapirmeng distribusyong probabilidad. Ang pakikitungong minimaks ay maaaring mapakinabangan kung saan ang mga modelong stokastiko ay hindi makukuha ngunit maaaring labis na magtantiya ng labis na hindi malamang (ngunit magastos) na mga pangyayari na dramatikong umiimpluwensiya sa stratehiya sa gayong mga eksena kung ipinagpapalagay na ang kalaban ay magpupwersa ng gayong pangyayari. Ang mga pangkalahatang modelo na kinabibilangan ng lahat ng mga elemento ng kalalabasang stokastiko, mga kalaban at parsiyal o maingay na obserbabilidad (ng mga galaw ng ibang mga manlalaro) ay pinag-aralan rin. Ang pamantayang ginto ay itinuturing na parsiyal na mapagmamasdang larong stokastiko (POSG) ngunit kaunting mga problemang realistiko ay magagawang komputasyonal sa representasyong POSG.

Mga metalaro

Ito ang mga laro na ang laro ay isang pag-unlad ng mga patakaran ng isa pang laro na pinupuntirya o paksang laro. Ang metalaro ay naghahangad na imaksima ang halagang utilidad ng hanay ng patakaran na binuo. Ang teoriya ng mga metalaro ay kaugnay ng teoriyang disenyong mekanismo. Ang terminong analisis ng metalaro ay ginagamit rin upang tukuyin ang isang praktikal na pakikitungong binuo ni Nigel Howard kung saan ang sitwasyon ay binalangkas bilang isang larong stratehiko kung saan ang mga may hawak ng taya ay sumusubok na tuparin ang kanilang mga layunin sa pamamagitan ng mga opsiyon makukuha nila. Ang mga kalaunang pag-unlad ay tumungo sa pormulasyon ng analisis ng konprontasyon.