search

shizejin / Lemke_Howson_notebook

BSD 3-Clause "New" or "Revised" License
6 stars 1 forks source link

Outlines for lemke-howson notebook #1

Open shizejin opened 7 years ago

shizejin commented 7 years ago

I am thinking about the outlines of lemke-howson notebook. I think the content might be ordered as follows:

  1. Nondegenerate game 1.1 basic algorithm: Complementary Pivoting 1.2 Integer Pivoting
  2. Degenerate game 2.1 Lexico-Minimum Test 2.2 Rewrite Complementary Pivoting with Lexico-Minimum Test 2.3 Rewrite Integer Pivoting with Lexico-Minimum Test

I am wondering whether we need to put mathematic background about polyhedron and the idea of equilibrium computation of von Stengel, B. (2007) before introducing lemke-howson algorithm? Especially for von Stengel, B. (2007), if we introduce this in the beginning, then would it be more natural for us to introduce support enumeration before lemke-howson? @oyamad

oyamad commented 7 years ago

Aim at complementing von Stengel (2007) not substituting it. We can refer to von Stengel (2007) for math backgrounds unless there is something that is really necessary.

It is not a bad idea to introduce support enumeration.

shizejin commented 7 years ago

I see. I think the necessary things to say before introducing algorithm are that a mixed action nash equilibrium (x, y) requires |supp(x)| = |supp(y)| and that x y are totally labelled. Is it okay to refer these conclusions directly in this notebook without talking about the mathematical proof of this?

About the support enumeration, should I add support enumeration in the same notebook, and put it before lemke-howson, or open a new notebook for it?

oyamad commented 7 years ago

The definition of non-degeneracy is necessary. Put support enumeration in at the same notebook. We can decide later whether to divide it into two notebooks.

shizejin commented 7 years ago

Dear professor Oyama,

I added the part of lemke howson algorithm to the notebook. (http://nbviewer.jupyter.org/github/shizejin/Lemke_Howson_notebook/blob/master/Lemke_howson.ipynb)

About the last part of experimental analysis (Codenotti, De Rossi, and Pagan's simulations), I need lemke_howson to return the number of steps it uses to find a NE, which is not supported in the current version of quantecon.game_theory. Shall I change this part, or define a new lemke_howson function which returns the number of steps in the notebook? @oyamad

Best, Zejin

oyamad commented 7 years ago

See the documentation by lemke_howson? at a Jupyter notebook.

shizejin commented 7 years ago

So sorry that I thought that res only shows the status of whether a NE is found.

I added the part of experimental analysis to the notebook, using lemke_howson from quantecon.py. Best, Zejin