Matrix spel
I matematik förstås matrisspel som ett nollsummespel av två personer med ett begränsat antal strategier. Utdelningen bestäms av spelmatrisen (payoff-matrisen), som också är den normala formen av spelet .
Matrisspel och linjär programmering
Låt matrisspelet ges av uppsättningen av strategier för den första spelaren , uppsättningen strategier för den andra spelaren och payoff matrisen .
![A[M,N]](https://wikimedia.org/api/rest_v1/media/math/render/svg/bc0953e96410bdb1d99ad7ad0c655d5534694e4c)
Tänk på två linjära programmeringsproblem
Uppgift 1
Hitta det maximala
![{\displaystyle 1^{T}[N]y[N]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f2e46703d41498d498dba747b2a28ac473b11e3f)
Med restriktioner
![{\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)
Problem 2 (dubbel)
Hitta minimum
![{\displaystyle 1^{T}[M]x[M]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d091fec68148f551e8bac254a916650e0d5c10c8)
Med restriktioner
![{\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)
Det är känt att följande påståenden är likvärdiga
1. Matrisspelet har ett positivt spelvärde
2. Problem 1 och 2 är lösbara. Dessutom, om priset på spelet är,
och är optimala lösningar,
![{\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)
sedan
![{\displaystyle 1/v=1^{T}[N]y[N]=1^{T}[M]x[M]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/25431eb206d63dc4ee3df3d40b4d9baf48bc009a)
och , kommer att vara de optimala blandade strategierna för spelarna.
Notera: När du kan lägga till en (tillräckligt stor) konstant till alla element i matrisen, vilket inte ändrar spelarnas strategier. Du kan till exempel hitta minimielementet (negativt) och använda dess absoluta värde som en additiv.
Länkar
- Karlin S. Matematiska metoder i spelteori, programmering och ekonomi M., Mir, 1964
- Owen G. Spelteori. M. "Mir", M., 1971