Ïðèìåíåíèå àëãîðèòìè÷åñêîé òåîðèè èãð äëÿ ìîäåëèðîâàíèÿ ïîâåäåíèÿ ó÷àñòíèêîâ â öåïÿõ ïðîèçâîäñòâ è ïîñòàâîê
Ïðîåêò Áåëîðóññêîãî Ôîíäà Ôóíäàìåíòàëüíûõ Èññëåäîâàíèé Ô10Ì-071
«Ïðèìåíåíèå àëãîðèòìè÷åñêîé òåîðèè èãð äëÿ ìîäåëèðîâàíèÿ ïîâåäåíèÿ ó÷àñòíèêîâ â öåïÿõ ïðîèçâîäñòâ è ïîñòàâîê»
(2010-2012)
![Ïðèìåíåíèå àëãîðèòìè÷åñêîé òåîðèè èãð äëÿ ìîäåëèðîâàíèÿ ïîâåäåíèÿ ó÷àñòíèêîâ â öåïÿõ ïðîèçâîäñòâ è ïîñòàâîê Ïðèìåíåíèå àëãîðèòìè÷åñêîé òåîðèè èãð äëÿ ìîäåëèðîâàíèÿ ïîâåäåíèÿ ó÷àñòíèêîâ â öåïÿõ ïðîèçâîäñòâ è ïîñòàâîê](/structure/l_mc/f10m_071_big.png)
Öåëü ðàáîòû – íàõîæäåíèÿ ñèòóàöèé ðàâíîâåñèÿ èññëåäóåìûõ ýêîíîìè÷åñêèõ ñèñòåì, óñòàíîâëåíèå ïàðàìåòðîâ òàêèõ ðàâíîâåñíûõ ñèòóàöèé, â òîì ÷èñëå ðàâíîâåñíûõ öåí, ðàçðàáîòêà àëãîðèòìîâ ïîñòðîåíèÿ òàêèõ ðàâíîâåñíûõ ñèòóàöèé, óñòàíîâëåíèå âû÷èñëèòåëüíîé ñëîæíîñòè èññëåäóåìûõ çàäà÷, ðàçðàáîòêà ïðèáëèæåííûõ è òî÷íûõ àëãîðèòìîâ äëÿ èññëåäóåìûõ çàäà÷.
Îáúåêòàìè äëÿ èññëåäîâàíèÿ ÿâëÿþòñÿ òàêèå ýêîíîìè÷åñêèå ïðîöåññû êàê àóêöèîíû [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.