Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Эль-Фарол бар проблемасы – ойын теориясындағы мәселе. Әр бейсенбі күні кешке, белгілі бір топ адам "Эль-Фарол" барына көңіл көтеруге барады, егер ол тым көп адамға толмаса. Егер халықтың 60%-дан азы барға барса, олардың бәрі үйде отыруға қарағанда көбірек ләззат алады. Егер халықтың 60%-дан астамы барға барса, олардың бәрі үйде отыруға қарағанда аз ләззат алады. Әрбір адам басқалардың таңдауын білмей, бір уақытта баруға немесе бармауға шешім қабылдауы керек. Парадоксалды жағдай, егер барлығы детерминистік, таза стратегия қолданса, симметриялы (барлық ойыншылар үшін бірдей стратегия) болса, нәтижесі сәтсіздікке ұшырауы сөзсіз. Егер стратегия көп адам болмайды десе, барлығы барады, демек, бар толы болады; ал егер стратегия көп адам болады десе, ешкім бармайды, демек, бар толы болмайды, бірақ ешкім де көңіл көтере алмайды. Ықтималдық аралас стратегиясымен жақсы нәтижеге қол жеткізу мүмкін. Бір кезеңдік Эль-Фарол бар мәселесі үшін, барлық ойыншылардың белгілі бір ықтималдықпен барға баруын көздейтін бірегей симметриялық Нэш тепе-теңдігі аралас стратегиясы бар. Бұл ықтималдық ойыншылар санына, көп адамға толу шегіне және үйде отырумен салыстырғанда, толы немесе толмаған барға барудың салыстырмалы пайдалылығына байланысты анықталады. Бір немесе бірнеше ойыншылар таза стратегия қолданатын бірнеше Нэш тепе-теңдіктері де бар, бірақ бұл тепе-теңдіктер симметриялық емес. Герберт Гинтистің "Ойын теориясының эволюциясы" еңбегінде бірнеше нұсқа қарастырылған. Мәселенің кейбір нұсқаларында ойыншыларға барға баруды шешуге дейін бірін-бірімен сөйлесуге рұқсат етіледі. Алайда, олар шындықты айтуға міндетті емес. Санта-Фе (Нью-Мексико) қаласындағы бардың атымен аталған бұл мәселені 1994 жылы В. Брайан Артур жасаған. Дегенмен, басқа атаумен, бұл мәселе алты жыл бұрын Б. А. Хуберман және Т. Хогг тарапынан формулиленіп, шешілген.
The El Farol bar problem is a problem in game theory. Every Thursday night, a fixed population want to go have fun at the El Farol Bar, unless it's too crowded. If less than 60% of the population go to the bar, they'll all have more fun than if they stayed home. If more than 60% of the population go to the bar, they'll all have less fun than if they stayed home. Everyone must decide at the same time whether to go or not, with no knowledge of others' choices. Paradoxically, if everyone uses a deterministic pure strategy which is symmetric (same strategy for all players), it is guaranteed to fail no matter what it is. If the strategy suggests it will not be crowded, everyone will go, and thus it will be crowded; but if the strategy suggests it will be crowded, nobody will go, and thus it will not be crowded, but again no one will have fun. Better success is possible with a probabilistic mixed strategy. For the single stage El Farol Bar problem, there exists a unique symmetric Nash equilibrium mixed strategy where all players choose to go to the bar with a certain probability, determined according to the number of players, the threshold for crowdedness, and the relative utility of going to a crowded or uncrowded bar compared to staying home. There are also multiple Nash equilibria in which one or more players use a pure strategy, but these equilibria are not symmetric. Several variants are considered in Game Theory Evolving by Herbert Gintis. In some variants of the problem, the players are allowed to communicate before deciding to go to the bar. However, they are not required to tell the truth. Named after a bar in Santa Fe, New Mexico, the problem was created in 1994 by W. Brian Arthur. However, under another name, the problem was formulated and solved dynamically six years earlier by B. A. Huberman and T. Hogg.
Азшылық ойыны
Фрибург университетінің И Чен Чжан және Дэмиен Шале ұсынған Азшылық ойынының бір нұсқасы бар. Әр кезеңде ойыншылардың саны тақ болуы керек, және әрбір ойыншы екі бағыттың бірін тәуелсіз түрде таңдайды. Жеңімпаз – азшылыққа қолдау көрсеткен ойыншылар. Эль-Фарол Бар мәселесіндегідей, ешқандай бір (симметриялық) нақты стратегия тепе-теңдікке әкелмейді, бірақ аралас стратегиялар үшін бірегей симметриялық Нэш тепе-теңдігі бар (әр ойыншы 50% ықтималдықпен таңдайды), сондай-ақ көптеген асимметриялық тепе-теңдіктер де бар. "Адамгер ойыны" мангасында көп кезеңді, ынтымақтастық Азшылық ойыны көрсетілген, онда көпшілік ойыншылар бір ғана ойыншы қалғанша қайта-қайта іріктеліп алынды.
A variant is the Minority Game proposed by Yi Cheng Zhang and Damien Challet from the University of Fribourg. An odd number of players each must make a binary choice independently at each turn, and the winners are those players who end up on the minority side. As in the El Farol Bar problem, no single (symmetric) deterministic strategy can give an equilibrium, but for mixed strategies, there is a unique symmetric Nash equilibrium (each player chooses with 50% probability), as well as multiple asymmetric equilibria. A multi stage, cooperative Minority Game was featured in the manga Liar Game, in which the majority was repeatedly eliminated until only one player was left.
Калькуттадағы мейрамхана мәселесі
Эль-Фарол барының тағы бір түрі – Колкаттаның пайсэ мейрамханасы проблемасы (KPR), осы атау жұмысшылардың жылдам тамақтана алатын көптеген арзан мейрамханаларға байланысты, бірақ таңдаған мейрамханасы тым көп адамға толып кетсе, аш күйінде жұмысқа қайтуы мүмкін. Формальды түрде, N санындағы көптеген ойыншылардың әрқайсысы n санындағы мейрамханалардың біреуін таңдайды, әдетте N = n (ал Эль-Фарол бары проблемасында n = 2, үйде қалу мүмкіндігін қоса алғанда). Әр мейрамханада біреу кездейсоқ түрде тамақтанады (сыйлық = 1), ал қалғаны ұтылады (сыйлық = 0). Ойыншылар бір-бірінің таңдауын белгілі бір күні білмейді, бірақ ойын күнде қайталанады және барлық ойыншылардың таңдау тарихы барлығына қолжетімді. Оңтайлы жағдайда, әр ойыншы әртүрлі мейрамхананы таңдайды, бірақ координациясыз бұл практикалық тұрғыдан мүмкін емес, нәтижесінде аш клиенттер мен пайдаланылмаған сыйымдылықпен қараусыз қалған мейрамханалар пайда болады. Ұқсас проблемада, әр жерде аурухана төсектер бар, бірақ пациенттер өз аудандарының сыртындағы беделді ауруханаларға баруға құштар. Дегенмен, егер тым көп пациент беделді ауруханаға барса, кейбіреулері мүлдем төсек таба алмайды, сонымен қатар жергілікті ауруханалардағы бос төсектер ысырап болады. Стратегиялар олардың жалпы сыйлықтарына және/немесе қатысқан мейрамханалардың үлесіне (пайдалану коэффициенті) сүйене отырып бағаланады. ~0.79 пайдаланумен ең озық стохастикалық стратегия, әрбір клиентке кешегідей бірдей мейрамхананы таңдау ықтималдығын (p бұл мейрамхананы кеше таңдаған ойыншылар санына кері пропорционалды түрде өзгереді) береді, ал қалған мейрамханалардың арасынан біркелкі ықтималдықпен таңдайды. Бұл детерминистік алгоритмдерден немесе қарапайым кездейсоқ таңдаудан (шу саудагерінен) жақсы нәтиже, пайдалану үлесі 1 - 1/e ≈ 0.63. Саяхатшы сатушы проблемасы сияқты алгоритмдерді қолдана отырып, жергілікті оңтайландыру іздеуіне мүмкіндік берілген клиенттер үшін пайдаланудың артуы да зерттелді. KPR-дің шақыру бойынша автомобиль жалға алу проблемаларын кеңейту мәселелері де қарастырылды. Тамақтану клубтарының енгізілуімен шақырылған KPR-дің тұрақтылығы да зерттелді. Үш ойыншылық KPR үшін кванттық ойындарға кеңейтулер зерттелді; жақындағы шолуды қараңыз.
Another variant of the El Farol Bar problem is the Kolkata Paise Restaurant Problem (KPR), named for the many cheap restaurants where laborers can grab a quick lunch, but may have to return to work hungry if their chosen restaurant is too crowded. Formally, a large number N of players each choose one of a large number n of restaurants, typically N = n (while in the El Farol Bar Problem, n = 2, including the stay home option). At each restaurant, one customer at random is served lunch (payoff = 1) while all others lose (payoff = 0). The players do not know each others' choices on a given day, but the game is repeated daily, and the history of all players' choices is available to everyone. Optimally, each player chooses a different restaurant, but this is practically impossible without coordination, resulting in both hungry customers and unattended restaurants wasting capacity. In a similar problem, there are hospital beds in every locality, but patients are tempted to go to prestigious hospitals out of their district. However, if too many patients go to a prestige hospital, some get no hospital bed at all, while additionally wasting the unused beds at their local hospitals. Strategies are evaluated based on their aggregate payoff and/or the proportion of attended restaurants (utilization ratio). A leading stochastic strategy, with utilization ~0.79, gives each customer a probability p of choosing the same restaurant as yesterday (p varying inversely with the number of players who chose that restaurant yesterday), while choosing among other restaurants with uniform probability. This is a better result than deterministic algorithms or simple random choice (noise trader), with utilization fraction 1 1/e ≈ 0.63. Increased utilization for customers having allowance for local optimization search using Traveling Salesman Problem type algorithms have also been studied. Extensions of KPR for on call car hire problems have been explored in. Stability of the KPR, induced by the introduction of dining clubs have also studied. Extensions to quantum games for three player KPR have been studied; see for a recent review.