Сложность ядра: различия между версиями

Концепция наименьшего ядра порождает новые проблемы относительно алгоритмических вопросов. Наиболее естественной задачей является эффективное вычисление значения £* для заданной кооперативной игры. Загвоздка в том, что вычисление £* требует решения линейной программы с экспоненциальным числом ограничений. Хотя существуют случаи, когда это значение может быть вычислено за полиномиальное время [ ], в общем случае это очень сложно. Если величина £* рассматривается как некая субсидия, предоставляемая центральным органом для обеспечения существования кооперации, то важно дать ее приближенное значение, даже если ее вычисление является NP-сложным.

Другой возможный подход заключается в интерпретации приближения как ограниченной рациональности. Например, было бы интересно узнать, существует ли какая-нибудь игра со свойством, что для любого " > 0 проверка принадлежности к "-ядру может быть выполнена за полиномиальное время, но определение того, содержится ли в ядре дележ, будет NP-сложной задачей. В таких случаях восстановление сотрудничества было бы результатом применения подхода ограниченной рациональности. То есть, игроки не будут беспокоиться о дополнительном выигрыше или проигрыше " за счет вычислительных ресурсов более высокого порядка степени. В дальнейшем эту методику можно применить к другим концепциям решений.