Mostrar código-fonte de Bimatriz

Na [[teoria dos jogos]], uma '''bimatriz''' é um [[jogo simultâneo]] para dois jogadores em que cada jogador tem um número finito de ações possíveis. O nome vem do fato de que a [[Forma normal (teoria dos jogos)|forma normal]] de tal jogo pode ser descrita por duas matrizes — a matriz <math>A</math> descreve os [[payoff]]s do jogador 1 e a matriz <math>B</math> descreve os payoffs do jogador 2.<ref name="Chand">{{citar web|url=http://www.utdallas.edu/~chandra/documents/6311/bimatrix.pdf |título=Bimatrix games |acessodata=17 de dezembro de 2015 |autor =Chandrasekaran, R}}</ref>
O jogador 1 é frequentemente chamado de "jogador da linha" e o jogador 2, "jogador da coluna". Se o jogador 1 tem <math>m</math> ações possíveis e o jogador 2 tem <math>n</math> ações possíveis, então cada uma das duas matrizes tem <math>m</math> linhas por <math>n</math> colunas. Quando o jogador da linha seleciona a <math>i</math>-ésima ação e o jogador da coluna seleciona a <math>j</math>-ésima ação, o payoff para o jogador da linha é <math>A[i,j]</math> e o payoff para o jogador da coluna é <math>B[i,j]</math>.
Os jogadores também podem jogar [[Estratégia (teoria dos jogos)|estratégias mistas]]. Uma estratégia mista para o jogador da linha é um vetor não negativo <math>x</math> de comprimento <math>m</math> tal que: <math>\sum_{i=1}^m x_i = 1</math>. Da mesma forma, uma estratégia mista para o jogador da coluna é um vetor não negativo <math>y</math> de comprimento <math>n</math> tal que: <math>\sum_{j=1}^n y_j = 1</math>. Quando os jogadores jogam estratégias mistas com vetores <math>x</math> e <math>y</math>, o retorno esperado do jogador da linha é: <math>x^T A y</math> e do jogador da coluna: <math>x^T B y</math>.
== Equilíbrio de Nash na bimatriz ==
Todo jogo de bimatriz tem um [[equilíbrio de Nash]] em (possivelmente) estratégias mistas. Encontrar esse equilíbrio de Nash é um caso especial do [[problema de complementaridade linear]] e pode ser feito em tempo finito pelo [[algoritmo de Lemke-Howson]].<ref name="Chand" />
Há uma [[Redução (complexidade)|redução]] do problema de encontrar um equilíbrio de Nash em uma bimatriz para o problema de encontrar um equilíbrio competitivo em uma economia com [[utilitários de Leontief]].<ref name="co2006">{{citar livro|título=Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm  - SODA '06|último1 =Codenotti|primeiro1 =Bruno|último2 =Saberi|primeiro2 =Amin|último3 =Varadarajan|primeiro3 =Kasturi|último4 =Ye|primeiro4 =Yinyu|capítulo=Leontief economies encode nonzero sum two-player games|doi=10.1145/1109557.1109629|isbn=0898716055|páginas=659|ano=2006}}</ref>
== Temos relacionados ==
Um [[Soma-zero|jogo de soma zero]] é um caso especial de uma bimatriz em que <math>A+B = 0</math>.
{{Referências}}
{{Portal3|Jogos}}
{{Controle de autoridade}}
[[Categoria:Teoria dos jogos]]