عنوان
پدید آورنده
موضوع
رده
کتابخانه
محل استقرار
شماره کتابشناسی ملی
شماره
TLets435061
عنوان و نام پديدآور
عنوان اصلي
Finding Nash equilibria of bimatrix games
نام عام مواد
[Thesis]
نام نخستين پديدآور
Savani, Rahul
وضعیت نشر و پخش و غیره
نام ناشر، پخش کننده و غيره
London School of Economics and Political Science (LSE)
تاریخ نشرو بخش و غیره
2006
یادداشتهای مربوط به پایان نامه ها
جزئيات پايان نامه و نوع درجه آن
Ph.D.
کسي که مدرک را اعطا کرده
London School of Economics and Political Science (LSE)
امتياز متن
2006
یادداشتهای مربوط به خلاصه یا چکیده
متن يادداشت
This thesis concerns the computational problem of finding one Nash equilibrium of a bimatrix game, a two-player game in strategic form. Bimatrix games are among the most basic models in non-cooperative game theory, and finding a Nash equilibrium is important for their analysis. The Lemke-Howson algorithm is the classical method for finding one Nash equilib-rium of a bimatrix game. In this thesis, we present a class of square bimatrix games for which this algorithm takes, even in the best case, an exponential number of steps in the dimension d of the game. Using polytope theory, the games are constructed using pairs of dual cyclic polytopes with 2d suitably labelled facets in d-space. The construc-tion is extended to two classes of non-square games where, in addition to exponentially long Lemke-Howson computations, finding an equilibrium by support enumeration takes exponential time on average. The Lemke-Howson algorithm, which is a complementary pivoting algorithm, finds at least one solution to the linear complementarity problem (LCP) derived from a bimatrix game. A closely related complementary pivoting algorithm by Lemke solves more general LCPs. A unified view of these two algorithms is presented, for the first time, as far as we know. Furthermore, we present an extension of the standard version of Lemke's algorithm that allows one more freedom than before when starting the algorithm.
موضوع (اسم عام یاعبارت اسمی عام)
موضوع مستند نشده
QA Mathematics
نام شخص به منزله سر شناسه - (مسئولیت معنوی درجه اول )
مستند نام اشخاص تاييد نشده
Savani, Rahul
شناسه افزوده (تنالگان)
مستند نام تنالگان تاييد نشده
London School of Economics and Political Science (LSE)
دسترسی و محل الکترونیکی
نام الکترونيکي
مطالعه متن کتاب وضعیت انتشار
فرمت انتشار
p
اطلاعات رکورد کتابشناسی
نوع ماده
[Thesis]
کد کاربرگه
276903
اطلاعات دسترسی رکورد
سطح دسترسي
a
تكميل شده
Y
