LCP und Nash-Gleichgewicht

[otze]

Moin.

Ich versuche mich grade durch den lemke-Howson Algorithmus für 2-Spieler Nash-Gleichgewichte zu quälen, und stoße auf einige Probleme bei der Theorie dahinter. Es wird gesagt, dass die Formulierung dieses Problems ein LCP (linear complementary Problem) ist.
Nach meinen Quellen, sieht ein LCP immer wie folgt aus:

$$

\underline{r}-M\underline{x}=\underline{q}

$$

$$

\underline{x}_i,\underline{r}_i \geq 0

$$

$$

\underline{x}^T\underline{r} = 0

$$

Im Idealfall ist M symmetrisch, positiv-semidefinit.

Nun ist die Formulierung des LCP für das Nash-Gleichgewich etwas anders:

$$

\underline{r}+U\underline{x}=1

$$

$$

U_{ij}>=0

$$

(rest ist gleich zu oben).

Ich kriege das beides nicht so recht zusammen, insbesondere die Definition des LCP macht mir Kopfschmerzen.

Nach Komplementaritätsbedingung gilt, dass r_i=p_i oder r_i=0.
Da r_i>0 sein muss, gilt p_i>0. Wenn also r_i=0 ist, folgt (-Mx)_i=q_i. Und das kann sich sein, Da M positiv Semidefinit sein darf.

Im Gegensatz dazu macht die Definition des Nash Gleichgewichts für mich Sinn.

Wo ist mein Denkfehler? Warum ist das Gleichungssystem für das Nash-Gleichgewicht ein LCP?

[otze]

schade. Weiß das wirklich niemand, oder ist die Frage so dumm?