Esmakordselt avaldatud Wed 14. juuni 2017; sisuline läbivaatamine teisipäev, 1. august 2017
Selles sissejuhatuses käsitletakse matemaatiliste keelte kasutamist võimu formaalsete omaduste väljendamiseks ja analüüsimiseks tavalistes mängudes. Selles sissekandes käsitletud matemaatilisi keeli nimetatakse loogikaks ja liigitatakse vastavalt nende võimele mänguga seotud mõisteid väljendada.
Selle sissekande materjal piirdub üksikisikute (rühmade) strateegiate ja eelistuste loogilise analüüsiga tavalistes mängudes. See ei hõlma mänguteooria kasutamist loogiliste keelte uurimisel ega episteemiliste mõistete rolli strateegilistes otsustes. Samuti ei hõlma see järjestikuste otsuste tegemise aspekte, mis on tüüpilised strateegilistele mõttekäikudele laiades mängudes. Nende kohta võib leida vastava sisestuse loogika ja mängud, mänguteooria episteemilised alused (vt ka van Benthem, Pacuit, & Roy 2011 ja van Benthem 2014).
1. Normaalsete vormimängude loogika
2. Põhikoostisosad
2.1 Eelistused
2.2 Valikud
3. Võimsuse analüüsimine
3.1 Koostöömängud ja nende loogika
3.2 Strateegilised mängud ja nende loogika
3.2.1 Mittemonotoonne tegevusloogika
3.2.2 Loogikapõhised mängud
4. Järeldused: analüüsi õigel tasemel
Bibliograafia
Akadeemilised tööriistad
Muud Interneti-ressursid
Seotud kirjed
1. Normaalsete vormimängude loogika
(Tavaline-vorm) mäng on matemaatiline kirjeldus suhe kogum üksikisikute (või üksikisikute rühmad) ja komplekt potentsiaali tulemusi. Inimesed valivad iseseisvalt ja samaaegselt tulemuste alamhulga, kusjuures lõpptulemus valitakse iga valiku kombinatsiooni hulgast. Sõltumatult tähendab, et üksikisikute valikud ei mõjuta üksteist. Samaaegselt tähendab see, et iga inimese valikud tehakse mitte teiste mängijate valikuid teades. Eeldatakse, et iga inimene eelistab tulemuste kogumit, st talle meeldivad mõned tulemused rohkem kui teised ja tavaliselt eeldatakse, et ta teab teiste inimeste võimalikke valikuid ja eelistusi, kohandades oma otsuseid vastavalt.
Mänge kasutatakse igasuguste olukordade modelleerimiseks, alates loomade käitumisest kuni rahvusvaheliste konfliktide lahendamiseni (Osborne & Rubinstein 1994). Selle kande jaoks on kasulik rakendus kollektiivsete otsuste tegemine, mille üheks näiteks on toimiv näide.
Näide 1: (Rooma leping)
Rooma lepinguga (1958–1973) loodi Euroopa Majandusühendus. Asutamislepingu artikli 148 kohaselt on nende vastuvõtmiseks vajalikud nõukogu (üks peamisi seadusandlikke institutsioone) aktid:
12 häält (kui õigusakti tegi ettepaneku komisjon) või
12 häält vähemalt 4 liikmesriigilt (kui õigusakti ei teinud komisjon ettepanekut).
Ülaltoodud väärtused viitavad EL-6-le, asutajaliikmetele. Lepingus jagati hääled järgmiselt:
4 häält: Prantsusmaa, Saksamaa, Itaalia;
2 häält: Belgia, Holland;
1 hääl: Luksemburg.
Seda stsenaariumi saab kirjeldada kui mängu.
Mängijaid on kuus, riigid:
Prantsusmaa, Saksamaa, Itaalia, Belgia, Holland ja Luksemburg.
Nad hääletavad korraga ühel teemal. Küsimused võivad olla binaarsed, nt piirikaitseskeemi vastuvõtmine, või mitme väärtusega teemad, nt mitu miljonit tuleks kulutada piirikaitsekava vastuvõtmisele.
Riikidel võivad olla eelistused hääletamise tulemuse või isegi teiste riikide konkreetse hääletuse suhtes ning tavaliselt hääletavad nad ilma, et nad teaksid, kuidas teised on hääletanud.
Sageli on need mängud sellised, et ükski osaleja ei suuda üksi lõplikku tulemust otsustada, kuid mõnel juhul võiksid nad teha koostööd ja leppida kokku ühises strateegias.
Sõltuvalt mängijate eelistustest, teadmistest ja võimalustest valitakse tõenäolisemalt mõni tulemus. Milliste mõistmiseks on mängude teooria välja töötanud lahenduste kontseptsioonid, mis funktsioneerivad formaalselt mängude komplektist kõigi nende mängude tulemuste komplektini, mis kirjeldavad mängijate ratsionaalsust matemaatiliselt. Nagu hiljem näeme, saab lahenduskontseptsioone lühidalt väljendada lihtsas ja hästi käituvas loogikas.
Järgnevalt kirjeldame mänge kui matemaatilisi struktuure, rõhutades erinevaid põhikomponente (nt koalitsioonide moodustamise võimalust, võimalust võtta vastu otsuseid õigel ajal jne) ja nende väljendamiseks kõige paremini sobivaid keeli.
2. Põhikoostisosad
Formaalselt koosnevad mängud piiratud hulgast mängijatest (N = {1,2, \ ldots, n }) ja võimalikust lõpmatust tulemuste komplektist (W = {w_1, w_2, \ ldots, w_k, \ ldots }).
Näide 2: Ülaltoodud näites on mängijateks N {Prantsusmaa, Saksamaa, Itaalia, Belgia, Holland, Luksemburg}. Kui kaalume piiri kaitseskeemi vastuvõtmist, on sellel kaks tulemust: jah ja ei, st (W = { mbox {jah, ei} }). Kui arvestada selle asemel piirikaitseskeemidele kulutatud miljonite probleemidega, võib tulemuste piir olla lõpmatu, st (W = { textrm {0M}, \ textrm {1M}, \ textrm {2M}, \ ldots }). Võimalik on saada tulemuste kogumit, mida veelgi täpsustatakse, näiteks täpsustades mängijate hääletamise viisi. Sel juhul oleks tulemus, kus Prantsusmaa hääletab jah, teised hääletavad ei, ja tulemus on ei, erinev sellest, kui Itaalia hääletab jah, teised hääletavad ei, ja tulemus on ei, ehkki hääl on sama. Oluline on rõhutada, et iga tulemuste komplektiga kaasneb kirjeldus, mis toimub taustal toimuvas interaktsioonis. Puudub a priori õige või vale kirjelduse tase, valik sõltub selle mängu omadustest, mis sind huvitab.
Mängijate ja tulemuste kõrval on mängudel veel kaks suhet:
eelistus seoses tähistatakse (succeq), mis kirjeldab mängijad eelistuste üle tulemusi;
meetmeid seoses tähistatakse (E), milles kirjeldatakse tulemusi, et mängijad või rühmad mängijad suudavad kehtestada või vastupidi, välistama;
Oluline seos mängudes on teadmine, mis kirjeldab ametlikult seda, mida mängijad mängust ja vastastest teavad. Seda seost antakse mõnikord selgesõnaliselt, teised ajad kaudselt. See sissekanne ei muuda suhet selgeks, vaid lisab selle pigem mängijate ratsionaalsuse vormistamisele.
Nii eelistus kui ka tegevussuhted koguvad individuaalsete suhete peresid, üks mängija kohta. Näiteks eelistussuhe jaguneb perekonnaks ({ õnnestq_i } _ {i \ in N}), kirjeldades tulemuste eelistamist iga üksikisiku jaoks, samas kui toimingusuhe kogub perekonda ({E_C } _ {C \ subseteq N}) kirjeldab igaüks, mida konkreetne mängijate rühm võib saavutada.
Üldiselt võib mängu pidada matemaatiliseks struktuuriks
[(matemaatiline {N}, W, \ õnnestunud, E))
kus (matemaatiline {N}) on mängijate komplekt, tavaliselt piiratud, (W) tulemuste komplekt, (õnnestq) eelistussuhe ja (E) toimingusuhe.
Seda matemaatilist struktuuri tuntakse ka relatsioonilise struktuurina (Blackburn, Rijke ja Venema 2001), mis on nn modaalloogika setteoreetiline ekvivalent (Blackburn et al. 2001), matemaatiline keel, mis sobib hästi väljendada suhete matemaatilisi omadusi. Relatsioonistruktuuri tähistatakse edaspidi (F), mis tähistab kaadrit.
Viimane koostisosa, mida me relatsioonistruktuuride ja modaaloogika ühendamiseks vajame, on aatomipositsioonide aatomite kogumi spetsifikatsioon, mis väljendab meid huvitavate tulemuste asjakohaseid omadusi. Seda komplekti peetakse tavaliselt loendamiseks [1] ja seostatakse tulemustega hindamisfunktsiooni, st vormi funktsiooni abil
[V: W \ kuni 2 ^ \ texttt {aatomid})
seostades iga tulemusega pakkumise aatomite komplekti, mis on selle tulemuse puhul tõsi.
Paari ((F, V)) nimetatakse mudeliks, mida tähistatakse kui (M).
Mängustruktuuri suhteid üksikute mängijate (ja rühmade) suhtes kirjeldatakse ametlikult seoses peamise modaalloogikaga, mida kasutatakse nende omaduste väljendamiseks, kirjelduse ja detailsuse erinevatel tasemetel.
Järgmises lõigus on kokku võetud tehnilised taustmõisted, mida on vaja selles sissekandes kasutatud moodi keelte tõlgendamiseks. Modaalloogikaga juba tuttav lugeja võib selle vahele jätta. Põhjalikumaks uurimiseks võite tutvuda vastava sissejuhatusega modaalloogika kohta (Garson 2014). Tuntud klassikalised õpikud on Modal Logic: An Introduction (Chellas 1980), mis keskendub mitte-normaalsele modaalloogikale, ja Modal Logic (Blackburn jt 2001), mis keskendub selle asemel normaalse modaalloogika matemaatilisemale käsitlemisele. [2]
Modal Logic: tausta mõisted: modaalne loogika on jätk keeles loogika komplekt ümbersuunatud operaatorid (Box_1 \ ldots \ Box_n \ ldots), mis on defineeritud loendatavaks kogum aatomi ettepanekud (texttt {aatomid} = {p_1, p_2, \ ldots }), mille peale hästi moodustatud valemite komplekt on induktiivselt üles ehitatud (loogika ja induktsiooni matemaatiliseks käsitlemiseks vt näiteks Dalen 1980). Iga modaalkeele ((matemaatiline {L})) hästi formuleeritud valem (varphi), mida edaspidi nimetatakse lihtsalt valemiks, konstrueeritakse järgmise grammatika abil:
kus (Box_i \ in { Box_1, \ ldots, \ Box_n, \ ldots }) and (p \ in \ texttt {Atoms}).
Selle keele mudeliks on struktuur (M = ((W, R_1, \ ldots, R_n, \ ldots), V)), mis koosneb maailmade või olekute või tulemuste kogumist (W); kättesaadavus seoses (R_i) iga modaalne operaator (Box_i), mis on määratletud kaudu nn naabruses funktsioone (Chellas 1980), st funktsioonid (R_i: W \ 2 ^ {2 ^ {W}}); ja hindamisfunktsioon (V: \ texttt {Aatomid} kuni 2 ^ {W}), mis määrab igale aatomi pakkumisele alamhulga (W), ideega, et iga aatomi pakkumine on määratud komplektiga maailmadest, kus see väide on tõene.
Üldiselt tähistatakse mitmeliigilist keelt koos modaalsustega (Box_1),…, (Box_n),… tähega (matemaatiline {L} ^ {f (Box_1), \ ldots, f (Box_n), \ ldots}), kus funktsioon (f) seostab iga modaalsusega selle intuitiivse stenogrammi. Olgu (Delta) modaalkeel, mis koosneb modaalsustest (Box_1),…, (Box_n),… ja las (M = ((W, R_1, \ ldots, R_n, \ ldots)), V)) olla selle keele eeskuju. Rahulolu seoses valemi (varphi \ in \ Delta) suhtes paari ((M, w)), kus (w \ W), defineeritakse vastavalt järgmisele tõtt tingimustele:
) alusta {joonda *} M, w & \ mudelid p & \ mbox {ainult siis, kui} & w \ V (p) \ M, w & \ mudelid \ neg \ varphi & \ mbox {ainult siis, kui } Ja M, w \ ei \ mudelid \ varphi \\ M, w & \ mudelid \ varphi \ land \ psi & \ mbox {ainult siis, kui} & M, w \ mudelid \ varphi \ mbox {ja} M, w \ mudelid \ psi \\ M, wy & \ mudelid \ Box_i \ varphi & \ mbox {ainult siis, kui} & \ varphi ^ M \ R_i (w) \ \ end {joondada *})
kus (varphi ^ {M} = {w \ W \ mid M, w \ mudelite \ varphi }) nimetatakse tõtt set või pikendamise kohta (varphi).
Modaalkeele valem (varphi) ((Delta)): hoiab mudeli (M) olekus (w) alati, kui (M, w \ mudelid \ varphi); on kehtiv mudelis (M), mida tähistatakse (models_ {M} varphi), siis ja ainult siis, kui (M, w \ mudelite \ varphi) iga (w \ W), kus (W) on (M) domeen; on kehtiv klassi mudelite (mathcal {M}), mida tähistatakse (mudelid _ { mathcal {M}} varphi), siis ja ainult siis, kui see kehtib iga (M \ in \ mathcal {M}); on kehtiv raami ({F}), mida tähistatakse (mudelid _ {{F}} varphi), siis ja ainult siis, kui iga hindamise (V) meil on see (mudelid _ {(F, V)} varphi); on kehtiv klassi raamid (matemaatiline {F}), tähistatud (mudelid _ { matemaatiline {F}} varphi), ja ainult siis, kui see kehtib kõigis (F \ \ mathcal {F}).
(Delta) valemite komplekt, mis kehtib mudeliklassis (matemaatiline {M}), on tähistatud (Delta _ { matemaatiline {M}}) (kaadrite jaoks on tähis (Delta _ { matemaatiline {F}})). Valemite komplekti (Sigma) jaoks kirjutame (M, w \ mudelid \ Sigma), et öelda, et (M, w \ mudelid \ sigma), kõigi (sigma \ in Sigma). Me ütleme, et valemite komplekt (Sigma) tähendab semantiliselt valemit (varphi) mudeliklassis (matemaatiline {M}), tähistatud (Sigma \ mudelid _ { matemaatiline {M }} varphi), kui iga (M \ in \ matemaatilises {M}) puhul on meil see (models_ {M} Sigma) tähendab (models_ {M} varphi).
Modaalne reegel
) frac { varphi_1, \ ldots, \ varphi_n} { psi})
on heli mudeliklassis (matemaatiline {M}), kui (varphi_1, \ ldots, \ varphi_n \ mudelid _ { matemaatiline {M}} psi).
Tuletame meelde pärast Chellast (1980), et modaalset loogikat (Delta) nimetatakse klassikaliseks, kui see on suletud samaväärsuse reegli alusel, st iga (Box) keeles (Delta) meil on:
Seda nimetatakse monotooniliseks, kui see on klassikaline ja pealegi on see monotoonsuse reegli kohaselt suletud, st iga (kasti) jaoks meie keeles (delta):
Seda nimetatakse normaalseks, kui see on monotoonne, on see suletud üldistusreeglite kohaselt ja sisaldab (K) aksioomi, st iga (Box) valemi jaoks meie jaoks ((Delta))
) frac { varphi} { Box \ varphi})
ja (Delta) sisaldab (Box (varphi \ kuni \ psi) kuni (Box \ varphi \ kuni \ Box \ psi)).
Tavalist modaalloogikat saab tõlgendada kujul struktuurides (M = ((W, R'_1, \ ldots, R'_n, \ ldots), V))), kus iga (R'_i) on põhifilter [3] või teise võimalusena see on kujul (R'_i: W \ kuni 2 ^ {W}).
2.1 Eelistused
Tuletage meelde relatsioonistruktuur ((matemaatiline {N}, W, \ õnnestq, E)) ja kaaluge seost (õnnestq). See suhe tähistab kompaktselt individuaalsete eelistuste suhete rühma ({ õnnestq_i } _ {i \ in N}), millest igaüks on mängijaga indekseeritud.
Formaalselt on mängija (i) eelistamine suhe
) õnnestq_i \ subseteq W \ korda W)
Idee on see, et kui kaks tulemust (w) ja (w ') on sellised, et ((w, w') sisse \ õnnestq_i), arvestab mängija (i) tulemust (w) vähemalt sama hea kui tulemus (w '). Fakt, et ((w, w ') sisse \ õnnestq_i) lühendatakse (w \ õnnestq_i w'). Selle pöördvõrdeline suhe on (preceq_i), mis kehtib ((w, w ')) jaoks alati, kui (w' \ õnnestq_i w). Selle range vaste on suhe (succ_i), mis kehtib ((w, w ')) jaoks alati, kui (w \ õnnestq_i w'), ja see ei ole nii, et (w '\ õnnestq_i w). Lisaks tähistab (w \ sim_i w ') asjaolu, et (w \ õnnestq_i w') ja (w '\ õnnestq_i w), mis tähendab, et (i) on (w) ja (w ').
Näide 3:Läheme tagasi oma peamise näite juurde. Tavaliselt on riikidel eelistused otsuse tulemuste ees, nt Itaalia arvab, et kava jaoks peaksime kulutama 5–10 miljonit eurot, Saksamaa arvab, et peaksime kulutama 1–2, Belgia 4–5, Luksemburg, Holland ja Prantsusmaa täpselt 5. See tähendab näiteks, et Itaalia eelistussuhe on selline, et (w \ succ _ { textrm {Italy}} w ') alati (textrm {5M} leq w \ leq \ textrm {10M}) ja kas (w '> \ textrm {10M}) või (0 \ leq w' \ textrm {10M}) või (0 \ leq w '<\ textrm {5M}), (w \ succ _ { textrm {Italy}} w ') alati, kui (textrm {5M} leq w' <w \ leq \ textrm {10M}) samas (w \ sim _ { textrm {Italy}} w '), vastasel juhul. Mitte kõik hääletustulemused ei jõua kokkuleppele. Seejärel määratleme tehnilistel eesmärkidel lisatulemuse (w ^ {d}),tõlgendatakse lahkarvamuse tulemusena. Mõte on selles, et see on hääletuse tulemus, mis ei saavuta üksmeelt. Eeldame, et mis tahes kokkulepe on mängija jaoks rangelt parem kui erimeelsused, st (w \ succ _ {{i}} w ') alati, kui (w' = w ^ {*}) ja (w \ neq w ^ {*}) iga (i \ sisse N).
Nende suhete omadusi saab väljendada modaalloogika abil. Selleks tutvustame iga vastava modaaloperaatori (Teemant ^ { preceq} _i), (Teemant ^ { prec} _i) ja (Teemant ^ { sim} _i) jaoks iga vastava suhted.
(R \ in { preceq, \ prec, \ sim }) tõlgendus on järgmine:
[M, w \ mudelid \ Teemant ^ {R} _i \ varphi \ enskip \ mbox {ainult siis, kui} enskip M, w ^ { prime} mudelid \ varphi, \ mbox {mõne jaoks} w ^ { prime} mbox {koos} w R_i w ^ { prime})
Vaadeldavatel suhetel on sageli lisaomadusi. Näiteks loetakse (preceq_i) tavaliselt järgmisteks:
refleksivus st. (forall w \ W, i \ N,), meil on see: (w \ preceq_i w);
transitiivsus st. (forall w_1, w_2, w_3 \ in W, i \ in N,) on meil olemas: ((w (w_1 \ preceq_i w_2) ja (w_2 \ preceq_i w_3)) tähendab, et (w_1 \ preceq_i w_3).
ühenduvus, st (kõik w_1, w_2 \ W, i \ N,), on meil olemas: kas (w_1 \ preceq_1 w_2) või (w_2 \ preceq_i w_1).
Esimese kahe omaduse võib iseloomustada normaalses modaalne loogika ühe modaalne operaator per mängija abil järgmise aksioomidel ja kehtivusaegadest.
Kuid ühenduvuse osas see nii ei ole, kuna sellised modaalkeeled võivad rääkida ainult suhete kohalikest omadustest (Blackburn jt 2001).
Selleks peame tutvustama eritüüpi operaatoreid: universaalset (või globaalset) modaalsust (Goranko & Passy 1992). See modaalsus väljendab mudeli (M) domeeni (W) kõigi olekute omadusi ja seda tõlgendatakse järgmiselt.
[M, w \ mudelid A \ varphi \ enskip \ mbox {ainult siis, kui} enskip M, w ^ { prime} mudelid \ varphi, \ mbox {kõigi jaoks} w ^ { prime} W)
Valem (neg A \ neg \ varphi) lühendatakse (E \ varphi). Sümbol (E) on (A) eksistentsiaalne duble ja see näitab, et teatav valem on mudeli mingis olekus. Globaalse modaalsusega on meil tõeliselt lisatud ekspressiivsus (koos täiendavate kulude ja edasise kasuga, nagu on näidatud Goranko & Passy 1992), seetõttu saame mudeli kehtivust väljendada tõe väljendamise kaudu maailmas, olla tunnistajaks tõsiasjale, et (M, w \ mudelid A \ varphi) kehtib ainult siis, kui (mudelid_M \ varphi).
Tuletage meelde, et seos (R) on keerukas, kui ja ainult siis, kui kõigi (x, y \ jaoks W) korral on tegemist kas (xRy, yRx) või (y = x). Järgmise kaadriavalduse saamiseks saame kasutada eelistuste ja globaalsete modaalsuste kombinatsiooni.
Ettepanek 2 Laske (F) olla raam. Meil on see:
(mudelid_F (varphi \ kiil \ Box ^ { preceq} _i \ psi) kuni A (psi \ vee \ varphi \ vee \ Diamond ^ { preceq} _i \ varphi)) ainult siis, kui (preceq_i) on keerukas
Alternatiivne ja võimalik, et intuitiivsem valem, mida saab selle asemel kasutada, on (p, q) aatomisavaldused:
[E p \ maa E q \ kuni E (p \ maa q) lor E (p \ maa \ Teemant ^ { preceq} _i q) lor E (q \ maa \ Teemant ^ { preceq} _i p))
(Preceq_i) trihhotoomia, transitiivsus ja refleksiivsus on võrdsed sellega, et seos on nõrk lineaarne järjekord ja on seega ühendatud.
Seost (prec_i), st range eelistuse seost, saab määratleda järgmiselt: (preceq_i). Kuid (prec_i) vastab järgmisele omadusele:
ebarefleksivsus, st (forall w \ in W, i \ in N,) meil on see: ei ole nii, et (w \ prec_i w)
Liigne paindlikkus ei ole modaalloogikas määratletav (Blackburn jt 2001). Kui aga aatomisündmused on piisavalt võimsad, et iga tulemus eraldi eristada, muutub ebarefleksivsus määratletavaks. Näiteks olgu (w_k) muutuja, mis identifitseerib maailma (w_k). [4] Meil on järgmised.
Lõpuks rahuldab ükskõiksuse suhe (sim) refleksiivsuse, transitiivsuse ja sümmeetria omadusi. Kui refleksiivsust ja transitiivsust määratletakse analoogselt varasema modaalsusega, määratletakse sümmeetria järgmiselt.
sümmeetria, st, (forall w_1, w_2 \ W, i \ in N,) meil on see: (w_1 \ sim_i w_2) tähendab, et (w_2 \ sim_i w_1)
Kui kahe esimese aksioomid on sarnased (preceq_i) aksioomidega, iseloomustatakse sümmeetriat järgmiselt
Kolm ülaltoodud omadust ütlevad koos, et iga (sim_i) on matemaatiliselt ekvivalentsussuhe, st suhe, mis
) bigcup_ {w \ sisse W} {[w] keset w '\ kausta [w] mbox {alati} w \ sim_i w' })
on (W) partitsioon. Selle partitsiooni iga element on mängija (i) ükskõiksuse klass, st tulemuste kogum, mille suhtes ta on ükskõikne.
Samaväärsussuhete loogikat, nagu (sim_i), tuntakse ka kui ({ bf S5}) süsteemi.
Eelistused ja utiliidid Kuna mängude teoorias on neid laialdaselt kasutatud, on oluliseks eelistussuhete klassiks need, mis vastavad numbrilistele väärtustele või utiliidifunktsioonidele.
Kasulikkusfunktsiooniga on funktsioon
[u_i: W \ paremnool \ mathbb {R})
tulemuste kaardistamine reaalarvudega, mis näitab, kui palju mängija väärtustab teatud olekut.
Definitsioon 5 Olgu (u) utiliidifunktsioon. Me ütleme, et (õnnestq ^ * _ i) vastab (u), kui kehtib järgmine:
[w \ õnnestq ^ * _ i w '\ enskip \ textrm {ainult siis, kui} enskip u_i (w) geq u_i (w'))
Pange tähele, kuidas iga nõrk lineaarne järjekord piiratud tulemuste komplekti korral vastab mingile kasuliku funktsioonile.
Eelistuste rolli üksikasjalikumaks analüüsimiseks filosoofias ja otsuste teoorias viidatakse seotud eelistuste (Hansson & Grune-Yanoff 2011) ja otsusteooria (Steele & Stefansson 2015) sissekannetele.
2.2 Valikud
Mäng on ka kirjeldus sellest, mida mängijad saavad ise saavutada või koalitsioonides saavutada. Selle vormistamiseks kasutame efektiivsuse funktsioone, abstraktset võimumudelit, mis tutvustati komisjonides hääletamisstrateegiaid (Moulin & Peleg 1982).
Mõjusust funktsiooni (Moulin & Peleg 1982) on funktsioon
[E: 2 ^ {N} kuni 2 ^ {2 ^ {W}})
iga mängijarühmaga tulemuste komplekti seostamine.
Mõte on selles, et kui on nii, et (X \ sisse E (C)), saab koalitsioon (C) otsustada, et mängu tulemus jääb komplekti (X), ja võib seetõttu välistada tulemuste (W \ setminus X) valimise lõpuks. Teisisõnu: (X) on koalitsiooni võimuses (C).
Efektiivsuse funktsioonid suletakse alamhulkade all, st meil on see, et (X \ sisse E (C)) ja (X \ subseteq Y \ subseteq W) tähendavad, et (Y \ sisse E (C)). Teisisõnu, kui (X) on koalitsiooni (C) võimuses, siis on ka iga (X) supersetts. Siit järeldub, et kui teatud koalitsiooni efektiivsusfunktsioon ei ole tühi, sisaldab see alati kõigi tulemuste komplekti.
4. näide: pöördudes tagasi peamise näite juurde, mõelge iga riigi võimsusele. Mängureeglite tõttu pole ühelgi riigil üksi võimalust tulemusi välistada.
Tõhususfunktsioonide kasutamine: iga (i \ sisse N) puhul on meil see (E ({i }) = {W }).
See kehtib ka koalitsioonide kohta, mis pole piisavalt suured. Näiteks võta kõik vähemalt kahe riigi koalitsioonid, mis võivad moodustuda Hollandi, Belgia ja Luksemburgi vahel.
Kuna nende kogukaal on maksimaalselt 5 häält, ei suuda nad iseseisvalt leppida kokku ega välistada ühtegi võimalikku kokkulepet. Komisjoni ettepanekute puhul on tegelikult igal koalitsioonil (C), kelle häälekaal ei ole vähemalt 12, sama tõhususfunktsioon (E (C) = {W }).
Teiste koalitsioonide puhul on olukord erinev. Mõelgem näiteks Prantsusmaa, Saksamaa ja Itaalia sõlmitud koalitsioonile, millel on koos 12. hääleõigus. Nende jaoks on meil:
[E ({ textrm {Prantsusmaa, Saksamaa, Itaalia} }) = { {w } keskel \ \ W } ^ {+})
See tähendab, et kolm liiget saavad ise otsustada hääletamise tulemuse. See kehtib kõigi koalitsioonide kohta, mille hääleõigus on vähemalt 12.
Kuidas on lood õigusaktidega, mida komisjon ei ole välja pakkunud? Kasutagem nende jaoks erinevat efektiivsuse funktsiooni, mille märgistame (E ^ {*}).
Sel juhul peab võitnud koalitsioon koosnema vähemalt neljast liikmest.
Niisiis, (E ^ {*} ({ mbox {Prantsusmaa, Saksamaa, Itaalia} }) = {W }), samas kui (E ^ {*} ({) Prantsusmaa, Saksamaa, Belgia, Holland (}) = { {w } keskel w \ W } ^ {+}).
Üldiselt on see seisukohal, et (E (C) = E ^ {*} (C)) alati (| C | \ geq 4). Hääletusmängu omaduste tõttu on meil ka (E (C) = E ^ {*} (C)) alati (| C | \ leq 2). Erinevust teevad koalitsioonid suurusega 3: koos (E ^ {*}) ei suuda nad kunagi saavutada enamat kui ({W }), samas kui (E) saavad nad saavutada ({ {w } keskel w \ W } ^ {+}), kui nende hääleõigus on vähemalt 12. Pange tähele, et Luksemburg ei oma tähtsust komisjoni esitatud arvete osas, st (E (C) = E (C \ cup \ textrm {Luksemburg})). Nagu me täheldasime, ei kehti see teiste arvete puhul.
Efektiivsuse funktsioonide omadusi saab väljendada modaalloogikas. Selleks on oluline jälgida, et iga efektsusfunktsioon vastab (mitte-normaalsele) seosele relatsioonistruktuuris. See, mida efektiivsusfunktsioonid täidavad, on erilise naabrusstruktuuri esilekutsumine, mida me nimetame koalitsioonimudeliks.
Definitsioon 6 [koalitsioonimudelid] Koalitsioonimudel on kolmekordne ((W, E, V)), kus:
(W) on olekuteta olekute kogum;
(E: W \ longrrowar (2 ^ {N} longrrowar 2 ^ {2 ^ W})) on dünaamiline efektiivsuse funktsioon;
(V: W \ longrightarrow 2 ^ { texttt {Aatomid}}) on hindamisfunktsioon.
Nagu lugeja märkab, võimaldavad dünaamilised efektiivsuse funktsioonid igal riigil koalitsioonide vahel erinevat võimsuse jaotust. See on strictu sensu ebaoluline tavaliste mängude korral võimu käsitlemisel (punkt 3), kus tulemustega seotud efektiivsuse funktsioone võidakse samuti mudelis kõikjal võrdsustada, kuid mudel on piisavalt üldine, et käsitleda ulatuslikku ja korduvat interaktsioon, kus interaktsiooni järjestikune struktuur on selgesõnaliselt määratletud. Tavaliselt lühendame (E (w) (C)) kui (E_w (C)) või isegi (E (C)), kui need on kontekstist selged.
Koalitsioonimudelitest rääkimisel kasutatakse keelt Coalition Logic (Pauly 2001), mis on mitte-normaalne modaalne loogika mängijate rühmade valikute väljendamiseks. Koalitsiooniloogika on pakkumisloogika laiendus (| 2 ^ {N} |) vormi ([C]) modaalsustega, seega modaaloperaatorit indekseeritakse koalitsiooniga.
Vormi ([C] varphi) valemite rahulolu suhe paari (M, w) suhtes on määratletud järgmiselt:
[M, w \ mudelid [C] varphi \ enskip \ textrm {ainult siis, kui} enskip \ varphi ^ M \ E_w (C))
kus, (varphi ^ M = {w \ W-keskel M, w \ mudelid \ varphi }).
Intuitiivselt tähendab (varphi ^ M \ E_w (C)), et koalitsioon (C) on võimeline saavutama vara (varphi).
Kuna suverühmas suletust või tulemuse monotoonsust peetakse kõigi efektsusfunktsioonide omaduseks, kehtib Coalition Logicus monotoonsuse reegel, mis on seega monotoonne modaaloogika (Hansen 2003).
Monotoonsuse reegel on iga (C \ subseteq N) jaoks järgmine:
) fra { varphi \ kuni \ psi} {[C] varphi \ kuni [C] psi}
Intuitiivselt, kui (C) on võimeline saavutama (varphi) ja kui meil on see, et (varphi) tähendab (psi), siis on (C) võimeline saavutama ka (psi).
Võimsuse matemaatilised omadused Lisaks tulemuste monotoonsusele võib mängudes koalitsioonijõu modelleerimiseks vajalikuks pidada ka palju muid omadusi. Näiteks tõhususe funktsioonil on järgmised omadused:
elujõulisus, st (emptyset \ not \ sisse E (C)), iga (C \ subseteq N) jaoks;
ohutus, st (W \ sisse E (C)), iga (C \ subseteq N) jaoks;
korrektsus, st, (X \ E (C)) tähendab, et (ülejoonitud {X} mitte \ sisse lülitatud E (ülejooneline {C})), iga (C \ subseteq N, X \ subseteq W);
N -maksimaalsus, st (ületähendatud {X} sisse E (emptyset)) tähendab, et ({X} sisse E (N)) ja (X \ subseteq W);
ülitäpsus, st (X \ sisse E (C)) ja (Y \ sisse E (D)) tähendab, et (X \ kork Y \ E-s (C \ tass D)) iga (C), (D \ subseteq N), (C \ cap D = \ emptyset), (X, Y \ subseteq W);
koalitsiooni monotoonsus, st (X \ E (C)) tähendab, et (X \ sisse E (D)) iga (C \ subseteq D \ subseteq N), (X \ subseteq W);
hästi põhjendatud, st (X \ sisse E (N)) tähendab, et ({x } sisse E (N)), mõne (x \ sisse X), iga (X \ subseteq W).
Efektiivsuse funktsiooni nimetatakse mängitavaks (Pauly 2001), kui sellel on elujõulisus, turvalisus, N-maksimaalsus ja ülitäpsus. Seda nimetatakse tõeliselt mängitavaks (Goranko, Jamroga ja Turrini 2013), kui see on mängitav ja hästi põhjendatud. Pange tähele, et kui (W) on piiratud, saab efektiivsuse funktsiooni mängida ainult siis ja ainult siis, kui see on tõeliselt mängitav (Goranko jt 2013).
Tõeline mängitavus on efektiivsuse funktsioonide põhiline omadus ja see ühendab ühe võttega koalitsioonimängud ühe löögi strateegiliste mängudega, nagu hiljem selgub.
Näide 5: Meie töötava näite efektiivsuse funktsioonid on kõik tõeliselt mängitavad.
Naabruskonstruktsioonides on seosed teoreetiliste ja loogiliste omaduste vahel sageli vahetud ning standardseid vastavustulemusi kaadrite klassi ja naabrusfunktsioonide vahel (Chellas 1980) saab automaatselt kasutada koalitsiooniloogika jaoks.
Koalitsiooniloogika on tegelikult piisavalt väljendusrikas, et iseloomustada kõiki seni mainitud piiranguid.
Lause 7 Olgu (F = (W, E)) koalitsiooniraam ja (C, C ^ { prime}, C '') oleksid koalitsioonid, nii et (C \ cap C '= \ emptyset) ja (C \ subseteq C ''). Järgmised tulemused:
(mudelid_F [C] varphi \ to \ neg) ületähtsustatud {C}] neg \ varphi) ainult siis, kui (E) on korrapärane;
(mudelid_F [C] top) ainult siis, kui (E) on ohutu;
(mudelid_F [C] varphi \ kuni [C ''] varphi) ainult siis, kui (E) on koalitsioon monotooniline;
(models_F \ neg [C] bot) ainult siis, kui (E) on elujõuline;
(mudelid_F \ neg) emptyset] neg \ varphi \ kuni [N] varphi) ainult siis, kui (E) on N-maksiimne;
(mudelid_F [C ^ { prime}] varphi \ kiil [C] psi \ kuni [C ^ { prime} cup C] (varphi \ kiil \ psi)) ainult siis, kui (E) on superaditiivne;
(varphi \ kuni \ psi \ mudelid_F [C] varphi \ kuni [C] psi) ainult siis, kui (E) on tulemuseks monotoonne.
Tõendite saamiseks pöörduge Pauly 2001 poole.
Kirjavahetuse tulemused võimaldavad meil modaalsete vahendite abil eristada arvukalt kaadriklasse. Kuid transpordiliikide operaatorite ekspressiivsus piirab tugevalt keele oskust eristada klasside struktuure. Selles osas peaks lugeja tähele panema, et nii mängitavate kui ka tõeliselt mängitavate efektsusraamide loogika jagab tõsiasja, et (models_F) emptyset] top). Kuid see väide, mille tõlgendus on, et iga (w \ W, {W } E_w (emptyset)) puhul ei ole piisav, et teha ametlik vahet (E_w (emptyset)) vahel efektiivsuse funktsioonide kahes erinevas klassis.
Järgnev tulemus ütleb meile, et ka koalitsiooniloogika on piisavalt hea, et arutada tõeliselt mängitavate efektsusfunktsioonide üle (või kui eelistate, siis nõrgaks eristada).
Teoreem 8 (Goranko jt 2013) Olgu (matemaatiline {P}) mängitavate kaadrite klass ja (matemaatiline {P} ^ {*}) tõeliselt mängitavate kaadrite klass. Siis iga koalitsiooniloogika valemi (varphi) jaoks
See tuleneb asjaolust, et mängitaval koalitsiooniloogikal on piiratud mudeli omadus (Pauly 2001) ja piiratud mudelites on mängitavad efektsusfunktsioonid tõeliselt mängitavad. [5]
Nagu varem märgitud, mainitakse selles sissekandes üksnes seda, kuidas teadmised kaudselt mängukonstruktsioonidesse kuuluvad, kuid ei kaevu ratsionaalse mängu episteemiliste eeltingimuste uurimise juurde. Seotud sissekanded, mis on pühendatud episteemilisele loogikale (Hendricks & Symons 2006), dünaamilisele episteemilisele loogikale (Baltag & Renne 2016) ja eriti episteemilise mängu teooriale (Pacuit & Roy 2015), uurivad põhjalikult teadmiste rolli otsuste tegemisel. Mängude modaalloogika käsitlus, mis keskendub pigem teabe rollile, on Hoek & Pauly 2006.
3. Võimsuse analüüsimine
Selles jaotises käsitletakse mänge, milles üksikisikud või rühmad teevad oma valikuid iseseisvalt ja samaaegselt, ning rõhutame veel kord, et võtame osa sellest, kuidas interaktsioon ajas areneb. Selles pööratakse erilist tähelepanu mängijate valikute ja eelistuste seosele, mainitakse teadmiste rolli ja mis kõige tähtsam - see, kuidas lahendusmõisteid loogilises keeles väljendada.
Selles jaotises kirjeldatakse kõigepealt ühismängude üldist seadistamist, seejärel käsitletakse strateegiliste mängude piiramatumat ja võib-olla paremini tuntud klassi.
3.1 Koostöömängud ja nende loogika
Mängu kirjeldus, mis on esitatud vormi relatiivses struktuuris ((matemaatiline {N}, W, \ õnnestum, E)), ei ole piisav, et mõista, milline täpne tulemus lõpuks valitakse. Selleks vajame lahenduskontseptsiooni, st kaardistamist, mis seob mänguga selle mängu tulemuste komplekti (Abdou & Keiding 1991).
Koalitsioonimängude jaoks on kasutusele võetud rida lahendusi (vt näiteks Osborne & Rubinstein 1994 ja Apt 2009 (muud Interneti-ressursid)). Praegustel eesmärkidel arutame ainult seda, mis on kõige tuntum: tuum. Tuum on stabiilsete tulemuste kogum, st tulemused, mille jaoks puudub koalitsioon, mille liikmed on mõlemad võimelised ja tahavad sellest kalduda. Seda võib vaadelda tulemuste kogumina, millele puudub tõhus vastuseis (Abdou & Keiding 1991).
Formaalselt, arvestades relatsioonilist struktuuri (F = (matemaatiline {N}, W, \ õnnestunud, E)), öeldakse, et tulemus (w \ W) on stabiilne, kui puudub koalitsioon (C) ja tulemuste kogum (X \ subseteq W) nii, et mõlemad järgmised tingimused on täidetud:
(X \ sisse E (C))
(y \ sisse X) ja (i \ C) tähendavad, et (y \ succ_i w)
Sõnades on tulemus stabiilne, kui ükski grupp inimesi ei suuda saavutada alternatiivi, mida nad kõik rangelt eelistavad.
Tuum on kogumik kõik stabiilne tulemusi.
Näide 6:
Mõelge tulemusele 1M, mis on ainus tulemus, mida Saksamaa peab vastuvõetavaks. Nagu juba täheldatud, on Saksamaal efektsusfunktsioon (E ({ textrm {Saksamaa} }) = {W }), nii et üksi ei suuda nad oma eelistust tulemuseks muuta. Kuid koos teiste riikidega on nad selleks võimelised. Oletame, et nende liitlased on Belgia, Prantsusmaa ja Holland. Kas 1M on siis hea tulemus? Kui vaatame teiste koalitsiooni osaliste, st Belgia, Prantsusmaa, Hollandi, eelistusi, siis järgime järgmist. Belgias oli tulemus pigem vahemikus 4–5 miljonit, Prantsusmaal ja Hollandis täpselt 5 miljonit. Need riigid võiksid kokku saada ja valida 5M, mis on neile vastuvõetav tulemus. ({) Belgia, Prantsusmaa, Hollandi (}) efektiivsusfunktsioon on siiski (E ({) Belgia, Prantsusmaa,Madalmaad (}) = {W }), mis tähendab, et kolmest riigist ei piisa 5 miljoni arve edastamiseks. Kuid Belgia, Prantsusmaa, Itaalia ja Hollandi moodustatud koalitsioon oleks. Pange tähele, et 5M on üks Itaalia eelistatud tulemusi. 5M on tegelikult mängu ainus stabiilne tulemus: pole koalitsiooni, kes oleks üheskoos nõus ja võimeline sellest kõrvale kalduma.
Tuuma tähistamiseks saab kasutada modaalset loogikat. Mõelge kõigepealt valemile
[p \ parempoolne nool \ bigvee_ {C \ subseteq N} [C] vasakul (bigwedge_ {i \ C-s} Teemant ^ \ succ_i p \ paremal))
See ütleb, et kui (p) vastab tõele, saavad mõne koalitsiooni liikmed parandada mõnda (p) maailma, mis ei tundu olevat õige valem loogika stabiilsuse väljendamiseks. Siiski võime tõestada järgmisi tulemusi, milles kasutatakse vastavust valemi ja konkreetse kaadriklassi vahel.
Olgu (E) efektiivsuse funktsioon (tulemus monotoonne) ja (õnnestq_i) nõrk lineaarne järjekord. Siis:
[(F, V '), w \ mudelid p \ parempoolne \ bigvee_ {C \ subseteq N} [C] vasakul (bigwedge_ {i \ C-s} Teemant ^ \ succ_i p \ paremal))
hoiab (w) iga (V ') korral, kui ja ainult siis leidub (C \ subseteq N) ja (X \ E_w (C)), nii et kõigi (i \ jaotises C), (x \ X-is) on meil (x \ succ_i w).
Seega kehtib valem väärtuse (w) korral iga hindamise korral ainult siis, kui (w) ei kuulu tuuma. On selge, et kui valem on tulemuse ja mõne väärtuse osas vale, siis tähendab see, et tulemus kuulub tuumiku alla.
Pange tähele, et kuna efektiivsuse funktsioonid on tulemuseks monotoonsed, siis kui meil on see (X \ sisse E_w (C)) ja
[X \ subseteq \ vasakul (bigwedge_ {i \ C-s} Teemant ^ \ succ_i p \ paremal) ^ {(F, V ')},)
siis
) vasak (bigwedge_ {i \ C-s} Teemant ^ \ succ_i p \ paremal) ^ {(F, V ')} E_w (C) -s.)
Pange ka tähele, et ülaltoodud tulemus võimaldab juhtuda
mis võib olla vastupidine. Selle eest hoolitseb elujõulisuse nõudmine (E).
Pange tähele ka seda, kuidas pidime hindamiskomplektile kehtestama universaalse kvantifitseerimise. Ilma selle selgesõnalise kvantifitseerimiseta kehtiks valem ainult ühe konkreetse mudeli jaoks, mis ei oleks sobiv lahendus. Kui meid huvitab vaid see, kas on olemas mõni stabiilne tulemus või, vastupidi, kas tuum on tühi, piisab, kui eeldada, et ülaltoodud valem on aksioom. See tähendaks, et ükski tulemus pole stabiilne, st et tuum on tühi.
10. ettepanek. Olgu (F) raam. Meil on see olemas
) models_F p \ rightarrow \ bigvee_ {C \ subseteq N} [C] left (bigwedge_ {i \ in C} Diamond ^ \ succ_i p \ right))
ainult siis, kui ükski (F) tulemus ei kuulu tuuma.
Jällegi, elujõulisus hoolitseks selle tühise juhtumi eest, milles
Nii et sõltuvalt meid huvitavatest omadustest sobivad nende väljendamiseks kõige paremini põhilise modaaloogika erinevad laiendused koos erinevate kehtivusvormidega (maailm vs mudel vs kaadril).
3.2 Strateegilised mängud ja nende loogika
Tavalised vormimängud ehk strateegilised mängud esindavad seda, mida üksikisikud, mitte koalitsioonid, võivad saavutada ja millised on nende eelistused.
Formaalselt on strateegiline mänguvorm nüpel
[(N, W, { Sigma_i } _ {i \ in N}, o))
kus N on piiratud mängijate komplekt, (W) tulemuste komplekt, ({ Sigma_i } _ {i \ N}) strateegiate kogum, üks iga mängija jaoks (i), (o: \ prod_ {i \ in N} Sigma_i \ to W) tulemusfunktsioon, seostades strateegiad rea tulemusega.
Strateegiline mäng on tükk ((S, { ansq_i } _ {i \ in N})), kus (S) on strateegilise mängu vorm ja ({ ansq_i } _ { i \ in N}) eelistussuhete kogum, üks iga mängija jaoks (i).
Näide 7: Kui mõtleme oma eelmises näites olevatele riikidele üksikute mängijatena ja nende häältele kui individuaalsetele strateegiatele, siis võime Rooma lepingu mängu modelleerida strateegilise mänguna, kus iga inimene saab hääletada rahasumma, mille pühendada piiride kaitsele. ja eelistused on nagu ülalpool.
Tulemusfunktsioon hoolitseb selle eest, et iga mängija hääl seostatakse kollektiivse otsuse lõpptulemusega, nt valitakse selline tulemus, mille hääletas vähemalt 12 hääletamiskaaluga riikide komplekt, või kui konsensuse saavutamisel otsust ei tehta,.
Näiteks:
Prantsusmaa hääletab 0M
Belgia hääletab 2M
Itaalia hääletab 10 miljonit
Saksamaa hääletab 0M
Holland hääletab 0M
Luksemburgi hääletus 0M
Selle vooru tulemusel otsust ei tehta, kuna ühegi tulemuse korral pole hääletusprotsent vähemalt 12.
Oletagem siiski, et teine voor on selline, et kõik peale Belgia jäävad oma hääletamisse ja oletame, et Belgia lülitub 0M hääletamisele. Nüüd on 0M-i koguarv 13, mis tähendab, et see valitakse lõplikuks otsuseks.
Vaadates meie näite ühtset käsitlust, näib, et normaalvormi mängude ja koalitsioonimängude vahel on seos. Seda suhet saab ametlikult täpsustada.
Mõelgem kõigepealt, mida üks mängijarühm tavalises vormis mängus teha saab. Selleks määratleme funktsiooni (alpha) efektiivsuse, mis on mängu koalitsioonistrateegiate matemaatiline kirjeldus tulemuste põhjal, mida nad võivad sundida.
Definitsioon 12) (alpha) - efektiivsuse funktsioon] Olgu (S) strateegiline mäng. Me defineerime (S), (E ^ { alpha} _S (C)) efektiivsuse funktsiooni:
(E ^ { alpha} _S (C) = {X \ \ mid) on olemas (sigma_C) nii, et kõigi (sigma '_ { overline {C}}) jaoks on meil olemas et (o (sigma_C, \ sigma '_ { ülajooneline {C}}) kaustas X })
Intuitiivselt kogub (alpha) efektiivsuse funktsioon (S) iga mängijate rühma jaoks tulemuste komplekti, mida nad saavad saavutada oma strateegia kehtestamisega, hoolimata sellest, kuidas nende vastased mängivad.
13. ettepanek (Goranko jt 2013)
Strateegilise mängu efektsusfunktsioon (alpha) on tõeliselt mängitav.
Järgmine tulemus näitab seost strateegiate ja efektiivsusfunktsioonide vahel.
Teoreem 14 (Goranko jt 2013)
Efektiivsuse funktsiooni saab tõeliselt mängida ainult siis, kui see on mõne strateegilise mängu (alpha) - efektiivsuse funktsioon.
See on üldistus Peleg 1998 tulemuste osas piiratud mängude jaoks, alustades strateegiliste mängude mudelitest, mis määratleti esmakordselt Pauly 2001-s. Lühidalt öeldes tähendavad need tulemused järgmist.
Lause 15 Laske (F) relatsioonilisel mängustruktuuril. Siis on (F) strateegiline mäng siis ja ainult siis, kui järgmised valemid kehtivad jaotises (F, F) eraldatava (C, C ^ { prime}) jaoks:
(varphi \ kuni \ psi \ mudelid_F [C] varphi \ kuni [C] psi)
(mudelid_F [C] ülemine)
(mudelid_F \ neg [C] bot)
(models_F \ neg) emptyset] varphi \ kuni [N] varphi)
Samamoodi nagu koostöömängude puhul, võime endalt küsida, kas tulemus on strateegilises olukorras stabiilne või ratsionaalne.
Nashi tasakaal ja määratletavus Strateegiliste mängude analüüsimise peamine lahenduskontseptsioon on Nashi tasakaal. Mitteametlikult on Nashi tasakaal strateegiate kogum, üks mängija kohta, nii et ükski mängija pole huvitatud oma strateegia muutmisest, kui teised peavad jääma oma mängu. Vormiliselt on strateegiaprofiil (sigma) (puhta strateegiaga) Neši tasakaal, kui kõigi mängijate (i \ N-is) ja kõigi (sigma'_i \ in \ Sigma_i) jaoks on meil selline
Selles mängus puudub üksmeel ühegi eelarve osas. Olukord võib tunduda ummikseisus, kuna kõik on hääletanud vastavalt oma eelistustele. Selle tulemuseks on erimeelsused, mida ükski mängija ei eelista ühelegi kokkuleppele. Ainus viis, kuidas mängijad saavad kokkuleppele jõuda, on see, et Itaalia muudab oma hääle 5M-ile. Kui see juhtub, saavutatakse tulemus 5M.
Pange tähele, et muudetud mäng, milles Itaalia hääletab 5M, on Nashi tasakaal.
Mõelge nüüd ülaltoodud mängu muudatusele, kus Itaalia ja Holland hääletavad 10 miljonit, teised aga hääletades. Üllataval kombel on see hoolimata erimeelsustest Nashi tasakaal, sest ükski mängija ei suuda samaaegselt mingisugust kokkulepet saavutada, ehkki on selleks nõus.
Kuidas väljendada Nashi tasakaalu loogikas? Tuletage meelde, kuidas valem
[p \ kuni \ bigvee_ {C \ subseteq N} [C] vasakul (bigwedge_ {i \ C-s} Teemant ^ \ succ_i p \ paremal))
hoiab kaadris (F) ainult siis, kui tuum on tühi, ja hübriidloogikalaiend võib meile öelda, kas konkreetne tulemus kuulub tuuma. Kui (F) põhineb tõeliselt mängitaval efektiivsuse funktsioonil, on meil juba tuumiku tavaline vormiversioon: selline tulemus, et ükski koalitsioon pole koos võimeline ja valmis kõrvale kalduma, arvestamata sellega, mida teised teevad. Nash Equilibrium fikseerib aga profiilide profiili nii, et ükski mängija pole võimeline ega soovi sellest kõrvale kalduda. Teisisõnu, see eeldab mängija parima reageerimise mõtet antud profiili suhtes.
Formaalsused, näiteks koalitsiooniloogika, on Nassi tasakaalu väljendamiseks liiga nõrgad. Kuid nad võivad väljendada tõsiasja, et teatud efektiivsuse funktsioonid võimaldavad võimaluseta Nassi tasakaal. See on Hansen & Pauly 2002 nimega Nash-järjepidev koalitsiooniloogika. Nassi tasakaal ei ole tegelikult põhimodaalloogikas määratletav (Benthem jt 2011), kuid seda saab teha modaalsusega, mis ristub nii eelistuse kui ka valikuga (Benthem jt 2011).
((F, V), w \ mudelid \ langle \ approx_i \ cap \ succ_i \ rangle \ varphi) ainult siis, kui (w (approx_i \ cap \ succ_i) w ') tähendab, et (w' \ mudelid \ varphi)
Siis määratletakse (i) jaoks parim vastus kui (langle \ approx_i \ cap \ succ_i \ rangle \ top), kuna puudub alternatiiv, mis oleks samal ajal saavutatav ja eelistatav kui (i). Teise võimalusena võib lahenduse pakkuda hübriidloogika, mis mainib keeles strateegiaprofiile, nagu tuuma puhul.
3.2.1 Mittemonotoonne tegevusloogika
Mõni loogika kasutab strateegilistele mängudele vastavate relatsioonistruktuuride kompaktsemat esitust.
Tõhususfunktsioonide kasutamise asemel seostatakse iga mängija (i) ekvivalentsussuhtega (approx_i \ subseteq W \ korda W), mille indutseeritud partitsioon tähistab valikuid, mida ta saab teha. Need ekvivalentsussuhted kirjeldavad mängijate rühma täpseid valikuid ja päritolumudeleid nimetatakse kirjanduses järelduslikeks (vt näiteks Belnap, Perloff ja Ming 2001).
Nüüd määratlege efektiivsusfunktsioon (E ^ {*}), mille jaoks ta seda hoiab
[E ^ {*} (i) = {[x] keskel x '\ kaustas [x] mbox {alati} x \ approx_i x' } ^ {+})
Intuitiivselt (E ^ {*} (i)) kogub, mida üksikisikud täpselt suudavad saavutada, ja kõik nende üliriigid.
(E ^ {*}) nimetatakse järelduslikeks, kui leiab, et:
(E ^ {*} (C) = { bigcap_ {i \ C-s} X_i \ keskel \ mbox {mõne jaoks} X_i \ E ^ {*} (i) })
(emptyset \ not \ sisse E ^ {*} (C)) iga (C \ neq N) jaoks
(E ^ {*} (N) = { {x } keskel x \ W } ^ {+})
Pange tähele, et (E ^ *) on tõeliselt mängitav efektsusfunktsioon.
Viimane omadus on hästi põhjendatud, nagu ka suvaliste tõhususfunktsioonide puhul. See ei ole omadus, mida eeldatakse kõigis variantides, nt Kooi & Tamminga 2008 valikustruktuurid ja selle ajaline variant STIT (Belnap jt 2001) seda ei tee. Nagu aga Turrini 2012 ja Tamminga 2013 täheldasid, vastavad hästi põhjendatud järelduslikud mudelid strateegilistele mängudele ja efektsusfunktsiooni (E) saab iga mängija ekvivalentsussuhtega (approx_i) tõhusalt simuleerida. Intuitiivselt (E ^ {*} (i)) on tulemuste komplekt, mida (i) saab valida, ilma et oleks võimalik edasi täpsustada.
Järjestikuste mudelite üle otsustamiseks kasutame niinimetatud järelduslike loogikaid, st ettepanekuloogikat, mis on laiendatud vormi ([C] varphi) modaalsustega ja mida tõlgendatakse järgmiselt:
(M, w \ mudelid [C] varphi) ainult siis, kui (M, w '\ mudelid \ varphi) kõigi (w') jaoks nii, et (w (bigcap_ {i \ in C} approx_i) w ')
Järjestikuste loogika on välja töötatud tegevuse ja tagajärgede üle arutlemiseks ning neil on huvitavad rakendused deontilises loogikas, näiteks Kooi & Tamminga 2008; Tamminga 2013; Turrini 2012. Lisaks on need strateegia, näiteks STIT ja strateegilise STIT, ajalise loogika alus, mida arutatakse hiljem. Erijuhtum on juhendjuhtimise loogika (Hoek & Wooldridge 2005; Troquard, Hoek ja Wooldridge 2009).
3.2.2 Loogikapõhised mängud
Paljudes olukordades on agentidel kontroll teatud pakkumismuutujate üle (Hoek & Wooldridge 2005), näiteks võivad nad olla vastutavad liikluse voogude eest või võivad teatud küsimuses veto panna. Muutujaid saab jagada ka (Gerbrandy 2006), näiteks hääletamine, kus mängijad jagavad kontrolli muutuja üle, mille realiseerimise määrab teatud liitmisfunktsioon, nt enamus (Troquard, Hoek ja Wooldridge 2011). Need propositsioonilise juhtimise loogikad täpsustavad, millised on väidetel agendid oma efektiivsuse funktsioonis. Näiteks kui agent (i) juhib (p), siis on nii (p ^ {M}) kui ka (neg p ^ {M}) tema efektiivsuse funktsioonis. Mõnes mõttes on need mudelid tõhususe funktsiooni väga erilised tüübid ja seda, mida agendid kontrollivad, võib vaadelda neile kättesaadava valiku või strateegiana.
Valikulise juhtimise loogikal on tüüpi ([[i]] varphi) modaalsused, mis tähendab, et mängijal (i]) on „juhtimisstrateegia”, et hoolitseda selle eest, et sõltumata sellest, kuidas teised agendid oma kontrolli valivad strateegiaid, siis (varphi) jääb lõpuks alles. Kuid neil on ka tüüpi ([[C]] varphi), mis tähendab, et (C) mängijatel on ühine kontrollistrateegia, mis tagab lõpuks (varphi). Strateegiaprofiil on seega samaväärne hindamisfunktsiooniga, mis määrab iga saadaoleva väite tõeväärtuse. Mängija (i) strateegiat saab omakorda vaadelda osalise hindamisfunktsioonina, mis annab tõeväärtuse ainult (i) kontrollitavatele väidetele.
Pisut kuritarvitades märkust, ütleme, et hinnang (V) vastab valemile (varphi), mida tähistatakse (V \ mudelid \ varphi), alati, kui see muudab (varphi) tõeseks praeguse ettepanekud. Teisisõnu: juhtpositsioonilisi kontrollmänge mängitakse ühes maailmas ja individuaalsed ülesanded määravad kindlaks, millised väited vastavad sellele maailmale. Kõigi väärtuste ja (matemaatiliste {V} _i) väärtuste komplekti märkimisel osalistele väärtustele, mis on (i) kontrolli all, on meil järgmine.
((F, V) mudelid [[C]] varphi) ainult siis, kui kõigi (i \ C-s) puhul on olemas (V'_i \ in \ mathcal {V} _i) nii, et kõigi (k \ in \ üherealiste {C}, V '_ {k} in \ matemaatika {V} _k) korral on meil see ((F, V') mudelid \ varphi)
Niisiis, kui ([[C]] varphi) on käes, saab koalitsioon (C) mängida kontrollistrateegiat nii, et hoolimata kontrollistrateegiast, mida nende vastased mängivad, rahuldab saadud tulemus (varphi).
Ettevalmistuskontrolli loogikat saab laiendada eesmärgipõhistele formalismidele, nn Boole'i mängudele (Harrenstein, van der Hoek, Meyer ja Witteveen 2001): ettepanekud jaotatakse mängijate vahel nii, et iga mängija kontrollib oma väidete komplekti. on määratud. Lisaks sellele omistatakse igale mängijale ka pakkumisloogika valem, mis on mõeldud tema eesmärgiks ja mille realiseerimine ei pruugi sõltuda ainult valikutest, mida ta on võimeline tegema.
Boolean-mänge on ulatuslikult uuritud multiagentide süsteemide valdkonnas kui lihtsaid ja kompaktseid mudeleid, mis esindavad strateegilist interaktsiooni loogikapõhises keskkonnas (Dunne & Hoek 2004; Dunne & Wooldridge 2012; Dunne, Hoek, Kraus ja Wooldridge 2008).
Nende kõige üldisemates variantides on tegemist loogika laiendamisega juhendjuhtimisega, kus igale agendile määratakse eesmärgi valem. Eesmärgi valem on keele rahuldav valem ja oluline omadus on see, et iga agendi eesmärk ei pea olema tema kontrolli all.
Näiteks agendile (i) võidakse määrata ainult pakkumise (p) juhtimine, kuid selle eesmärk võib olla (p \ leftrightarrow q). Seega, kas (i) eesmärk on täidetud, ei sõltu mitte ainult (i) pakkumise (p) õigeks seadmisest, vaid ka mõnest teisest agendist, näiteks (j), mis pakub pakkumist (q) olema tõsi. Agent (j) seevastu võib või ei pruugi olla huvitatud sellest, et (q) seatakse väärtusele true. Näiteks võib ta soovida, et väide (r) oleks tõene ja oleks seetõttu ükskõikne, kas (q) või (ülejooneline {q}) realiseerub lõpuks. Või võib-olla isegi eesmärk, mis (ületanud {q}).
Boolean-mängudes saab mõned eesmärgid realiseerida kõik koos, näiteks võivad kõik agendid soovida, et (p \ vee \ neg q) oleks tõsi, või võib juhtuda, et teatud hinnangutega ei realiseerita kõigi esindajate eesmärke, vaid ükski õnnetu agent ei suuda oma olukorda parandada, muutes ülesande tema kontrollitavate pakkumismuutujate järgi. See olukord on Nesši tasakaalu väga lihtne vorm, mida saab väljendada Boole'i mängudes.
Niisiis, kui (gamma_i) on mängija eesmärk (i) ja (v_i) osaline hindamine, mis on mängija kontrolli all, (i), ütleme, et hindamine (v) on Nashi tasakaal, kui meil on see iga (i) ja iga (v'_i) jaoks.
[(v_i, v _ {- i}) not \ models \ gamma_i \ mbox {tähendab, et} (v'_i, v _ {- i}) not \ models \ gamma_i)
Nii et kui (v) ei täida (i) eesmärki, ei saa midagi (i) selle saavutamiseks teha.
Nash-i tasakaalu analüüs Boole-mängus näitab nende mängude ja pakkumisloogika tihedat vastavust: kasutades pakutavate loogikavalemite rahuldamisprobleemi redutseerimist, kontrollitakse, kas tulemus (v) on Boole-i Nassi tasakaal. mäng on NP-ga täielik (Wooldridge, Endriss, Kraus ja Lang 2013).
4. Järeldused: analüüsi õigel tasemel
Tuletage meelde esimest näidet, kus hääletusmängu tulemusi võis kirjeldada ainult hääletuse üldist tulemust arvestades või kirjeldades selgesõnaliselt seda, mida kõik riigid hääletasid.
Sageli seisavad matemaatiliste struktuuride lühikeste keelte kirjeldamisel silmitsi küsimusega, milline neist on kõige sobivam keel. Mõni oskab eelistusi, teadmisi ja koalitsioonivõimet väljendada kõik koos, teised ainult kahe kohta, mõned teised ainult ühe kohta. Lõpuks suudavad mõned keeled väljendada ainult seda, mida üksikisikud, mitte koalitsioonid, suudavad saavutada.
Jällegi pole sellele küsimusele õiget vastust. Kõik sõltub sellest, millised on põhiomadused, mida üritatakse modelleerida. Naši tasakaalu väljendamiseks koordinatsioonimängus pole vaja ajalikku loogikal põhinevat formalismi. Vastupidi, kui soovitakse väljendada tagasiulatuvat sissejuhatust, siis pole keel, mis ei muuda otsustusprobleemi järjestikust ülesehitust selgeks, õige.
Tulles tagasi meie näite juurde, võib mõnel riigil olla eelistusi teiste riikide hääletamise suhtes ja see võib mõjutada nende otsustamist, muutes mängu üldisi tasakaalupunkte. Kui see on nii, siis on oluline rikkam keel. Kui me selle võimaluse julgelt välistame, näib sobivam valik sisutihedam keel.
Bibliograafia
Abdou, Joseph ja Hans Keiding, 1991, Efektiivsusfunktsioonid sotsiaalses valikus (teooria- ja otsustuskogu 8), Dordrecht: Springer Holland, doi: 10.1007 / 978-94-011-3448-4
Baltag, Alexandru ja Bryan Renne, 2016, “Dynamic Epistemic Logic”, Stanfordi filosoofia entsüklopeedias (2016. aasta talve väljaanne), Edward N. Zalta (toim), URL =
Belnap, Nuel, Michael Perloff ja Ming Xu, 2001, Facing the Future: Agents and Choices in Our Indeterminist World, Oxford: Oxford University Press.
Benthem, Johan van, 2014, Logic in Games, Cambridge, MA: MIT Press.
Benthem, Johan van, Eric Pacuit ja Olivier Roy, 2011, “Mänguteooria poole: mängude ja koostoimimise loogiline perspektiiv”, Mängud, 2 (1): 52–86. doi: 10.3390 / g2010052
Blackburn, Patrick, Maarten de Rijke ja Yde Venema, 2001, Modal Logic, Cambridge: Cambridge University Press. doi: 10.1017 / CBO9781107050884
Chellas, Brian, 1980, Modal Logic: An Introduction, Cambridge: Cambridge University Press.
Dalen, Dirk van, 1980, loogika ja ülesehitus, Berliin: Springer-Verlag. doi: 10.1007 / 978-3-662-02962-6
Dunne, Paul E. ja Wiebe van der Hoek, 2004, „Esindus ja keerukus Boolei mängudes“, José Júlio Alferes ja João Alexandre Leite (toim), tehisintellekti loogika, 9. Euroopa konverents, JELIA 2004, Lissabon, Portugal, 27. – 30. September 2004, Proceedings, Berliin, Heidelberg: Springer, 3229: 347–359. doi: 10.1007 / 978-3-540-30227-8_30
Dunne, Paul E. ja Michael Wooldridge, 2012, “Tractable Boolean Games” poole, Wiebe van der Hoek, Lin Padgham, Vincent Conitzer ja Michael Winikoff (toim), 11. rahvusvahelise autonoomsete esindajate ja multiagentsete süsteemide konverentsi toimetised., (AAMAS 2012), Valencia, Hispaania, 4. – 8. Juuni 2012, Richland, SC: Rahvusvaheline Autonoomsete Agentide ja Multiagentsete Süsteemide Fond, vol. 2, lk 939–946.
Dunne, Paul E., Wiebe van der Hoek, Sarit Kraus ja Michael Wooldridge, 2008, „Boole'i ühismängud“, Lin Padghamis, David C. Parkes, Jörg P. Müller ja Simon Parsons (toim), Proceedings of seitsmes rahvusvaheline autonoomsete esindajate ja multiagentsete süsteemide ühiskonverents (AAMAS 2008), Estoril, Portugal, 12. – 16. mai 2008, Richland, SC: Rahvusvaheline autonoomsete esindajate ja multiagentsete süsteemide fond, vol. 2, lk 1015–1022.
Garson, James, 2014, “Modal Logic”, Stanfordi filosoofia entsüklopeedias (2016. aasta kevadväljaanne), Edward N. Zalta (toim), URL = .
Gerbrandy, Jelle, 2006, “Propositsionaalse juhtimise loogika”, Hideyuki Nakashima, Michael P. Wellman, Gerhard Weiss ja Peter Stone (toim.), 5. autonoomsete ainete ja multiagentsete süsteemide rahvusvahelise ühiskonverentsi (AAMAS 2006) toimetised.), Hakodate, Jaapan, 8. – 12. Mai 2006, New York: ACM, lk 193–200. doi: 10.1145 / 1160633.1160664
Goranko, Valentin ja Salomon Passy, 1992, “Universaalse modaalsuse kasutamine: eelised ja küsimused”, ajakiri Logic and Computation, 2 (1): 5–30. doi: 10.1093 / logcom / 2.1.5
Goranko, Valentin, Wojciech Jamroga ja Paolo Turrini, 2013, “Strateegilised mängud ja tõeliselt mängitavad efektiivsuse funktsioonid”, autonoomsed esindajad ja multiagentide süsteemid, 26 (2): 288–314. doi: 10.1007 / s10458-012-9192-y
Hansen, Helle Hvid, 2003, Monotoonne modaaloogika, magistritöö, Universiteit van Amsterdam.
Hansen, Helle Hvid, Clemens Kupke ja Eric Pacuit, 2009, “Naabruskonstruktsioonid: bisimilaarsus ja põhimudeliteooria”, loogilised meetodid arvutiteaduses, 5 (2): lmcs: 1167. [Hansen, Kupke ja Pacuit 2009 on veebis saadaval]
Hansson, Sven Ove ja Till Grune-Yanoff, 2011, “Eelistused”, Stanfordi filosoofia entsüklopeedias (2011. aasta sügisel väljaanne), Edward N. Zalta (toim), URL => https://plato.stanford.edu/ arhiivid / sügis2011 / kanded / eelistused />
Harrenstein, Paul, Wiebe van der Hoek, John-Jules Meyer ja Cees Witteveen, 2001, „Boolean Games“, Johan van Benthem (toim), ratsionaalsuse ja teadmiste teoreetilisi aspekte käsitleva 8. konverentsi toimetised (Tark) 01), San Francisco: Morgan Kaufmann, lk 287–298.
Hendricks, Vincent ja John Symons, 2006, “Epistemic Logic”, Stanfordi filosoofia entsüklopeedias (2006. aasta kevadväljaanne), Edward N. Zalta (toim), URL =
Hodges, Wilfrid, 2013, “Loogika ja mängud”, Stanfordi filosoofia entsüklopeedias (2013. aasta kevadväljaanne), Edward N. Zalta (toim), URL = .
Hoek, Wiebe van der ja Marc Pauly, 2006, “Mängude ja teabe modaalne loogika”, Patrick Blackburn, Johan van Benthem ja Frank Wolter (toim), Modal Logic Handbook, lk 1077–1148, Elsevier.
Hoek, Wiebe van der ja Michael Wooldridge, 2005, “Koostöö ja propositsioonilise kontrolli loogikast”, tehisintellekt, 164 (1–2): 81–119. doi: 10.1016 / j.artint.2005.01.003
Kracht, Marcus ja Frank Wolter, 1999, “Tavaline ühemodaalne loogika võib kõiki teisi simuleerida”, Journal of Symbolic Logic, 64 (1): 99–138. doi: 10.2307 / 2586754
Moulin, Herve ja Bezalel Peleg, 1982, “Efektiivsuse funktsioonide tuumad ja rakendusteooria”, ajakiri Mathematical Economics, 10 (1): 115–145. doi: 10.1016 / 0304-4068 (82) 90009-X
Osborne, Martin ja Ariel Rubinstein, 1994, mänguteooria kursus, Cambridge, MA: MIT Press.
Pacuit, Eric ja Olivier Roy, 2015, “Mänguteooria episteemilised alused”, Stanfordi filosoofia entsüklopeedias (2015. aasta kevadväljaanne), Edward N. Zalta (toim), URL =
Pauly, Marc, 2001, sotsiaalse tarkvara loogika, Ph. D. lõputöö, Amsterdami ülikool. [Pauly 2001 on veebis saadaval]
Peleg, Bezalel, 1998, “Efektiivsuse funktsioonid, mänguvormid, mängud ja õigused”, sotsiaalne valik ja heaolu, 15 (1): 67–80. doi: 10.1007 / s003550050092
Steele, Katie ja Orri Stefansson, 2015, “Otsusteooria”, Stanfordi filosoofia entsüklopeedias (2015. aasta talve väljaanne), Edward N. Zalta (toim), URL =
Troquard, Nicolas, Wiebe van der Hoek ja Michael Wooldridge, 2009, “Mängude ja propositsioonilise juhtimise loogika”, Carles Sierras, Cristiano Castelfranchi, Keith S. Deckeris ja Jaime Simão Sichmanis (toim), 8. osa. Autonoomsete esindajate ja multiagentsete süsteemide rahvusvaheline ühiskonverents (AAMAS 2009), Budapest, Ungari, 10. – 15. Mai 2009, Richland, SC: Autonoomsete esindajate ja multiagentsete süsteemide rahvusvaheline sihtasutus, vol. 2, lk 961–968.
