Analiza efektywności wybranych algorytmów teorii gier

• Autorzy: Raif P.

Warianty tytułu

EN

Analysis of efficiency of some game theory algorithms

• Języki publikacji: PL

Abstrakty

PL

Artykuł dotyczy zagadnień związanych z obliczeniową teorią gier. Przeanalizowano w nim dostępne algorytmy, stosowane do wyznaczania równowag Nasha w n-osobowych grach niekooperacyjnych. Zbadano efektywność wybranych algorytmów. Do wyznaczania ich efektywności zastosowano metodę empiryczną, polegającą na pomiarze czasów działania algorytmów dla przygotowanego zestawu danych wejściowych. Jako dane wejściowe wykorzystano specjalnie przygotowane gry, będące modelami przepływu w sieci.

EN

Article concerns computational game theory. It presents analysis of available algorithms for finding Nash equilibrium in n-person noncooperative games. Comparison of algorithms is based on their actual performance in solving a set of prepared data. As initial data some special games, the simple models of network flow, have been used.

Słowa kluczowe

PL

teoria gier; obliczeniowa teoria gier; efektywność; gra niekooperacyjna; równowaga Nasha; Simplical Subdivision; PolEnum; Global Newton Method

EN

game theory; computational game theory; efficiency; noncooperative game; Nash equilibrium; Simplical Subdivision; Polymatrix Approximation Algorithm; PolEnum; Global Newton Method

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Zeszyty Naukowe. Organizacja i Zarządzanie / Politechnika Śląska
• Rocznik: 2006
• Tom: z. 38
• Strony: 179--190
• Opis fizyczny: Bibliogr. 15 poz.

Twórcy

autor

Raif P.

• Katedra Informatyki i Ekonometrii Politechniki Śląskiej, 41-800 Zabrze, ul.Roosevelta 26, tel [phone],

Bibliografia

• 1. Cormen T., Leiserson C, Rivest R., Wprowadzenie do algorytmów, WNT, Warszawa 1998.
• 2. Czumaj A., Selfish Routing on the Internet, www.cis.njit.edu/~czumaj/PUBLICATIONS/, Selfish-Routing-Survey.pdf, May 2003.
• 3. Fudenberg D., Tirole J., Game Theory. MIT Press, 1991.
• 4. Gupta D., On Selfish Routing, 2003.
• 5. Govindan S., Wilson R., Global Newton Method to Compute Nash Equilibria, www.stanford.edu/class/cs324/papers/govindanwilson01newton-method.pdf. May 2004.
• 6. Govindan S., Wilson R., Computing Nash Equilibria by Iterated Polymatrix Approximation, faculty-b.slanford.edu/wilson/pdf/PolymatrixApproximationJEDC, 010718.pdf, May 2004.
• 7. Johnson D. S., A Theoretican's Guide to the Experimental Analysis of Algorithms, Data Structures, Near Neighbor Searches, and Metodologhy: Fifth and Sixth DIMACS Implementation Challenges (2002), s. 215-250.
• 8. Kearns M., Littman M.L., Singh S., Graphical Models for Game Theory, in the Proceeding of the UAI2001, 253-260, 2001.
• 9. D. Roller and B. Milch, Multi-agent influence diagrams for representing and solving games, In IJCAI-01, 2001.
• 10. Koutsoupias E. Papadimitriou C, Worst-case equilibria, In Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science, pages 404-413, 1999.
• 11. McKelvey D.R., McLennan A., Computation of Equilibria in Finite Games, in Handbook of Computational Economics, Vol. 1. Elsevier Science B.V., Amsterdam 1996.
• 12. McKelvey R., McLennan A., Turocy T., Gambit. Software Tools for Game Theory, http://econweb.tamu.edu/gambit/download.html, May 2004.
• 13. Papadimitriou C, Algorithms, games, and the Internet. In Proceedings of the 33rd Annual ACM Symposium on the Theory of Computing, pages 749-753, 2001
• 14. Papadimitriou C, Roughgarden T.; Computing Equilibria in multi-Player Games; http://www.cs.berkeley.edu/~christos/papers/multiplayer.ps, Apr 2004.
• 15. Vickrey D., Koller D.; Multi-Agent Algorithms for Solving Graphical Games, Eighteenth national conference on Artificial Inteligence, Edmonton Alberta Canada, s. 345 - 351,2002.