Қооперативтік ойындардағы ядро және тұрақтылық шешімдері
Core (game theory)
Кооперативтік ойын теориясындағы «ядро» - барлық қатысушылардың ынтымақтастығын сақтауға мүмкіндік беретін, коалициялардың бөлінуінен пайда көре алмайтын бөлулер жиыны.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Кооперативтік ойын теориясында ядро – агенттердің ешбір коалициясы үлкен коалициядан бөлініп шығу арқылы пайда көре алмайтын, мүмкін болатын үлестірулер немесе есептер жиынтығы. Ядроны барлық агенттер арасындағы ынтымақтастықты сақтауға болатын жағдайларға сәйкес қарастыруға болады. Егер коалиция мүшелері бастапқы үлестіруде алғаннан көбірек құндылықты өндіре алса, онда бұл коалиция берілген үлестіруді жақсарта алады немесе тоқтатып тастады делінеді. Осылайша, мұндай коалиция үлкен коалицияда қалуға мүдделі емес. Егер оны жақсартатын коалиция болмаса, онда үлестіру ойынның ядросында деп есептеледі. Ядро – барлық мүмкін үлестірулердің жиынтығы.
In cooperative game theory, the core is the set of feasible allocations or imputations where no coalition of agents can benefit by breaking away from the grand coalition. One can think of the core corresponding to situations where it is possible to sustain cooperation among all agents. A coalition is said to improve upon or block a feasible allocation if the members of that coalition can generate more value among themselves than they are allocated in the original allocation. As such, that coalition is not incentivized to stay with the grand coalition. An allocation is said to be in the core of a game if there is no coalition that can improve upon it. The core is then the set of all feasible allocations .
Шығу тегі
Негізгі идея бұрыннан-ақ жазбаларында пайда болды, сол кезде ол келісім шарты қисығы деп аталды. Нейман мен Моргенштерн бұл тұжырымды қызықты деп есептесе де, олар тек ядросы әрқашан бос болатын нөлдік жиынтық ойындарымен жұмыс істеді. Ядроның қазіргі заманғы анықтамасы Гиллес еңбегіне байланысты.
The idea of the core already appeared in the writings of , at the time referred to as the contract curve. Even though von Neumann and Morgenstern considered it an interesting concept, they only worked with zero sum games where the core is always empty. The modern definition of the core is due to Gillies.
Анықтама
Ауыстырылатын пайдалы кооперативтік ойынды қарастырайық, онда ойыншылар жиынымен және сипаттамалық функциясымен белгіленеді. Егер коалиция болса, бір импутация екінші импутациядан үстемдік етеді, егер коалицияның әрбір ойыншысы бірінші импутацияны әлсіз артықшылықпен қабылдаса (барлығы үшін) және кемінде бір ойыншы оны қатаң артықшылықпен қабылдаса, сондай-ақ, үлкен коалициядан кету арқылы оны жүзеге асыра алатын болса. Негізгі ядро – ешқандай импутациядан үстемдік етпейтін импутациялардың жиынтығы.
Consider a transferable utility cooperative game where denotes the set of players and is the characteristic function. An imputation is dominated by another imputation if there exists a coalition , such that each player in weakly prefers ( for all ) and there exists that strictly prefers , and can enforce by threatening to leave the grand coalition to form The core is the set of imputations that are not dominated by any other imputation.
Әлсіз өзек
Егерде бір коалиция болса, онда бір импутация екінші импутацияны қатты басып озады, яғни коалицияның әрбір ойыншысы (барлығы үшін) қатты түрде артықшылық береді. Әлсіз ядро – қатты басып озбайтын импутациялар жиынтығы.
An imputation is strongly dominated by another imputation if there exists a coalition , such that each player in strictly prefers ( for all ). The weak core is the set of imputations that are not strongly dominated.
1-ші мысал: Шахташылар
Мысалы, үлкен алтын тастарын тапқан n кеншінің тобын қарастырайық. Егер екі кенші бір алтын тасын көтере алса, онда S коалициясының пайдасы былай анықталады:
Consider a group of n miners, who have discovered large bars of gold. If two miners can carry one piece of gold, then the payoff of a coalition S is
Егер екі кеншіден көп болса және кеншілердің саны жұп болса, онда ядрода әрбір кеншіге 1/2 бөлігінен тиетін жалғыз ғана пайда болады. Егер кеншілердің саны тақ болса, онда ядро бос болады.
If there are more than two miners and there is an even number of miners, then the core consists of the single payoff where each miner gets 1/2. If there is an odd number of miners, then the core is empty.
2-мысал: қолғаптар
А және Б мырзалары қолғаптар тоқып жатыр. Қолғаптар бір өлшемді, ал екі қолғаптан бір жұп жасалып, 5 евроға сатылады. Олардың әрқайсысы үш қолғап жасаған. Сатудан түскен табысты қалай бөлісу керек? Бұл мәселені сипаттамалық функциясы бар сипаттамалық функция түріндегі ойын арқылы сипаттауға болады: Әр адамның үш қолғапы бар, яғни бір жұптың нарықтық құны 5 евро. Екеуінің барлығында 6 қолғап немесе 3 жұп бар, олардың нарықтық құны 15 евро. Ойынның маңызды коалициялары бір адамнан тұратын коалициялар болғандықтан, осы соманың барлық мүмкін бөлістері ядроға жатады, егер екі адамның әрқайсысы кем дегенде 5 евро алса, яғни өздері жеке таба алатын сома. Мысалы, (7.5, 7.5) ядроға жатады, сондай-ақ (5, 10) немесе (9, 6) та жатады.
Mr A and Mr B are knitting gloves. The gloves are one size fits all, and two gloves make a pair that they sell for €5. They have each made three gloves. How to share the proceeds from the sale? The problem can be described by a characteristic function form game with the following characteristic function: Each man has three gloves, that is one pair with a market value of €5. Together, they have 6 gloves or 3 pair, having a market value of €15. Since the singleton coalitions (consisting of a single man) are the only non trivial coalitions of the game all possible distributions of this sum belong to the core, provided both men get at least €5, the amount they can achieve on their own. For instance (7.5, 7.5) belongs to the core, but so does (5, 10) or (9, 6).
3-мысал: Аяқ киім
Қазір аяқ киімнің өлшемдерін елемеңіз: бір жұп сол және оң аяқ киімнен тұрады, содан кейін оны 10 евроға сатуға болады. 2001 ойыншы бар ойынды қарастырайық: 1000-ның 1 сол аяғы бар, 1001-інің 1 оң аяғы бар. Бұл ойынның негізі біршама таңқаларлық: ол (сирек) сол аяқ киімге ие болғандарға 10, ал (артық) оң аяқ киімге ие болғандарға 0 беретін бір ғана үлестіруден тұрады. Ешқандай коалиция бұл нәтижеге кедергі келтіре алмайды, өйткені сол аяқ киім иесі 10-нан кем мөлшерде ақша қабылдамайды, ал оң аяқ киім иесіне оң сома төлеген кез келген үлестіруде басқа ойыншыларға 10000-нан кем сома төленуі керек, олар өздері 10000 алуға мүмкіндік алады. Демек, ядрода тек бір ғана үлестіру бар. Сол аяқ киімнің жетіспеушілігі сақталғанда сандарды арттырсақ та, хабардың мәні өзгеріссіз қалады. Ядро бір типтегі ойыншының артық ұсынысына өте сезімтал болғаны үшін сынға ұшырады.
For the moment ignore shoe sizes: a pair consists of a left and a right shoe, which can then be sold for €10. Consider a game with 2001 players: 1000 of them have 1 left shoe, 1001 have 1 right shoe. The core of this game is somewhat surprising: it consists of a single imputation that gives 10 to those having a (scarce) left shoe, and 0 to those owning an (oversupplied) right shoe. No coalition can block this outcome, because no left shoe owner will accept less than 10, and any imputation that pays a positive amount to any right shoe owner must pay less than 10000 in total to the other players, who can get 10000 on their own. So, there is just one imputation in the core. The message remains the same, even if we increase the numbers as long as left shoes are scarcer. The core has been criticized for being so extremely sensitive to oversupply of one type of player.
Жалпы тепе-теңдік теориясының негізі
Жалпы тепе-теңдік моделіндегі алмасу экономикасының Уолрасиялық тепе-теңдіктері агенттер арасындағы ынтымақтастық ойынының өзегінде жатады. Графикалық тұрғыдан алғанда, және екі агенттің экономикасында (Эджворт қорабын қараңыз), өзек – бастапқы мүліктерде белгіленген агенттердің әрқайсысының әлжуаздық қисықтары арасында жатқан келісім қисығындағы (Парето-оптималдық үлестірілімдер жиынтығы) нүктелер жиынтығы.
The Walrasian equilibria of an exchange economy in a general equilibrium model, will lie in the core of the cooperation game between the agents. Graphically, and in a two agent economy (see Edgeworth Box), the core is the set of points on the contract curve (the set of Pareto optimal allocations) lying between each of the agents' indifference curves defined at the initial endowments.
Дауыс беру теориясының негізі
Егер баламалар бөлулер болса (тұтыну жиынтықтарының тізімі), кез келген бос емес адамдар тобы берілген бөлуді тоқтатуға мүмкіндік алады деп есептеу орынды. Бірақ, егер баламалар жалпыға ортақ болса (мысалы, белгілі бір жалпы игіліктің көлемі), онда тек жеткілікті үлкен коалициялар ғана берілген баламаны тоқтатуға қабілетті деп санау дұрыс. Мұндай үлкен ("жеңімпаз") коалициялар жиынтығы қарапайым ойын деп аталады. Талғамдар профиліне қатысты қарапайым ойынның ядросы, тек жеңімпаз коалициялар ғана таңдаудың орнына басқа баламаны қабылдамайды деген идеяға негізделген. Барлық талғамдар профилі үшін ядроның бос еместігінің қажетті және жеткілікті шарты қарапайым ойын үшін Накамура саны арқылы беріледі.
When alternatives are allocations (list of consumption bundles), it is natural to assume that any nonempty subsets of individuals can block a given allocation. When alternatives are public (such as the amount of a certain public good), however, it is more appropriate to assume that only the coalitions that are large enough can block a given alternative. The collection of such large ("winning") coalitions is called a simple game. The core of a simple game with respect to a profile of preferences is based on the idea that only winning coalitions can reject an alternative in favor of another alternative A necessary and sufficient condition for the core to be nonempty for all profile of preferences, is provided in terms of the Nakamura number for the simple game.