Нақты ойын - Succinct game

Сондай-ақ оқыңыз: Ойындар теориясы § Баламалы ойын көріністері
Сәйкесінше {T, B}, {L, R} және {l, r} стратегияларына қарсы тұрған I, II және III үш ойыншының ойынын қарастырайық. Бұдан әрі шектеусіз, 3 * 23= Мұндай ойын сипаттау үшін 24 қызметтік мән қажет болады.
L, лL, рR, лR, р
Т4, 6, 25, 5, 58, 1, 71, 4, 9
B8, 6, 67, 4, 79, 6, 50, 3, 0
Әрбір стратегия профилі үшін бірінші ойыншының утилитасы бірінші болып тізімделеді (қызыл), содан кейін екінші ойыншының утилиталары (жасыл) және үшінші ойыншы (көк).

Алгоритмдік ойын теориясы, а қысқаша ойын немесе а қысқаша ұсынылатын ойын - оған қарағанда әлдеқайда аз мөлшерде ұсынылуы мүмкін ойын қалыпты форма өкілдік. Ойынның сипаттамасын сипаттайтын ойыншыларға шектеулер қоймай әрқайсысы қарама-қарсы тұрған ойыншылар стратегиялар, листингті қажет етеді қызметтік мәндер. Тіпті маңызды емес алгоритмдер а Нэш тепе-теңдігі бір уақытта көпмүшелік осындай үлкен кіріс ұзындығында. Қысқаша ойын көпмүшелік тип егер ұзындықтың жіпімен ұсынылған ойында n ойыншылардың саны, сондай-ақ әр ойыншының стратегияларының саны in-дағы көпмүшемен шектелген n[1] (формальды анықтама, қысқаша ойындарды сипаттайтын а есептеу проблемасы, Papadimitriou & Roughgarden 2008 берілген[2]).

Қысқаша ойын түрлері

Графикалық ойындар

Әр ойыншының утилитасы тек өзінің іс-әрекетіне және басқа ойыншының әрекетіне байланысты болады деп айтыңыз - мысалы, мен II-ге, II-ден III-ге және III-ден I-ге тәуелдімін. Мұндай ойын ұсыну үшін барлығы 2х2 бар үш кестені қажет етеді. тек 12 қызметтік мән.
LR
Т98
B34
лр
L68
R13
ТB
л44
р57

Графикалық ойындар әр ойыншының утилиталары басқа өте аз ойыншылардың әрекеттеріне байланысты болатын ойындар. Егер - бұл кез-келген жалғыз ойыншыға әсер ететін ойыншылардың ең көп саны (яғни бұл дәреже ойын графигі), ойын сипаттауға қажетті утилиталар саны , бұл, кішкене болса айтарлықтай жақсарту болып табылады.

Кез-келген қалыпты формадағы ойын болатыны көрсетілген төмендетілетін барлық дәрежелері үшпен шектелген және әр ойыншыға арналған екі стратегиядан тұратын графикалық ойынға.[3] Кәдімгі формалық ойындардан айырмашылығы, графикалық ойындарда таза Нэш тепе-теңдігін табу проблемасы (егер ол бар болса) NP аяқталды.[4] Графикалық ойында Нэш тепе-теңдігін табу мүмкін (мүмкін аралас) PPAD -толық.[5] А табу корреляциялық тепе-теңдік Графикалық ойынды полиномдық уақытта, ал шектелген график үшін жасауға болады кеңдік, бұл ан табу үшін де дұрыс оңтайлы корреляциялық тепе-теңдік.[2]

Сирек ойындар

Егер утилиталардың көпшілігі төменде көрсетілгендей 0 болса, қысқаша ұсыныс жасау оңай.
L, лL, рR, лR, р
Т0, 0, 02, 0, 10, 0, 00, 7, 0
B0, 0, 00, 0, 02, 0, 30, 0, 0

Сирек ойындар коммуналдық қызметтің көп бөлігі нөлге тең. Графикалық ойындар сирек ойындардың ерекше жағдайы ретінде қарастырылуы мүмкін.

Екі ойыншы үшін сирек ойын деп екі төлем (утилита) матрицасының әр жолы мен бағанында ең көп дегенде нөлдік емес жазбалар саны болатын ойын анықталуы мүмкін. Мұндай сирек ойында Нэш тепе-теңдігін табу PPAD-қиын екендігі және оның толық болмайтындығы көрсетілген. көпмүшелік-уақытқа жуықтау схемасы егер PPAD жоқ болса P.[6]

Симметриялық ойындар

Үш ойыншы да бірдей делік (бәрін бояймыз) күлгін), және {T, B} стратегия жиынтығына тап болыңыз. #TP және #BP сәйкесінше T және B таңдалған ойыншылардың құрдастарының саны болсын. Бұл ойынды сипаттау үшін тек 6 утилита мәні қажет.
# TP = 2
# BP = 0		# TP = 1
# BP = 1		# TP = 0
# BP = 2
Т522
B172

Жылы симметриялы ойындар барлық ойыншылар бірдей, сондықтан стратегиялар жиынтығының пайдалылығын бағалау кезінде маңыздысы - бұл қанша ойыншылар әрқайсысын ойнайды стратегиялар. Осылайша, мұндай ойынды сипаттау тек беруді қажет етеді қызметтік мәндер.

2 стратегиясы бар симметриялы ойында әрдайым таза Нэш тепе-теңдігі болады - дегенмен симметриялы таза Нэш тепе-теңдігі болмауы мүмкін.[7] Әрекеттер саны тұрақты болатын симметриялы ойында (мүмкін екіден көп ойыншымен) таза Нэш тепе-теңдігін табу мәселесі Айнымалы0; дегенмен, ойыншылар санының өсуіне байланысты әрекеттер саны көбейгенде (тіпті сызықтық түрде) проблема толық емес болып шығады.[8] Кез-келген симметриялы ойында а бар симметриялық тепе-теңдік. Симметриялы ойыны берілген n қарсы тұрған ойыншылар к Егер k = болса, көпмүшелік уақытта симметриялы тепе-теңдікті табуға болады.[9] Симметриялы ойындарда өзара тепе-теңдікті табу көпмүшелік уақытта жасалуы мүмкін.[2]

Анонимді ойындар

Егер ойыншылар өзгеше болса, бірақ басқа ойыншыларды ажырата алмаса, онда біз ойынның бейнеленуі үшін 18 пайдалы мәнін тізімдеуіміз керек еді, мысалы, әр ойыншы үшін жоғарыдағы «симметриялы ойындар» үшін берілген кесте.
# TP = 2
# BP = 0		# TP = 1
# BP = 1		# TP = 0
# BP = 2
Т8, 8, 22, 9, 54, 1, 4
B6, 1, 32, 2, 17, 0, 6

Жылы жасырын ойындар, ойыншылардың утилиталары әр түрлі, бірақ басқа ойыншылардың арасындағы айырмашылықты ажыратпайды (мысалы, «кинотеатрға бару» мен «барға бару» нұсқаларын таңдау керек, әр жерде адамдар қаншалықты көп болатынын ғана емес, онда кіммен кездесетінін ескеру керек). Мұндай ойында ойыншының утилитасы қай қатардастарының қайсысы қай стратегияны таңдағанына байланысты, және де солай қызметтік мәндер қажет.

Егер әрекеттер саны ойыншылар санымен өссе, анонимді ойында таза Нэш тепе-теңдігін табу болып табылады NP-hard.[8] Анонимді ойынның оңтайлы корреляциялық тепе-теңдігін көпмүшелік уақытта табуға болады.[2] Стратегия саны 2 болғанда белгілі болады PTAS табу үшін ε-шамамен Нэш тепе-теңдігі.[10]

Полиматрицалық ойындар

Егер қарастырылып отырған ойын полиматрица ойыны болса, оны сипаттайтын 24 пайдалы мән қажет болады. Қарапайымдылық үшін I ойыншысының утилиталарын ғана қарастырайық (басқа ойыншылардың әрқайсысына тағы екі осындай кесте керек болады).
LR
Т4, 68, 7
B3, 79, 1
лр
Т7, 71, 6
B8, 66, 4
лр
L2, 93, 3
R2, 41, 5

Егер стратегия профилі (B, R, l) таңдалса, I ойыншының утилитасы 9 + 8 = 17, II ойыншының утилитасы 1 + 2 = 3, ал III ойыншының утилитасы 6 + 4 = 10 болар еді.

Ішінде полиматрица ойыны (сонымен бірге а мультиматрицалық ойын), ойыншылардың әр жұбы үшін қызметтік матрица бар (i, j), i ойнатқышының утилитасының компонентін көрсететін. Ойнатқыштың соңғы утилитасы - барлық осы компоненттердің жиынтығы. Мұндай ойынды ұсыну үшін қажетті утилиталар саны .

Полиматрицалық ойындарда әрқашан кем дегенде бір аралас Нэш тепе-теңдігі болады.[11] Полиметрия ойынындағы Нэш тепе-теңдігін табу мәселесі PPAD-аяқталған.[5] Сонымен қатар, полиматрицалық ойында Нэштің тұрақты жуық тепе-теңдігін табу мәселесі де PPAD-аяқталған.[12] Полиметрия ойынының корреляциялық тепе-теңдігін табуды көпмүшелік уақытта жасауға болады.[2] Егер ойыншылар арасында өткізілген жұптық ойындарда таза Нэш тепе-теңдігі болса да, ғаламдық өзара әрекеттесу міндетті түрде таза Нэш тепе-теңдігін мойындамайтындығына назар аударыңыз (аралас Нэш тепе-теңдігі болуы керек).

Ойыншылардың тек нөлдік қосындысы бар бәсекелі полиматрицалық ойындар екі ойыншыны қорыту болып табылады нөлдік сома ойындар. The Минимакс теоремасы бастапқыда екі ойыншы ойындарына арналған фон Нейман нөлдік қосынды полиметрия ойындарына жалпылайды [13]. Екі ойыншы нөлдік сома ойындарымен бірдей, полиметрия нөлдік сома ойындары бар аралас Нэш тепе-теңдігі уақытты есептеуге болатын және сол тепе-теңдіктер сәйкес келеді корреляциялық тепе-теңдік. Бірақ екі ойыншыға арналған нөлдік сома ойындарының кейбір басқа қасиеттері жалпыланбайды. Атап айтқанда, ойыншылар ерекше мәнге ие болмауы керек ойын және тепе-теңдік стратегиялары теңдестіру стратегиясын қолданғанда ойыншылардың ең жаман төлемдері максималды болмайтын мағынада max-min стратегиялары емес.

Шеттерінде үйлестіру ойындары бар полиматрицалық ойындар ықтимал ойындар [14] және әлеуетті функция әдісін қолдану арқылы шешуге болады.

Айналмалы ойындар

Енді ойыншылардың әртүрлі стратегияларын «0» және «1» логикалық мәндерімен теңестірейік, ал X ойыншының таңдауы үшін X, II ойыншының таңдауы үшін Y және III ойыншының таңдауы үшін Z болсын. Әр ойыншыға схема тағайындайық:

I ойыншы: X ∧ (Y ∨ Z)
II ойыншы: X ⨁ Y ⨁ Z
III ойыншы: X ∨ Y

Бұл төменде қызметтік кестені сипаттайды.

0, 00, 11, 01, 1
00, 0, 00, 1, 00, 1, 10, 0, 1
10, 1, 11, 0, 11, 0, 11, 1, 1

Қысқаша ойын бейнелеу тәсілдерінің ең икемдісі - әр ойыншыны уақыт бойынша шектелген полином арқылы бейнелеу Тьюринг машинасы, ол барлық ойыншылардың әрекеттерін қабылдайды және ойыншының утилитасын шығарады. Мұндай Тьюринг машинасы а-ға тең Буль тізбегі, және дәл осы өкілдік, ретінде белгілі айналмалы ойындар, біз қарастыратын боламыз.

2 ойыншының мәнін есептеу нөлдік сома схемалық ойын - бұл EXP - толық проблема,[15] және мультипликативті коэффициентке дейінгі осындай ойынның мәні шамамен белгілі PSPACE.[16] Нэштің таза тепе-теңдігінің бар-жоғын анықтау а - толық проблема (қараңыз. қараңыз) Көпмүшелік иерархия ).[17]

Басқа өкілдіктер

Қысқаша ойынның көптеген басқа түрлері бар (көбісі ресурстарды бөлуге байланысты). Мысалдарға мыналар жатады кептеліске арналған ойындар, кептеліске арналған ойындар, ойындарды жоспарлау, жергілікті эффект ойындары, объектінің орналасуы ойындары, экшн-графикалық ойындар, гиперграфиялық ойындар және басқалары.

Тепе-теңдік табудың күрделілігінің қысқаша мазмұны

Төменде бірнеше ойын көріністерінде тепе-теңдіктің белгілі кластарын табуға арналған белгілі бір күрделілік нәтижелерінің кестесі берілген. «NE» - «Nash тепе-теңдігі», «CE» - «өзара тепе-теңдік». n ойыншылардың саны және с - бұл әр ойыншы кездесетін стратегиялардың саны (біз барлық ойыншылар бірдей мөлшерде кездеседі деп есептейміз). Графикалық ойындарда г. - бұл ойын графигінің максималды дәрежесі. Анықтамалық мақаланың негізгі мәтінін қараңыз.

ӨкілдікӨлшемі (O(...))Таза NEАралас NECECE оңтайлы
Қалыпты формадағы ойынNP аяқталдыPPAD-аяқталғанPP
Графикалық ойынNP аяқталдыPPAD-аяқталғанPNP-hard
Симметриялық ойынNP аяқталдыНэш симметриялы тепе-теңдігін есептеу екі ойыншы үшін PPAD қиын. Екі ойыншы үшін симметриялы емес Нэш тепе-теңдігін есептеу NP-аяқталды.PP
Анонимді ойынNP-hardPP
Полиматрица ойыныPPAD толық (полиметрия нөлдік қосындыға арналған көпмүшелік)PNP-hard
Схема ойыны-толық
Кептелу ойыныPLS аяқталдыPNP-hard


Ескертулер

  1. ^ Papadimitriou, Christos H. (2007). «Нэш ​​тепе-теңдігін табудың күрделілігі». Нисанда, Ноам; Роггарден, Тим; Тардос, Эва; т.б. (ред.). Алгоритмдік ойындар теориясы. Кембридж университетінің баспасы. бет.29 –52. ISBN  978-0-521-87282-9.
  2. ^ а б c г. e Пападимитриу, Христос Х.; Roughgarden, Tim (2008). «Көп ойыншы ойындарындағы өзара тепе-теңдікті есептеу». J. ACM. 55 (3): 1–29. CiteSeerX  10.1.1.335.2634. дои:10.1145/1379759.1379762.
  3. ^ Голдберг, Пол В.; Papadimitriou, Christos H. (2006). «Тепе-теңдік мәселелерінің азаюы». Есептеу теориясы бойынша ACM отыз сегізінші жыл сайынғы симпозиумының материалдары. Сиэттл, АҚШ, АҚШ: ACM. 61–70 бет. дои:10.1145/1132516.1132526. ISBN  1-59593-134-1. Алынған 2010-01-25.
  4. ^ Готлоб, Г .; Греко, Г .; Скарчелло, Ф. (2005). «Таза Nash тепе-теңдігі: қиын және қарапайым ойындар». Жасанды интеллектті зерттеу журналы. 24 (195–220): 26–37. arXiv:1109.2152. дои:10.1613 / jair.1683.
  5. ^ а б Даскалакис, Константинос; Фабрикант, Алекс; Papadimitriou, Christos H. (2006). «Ойын әлемі тегіс: нәзік ойындардағы Nash тепе-теңдігінің күрделілігі». Автоматтар, тілдер және бағдарламалау. Информатика пәнінен дәрістер. 4051. 513–524 беттер. CiteSeerX  10.1.1.111.8075. дои:10.1007/11786986_45. ISBN  978-3-540-35904-3.
  6. ^ Чен, Си; Дэн, Сяоти; Тэн, Шан-Хуа (2006). «Сирек ойындар қиын». Интернет және желілік экономика. бет.262–273. дои:10.1007/11944874_24. ISBN  978-3-540-68138-0.
  7. ^ Ченг, Ших-Фен; Ривз, Даниэль М .; Воробейчик, Евгений; Wellman, Michael P. (2004). Симметриялық ойындардағы тепе-теңдік туралы ескертпелер. AAMAS-04 ойын теориясы және шешім қабылдау теориясы.
  8. ^ а б Брандт, Феликс; Фишер, Феликс; Хольцер, Маркус (2009). «Симметрия және таза тырнақ тепе-теңдігінің күрделілігі». Дж. Компут. Сист. Ғылыми. 75 (3): 163–177. дои:10.1016 / j.jcss.2008.09.001. Алынған 2010-01-31.
  9. ^ Пападимитриу, Христос Х.; Roughgarden, Tim (2005). «Көп ойыншы ойындарындағы тепе-теңдікті есептеу». Дискретті алгоритмдер бойынша он алтыншы ACM-SIAM симпозиумының материалдары. Ванкувер, Британдық Колумбия: өндірістік және қолданбалы математика қоғамы. 82-91 бет. ISBN  0-89871-585-7. Алынған 2010-01-25.
  10. ^ Даскалакис, Константинос; Papadimitriou, Christos H. (2007). «Анонимді ойындардағы тепе-теңдікті есептеу». arXiv:0710.5582v1 [cs ].
  11. ^ Хоусон, Джозеф Т. (қаңтар 1972). «Полиметрия ойындарының тепе-теңдігі». Менеджмент ғылымы. 18 (5): 312–318. дои:10.1287 / mnsc.18.5.312. ISSN  0025-1909. JSTOR  2634798.
  12. ^ Рубинштейн, Авиад (2015-01-01). Нэш тепе-теңдігінің жақындамауы. Есептеу техникасы теориясы бойынша ACM-нің қырық жетінші жылдық симпозиумының материалдары. STOC '15. Нью-Йорк, Нью-Йорк, АҚШ: ACM. 409-418 бет. arXiv:1405.3322. дои:10.1145/2746539.2746578. ISBN  9781450335362.
  13. ^ Cai, Y., Candogan, O., Daskalakis, C., & Papadimitriou, C. (2016). Нөлдік қосынды полиметриялық ойындар: Минимаксты қорыту.https://people.csail.mit.edu/costis/zerosum_final3.pdf
  14. ^ Рахн, Мона және Шафер, Гидо (2015) Полиматрицалық үйлестіру ойындарындағы тиімді тепе-теңдік https://arxiv.org/pdf/1504.07518.pdf
  15. ^ Фейгенбаум, Джоан; Коллер, Дафне; Шор, Питер (1995). Интерактивті күрделілік кластарының ойын-теориялық классификациясы. Дискретті математикаға арналған цертер & теориялық информатика. Алынған 2010-01-25.
  16. ^ Фортнов, Ланс; Импальяццо, Рассел; Кабанец, Валентин; Уманс, Кристофер (2005). «Нөлдік-сумдық ойындардың күрделілігі туралы». Есептеу күрделілігі бойынша IEEE 20-шы жылдық конференциясының материалдары. IEEE Computer Society. 323-332 беттер. ISBN  0-7695-2364-1. Алынған 2010-01-23.
  17. ^ Шенебек, Грант; Вадхан, Салил (2006). «Нақты тепе-теңдікті есептеудің күрделілігі қысқаша ұсынылған ойындарда». Электронды коммерция бойынша 7-ші ACM конференциясының материалдары. Анн Арбор, Мичиган, АҚШ: ACM. 270–279 бет. дои:10.1145/1134707.1134737. ISBN  1-59593-236-4. Алынған 2010-01-25.

Сыртқы сілтемелер