Применение алгоритмической теории игр для моделирования поведения участников в цепях производств и поставок

Проект Белорусского Фонда Фундаментальных Исследований Ф10М-071
«Применение алгоритмической теории игр для моделирования поведения участников в цепях производств и поставок»
(2010-2012)

Цель работы – нахождения ситуаций равновесия исследуемых экономических систем, установление параметров таких равновесных ситуаций, в том числе равновесных цен, разработка алгоритмов построения таких равновесных ситуаций, установление вычислительной сложности исследуемых задач, разработка приближенных и точных алгоритмов для исследуемых задач.

Объектами для исследования являются такие экономические процессы как аукционы [1,2,3,4], комбинаторные аукционы [5], взаимодействие участников в цепях производств и поставок.

Результаты:

В результате исследований были найдены параметры оптимального по прибыли аукциона делимого объекта, построен алгоритм нахождения равновесных цен для комбинаторного аукциона специального вида, определены параметры ситуации равновесия и построено ряд алгоритмов для нахождения ситуаций равновесия для простой цепи производств и поставок в случае разных политик производства производителя, разработаны ряд формулировок математического программирования, позволяющих применить для задачи оптимизации железнодорожного узла метод генерации столбцов и метод ветвления и оценивания, установлена вычислительная сложность и доказано ряд свойств задачи минимизации максимального веса подмножества паросочетания в двудольном графе.

Изученные методы и подходы:

Отметим, что исследования проводились в основном в теоретической области алгоритмической теории игр и теории алгоритмов. Авторами проекта проанализирован большой объем информации по этим темам. Изучены новые методы, в частности методы построения равновесных цен для комбинаторных аукционов и рынков, прямо-двойственный метод построения приближенных алгоритмов и ситуаций равновесия, методы разделения стоимости, методы построения механизмов различных процессов, не допускающих сообщения неверной информации механизму участниками, метод генерации столбцов и метод ветвления и оценивания.

Практическое применение:

Все полученные результаты могут быть использованы при чтении лекций по алгоритмической теории игр и теории алгоритмов. В качестве примера практического применения задач алгоритмической теории игр и теории алгоритмов можно привести систему аукционов для рекламы google [6]. Опыт, полученный в ходе выполнения данного проекта, позволяет разработать подобные системы для белорусских заказчиков.

Исполнители проекта:
Объединенный институт проблем информатики Национальной академии наук Беларуси

Участники проекта:
Баркетов М.С.( к.ф.-м.н., с.н.с. )

Список источников:

[1] Vickrey W. Counterspeculation, Auctions, and Competitive Sealed Tenders / W. Vickrey // Journal of Finance. – Vol.16, No. 1. – P.8-37.

[2] Riley J.G., Samuelson W.F. Optimal Auctions / J.G. Riley, W.F. Samuelson // The American Economic Review. – Vol. 71, No. 3. – P.381-392.

[3] Myerson R.B. Optimal Auction Design / R.B. Myerson // Mathematics of Operations Research. – Vol. 6, No. 1. – P. 58-73.

[4] Milgrom P.R. A Theory of Auctions and Competitive Bidding / P.R. Milgrom, R.J. Weber // Econometrica. – Vol. 50, No 5. – P.1089-1122.

[5] Algorithmic game theory /eds: Noam Nisan et al. // Cambridge University Press. - 2007.

[6] Nisan N. Google’s Auction for TV Ads / N. Nisan et al // ICALP '09 Proceedings of the 36th Internatilonal Collogquium on Automata, Languages and Programming: Part II. - 2009.

Опубликованные и подготовленные статьи авторов проекта:

[1] М.С.Баркетов NP-полнота в сильном смысле задачи «3-РАЗБИЕНИЕ ПРОИЗВЕДЕНИЯ» / М.С.Баркетов // Информатика. – 2011. – Т. 26, № 2.

[2] M.S. Barketau The lagrangian lower bound for the problem of optimization of a railway hub / M.S.Barketau // EURO Journal on transportation and logistics, 2012.

[3] M.S. Barketau Negotiating parameters of the orders of the clients in the supply and production chain / M.S. Barketau // working paper, 2012.