Matrix pelit
Matematiikassa matriisipelit ymmärretään kahden henkilön nollasummapeliksi, jossa on äärellinen määrä strategioita. Voiton määrää pelimatriisi (voittomatriisi), joka on myös pelin normaali muoto .
Matriisipeli ja lineaarinen ohjelmointi
Olkoon matriisipeli ensimmäisen pelaajan strategioiden joukko, toisen pelaajan strategiajoukko ja voittomatriisi .
![A[M,N]](https://wikimedia.org/api/rest_v1/media/math/render/svg/bc0953e96410bdb1d99ad7ad0c655d5534694e4c)
Harkitse kahta lineaarista ohjelmointitehtävää
Tehtävä 1
Löydä maksimi
![{\displaystyle 1^{T}[N]y[N]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f2e46703d41498d498dba747b2a28ac473b11e3f)
Rajoituksella
![{\displaystyle A[M,N]y[N]\leq 1[M]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b315c53d2ed4bb58b4bf7bb830e27c03b6a1b030)
![{\displaystyle y[N]\geq 0[N]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/69dfa0761c7858ba23bd2c7a93c508228718ecc9)
Ongelma 2 (kaksois)
Etsi minimi
![{\näyttötyyli 1^{T}[M]x[M]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d091fec68148f551e8bac254a916650e0d5c10c8)
Rajoituksella
![{\displaystyle A^{T}[N,M]x[M]\geq 1[N]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/12c704dac00203d961e8872af2caf7835972f76c)
![{\displaystyle x[M]\geq 0[M]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0e9be5961e130eb29c9065a925b10fb0635e18f0)
Tiedetään, että seuraavat lausunnot ovat vastaavia
1. Matriisipelillä on positiivinen peliarvo
2. Tehtävät 1 ja 2 ovat ratkaistavissa; lisäksi, jos on pelin hinta,
ja ovat optimaalisia ratkaisuja,
![{\displaystyle x[M]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0fb850dd72a94b5dcb9c93e36b4e94a132857a74)
![{\displaystyle y[N]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a41cb408346f831e35a31685137996f1a3372328)
sitten
![{\displaystyle 1/v=1^{T}[N]y[N]=1^{T}[M]x[M]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/25431eb206d63dc4ee3df3d40b4d9baf48bc009a)
ja , ovat pelaajien optimaaliset sekastrategiat.
Huomaa: Kun voit lisätä (riittävän suuren) vakion kaikkiin matriisin elementteihin, mikä ei muuta pelaajien strategioita. Voit esimerkiksi etsiä minimielementin (negatiivin) ja käyttää sen absoluuttista arvoa lisäyksenä.
Linkit
- Karlin S. Matemaattiset menetelmät peliteoriassa, ohjelmointi ja taloustiede M., Mir, 1964
- Owen G. Peliteoria. M. "Mir", M., 1971