Koalitionsbildning är ett centralt problem i automatiserade förhandlingar mellan egenintresserade agenter och andra elektroniska handelstillämpningar. En koalition av agenter kan ibland åstadkomma saker som de enskilda agenterna inte kan eller kan göra saker och ting mer effektivt. Att motivera agenterna att följa en lösning kräver dock noggrann analys: endast en del av lösningarna är stabila i den meningen att ingen grupp agenter är motiverad att bryta upp och bilda en ny koalition. Denna begränsning har studerats i stor utsträckning i kooperativ spelteori. De beräkningsmässiga frågorna kring denna begränsning har dock fått mindre uppmärksamhet. När det gäller koalitionsbildning bland programvaruagenter (som representerar verkliga partier) blir dessa frågor allt tydligare. I detta dokument definierar vi en kortfattad allmän representation för spel i karakteristisk form som bygger på superadditionalitet, och visar att det möjliggör effektiv kontroll av om ett visst resultat är i kärnan. Vi visar sedan att avgöra om kärnan är nontomty är N P-komplett både med och utan överförbar nytta. Vi visar att det som gör problemet svårt i båda fallen är att bestämma samarbetsmöjligheterna (den uppsättning resultat som är möjliga för den stora koalitionen), genom att visa att om dessa ges blir problemet lättåtkomligt i båda fallen. Men sedan visar vi att för en hybridversion av problemet, där nyttoöverföring endast är möjlig inom den stora koalitionen, är problemet fortfarande N Pfullständig även när samarbetsmöjligheter ges.
Generellt, bestämma kärnan icke tomhet är NP-komplett för kooperativa spel både med och utan överförbar nytta REF.
Complexity of determining nonemptiness of the core
{'venue': "EC '03", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}