Численное построение равновесия в модели выбора Тибу

Данная работа посвящена одному из разделов теории игр. Целью данной работы является предложить алгоритм построения миграционно-устойчивого равновесия в модели выбора Тьебу. Задача формулируется в следующем виде. Пусть определено множество агентов (игроков), конечное или бесконечное, каждый из которых имеет собственные предпочтения, задаваемые функцией полезности. Так же в задаче задаются, некоторые условия, ограничения или объекты, которые позволяют задать множество стратегий игроков, что в дальнейшем позволяет сформировать коалиции, которые непосредственным образом влияют на полезность игроков. Например, рассмотрим задачу о размещении неограниченных мощностей (Uncapacitated Facility Location Problem), а именно задачу о формировании государств. Пусть на множестве X⊂R^2 задана функция плотности распределения игроков. Тогда задачу можно переформулировать в виде, как разместить столицы государств и границу между ними, чтобы издержки всех игроков были минимальны. В данной работе рассматривается задача построения равновесия при условии, что расположение мощностей (или столиц) фиксированы, а игроки принимают решения только относительно того, к какому из государств (коалиций) себя отнести. Целью данной работы является численное нахождение миграционно-устойчивого разбиения на заданном множестве при наличии трех фиксированных столиц. В первой части данной работы будет представлена математическая модель данной задачи. Во второй части работы будет подробно описан предлагаемый алгоритм для построения равновесия. Затем будут представлены результаты реализации алгоритма на языке С++. В заключении будут представлены недостатки данного алгоритма и вопросы, оставленные автором без внимания в силу ограниченности времени, а так же возможные направления дальнейших исследований и модификаций данного алгоритма. А так же пояснения почему реализация алгоритма получиться не эффективной.