Логика за анализ на мощността в игри с нормални форми

2023 Автор: Noah Black | [email protected]. Последно модифициран: 2023-08-25 04:38

Навигация за влизане

• Съдържание за участие
• библиография
• Академични инструменти
• Friends PDF Preview
• Информация за автора и цитирането
• Върнете се в началото

Логика за анализ на мощността в игри с нормални форми

Публикувана за първи път сря 14 юни 2017; съществена ревизия вт. 1 август 2017 г.

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

Материалът в този запис ще бъде ограничен до логическия анализ на стратегиите и предпочитанията на (групи от) индивиди в игри с нормална форма. Той няма да обхваща използването на теорията на игрите за изучаване на логическите езици, нито ролята на епистемичните концепции в стратегическите решения. Той също така няма да обхваща аспекти на последователното вземане на решения, характерни за стратегическите разсъждения в обширни игри. Сметка за тези може да бъде намерена в свързаните логики и игри, свързани с епистемичните основи на теорията на игрите (виж също van Benthem, Pacuit, & Roy 2011 и van Benthem 2014).

• 1. Логиката под игри с нормална форма

• 2. Основни съставки

  • 2.1 Предпочитания
  • 2.2 Избори

• 3. Анализиране на мощността

  • 3.1 Кооперативни игри и тяхната логика

  • 3.2 Стратегически игри и тяхната логика

    • 3.2.1 Немонотонна логика на действие
    • 3.2.2 Логически игри
• 4. Заключения: На правилното ниво на анализ
• библиография
• Академични инструменти
• Други интернет ресурси
• Свързани записи

1. Логиката под игри с нормална форма

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

Игрите се използват за моделиране на всякакви ситуации, вариращи от поведението на животните до разрешаването на международни конфликти (Osborne & Rubinstein 1994). Полезно приложение за целите на този запис е колективно вземане на решения, пример за който ще бъде работният пример в целия.

Пример 1: (Римският договор)

Римският договор (1958–1973) създава Европейската икономическа общност. Съгласно член 148 от Договора, актовете на Съвета (една от основните законодателни институции), необходими за приемането им:

• 12 гласа (ако актът е предложен от Комисията), или
• 12 гласа от поне 4 държави-членки (ако актът не е предложен от Комисията).

Стойностите по-горе се отнасят за ЕС-6, страните членки. Договорът разпредели гласовете, както следва:

• 4 гласа: Франция, Германия, Италия;
• 2 гласа: Белгия, Холандия;
• 1 глас: Люксембург.

Този сценарий може да бъде описан като игра.

Има шестима играчи, страните:

Франция, Германия, Италия, Белгия, Холандия и Люксембург.

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

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

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

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

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

2. Основни съставки

Формално игрите се състоят от ограничен набор от играчи (N = {1,2, / ldots, n }) и евентуално безкраен набор от резултати (W = {w_1, w_2, / ldots, w_k, / ldots }).

Пример 2: В примера по-горе множеството играчи N е {Франция, Германия, Италия, Белгия, Холандия, Люксембург}. Ако вземем предвид приемането на схема за защита на границите, има два резултата: да и не, т.е. (W = { mbox {да, не} }). Ако вместо това разгледаме въпроса за милиони, изразходвани за схема за защита на границите, има потенциално безкрайно пространство за изход, т.е. (W = { textrm {0M}, / textrm {1M}, / textrm {2M}, / ldots }). Възможно е да има набор от резултати, който е дори усъвършенстван допълнително, например да се посочи начинът, по който играчите са гласували. В този случай резултатът, при който Франция гласува „да“, другите гласуват „не“, а резултатът е „не“, би бил различен от резултата, в който Италия гласува „да“, другите гласуват „не“, а резултатът е „не“, въпреки че резултатът от вотът е същото. Важно е да се подчертае, че всеки набор от резултати идва с ниво на описание на това, което се случва в основното взаимодействие. Няма априори правилно или грешно ниво на описание, изборът зависи от свойствата на играта, от които човек се интересува.

Освен играчите и резултатите, игрите идват с още две отношения:

• една връзка предпочитание, означена (succeq), описвайки предпочитанията на играчите над резултати;
• отношение на действието, обозначено (E), описващо резултатите, които играчите или групите играчи могат да наложат или, обратно, да изключат;

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

Както отношенията на предпочитания, така и действията събират семейства от индивидуални отношения, по един на играч. Отношението на предпочитанията например се разгражда на семейство ({ succeq_i } _ {i / в N}), описвайки предпочитанието пред резултатите за всеки от индивидите, докато отношението за действие събира семейство ({E_C } _ {C / subseteq N}) всеки описва какво може да постигне определена група играчи.

Като цяло играта може да се разглежда като математическа структура

[(mathcal {N}, W, / succeq, E))

където (mathcal {N}) е набор от играчи, обикновено краен, (W) набор от резултати, (succeq) отношение на предпочитания и (E) отношение на действие.

Тази математическа структура е известна още като релационна структура (Blackburn, Rijke, & Venema 2001), която е теоретично зададен еквивалент на така наречената модална логика (Blackburn et al. 2001), математически език, който е добре подходящ. да се изразят математическите свойства на отношенията. Отсега нататък ще бъде обозначена релационна структура (F), която означава рамка.

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

[V: W / до 2 ^ / texttt {Atoms})

асоциирайки към всеки резултат набора от предложения атоми, които са верни при този резултат.

Капак ((F, V)) ще бъде посочен като модел, който ще бъде обозначен (M).

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

Следващият параграф събира основните технически понятия, необходими за тълкуване на модалните езици, използвани в този запис. Читателят, вече запознат с модалната логика, може да го прескочи. За по-задълбочено изследване може да се консултирате със съответния запис относно модалната логика (Garson 2014). Добре познатите класически учебници са Modal Logic: An Introduction (Chellas 1980), който се фокусира върху ненормалните модални логики, и Modal Logic (Blackburn et al. 2001), който вместо това се фокусира върху по-математическото третиране на нормалната модална логика. ^[2]

Прехвърляне Logic: фонови понятия: А модална логика е разширение на езика на Пропозиционални логика с набор от модалните оператори (Box_1 / ldots / Box_n, / ldots), определени от изброимо множество атомни предложения (texttt {Atoms} = {p_1, p_2, / ldots }), над които се изгражда наборът от добре оформени формули (за математическо третиране на логиката и индукцията вижте например Dalen 1980). Всяка добре оформена формула (varphi) на модален език (mathcal {L}), оттук нататък просто наречена формула, се конструира, използвайки следната граматика:

) varphi:: = p / mid / lnot / varphi / mid / varphi / wedge / varphi / mid / Box_i / varphi)

където (Box_i / в { Box_1, / ldots, / Box_n, / ldots }) и (p / in / texttt {Atoms}).

Модел за този език е структура (M = ((W, R_1, / ldots, R_n, / ldots), V)), състояща се от набор от светове или състояния или резултати (W); отношение на достъпността (R_i) за всеки модален оператор (Box_i), дефинирано чрез така наречените квартални функции (Chellas 1980), т.е. функции (R_i: W / до 2 ^ {2 ^ {W}}); и функция за оценка (V: / texttt {Atoms} до 2 ^ {W}), която приписва на всяко атомно предложение подмножество от (W), с идеята, че всяко атомно предложение е присвоено на множеството на светове, в които това твърдение е вярно.

Като общо правило, мултимодален език с модалности (Box_1), …, (Box_n), … ще бъде означен с (mathcal {L} ^ {f (Box_1), / ldots, f (Box_n), / ldots}), където функцията (f) асоциира към всяка модалност своята интуитивна стенограма. Нека (Delta) е модален език, състоящ се от модалности (Box_1), …, (Box_n), … и нека (M = ((W, R_1, / ldots, R_n, / ldots), V)) да бъде модел за този език. Отношението на удовлетвореност на формула (varphi / в / Delta) по отношение на двойка ((M, w)), където (w / in W), се определя в съответствие със следните условия за истинност:

) начало {подравняване *} M, w & / модели p & mbox {ако и само ако} & w / в V (p) / M, w & / модели / neg / varphi & / mbox {ако и само ако } & M, w / не / модели / varphi \\ M, w & / модели / varphi / land / psi & / mbox {ако и само ако} & M, w / модели / varphi / mbox {и} M, w / модели / psi \\ M, wy & / модели / Box_i / varphi & / mbox {ако и само ако} & / varphi ^ M / в R_i (w) / \ end {align *})

където (varphi ^ {M} = {w / в W / средата на M, w / модели / varphi }) се нарича набор от истини или разширение на (varphi).

Формула (varphi) на модален език (Delta): държи в състояние (w) на модел (M) всеки път (M, w / models / varphi); е валиден в модел (M), обозначен (models_ {M} varphi), ако и само ако (M, w / модели / varphi) за всеки (w / в W), където (W) е домейнът на (M); е валиден в клас от модели (mathcal {M}), обозначен (модели _ { mathcal {M}} varphi), ако и само ако е валиден във всеки (M / в / mathcal {M}); е валидно в рамка ({F}), обозначена (модели _ {{F}} varphi), ако и само ако за всяка оценка (V) имаме това (модели _ {(F, V)} varphi); е валиден в клас от рамки (mathcal {F}), обозначен (модели _ { mathcal {F}} varphi), ако и само ако е валиден във всеки (F / в / mathcal {F}).

Наборът от формули на (Delta), които са валидни в клас от модели (mathcal {M}) се обозначава (Delta _ { mathcal {M}}) (за кадрите обозначението е (Delta _ { mathcal {F}})). За набор от формули (Sigma) пишем (M, w / модели / Sigma), за да кажем, че (M, w / models / sigma), за всички (sigma / in / Sigma). Казваме, че набор от формули (Sigma) семантично включва формула (varphi) в клас от модели (mathcal {M}), обозначени (Sigma / models _ { mathcal {M }} varphi), ако за всеки (M / in / mathcal {M}) имаме, че (models_ {M} Sigma) предполага (models_ {M} varphi).

Модално правило

) frac { varphi_1, / ldots, / varphi_n} { psi})

е звук в клас от модели (mathcal {M}), ако (varphi_1, / ldots, / varphi_n / models _ { mathcal {M}} psi).

Спомнете си, че след Челлас (1980) модалната логика (Delta) се нарича класическа, ако е затворена при правилото за еквивалентност, т.е. за всяко (поле) на езика (Delta) ние имаме:

) frac { varphi / leftrightarrow / psi} { Box / varphi / leftrightarrow / Box / psi})

Тя се нарича монотонна, ако е класическа и освен това е затворена под правилото за монотонност, т.е. за всеки (поле) на езика (Delta) имаме:

) frac { varphi / rightarrow / psi} { Box / varphi / rightarrow / Box / psi})

Тя се нарича нормална, ако е монотонна, тя е затворена под правилото на обобщаване и съдържа аксиомата (K), т.е. за всяка (поле) във формулите на (Delta) имаме

) frac { varphi} { Box / varphi})

и (Delta) съдържа (Box (varphi / to / psi) to (Box / varphi / to / Box / psi)).

Нормалната модална логика може да се интерпретира в структури с формата (M = ((W, R'_1, / ldots, R'_n, / ldots), V)), където всеки (R'_i) е главен филтър ^[3] или, алтернативно, той е във формата (R'_i: W / до 2 ^ {W}).

2.1 Предпочитания

Спомнете си релационната структура ((mathcal {N}, W, / succeq, E)) и помислете за отношението (succeq). Тази връзка компактно представлява семейство ({ succeq_i } _ {i / в N}) от индивидуални отношения на предпочитания, всеки индексиран с играч.

Формално предпочитание към играча (i) е отношение

) succeq_i / subseteq W / пъти W)

Идеята е, че ако два резултата (w) и (w ') са такива, че ((w, w') in / succeq_i) тогава играчът (i) счита резултата (w) поне толкова добър, колкото резултат (w '). Фактът, че ((w, w ') в / succeq_i) ще бъде съкратено (w / succeq_i w'). Неговата обратна страна е отношението (precedq_i), което се отнася за ((w, w ')) винаги, когато (w' / succeq_i w). Неговият строг контрагент е отношението (succ_i), което се отнася за ((w, w ')) винаги, когато (w / succeq_i w') и не е така, че (w '\ succeq_i w). Освен това (w / sim_i w ') означава факта, че (w / succeq_i w') и (w '\ succeq_i w), което означава, че (i) е безразличен между (w) и (w ').

Пример 3: Да се върнем към основния ни пример. Обикновено страните имат предпочитания пред резултата от решението, например Италия смята, че трябва да отделим между 5 и 10 милиона евро за схемата, Германия смята, че трябва да похарчим между 1 и 2, Белгия между 4 и 5, Люксембург, Холандия и Франция точно 5. Това означава, че отношението на предпочитанията на Италия е такова, че (w / succ _ { textrm {Италия}} w ') всеки път (textrm {5M} leq w / leq / textrm {10M}) и или (w '> / textrm {10M}), или (0 / leq w' / textrm {10M}) или (0 / leq w '<\ textrm {5M}), (w / succ _ { textrm {Италия}} w ') всеки път (textrm {5M} leq w' <w / leq / textrm {10M}), докато (w / sim _ { textrm {Италия}} w '), в противен случай. Не всички резултати от гласуването ще постигнат споразумение. След това за технически цели определяме спомагателен резултат (w ^ {d}),интерпретиран като резултат от несъгласие. Идеята е, че това е резултат от вота, който не постига консенсус. Приемаме, че всяко споразумение е строго по-добро за всеки играч, отколкото несъгласие, т.е. (w / succ _ {{i}} w ') всеки път (w' = w ^ {*}) и (w / neq w ^ {*}), за всеки (i / в N).

Свойствата на тези отношения могат да бъдат изразени с помощта на модална логика. За целта въвеждаме модални оператори (Diamond ^ { predeq} _i), (Diamond ^ { prec} _i) и (Diamond ^ { sim} _i) за всеки от съответните отношения.

Интерпретацията за (R / в { превес, / prec, / sim }) е следната:

[M, w / models / Diamond ^ {R} _i / varphi / enskip / mbox {ако и само ако} enskip M, w ^ { prime} модели / varphi, / mbox {за някои} w ^ { prime} mbox {с} w R_i w ^ { prime})

Въпросните отношения често идват с допълнителни свойства. Например, (precedq_i) обикновено се приема, за да удовлетвори следното:

• рефлексивност, т.е. (forall w / в W, i / в N,) имаме това: (w / precedq_i w);
• транзитивност, т.е. (forall w_1, w_2, w_3 / в W, i / в N,) имаме, че: ((w_1 / precedq_i w_2) и (w_2 / precedq_i w_3)) означава, че (w_1 / preceq_i w_3).
• свързаност, т.е. (forall w_1, w_2 / в W, i / в N,) имаме това: или (w_1 / precedq_1 w_2), или (w_2 / precedq_i w_1).

На първите две свойства могат да се характеризират с нормален модална логика с един модален оператор на играч, с помощта на следните аксиоми и Срокът на валидност.

Предложение 1

) начало {подравняване *} models_F / varphi & / rightarrow / Diamond ^ { predeq} _i / varphi & / mbox {ако и само ако} & / predeq_i / mbox {е рефлексивен} / \ models_F / Diamond ^ { precedq} _i / Diamond ^ { precedq} _i / varphi & / rightarrow / Diamond ^ { predeq} _i / varphi & / mbox {ако и само ако} & / predeq_i / mbox {е преходен} край {приравни *})

Това обаче не е така за свързаността, тъй като модалните езици като този могат да говорят само за локални свойства на отношенията (Blackburn et al. 2001).

За целта трябва да въведем специален тип оператор: универсалната (или глобалната) модалност (Goranko & Passy 1992). Тази модалност изразява свойствата на всички състояния в домейн (W) на модел (M) и се интерпретира по следния начин.

[M, w / модели A / varphi / enskip / mbox {ако и само ако} enskip M, w ^ { prime} модели / varphi, / mbox {за всички} w ^ { prime} в W)

Формулата (neg A / neg / varphi) ще бъде съкратена (E / varphi). Символът (E) е екзистенциалният дуал на (A) и показва, че определена формула е в някакво състояние в модела. С глобалната модалност имаме истинско допълнение на експресивността (заедно с по-нататъшните разходи и по-нататъшни печалби, както е показано в Goranko & Passy 1992), следователно можем да изразим валидност по модел чрез изразяване на истината в един свят, свидетел на факта, че (M, w / модели A / varphi) има, ако и само ако (models_M / varphi) има.

Спомнете си, че отношение (R) е трихотомно, ако и само ако за всички (x, y / в W) или случаят е (xRy, yRx), или (y = x). Можем да използваме комбинация от предпочитания и глобални модалности, за да получим следната рамкова кореспонденция.

Предложение 2 Нека (F) е рамка. Имаме това:

(models_F (varphi / wedge / поле ^ { preceq} _i / psi) до A (psi / vee / varphi / vee / Diamond ^ { predeq} _i / varphi)) само и само ако (precedq_i) е трихотомен

Алтернативна и вероятно по-интуитивна формула, която може да се използва вместо това, е (p, q) атомни предложения:

[E p / land E q / to E (p / land q) lor E (p / land / Diamond ^ { predeq} _i q) lor E (q / land / Diamond ^ { predeq} _i p))

Трихотомията, транзитивността и рефлексивността на (precedq_i) са еквивалентни на това, че отношението е слаб линеен ред и следователно е свързано.

Отношението (prec_i), т.е. отношението на строги предпочитания, може да бъде дефинирано по отношение на (precedq_i). Но (prec_i) удовлетворява следното свойство:

нерефлексивност, т.е. (forall w / в W, i / в N,) имаме това: не е така (w / prec_i w)

Нерефлексивността не може да се определи в основната модална логика (Blackburn et al. 2001). Ако обаче атомните предложения са достатъчно мощни, за да разделят всеки резултат отделно, тогава нерефлексивността става определяема. Например, нека (w_k) е променлива идентифицираща света (w_k). ^[4] Имаме следното.

Предложение 3

) models_F w_k / to / neg / Diamond ^ / prec_i w_k / enskip / mbox {ако и само ако} enskip / prec_i / mbox {не е рефлексивен})

И накрая, отношението за равнодушие (sim) удовлетворява свойствата на рефлексивност, транзитивност и симетрия. Докато рефлексивността и транзитивността са дефинирани аналогично на предишните модалности, симетрията се дефинира както следва.

симетрия, т.е. (forall w_1, w_2 / в W, i / в N,) имаме, че: (w_1 / sim_i w_2) означава, че (w_2 / sim_i w_1)

Докато аксиомите за първите две са подобни на тези за (precedq_i), симетрията се характеризира както следва

Предложение 4

) models_F (psi / to / Box ^ { sim} _i / Diamond ^ { sim} _i / psi) enskip / mbox {ако и само ако} enskip / sim_i / mbox {е симетричен})

Трите свойства по-горе казват заедно, че всяко (sim_i) е математически отношение на еквивалентност, т.е.

) bigcup_ {w / в W} {[w] mid w '\ в [w] mbox {винаги} w / sim_i w' })

е дял на (W). Всеки елемент от този дял е клас безразличие за играча (i), т.е. набор от резултати, към които той или тя е безразличен.

Логиката на отношенията на еквивалентност, като (sim_i), е известна също като системата ({ bf S5}).

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

Една функция полезност е функция

[u_i: W / rightarrow / mathbb {R})

картографиране на резултатите до реални числа, представящи колко играч оценява определено състояние.

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

Определение 5 Нека (u) е полезна функция. Казваме, че (succeq ^ * _ i) съответства на (u), ако има следното:

[w / succeq ^ * _ i w '\ enskip / textrm {ако и само ако} enskip u_i (w) geq u_i (w'))

Забележете как всеки слаб линеен ред над ограничен набор от резултати съответства на някаква функция на полезност.

За по-подробен анализ на ролята на предпочитанията във философията и теорията на решенията се обръщаме към свързаните записи относно предпочитанията (Hansson & Grune-Yanoff 2011) и теорията на решенията (Steele & Stefansson 2015).

2.2 Избори

Играта е и описание на това, което играчите могат да постигнат, самостоятелно или в рамките на коалиции. За да формализираме това, използваме функции за ефективност, абстрактни модели на власт, въведени за изучаване на стратегии за гласуване в комитетите (Moulin & Peleg 1982).

Функция за ефективност (Moulin & Peleg 1982) е функция

[E: 2 ^ {N} до 2 ^ {2 ^ {W}})

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

Идеята е, че когато случаят е, че (X / в E (C)), тогава коалицията (C) е в състояние да реши, че резултатът от играта се намира вътре в множеството (X), и следователно може да изключи резултатите в крайна сметка (W / setminus X). С други думи (X) е в силата на коалицията (C).

Функциите за ефективност са затворени под суперсетове, т.е. имаме, че (X / в E (C)) и (X / subseteq Y / subseteq W) предполагат, че (Y / в E (C)). С други думи, ако (X) е в силата на коалицията (C), тогава това е и всяко от суперсети на (X). От това, забележете, следва, че ако функция за ефективност на определена коалиция не е празна, тя винаги съдържа множеството от всички резултати.

За (mathcal {X} subseteq {2 ^ {W}}) обозначаваме (mathcal {X} ^ {+}) неговото затваряне на суперсета.

Пример 4: Връщайки се към основния пример, помислете за силата на всяка отделна държава. Поради правилата на играта, никоя държава не е сама в състояние да изключи какъвто и да е резултат.

Прибягвайки до функции за ефективност: за всеки (i / в N) имаме това (E ({i }) = {W }).

Това обаче е и при коалициите, които не са достатъчно големи. Например вземете всички коалиции от поне две държави, които могат да се образуват между Холандия, Белгия и Люксембург.

) начало {подравняване *} E ({ mbox {Люксембург, Белгия} }) & = \\ E ({ mbox {Люксембург, Холандия} }) & = \\ E ({ mbox {Белгия, Холандия} }) & = \\ E ({ mbox {Люксембург, Белгия, Холандия} }) & = {W }. / end {align *})

Тъй като общата им тежест е най-много до 5 гласа, те сами по себе си не могат да постигнат или да изключат всяко възможно споразумение. В действителност, за актовете, предложени от Комисията, всяка коалиция (C), чието тегло на глас не е най-малко 12, има една и съща функция за ефективност (E (C) = {W }).

За останалите коалиции ситуацията е друга. Помислете например за коалицията, направена от Франция, Германия и Италия, които заедно имат тежест на глас 12. За тях имаме, че:

[E ({ textrm {Франция, Германия, Италия} }) = { {w } средата w / в W } ^ {+})

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

Какво ще кажете за актовете, които не са предложени от Комисията? За тях нека използваме различна функция за ефективност, която обозначаваме (E ^ {*}).

В този случай печелившата коалиция трябва да се състои от най-малко четирима членове.

Така (E ^ {*} ({ mbox {Франция, Германия, Италия} }) = {W }), докато (E ^ {*} ({) Франция, Германия, Белгия, Холандия (}) = { {w } средата w / в W } ^ {+}).

В общия случай се счита, че (E (C) = E ^ {*} (C)) винаги, когато (| C | / geq 4). Поради свойствата на играта за гласуване, ние също имаме, че (E (C) = E ^ {*} (C)) всеки път (| C | / leq 2). Разликата се прави чрез коалиции с размер 3: с (E ^ {*}) те никога не могат да постигнат повече от ({W }), докато с (E) те могат да постигнат ({ {w } mid w / in W } ^ {+}), ако тяхната право на глас е най-малко 12. Забележете, че Люксембург няма значение, когато става въпрос за предложени от Комисията законопроекти, т.е. (E (C) = E (C / cup / textrm {Люксембург})). Това не е така при другите законопроекти, както наблюдавахме.

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

Определение 6 [Коалиционни модели] Коалиционният модел е троен ((W, E, V)), където:

• (W) е непразен набор от състояния;
• (E: W / longrightarrow (2 ^ {N} longrightarrow 2 ^ {2 ^ W})) е функция за динамична ефективност;
• (V: W / longrightarrow 2 ^ { texttt {Atoms}}) е функция за оценка.

Както читателят ще забележи, динамичните функции за ефективност позволяват на всяко състояние да има различно разпределение на мощността между коалициите. Това е strictu sensu без значение за третирането на мощността в игрите с нормална форма (Раздел 3), където ефективността на функциите, свързани с резултатите, също може да се приеме за еквивалентна навсякъде в модела, но моделът е достатъчно общ, за да третира широко и повторно взаимодействие, при което последователната структура на взаимодействието е дефинирана изрично. Обикновено ще съкратим (E (w) (C)) като (E_w (C)) или дори (E (C)), когато е ясно от контекста.

Езикът, използван за обсъждане на Coalition Models, е Coalition Logic (Pauly 2001), ненормална модална логика за изразяване на избор на групи от играчи. Коалиционната логика е разширение на логиката на предложение с модалности (| 2 ^ {N} |) на формата ([C]), така че модален оператор, всеки индексиран с коалиция.

Отношението на удовлетвореност на формулите на формата ([C] varphi) по отношение на двойка (M, w) се определя, както следва:

[M, w / models [C] varphi / enskip / textrm {ако и само ако} enskip / varphi ^ M / в E_w (C))

където, (varphi ^ M = {w / в W / средата на M, w / модели / varphi }).

Интуитивно (varphi ^ M / в E_w (C)) означава, че коалицията (C) е в състояние да постигне свойство (varphi).

Тъй като затварянето под суперсет или монотонност на изхода се приема като свойство на всички функции на ефективността, правилото за монотонност е валидно в коалиционната логика, което следователно е монотонна модална логика (Hansen 2003).

Правилото за монотонност приема тази форма за всеки (C / subseteq N):

) frac { varphi / to / psi} {[C] varphi / до [C] psi})

Интуитивно, ако (C) е в състояние да постигне (varphi) и имаме, че (varphi) предполага (psi), тогава (C) също е в състояние да постигне (ИОС).

Математически свойства на силата Освен монотонността на резултатите, много други свойства могат да се считат за необходими за моделиране на коалиционната сила в игрите. Например функция за ефективност има свойството:

• жизненост, т.е. (празен набор / не / в E (C)), за всеки (C / subseteq N);
• безопасност, т.е. (W / в E (C)), за всеки (C / subseteq N);
• редовността, т.е. (X / в E (C)) означава, че (overline {X} не / в E (overline {C})), за всеки (C / subseteq N, X / subseteq W);
• N -максималност, т.е. (overline {X} в E (празен набор)) означава, че ({X} в E (N)) и (X / subseteq W);
• свръхпроизводителност, т.е. (X / в E (C)) и (Y / в E (D)) означава, че (X / cap Y / в E (C / чаша D)), за всеки (C), (D / subseteq N), (C / cap D = / emptyset), (X, Y / subseteq W);
• монотонност на коалицията, т.е. (X / в E (C)) означава, че (X / в E (D)), за всеки (C / subseteq D / subseteq N), (X / subseteq W);
• добре обоснованост, т.е. (X / в E (N)) означава, че ({x } в E (N)), за някои (x / в X), за всеки (X / subseteq W).

Функция за ефективност се нарича играеща (Pauly 2001), ако има жизненост, безопасност, N-максималност и свръхдатливост. Нарича се наистина играеща (Goranko, Jamroga, & Turrini 2013), ако е игрална и добре обоснована. Забележете, че ако (W) е ограничена, функция за ефективност е възпроизвеждана, ако и само ако е наистина играеща (Goranko et al. 2013).

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

Пример 5: Всички функции на ефективността на нашия работен пример са наистина играещи.

В структурите на съседства отношенията между теоретично зададените и логическите свойства често са непосредствени и стандартните резултати за съответствие между класа от кадри и съседни функции (Chellas 1980) могат да бъдат автоматично използвани за коалиционна логика.

Коалиционната логика всъщност е достатъчно изразителна, за да характеризира всички ограничения, споменати досега.

Предложение 7 Нека (F = (W, E)) е рамка на коалицията, и (C, C ^ { prime}, C '') са коалиции, така че (C / cap C '= / празен набор) и (C / subseteq C ''). Следват следните резултати:

• (models_F [C] varphi / to / neg) overline {C}] neg / varphi), ако и само ако (E) е редовен;
• (models_F [C] top), ако и само ако (E) има безопасност;
• (models_F [C] varphi / to [C ''] varphi), ако и само ако (E) е монотонно коалиция;
• (models_F / neg [C] bot), ако и само ако (E) има оживление;
• (models_F / neg) emptyset] neg / varphi / до [N] varphi), ако и само ако (E) е N -максимално;
• (models_F [C ^ { prime}] varphi / wedge [C] psi / to [C ^ { prime} cup C] (varphi / wedge / psi)) само и само ако (E) е свръхприемлива;
• (varphi / to / psi / models_F [C] varphi / to [C] psi), ако и само ако (E) е монотонен резултат.

За доказателствата се консултирайте с Поли 2001.

Резултатите от кореспонденцията ни позволяват да разграничим по модален начин редица клас кадри. Въпреки това експресивността на модалните оператори силно ограничава капацитета на езика да различава класове структури. В тази степен читателят трябва да забележи, че логиките както на възпроизвежданите, така и на наистина възпроизвежданите рамки за ефективност споделят факта, че (models_F) emptyset] top). Това предложение обаче, чието тълкуване е, че за всеки (w / в W, {W } в E_w (празен набор)) не е достатъчно, за да направи официално разграничение между (E_w (празен набор)) в двата различни класа функции на ефективност.

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

Теорема 8 (Goranko et al. 2013) Нека (mathcal {P}) е класът на рамки за игра и (mathcal {P} ^ {*}) клас на наистина играещи се. След това за всяка формула на коалиционната логика (varphi)

) models_ / mathcal {P} varphi / textrm {ако и само ако} модели _ { mathcal {P} ^ {*}} varphi)

Това следва от факта, че Playable Coalition Logic има свойството на крайния модел (Pauly 2001) и в крайните модели функциите за ефективност на възпроизвеждане са наистина играещи. ^[5]

Както беше посочено по-рано, в този запис ще се споменава само как знанието е имплицитно в структурите на игрите, но няма да се задълбочава в изучаването на епистемични предпоставки за рационална игра. Свързани записи, посветени на епистемичната логика (Hendricks & Symons 2006), динамичната епистемична логика (Baltag & Renne 2016) и в частност теорията на епистемичните игри (Pacuit & Roy 2015), изследват в дълбочина ролята на знанието при вземане на решения. Третиране на модалната логика за игри, която вместо това се фокусира върху ролята на информацията, е Hoek & Pauly 2006.

3. Анализиране на мощността

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

Разделът първо описва общата настройка на съвместните игри, след това разглежда по-ограничения и вероятно по-добре известен клас на стратегическите игри.

3.1 Кооперативни игри и тяхната логика

Описанието на играта, дадено в релационна структура на формата ((mathcal {N}, W, / succeq, E)), не е достатъчно, за да разберем кой точно резултат ще бъде избран в крайна сметка. За това ни е необходима концепция за решение, т.е. карта, която свързва към играта набор от резултати от тази игра (Abdou & Keiding 1991).

Бяха въведени редица концепции за решения за коалиционните игри (виж например Osborne & Rubinstein 1994 и Apt 2009 (Други интернет ресурси)). За сегашните цели ще обсъдим само това, което е възможно най-добре познатото: ядрото. Ядрото е съвкупност от стабилни резултати, т.е. резултати, за които няма коалиция, чиито членове могат и желаят да се отклонят от нея. Може да се разглежда като набор от резултати, към които няма ефективна опозиция (Abdou & Keiding 1991).

Формално, като се има предвид релационна структура (F = (mathcal {N}, W, / succeq, E)), изход (w / в W) се казва, че е стабилен, ако няма коалиция (C) и набор от резултати (X / subseteq W), така че да са изпълнени и двете от следните условия:

1. (X / в E (C))
2. (y / в X) и (i / в C) означава, че (y / succ_i w)

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

В сърцевината е събирането на всички резултати стабилни.

Пример 6:

Помислете за резултата 1М, което е единственият резултат, който Германия смята за приемлив. Както вече беше отбелязано, Германия има функция на ефективност на (E ({ textrm {Германия} }) = {W }), така че сами по себе си не са в състояние да превърнат предпочитанията си в резултат. Въпреки това, заедно с други държави, те са в състояние да го направят. Да предположим, че техните съюзници са Белгия, Франция и Холандия. Тогава 1М е добър резултат? Ако погледнем предпочитанията на останалите участници в коалицията, т.е. Белгия, Франция, Холандия, наблюдаваме следното. Белгия има по-скоро резултат между 4M и 5M, Франция и Холандия точно 5M. Тези страни биха могли да се съберат и да изберат 5 милиона, което е приемлив за тях резултат. Въпреки това функцията на ефективност на ({) Белгия, Франция, Холандия (}) е (E ({) Белгия, Франция,Холандия (}) = {W }), което означава, че трите държави не са достатъчни, за да приемат сметката за 5 милиона. Но коалицията, направена от Белгия, Франция, Италия и Холандия, ще бъде. Забележете още, че 5M е един от предпочитаните резултати на Италия. 5M всъщност е единственият стабилен резултат от играта: няма коалиция, която да е заедно желаеща и способна да се отклони от нея.

Модалната логика може да се използва за представяне на ядрото. Обмислете първо формулата

[p / rightarrow / bigvee_ {C / subseteq N} [C] вляво (bigwedge_ {i / в C} Diamond ^ / succ_i p / вдясно))

Това казва, че ако (p) е вярно, тогава членовете на някаква коалиция могат да се подобрят в някакъв (p) свят, което не изглежда правилната формула за изразяване на стабилност в логиката. Въпреки това можем да докажем следните резултати, които използват съответствието между формулата и конкретен клас кадри.

Нека (E) е (монотонна) резултатност функция и (succeq_i) слаб линеен ред. Тогава:

[(F, V '), w / модели p / rightarrow / bigvee_ {C / subseteq N} [C] наляво (bigwedge_ {i / в C} Diamond ^ / succ_i p / вдясно))

има стойност (w) за всеки (V '), ако и само съществува (C / подсектор N) и (X / в E_w (C)), така че за всички (i / в C), (x / в X) имаме това (x / succ_i w).

Така че формулата важи при (w) за всяка оценка, ако и само ако (w) не принадлежи към ядрото. Ясно е, че ако формулата е невярна при резултат и някакво оценяване, това означава, че резултатът наистина принадлежи към сърцевината.

Забележете, тъй като функциите на ефективност са монотонни, ако имаме това (X / в E_w (C)) и

[X / subseteq / наляво (bigwedge_ {i / в C} Diamond ^ / succ_i p / дясно) ^ {(F, V ')},)

тогава

) вляво (bigwedge_ {i / в C} Diamond ^ / succ_i p / right) ^ {(F, V ')} в E_w (C).)

Също така забележете, че резултатът по-горе позволява случаят на

) emptyset = / наляво (bigwedge_ {i / в C} Diamond ^ / succ_i p / дясно) ^ {M} в E_w (C),)

което може да бъде противодействащо. Изискването (E) да има оживление се грижи за това.

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

Предложение 10 Нека (F) е рамка. Имаме това

) models_F p / rightarrow / bigvee_ {C / subseteq N} [C] вляво (bigwedge_ {i / в C} Diamond ^ / succ_i p / вдясно))

ако и само ако няма резултат в (F) принадлежи на ядрото.

Отново оживеността щеше да се погрижи за тривиалния случай, в който

) вляво (bigwedge_ {i / в C} Diamond ^ / succ_i p / дясно) ^ {(F, V)} = / празен набор.)

Алтернативен подход е да се идентифицира всеки резултат с име (или номинално) на езика, т.е. да се използва хибридна логика. Тогава имаме следното.

Предложение 11 Нека (w_k) атомното предложение е вярно при изход (w_k) и само при изход (w_k).

[(F, V), w_k / модели w_k / rightarrow / bigvee_ {C / subseteq N} [C] наляво (bigwedge_ {i / в C} Diamond ^ / succ_i w_k / дясно))

ако и само ако (w_k) не принадлежи към ядрото.

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

3.2 Стратегически игри и тяхната логика

Игрите в нормална форма или стратегическите игри представляват какво могат да постигнат индивидите, а не коалициите и какви са техните предпочитания.

Формално стратегическата форма за игра е кортеж

[(N, W, { Sigma_i } _ {i / в N}, o))

където N е краен набор от играчи, (W) набор от резултати, ({ Sigma_i } _ {i / в N}) сбор от стратегии, по една за всеки играч (i), (o: / prod_ {i / в N} Sigma_i / до W) функция на резултата, свързваща набор от стратегии към резултат.

Стратегическа игра е кортеж ((S, { succeq_i } _ {i / в N})), където (S) е стратегическа форма на игра и ({ succeq_i } _ { i / в N}) колекция от отношения на предпочитания, по една за всеки играч (i).

Пример 7: Ако мислим за страните в предишния ни пример като отделни играчи и техните гласове като индивидуални стратегии, можем да моделираме играта на Римския договор като стратегическа игра, при която всеки индивид може да гласува сума пари, която да отдели за защита на границите и предпочитанията са както по-горе.

Функцията за резултат ще се погрижи за присъединяването към гласа на всеки отделен играч окончателния резултат от колективното решение, например, избиране на резултат, гласуван от набор от държави с тежест на гласуване най-малко 12, или в резултат на което няма решение, ако не бъде постигнат консенсус, Например:

• Франция гласува 0М
• Белгия гласува 2 милиона
• Италия гласува 10 милиона
• Германия гласува 0М
• Холандия гласува 0 милиона
• Люксембург гласува 0М

Този кръг не дава никакво решение, тъй като нито един резултат не е събрал тежест на гласуване от поне 12.

Да предположим обаче, че вторият тур е такъв, че всички, освен Белгия, се придържат към своя вот и приемете, че Белгия преминава към гласуване 0M. Сега 0M има съвкупност от 13, което означава, че е избран за окончателно решение.

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

Нека първо помислим какво може да направи група играчи в нормална игра. За целта ние дефинираме функцията (alpha) - ефективност, математическо описание на коалиционните стратегии в играта по отношение на изходните резултати, които те могат да принудят.

Определение 12) (alpha) - ефективност функция] Нека (S) е стратегическа игра. Дефинираме функцията на ефективност (alpha) на (S), (E ^ { alpha} _S (C)):

(E ^ { alpha} _S (C) = {X / \ mid) съществува (sigma_C) такъв, че за всички (sigma '_ { overline {C}}) имаме че (o (sigma_C, / sigma '_ { overline {C}}) в X })

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

Предложение 13 (Горанко и др. 2013)

Функцията (alpha) - ефективност на стратегическата игра е наистина играеща.

Следващият резултат показва връзката между стратегиите и функциите на ефективността.

Теорема 14 (Горанко и др. 2013)

Функцията за ефективност е наистина възпроизводима, ако и само ако е (alpha) - ефективността функция на някаква стратегическа игра.

Това е обобщение на резултата в Peleg 1998 за ограничени игри, започвайки от модели на стратегически игри, първоначално дефинирани в Pauly 2001. С две думи това, което тези резултати предполагат, е следното.

Предложение 15 Нека (F) релационна структура на играта. Тогава (F) е стратегическа игра, ако и само ако следните формули са валидни в (F) за разминаване (C, C ^ { prime}):

• (varphi / to / psi / models_F [C] varphi / to [C] psi)
• (models_F [C] горе)
• (models_F / neg [C] bot)
• (models_F / neg) emptyset] varphi / до [N] varphi)
• (models_F [C ^ { prime}] varphi / wedge [C] psi / to [C ^ { prime} cup C] (varphi / wedge / psi))

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

Равновесие и дефинираност на Наш Основната концепция за анализ на стратегическите игри е равновесието на Наш. Неофициално равновесието на Наш е съвкупност от стратегии, по една на играч, така че никой играч не е заинтересован да промени стратегията си, като се имат предвид останалите да се придържат към тяхната. Формално профилът на стратегия (sigma) е (чиста стратегия) равновесие на Неш, ако за всички играчи (i / в N) и за всички (sigma'_i / в / Sigma_i) имаме това

[o (sigma_i, / sigma _ {- i}) succeq_i o (sigma'_i, / sigma _ {- i}))

Пример 8: Обмислете следното гласуване

• Франция гласува 5 милиона
• Белгия гласува 5 милиона
• Италия гласува 10 милиона
• Германия гласува 1М
• Холандия гласува 5 милиона
• Люксембург гласува 5 милиона

В тази игра няма консенсус по никакъв бюджет. Ситуацията може да изглежда като задънена улица, тъй като всички са гласували според предпочитанията си. Резултатът обаче е разногласие, което нито един играч не предпочита никакво споразумение. Единственият начин играчите да се сближат със споразумение е Италия да промени гласа си на 5 милиона. Ако това се случи, 5М се постига като резултат.

Забележете, че модифицираната игра, в която Италия гласува 5M, е равновесие на Наш.

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

Как да изразим равновесието на Наш в логиката? Спомнете си как формулата

[p / до / bigvee_ {C / subseteq N} [C] вляво (bigwedge_ {i / в C} Diamond ^ / succ_i p / вдясно))

има рамка (F), ако и само ако ядрото е празно, а хибридното логическо разширение може да ни каже дали конкретен резултат принадлежи на ядрото. Ако (F) се основава на действително възпроизводима функция за ефективност, ние вече имаме нормална версия на играта на формата на ядрото: резултат такъв, че никоя коалиция не е в състояние и не е в състояние да се отклони, без да се взема предвид какво правят другите. Въпреки това Nash Equilibrium фиксира профил на стратегии, така че никой играч не може и не желае да се отклони от там. С други думи, тя изисква идеята за най-добър отговор на играча по отношение на даден профил.

Формализми като коалиционната логика са твърде слаби, за да изразят равновесието на Наш. Те обаче могат да изразят факта, че определени функции на ефективност позволяват възможността за равновесие на Наш. Това е, което в Hansen & Pauly 2002 се нарича несъответстваща на Nash Coalition Logic. Равновесието на Наш всъщност не е определено в основна модална логика (Benthem et al. 2011), но може да се направи с модалност, която пресича както отношенията на предпочитания, така и отношенията на избор (Benthem et al. 2011).

((F, V), w / models / langle / Appro_i / cap / succ_i / rangle / varphi), ако и само ако (w (pribli_i / cap / succ_i) w ') означава, че (w' / модели / varphi)

Тогава най-добрият отговор за (i) се определя като (langle / Appro_i / cap / succ_i / rangle / top), тъй като няма алтернатива, която в същото време да е постижима и за предпочитане пред (i), Алтернативно, хибридна логика, която споменава стратегическите профили на езика, може да осигури решение, подобно на случая с ядрото.

3.2.1 Немонотонна логика на действие

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

Вместо да използва функции за ефективност, всеки играч (i) е свързан с отношение на еквивалентност (приблизително_i / подсетек W / пъти W), чийто индуциран дял представлява избора, който той или тя може да извърши. Тези отношения на еквивалентност описват точния набор от избори, които група играчи могат да изпълняват и първоначалните модели са посочени като последователни в литературата (виж например Belnap, Perloff, & Ming 2001).

Сега дефинирайте функция за ефективност (E ^ {*}), за която тя държи това

[E ^ {*} (i) = {[x] mid x '\ в [x] mbox {винаги} x / приблизително x' } ^ {+})

Интуитивно (E ^ {*} (i)) събира какво точно могат да постигнат индивидите и всичките им суперсети.

(E ^ {*}) се нарича последователен, ако има това:

• (E ^ {*} (C) = { bigcap_ {i / в C} X_i / mid / mbox {за някои} X_i / в E ^ {*} (i) })
• (празен набор / не / в E ^ {*} (C)) за всеки (C / neq N)
• (E ^ {*} (N) = { {x } средата x / в W } ^ {+})

Забележете, че (E ^ *) е наистина възпроизводима функция за ефективност.

Последното свойство е обоснованост, както в случая на произволни функции на ефективност. Това не е свойство, което се приема във всички варианти, например структурите за избор в Kooi & Tamminga 2008 и неговият времеви вариант STIT (Belnap et al. 2001) не го правят. Както обаче се забелязва в Turrini 2012 и Tamminga 2013, добре обосновани последователни модели съответстват на стратегическите игри и функцията на ефективност (E) може да бъде ефективно симулирана от съотношението на еквивалентност (приблизително_i) за всеки играч. Интуитивно (E ^ {*} (i)) е набор от набори резултати, които (i) могат да избират, без да могат да се прецизират допълнително.

За да разсъждаваме за последователни модели, използваме така наречената последователна логика, т.е. логика на предложенията, разширена с модалности на формата ([C] varphi), интерпретирана по следния начин:

(M, w / модели [C] varphi), ако и само ако (M, w '\ модели / varphi) за всички (w') такива, че (w (bigcap_ {i / in C} приблизително_i) w ')

Консеквенциалистичната логика е разработена да разсъждава за действие и следствие и има интересни приложения в деонтичната логика, като Kooi & Tamminga 2008; Тамминга 2013; Turrini 2012. Освен това те са в основата на времевата логика на стратегията като STIT и стратегически STIT, обсъдени по-късно. Специален случай са логиките на предложенията за контрол (Hoek & Wooldridge 2005; Troquard, Hoek, & Wooldridge 2009).

3.2.2 Логически игри

В много ситуации агентите имат контрол върху определени предложения за променливи (Hoek & Wooldridge 2005), например те могат да бъдат отговорни за потока на трафика или могат да наложат вето върху определен проблем. Променливите също могат да бъдат споделени (Gerbrandy 2006), пример за гласуване, при който играчите споделят контрол върху променлива, чиято реализация се определя от определена функция за агрегиране, например мнозинство (Troquard, Hoek, & Wooldridge 2011). Тези логики на контрола на предложенията уточняват какви агенти за предложения имат функцията на ефективност. Например, ако агент (i) контролира (p), и двете (p ^ {M}) и (neg p ^ {M}) са в неговата ефективност. По някакъв начин тези модели са много специални видове функция за ефективност и това, което контролира агентите, може да се разглежда като избор или стратегия, достъпна за тях.

Логиката на предложенията за контрол има модалности от типа ( varphi), което означава, че играчът (i) има стратегия за „контрол“, за да се съобрази с това, без значение как другите агенти избират контрола си стратегии, след това (varphi) е в сила. Но те също имат модалности от типа ([C] varphi), което означава, че играчите в (C) имат съвместна стратегия за контрол, осигуряваща (varphi) в крайна сметка. По този начин профилът на стратегията е еквивалентен на функция за оценка, която присвоява истинност на всяко налично предложение. От своя страна, стратегия на играч (i) може да се разглежда като частична функция за оценка, която присвоява стойност на истината само на предложенията, контролирани от (i).

Леко злоупотребявайки с нотация, казваме, че оценката (V) удовлетворява формула (varphi), обозначена (V / модели / varphi), винаги, когато прави (varphi) вярно при текущото задаване на предложения. С други думи, предложенията за контролни игри се играят в един единствен свят, а индивидуалните задачи определят кои предложения са верни са този свят. Означавайки (mathcal {V}) набора от всички оценки и (mathcal {V} _i) на частичните, под контрола на (i), имаме следното.

((F, V) моделиvarphi) ако и само ако за всички (i / в C) съществува (V'_i / в / mathcal {V} _i) такъв, че за всички (k / в / overline {C}, V '_ {k} в / mathcal {V} _k) имаме това ((F, V') модели / varphi)

Така че, когато ([C] varphi) е в сила, коалицията (C) може да играе контролна стратегия по такъв начин, че без значение каква е стратегията за контрол, която играят противниците им, полученият резултат удовлетворява (varphi).

Логиката на контрола върху предложенията може да се разшири до формати, основани на целите, т. Нар. Булеви игри (Harrenstein, van der Hoek, Meyer, & Witteveen 2001): предложенията се разпределят между играчите, като всеки играч контролира набора от предложения, който той или тя е назначен за. На всичкото отгоре на всеки играч е присвоена и формула на логиката на предложенията, която трябва да бъде неговата цел и чиято реализация може да зависи не само от избора, който той / тя може да направи.

Булевите игри бяха подробно изучени в областта на многоагентните системи, като прости и компактни модели за представяне на стратегическо взаимодействие в базирана на логика обстановка (Dunne & Hoek 2004; Dunne & Wooldridge 2012; Dunne, Hoek, Kraus и Wooldridge 2008).

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

Например, агент (i) може да бъде назначен само контролът на предложение (p), но може да има целта, която (p / leftrightarrow q). Така че дали целта на (i) е изпълнена зависи не само от (i) задаването на предложение (p) да е вярно, но и от някой друг агент, да кажем (j), задаването на предложение (q) да е вярно. Агент (j), от друга страна, може или не може да се интересува дали (q) е зададено на true. Например той или тя може да иска предложението (r) да бъде вярно и следователно да е безразличен към това дали (q) или (overline {q}) е реализиран в крайна сметка. Или дори може да има целта, която (overline {q}).

В булевите игри някои цели могат да бъдат реализирани всички заедно, например агентите може би всички искат (p / vee / neg q) да е вярно, или може да се случи някои оценки да не реализират целите на всички агенти, но никой нещастен агент не е в състояние да подобри собствената си ситуация чрез промяна на заданието на предложените променливи, които той или тя контролира. Тази ситуация е много проста форма на равновесие на Наш, която може да се изрази в булевите игри.

Така че, за да бъде (gamma_i) целта на играча (i) и (v_i) частична оценка, която е под контрола на играча (i), ние казваме, че оценката (v) е равновесие на Неш, ако имаме това за всеки (i) и всеки (v'_i).

[(v_i, v _ {- i}) не / модели / gamma_i / mbox {означава, че} (v'_i, v _ {- i}) не / модели / gamma_i)

Така че, ако (v) не удовлетворява целта на (i), няма нищо (i) да го постигне.

Анализът на равновесието на Наш в булева игра показва тясно съответствие между тези игри и логиката на предлагане: използване на редукцията до проблема за удовлетворяемост на формулировките на предложенията, проблемът за проверка дали резултатът (v) е равновесие на Бул на Булево равновесие играта е съвместно NP (Wooldridge, Endriss, Kraus, & Lang 2013).

4. Заключения: На правилното ниво на анализ

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

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

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

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

библиография

• Абду, Джоузеф и Ханс Кийдинг, 1991, Функции на ефективността в социалния избор, (Библиотека за теория и решения 8), Дордрехт: Спрингер Холандия, дой: 10.1007 / 978-94-011-3448-4
• Балтаг, Александру и Браян Рен, 2016, „Динамична епистемична логика“, в Станфордската енциклопедия на философията, (издание зима 2016), Едуард Н. Залта (съст.), URL =
• Belnap, Nuel, Michael Perloff и Ming Xu, 2001, Facing the Future: Agentes and Choices in Our Indeterministries World, Oxford: Oxford University Press.
• Benthem, Йохан ван, 2014, Логика в игри, Кеймбридж, МА: MIT Press.
• Бентхем, Йохан ван, Ерик Пакуит и Оливие Рой, 2011 г., „Към теория на играта: Логическа перспектива за игрите и взаимодействието“, Игри, 2 (1): 52–86. Дой: 10.3390 / g2010052
• Blackburn, Patrick, Maarten de Rijke и Yde Venema, 2001, Modal Logic, Cambridge: Cambridge University Press. Дой: 10.1017 / CBO9781107050884
• Chellas, Brian, 1980, Modal Logic: An Introduction, Cambridge: Cambridge University Press.
• Дален, Дирк ван, 1980, Логика и структура, Берлин: Спрингер-Верлаг. DOI: 10.1007 / 978-3-662-02962-6
• Dunne, Paul E. и Wiebe van der Hoek, 2004, „Представителство и сложност в булевите игри“, в Жозе Хулио Алферес и Жоао Александър Лейте (ред.), „Логика в изкуствения интелект“, 9-та Европейска конференция, JELIA 2004, Лисабон, Португалия, 27–30 септември 2004 г., Proceedings, Berlin, Heidelberg: Springer, 3229: 347–359. DOI: 10.1007 / 978-3-540-30227-8_30
• Dunne, Paul E. и Michael Wooldridge, 2012, „Към проследими булеви игри“, във Wiebe van der Hoek, Lin Padgham, Vincent Conitzer и Michael Winikoff (ред.), Сборник от 11-тата международна конференция за автономните агенти и многоагентните системи, (AAMAS 2012), Валенсия, Испания, 4–8 юни 2012 г., Ричланд, SC: Международна фондация за автономни агенти и многоагентни системи, кн. 2, с. 939–946.
• Dunne, Paul E., Wiebe van der Hoek, Sarit Kraus и Michael Wooldridge, 2008, „Кооперативни булеви игри“, в Лин Падгам, Дейвид К. Паркс, Йорг П. Мюлер и Саймън Парсънс (редактори), седмата международна съвместна конференция за автономните агенти и мултиагентните системи (AAMAS 2008), Есторил, Португалия, 12–16 май 2008 г., Ричланд, SC: Международна фондация за автономни агенти и многоагентни системи, кн. 2, с. 1015–1022.
• Гарсън, Джеймс, 2014 г., „Модална логика“, в Станфордската енциклопедия на философията, (пролет 2016, издание), Едуард Н. Залта (съст.), URL = ,
• Гербранди, Джеле, 2006 г., „Логика на предложенията за контрол”, в Хидейки Накашима, Майкъл П. Уелман, Герхард Вайс и Питър Стоун (ред.), Протоколи от петата международна съвместна конференция за автономните агенти и многоагентните системи, (AAMAS 2006), Хакодате, Япония, 8–12 май 2006 г., Ню Йорк: ACM, стр. 193–200. DOI: 10.1145 / 1,160,633.1160664
• Горанко, Валентин и Саломон Паси, 1992, „Използване на универсалната модалност: печалби и въпроси“, сп. „Логика и изчисления“, 2 (1): 5–30. Дой: 10.1093 / logcom / 2.1.5
• Горанко, Валентин, Войчех Джамрога и Паоло Турини, 2013, „Стратегически игри и действително изпълними функции за ефективност“, Автономни агенти и многоагентни системи, 26 (2): 288–314. DOI: 10.1007 / s10458-012-9192-у
• Hansen, Helle Hvid, 2003, Монотонна модална логика, магистърска теза, Universiteit van Amsterdam.
• Hansen, Helle Hvid и Marc Pauly, 2002, „Axiomatising Nash-последователна коалиционна логика“, в Sergio Flesca, Sergio Greco, Nicola Leone, & Giovambattista Ianni (ред.), Logics in Artificial Intelligence, Berlin: Springer, 2424: 394– 406. DOI: 10.1007 / 3-540-45757-7_33
• Хансън, Хел Хвид, Клеменс Купке и Ерик Пакуит, 2009 г., „Съседски структури: теория на подобие и теория на базовия модел“, Логически методи в компютърните науки, 5 (2): lmcs: 1167. [Hansen, Kupke, & Pacuit 2009 на разположение онлайн]
• Hansson, Sven Ove и Till Grune-Yanoff, 2011 г., „Предпочитания“, в Станфордската енциклопедия на философията, (Есен 2011 г. издание), Edward N. Zalta (ed.), URL => https://plato.stanford.edu/ архиви / fall2011 / записи / предпочитания />
• Harrenstein, Paul, Wiebe van der Hoek, John-Jules Meyer и Cees Witteveen, 2001 г., "Булеви игри", в Йохан ван Бентхем (съст.), Сборник от Осмата конференция по теоретични аспекти на рационалността и познанието, (Tark ' 01), Сан Франциско: Морган Кауфман, стр. 287–298.
• Хендрикс, Винсент и Джон Симонс, 2006 г., „Епистемична логика“, в Станфордската енциклопедия на философията, (Пролет 2006 г.), Едуард Н. Залта (съст.), URL =
• Hodges, Wilfrid, 2013, „Логика и игри“, в Станфордската енциклопедия на философията, (Пролет 2013, издание), Edward N. Zalta (ed.), URL = ,
• Hoek, Wiebe van der and Marc Pauly, 2006, „Модална логика за игри и информация“, в Patrick Blackburn, Johan van Benthem, and Frank Wolter (eds.), Handbook of Modal Logic, стр. 1077–1148, Elsevier.
• Hoek, Wiebe van der и Michael Wooldridge, 2005, „За логиката на сътрудничеството и предложенията за контрол“, Изкуствен интелект, 164 (1–2): 81–119. Дой: 10.1016 / j.artint.2005.01.003
• Kooi, Barteld и Allard Tamminga, 2008, „Морални конфликти между групи агенти“, сп. „Философска логика“, 37 (1): 1–21. DOI: 10.1007 / s10992-007-9049-Z
• Крахт, Маркъс и Франк Волтер, 1999, „Нормалната мономодална логика може да симулира всички останали“, сп. „Символична логика“, 64 (1): 99–138. DOI: 10.2307 / 2586754
• Moulin, Herve и Bezalel Peleg, 1982, „Ядра на функциите на ефективността и теорията на прилагането“, Journal of Mathematical Economics, 10 (1): 115–145. Doi: 10,1016 / 0304-4068 (82) 90009-X
• Осборн, Мартин и Ариел Рубинщайн, 1994, Курс по теория на игрите, Кеймбридж, МА: MIT Press.
• Пакуит, Ерик и Оливие Рой, 2015, „Епистемични основи на теорията на игрите“, в Станфордската енциклопедия на философията, (издание пролет 2015), Edward N. Zalta (ed.), URL =
• Поли, Марк, 2001, Логика за социален софтуер, доктор на науките дисертация, Университет в Амстердам. [Pauly 2001 на разположение онлайн]
• Peleg, Bezalel, 1998, „Функции за ефективност, игрови форми, игри и права“, Social Choice and Welfare, 15 (1): 67–80. Дой: 10.1007 / s003550050092
• Steele, Katie и Orri Stefansson, 2015, „Теория на решенията“, в Станфордската енциклопедия на философията, (издание Winter 2015), Edward N. Zalta (ed.), URL =
• Tamminga, Allard, 2013, „Деонтична логика за стратегически игри”, Erkenntnis, 78 (1): 183–200. Дой: 10.1007 / s10670-011-9349-0
• Troquard, Nicolas, Wiebe van der Hoek, and Michael Wooldridge, 2009, „Logic of Games and Propositions Control“, в Карлес Сиера, Кристиано Кастелфранчи, Кийт С. Декър и Хайме Симао Сичман (ред.), Сборник от 8-ми Международна съвместна конференция за автономни агенти и многоагентни системи (AAMAS 2009), Будапеща, Унгария, 10–15 май 2009 г., Ричланд, SC: Международна фондация за автономни агенти и многоагентни системи, кн. 2, с. 961–968.
• –––, 2011, „Разсъждение за функциите на социалния избор“, сп. „Философска логика“, 40 (4): 473–498. DOI: 10.1007 / s10992-011-9189-Z
• Turrini, Paolo, 2012, „Споразумения като норми“, в Thomas Agogotnes, Jan Broersen и Dag Elgesem (ред.), Deontic Logic in Computer Science: 11th International Conference (DEON 2012), Берген, Норвегия, 16–18 юли, 2012, Берлин: Спрингер, 7393: 31–45. DOI: 10.1007 / 978-3-642-31570-1_3
• Уолдридж, Майкъл, Ул Ендрис, Сарит Краус и Йером Ланг, 2013, „Стимулиращо инженерство за булеви игри“, Изкуствен интелект, 195: 418–439. Дой: 10.1016 / j.artint.2012.11.003

Академични инструменти

	Как да цитирам този запис.
	Вижте PDF версията на този запис в Дружеството на приятелите на SEP.
	Разгледайте тази тема за вписване в интернет философския онтологичен проект (InPhO).
	Подобрена библиография за този запис в PhilPapers, с връзки към неговата база данни.

Други интернет ресурси

• Apt, Krzysztof, 2009, "Кооперативни игри", Курсови бележки, Centrum Wiskunde & Informatica, Амстердам.
• Логика в действие