Teoria dos Jogos - Jogos de Soma Zero e Estrategias Mistas - Notas de Aula

Notas de Aula da Disciplina de Métodos Quantitativos para Tomada de Decisão Prof Edgard Pedroso Arquivo de aulas n o 21 Introdução à Teoria dos Jogos jogos de soma zero com soluções de estratégias pura ou mista Os estudos da teoria dos jogos abordam situações de tomada de decisão envolvendo dois oponentes concorrentes racionais com objetivos conflitantes que procuram estrategicamente superar um ao outro Nestas situações um estado ou cenário decorre da decisão tomada pelo outro participante ex estratégias de marketing e de ações militares Uma breve introdução a Teoria dos Jogos Jogos de soma zero entre dois participantes Cada jogador tem um determinado número de estratégias alternativas As duas estratégias adotadas por um e por outro jogador estão vinculadas ao retorno resultado ganho payoff que um pode receber do outro Os jogos de soma zero são denominados dessa forma porque o ganho de um jogador tem como consequência a perda igual do outro e nesse caso o jogo pode ser resumido em termos dos ganhos de um único jogador Von Neumann e Morgenstern 1935 Matriz de retornos ganhos pagamentos resultados payoffs para o jogador A Jogador B Estratégias B1 B2 Bn Jogador A A1 a11 a12 a1n A2 a21 a22 a2n Am am1 am2 amn A representação matricial subentende que se o jogador A usar a estratégia Ai e o jogador B usar Bj então supondo aij positivo o retorno ganho de A será aij ou seja o jogador B perde paga para A o valor aij É de costume representar o jogo pela matriz de retorno do jogador A Assim quando A ganha seu retorno é positivo e quando perde negativo e viceversa para B positivo quando perde e negativo quando ganha Solução ótima de jogos de soma zero com dois participantes A solução ótima seleciona uma ou mais estratégias para cada jogador de maneira a garantir o melhor retorno a ambos independentemente de quem ganhe As soluções podem ser apresentadas na forma de estratégia única estratégia pura ou de um conjunto de estratégias estratégias mistas que são usadas conforme determinadas probabilidades Exemplo 1 Extraído do livro de PO Hamdy A Taha Estratégia Pura Duas empresas A e B vendem duas marcas de medicamento para gripe A empresa A anuncia em rádio A1 televisão A2 e jornais A3 A empresa B além de usar rádio B1 televisão B2 e jornais B3 também envia folhetos B4 por mala direta Dependendo da efetividade de cada campanha publicitária uma empresa pode capturar uma parte do mercado da outra A matriz a seguir resume a percentagem de mercado capturada ou perdida pela empresa A Empresa B Estratégias B1 B2 B3 B4 Empresa A A1 8 2 9 3 A2 6 5 6 8 A3 2 4 9 5 de mercado capturada ou perdida por A Empresa B Estratégias B1 B2 B3 B4 Empresa A A1 8 2 9 3 A2 6 5 6 8 A3 2 4 9 5 Empresa A Deve escolher a estratégia que garanta o melhor entre os piores retornos que A teria ao decidir por cada uma de suas estratégias A1 A2 A3 independentemente da estratégia escolhida por B Usase o princípio maxmin Empresa B Estratégias B1 B2 B3 B4 piores p A min da linha Empresa A A1 8 2 9 3 3 A2 6 5 6 8 5 melhor entre piores p A maxmin A3 2 4 9 5 9 de mercado capturada ou perdida por A Empresa B Como a matriz foi construída tomandose como referência os retornos de A então o melhor entre piores retornos para B seria alcançado escolhendo a estratégia B1 B2 B3 B4 que resulte no menor entre os maiores valores selecionados de cada coluna independentemente da estratégia escolhida por A ou seja para B usase o princípio minmax Empresa B Estratégias B1 B2 B3 B4 piores p A min da linha Empresa A A1 8 2 9 3 3 A2 6 5 6 8 5 melhor entre as piores p A maxmin A3 2 4 9 5 9 Empresa B Estratégias B1 B2 B3 B4 piores p A min da linha Empresa A A1 8 2 9 3 3 A2 6 5 6 8 5 melhor entre as piores p A maxmin A3 2 4 9 5 9 piores p B max da coluna 8 5 9 8 melhor entre as piores p B minmax Empresa B Estratégias B1 B2 B3 B4 piores p A min da linha Empresa A A1 8 2 9 3 3 A2 6 5 6 8 5 maxmin A2 A3 2 4 9 5 9 piores p B max da coluna 8 5 9 8 minmax B2 A solução ótima do jogo é selecionar as estratégias A2 e B2 Especificamente neste exemplo o retorno favorecerá a empresa A por ser que capturará 5 do mercado que pertencia a B A solução é a melhor para as duas empresas e impossibilita a escolha tanto para A como para B de uma outra estratégia melhor que a já escolhida veja a seguir Se B mudar p B1 então A pode escolher A1 e ganhará 8 do mercado de B Se B mudar p B3 então A pode escolher A1 e ganhará 9 do mercado de B Se B mudar p B4 então A pode escolher A2 e ganhará 8 do mercado de B Logo B não teria vantagem em trocar de estratégia Se A mudar p A1 então B pode escolher B4 e A perderá 3 do mercado p B Se A mudar p A3 então B pode escolher B3 e A perderá 9 do mercado p B Logo A também não teria vantagem em trocar de estratégia Dizse que o valor do jogo é de 5 e que A e B estão usando uma solução de ponto de sela OBS Como v é então A ganha o jogo se fosse A perderia e se fosse zero empatariam VALOR ÓTIMO DO JOGO maxmin v minmax 5 v 5 v 5 Paraboloide Hiperbólico Sela ponto de sela Paraboloide Hiperbólico A B Exemplo 2 Extraído do livro de PO Hamdy A Taha Estratégia Mista Dois jogadores A e B jogam cara ou coroa com uma moeda Cada jogador sem o conhecimento do outro escolhe cara H ou coroa T Ambos revelarão suas escolhas simultaneamente Se escolherem a mesma coisa HH ou TT o jogador A recebe 100 de B Caso contrário A paga 100 para B A seguinte matriz de retorno para o jogador A dá o valor mínimo de cada linha e máximo de cada coluna correspondentes às estratégias dos jogadores A e B respectivamente Jogador B Estratégias BH BT piores p A min das linhas Jogador A AH 1 1 1 maxmin 1 AT 1 1 1 piores p B max das colunas 1 1 minmax 1 Observe que os valores de maxmin 1 e minmax 1 não são iguais e então não temos uma estratégia de solução pura Se A tiver escolhido a estratégia AH cara e B escolher BT coroa ganhando 100 de A então A poderia mudar para a estratégia AT coroa revertendo o resultado e ganhando 100 de B e assim sucessivamente A constante alternância de estratégia não se ajusta ao conceito de uma estratégia de solução pura pois os participantes poderiam misturar aleatoriamente suas respectivas estratégias Nesse caso o valor ótimo do jogo estará entre os valores determinados para o maxmin e o minmax ou seja Jogador B Estratégias BH BT piores p A min da linha Jogador A AH 1 1 1 maxmin 1 AT 1 1 1 piores p B max da coluna 1 1 minmax 1 maxmin 1 valor ótimo do jogo minmax 1 1 v 1 OBS Particularmente neste caso se A misturasse aleatoriamente a escolha de suas estratégias AH e AT com a probabilidade de 50 cada e B fizesse o mesmo teríamos um valor ótimo do jogo tendendo a zero e portanto o jogo tendendo ao empate CORRIGIDO Jogador B Probabilidades y1 y2 yn Estratégias B1 B2 Bn Jogador A x1 A1 a11 a12 a1n X2 1 x1 A2 a21 a22 a2n Solução de jogos de Estratégia Mista repare que sendo e com probabilidades e mistura as estratégia s jogador O 2 1 i i 1 1 x 0 x 1 1 2 1 2 1 1 x x x A A A de solução Gráfica Exemplo e endo com probabilidades mistura jogador O n 1 j j j n 2 1 1 y y 0 y y y s n 2 1 B B B B Estes jogos podem ser resolvidos por programação linear ou no caso de pelo menos um jogador ter exatamente duas estratégias de forma gráfica e jogos e dois jogadores Considere o caso com B A n 2 Solução de jogos de Estratégia Mista B ou seja B A mínimos maximize x x x j 1 2 1 de os entre todas estratégia s selecionad retornos médios esperados para os que 1 e Devese procurar o par de probabilidades n 12 j a x a x v 2j x 1 2 1j 1 1 j B 1 x A j min max n 12 j x a v 1 i ij i j B 1 x 2 min max A j será dado por pura estratégia do jogador associado a retorno ou ganho médio esperado O j A B cada A v j B n 12 estratégia B j a x a x v j 2j x 1 2 1j 1 1 B j para cada A ou Exemplo 3 PO Hamdy A Taha Estratégia Mista com os seguintes retornos para o jogador Considere o jogo A 4 2 Jogador B Estratégias B1 B2 B3 B4 piores p A min da linha Jogador A A1 2 2 3 1 1 A2 4 3 2 6 2 maxmin 2 piores p B max da coluna 4 3 3 6 minmax 3 3 2 3 2 v Valor do Jogo v Jogador B Estra tégias B1 B2 B3 B4 Jogador A A1 A2 1234 estratégia B j 1x a a x x a v j 2j x 1 1j 1 1 i ij i 2 B j 2 A 2 1 B 2 1 B x 1 1 21 x 1 11 1 1 x x v 1 x a x a v 4 2 A A 4 2 x1 v 1 B A 2 3 B 2 3 B x 1 1 23 x 1 13 1 1 x x v 1 x a x a v 2 3 A A 3 x1 v B2 A 2 2 B 2 2 B x 1 1 22 x 1 12 1 1 x x v 1 x a x a v 3 2 A A 2 x1 v B3 A 2 4 B 2 4 B x 1 1 24 x 1 14 1 1 x x v 1 x a x a v 6 A A 6 7 x1 v B4 A 2 1 i xi a i1 2 1 i xi a i2 2 1 i xi a i3 2 1 i i a i4 x j1 j2 j3 j4 Jogador B Jogador A Probabilidades y1 y2 y3 y4 Estratégias B1 B2 B3 B4 x1 A1 2 2 3 1 X2 1 x1 A2 4 3 2 6 SoftwareTORA Temporary Ordered Routing Algorithm v 6 7x 2 x 3 x 4 2x 4 B 3 B 2 B 1 B v v v v A A A A v v mínimos B4 3 B A A e esperados res dos retornos médios Delimitado da mistura pto intersecção máximo v v 25 x1 05 Jogador A 1234 j 1x a a x v 2j x 1 1j 1 2 j B 1 x A j min max n 12 x a j v 1 i ij i j B 1 x 2 min max A j x 10 0 respectivamente e ades probabilid com as e recomenda misturar as estratégia s jogador Portanto a solução ótima do e associadas às estratégia s linhas esperados para Este ponto é definido pela interseção das retornos dos representa o de solução Ponto 05 1 x x 05 x A A A B B A piores melhor maxmin 1 2 1 2 1 4 3 50 e 50 6 7 2 6 7 2 1 1 1 1 2 1 x 8 4 x x x x x v B v B 4 3 v v 25 x1 05 Jogador A x A região tracejada representa a área com os piores retornos médios esperados para A independentemente do que B faça 10 0 25 v B 25 v B B B do jogo v valor 4 3 4 3 6 35 6 7x 2 05 2 x como verifica se a seguir e funções associadas às estratégia s das 05 em qualquer do substituin se o Determina 1 1 x1 motivo deixaremos de usá la esse e por pior retorno médio para de corretamente a área dos pontos taria porém não delimi do jogo valor interseçãoe também forneceriao de usada pois passa pelo mesmo ponto poderia ter sido linha de A A v B Obs 2 Valor do jogo v v 25 x1 05 Jogador A x 10 0 Jogador B Estra tégias B1 B2 B3 B4 Jogador A A1 A2 VB A1 a11 y1 a12 y2 a13 y3 a14 y4 2 0 2 0 3 y3 1 1 y3 VB A 1 4 y3 1 VB A2 a21 y1 a22 y2 a23 y3 a24 y4 4 0 3 0 2 y3 6 1 y3 VB A 2 4 y3 6 12 i estratégia A y y a y a y a a y a v i 4 i4 3 i3 2 i2 1 i1 4 1 j j ij Ai B estratégia s de são dados nas tabelas as Assim os retornos para associados devemser aplicadas são de os valores das probabilidades com que as estratégias e que definem a área inferior do gráfico e puras ser feita pelas linhas associadas as estratégia s pode determinação da mistura ótima para o jogador A A B B A A B 2 1 3 4 3 2 1 1 y y 0 y e 0 y y Jogador B 4 1 j j a1j y 4 1 j j a2j y y4 y4 i1 i2 Jogador B Jogador A Probabi lidades y1 y2 y3 y4 Estra tégias B1 B2 B3 B4 x1 A1 2 2 3 1 X2 1 x1 A2 4 3 2 6 TORA Temporary Ordered Routing Algorithm v y y B A A 6 4y 4y 1 3 3 2 A 1 A v v B B y3 0875 v 25 0 875 6 4 1 4 6 4 1 4 3 3 3 3 8 7 y3 y y y y v A v A 2 1 12 i 1 y a a y v i4 y 3 i3 3 4 i A 3 y B i max min 12 a i y v 1 j ij j Ai 3 y 4 max min B i A região tracejada vermelha representa a área de pior retorno médio esperado para B independentemente do que A faça 0125 respectivamente 1 8 0875 e 7 8 com probabilidades e as estratégia s misturar do jogador recomenda A 3 4 3 4 3 y y y B B B ótima solução 1 10 0 25 v A 25 v A A A valor do jogo v o 2 1 2 1 6 8 7 4 6 4y 1 8 4 7 1 4y seguir a verifique e s estratégia das funções associadas às uma 8 em qualquer 7 do y substituin se Determina 3 3 3 Valor do jogo y A1 A2 v v 25 y3 0875 0 875 6 4 1 4 6 4 1 4 3 3 3 3 8 7 y3 y y y y v A v A 2 1 10 0 Solução de jogos por programação linear das estratégia s do jogador A Cálculo das probabilidades ótimas m 2 1 x x x problema do jogador A matemático para o Modelo m 12 0 i x 1 x x x n 12 0 j a x v sa Z v max i m 2 1 m 1 i ij i v irrestrita em sinal m 12 0 i x 1 x x x a x a x a x min i m 2 1 m 1 i i in m 1 i i i2 m 1 i i i1 com ix max Retornos médios esperados de associado a cadaBj A então Se n 12 j a x a x a x a x min m 1 i i ij m 1 i i in m 1 i i i2 m 1 i i i1 v v Função objetivo do valor do jogo v Jogador A Solução de jogos por programação linear das estratégia s do jogador B Cálculo das probabilidades ótimas n 2 1 y y y problema do jogador B Modelo matemático para o n 12 0 j y 1 y y y m 12 0 i a y v sa D v min j n 2 1 n 1 j j ij irrestrita em sinal v n 12 0 j y 1 y y y a y a y a y max j n 2 1 n 1 j j nj n 1 j j 2j n 1 j j 1j sendo yj min Função objetivo do valor do jogo v Retornos médios esperados de associado a cadaAi B então Se m 12 i a y a y a y a y max n 1 j j ij n 1 j j nj n 1 j j 2j n 1 j j 1j v v Jogador B Exemplo 4 PO Hamdy A Taha Programação Linear Jogador B Estratégias B1 B2 B3 piores p A min da linha Jogador A A1 3 1 3 3 A2 2 4 1 2 maxmin 2 A3 5 6 2 6 piores p B max da coluna 3 4 2 minmax 2 por programaçã o linear Resolva o seguinte jogo 3 3 Valor do Jogo 2 2 v 2 2 Estratégias B1 B2 B3 x1 A1 3 1 3 x2 A2 2 4 1 x3 A3 5 6 2 0 x x x 1 x x x 0 2x x 3x v 0 6x 4x x v 0 5x 2x v 3x sa max Z v 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 m 12 0 i x 1 x x x n 12 0 j a x sa Z v max i m 2 1 m 1 i ij i v irrestrita em sinal v 0 x a x a x v a 3 p j 3 33 2 23 1 13 a Problema de programação linear do jogador A 0 x a x a x v a 1 j p 3 31 2 21 1 11 0 x a x a x v a 2 p j 3 32 2 22 1 12 3 1 i i1 xi a 3 1 i i2 xi a 3 1 i i3 xi a 0 5x 2x v 3x 3 2 1 0 6x 4x v 1x 3 2 1 0 2x 1x v 3x 3 2 1 j1 j2 j3 Estratégias y1 y2 y3 B1 B2 B3 A1 3 1 3 A2 2 4 1 A3 5 6 2 0 a y a y v a y 3 p i 3 33 2 32 31 1 n 12 0 j y 1 y y y m 12 0 i a y sa D v min j n 2 1 n 1 j j ij v irrestrita em sinal v 0 y y y 1 y y y 0 2y 6 y 5y v 0 y 4y 2 y v 0 3y y 3y v sa min D v 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 b Problema de programação linear do jogador B 0 a y a y v a y 1 p i 3 13 2 12 11 1 0 a y a y v a y 2 p i 3 23 2 22 21 1 3 1 J 1J yJ a 0 3y 1y v 3y 3 2 1 3 1 J 2J yJ a 0 1y 4y v 2y 3 2 1 3 1 J 3J yJ a 0 2y 6y v 5y 3 2 1 i1 i2 i3 0 x x x 1 x x x 0 2x x 3x v 0 6x 4x x v 0 5x 2x v 3x sa max Z v 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 0 y y y 1 y y y 0 2y 6 y 5y v 0 y 4y 2 y v 0 3y y 3y v sa min D v 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 Primal Dual 0 Y c sa A Y b Y D min T T 0 X b sa AX c X max Z T a Problema de programação linear do jogador A b Problema de programação linear do jogador B Primal Dual máx mín k ésima restrição é yk 0 k ésima restrição é yk é qualquer k ésima restrição é yk 0 xp 0 p ésima restrição é xp é qualquer p ésima restrição é xp 0 p ésima restrição é Dual Primal máx mín a Problema de programação linear do jogador A m 12 0 i x 1 x x x n 12 0 j a x sa Z v max i m 2 1 m 1 i ij i v 0 x x x 1 x x x 0 2x x 3x v 0 6x 4x x v 0 5x 2x v 3x sa max Z v 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 Primal Respostas Software Lindo A PERDE V 091 x1 039 x2 031 x3 029 Observe que o jogador A perde o jogo pois v é negativo Probabilidades com que o jogador A deve usar as estratégias A1 A2 e A3 respectivamente MAX v SUBJECT TO v 3x1 2x2 5x3 0 v x1 4x2 6x3 0 v 3x1 x2 2x3 0 x1 x2 x3 1 end LP OPTIMUM FOUND AT STEP 4 OBJECTIVE FUNCTION VALUE 1 09082569 VARIABLE VALUE REDUCED COST V 0908257 0000000 X1 0394495 0000000 X2 0311927 0000000 X3 0293578 0000000 ROW SLACK OR SURPLUS DUAL PRICES 2 0000000 0321101 3 0000000 0082569 4 0000000 0596330 5 0000000 0908257 NO ITERATIONS 4 b Problema de programação linear do jogador B 0 y y y 1 y y y 0 2y 6 y 5y v 0 y 4y 2 y v 0 3y y 3y v sa min D v 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 n 12 0 j y 1 y y y m 12 0 i a y sa D v min j n 2 1 n 1 j j ij v Dual Respostas Software Lindo V 091 Y1 032 Y2 008 Y3 060 Observe que o jogador B ganha o jogo pois v é positivo Probabilidades com que o jogador B deve usar as estratégias B1 B2 e B3 respectivamente B GANHA MIN v SUBJECT TO v 3y1 y2 3y3 0 v 2y1 4y2 y3 0 v 5y1 2y2 2y3 0 y1 y2 y3 1 end OBJECTIVE FUNCTION VALUE 1 09082569 VARIABLE VALUE REDUCED COST V 0908257 0000000 Y1 0321101 0000000 Y2 0082569 0000000 Y3 0596330 0000000 ROW SLACK OR SURPLUS DUAL PRICES 2 0000000 0394495 3 0000000 0311927 4 0000000 0293578 5 0000000 0908257 NO ITERATIONS 0 Notas de Aula Prof Edgard 1 GOLDBARG Marco Cesar LUNA Henrique Pacca L Otimização combinatória e programação linear modelos e algoritmos 2 ed rev e atual Rio de Janeiro Campus 2005 2 LOPES Heitor Silvério RODRIGUES Luiz Carlos de Abreu STEINER Maria Teresinha Arns Meta heurísticas em pesquisa operacional Curitiba Omnipax 2013 3 SHIMIZU Tamio Decisão nas organizações introdução aos problemas de decisão encontrados nas organizações e nos sistemas de apoio à decisão São Paulo Atlas 2001 4 ARENALES Marcos Nereu Pesquisa operacional para cursos de engenharia Rio de Janeiro Elsevier 2007 5 HILLIER Frederick S LIEBERMAN Gerald J Introdução à pesquisa operacional Porto Alegre AMGH 2013 6 GOMES Luiz Flavio Autran Monteiro GONZÁLEZ ARAYA Marcela Cecilia CARIGNANO Claudia Tomada de decisões em cenários complexos introdução aos métodos discretos do apoio multicritério à decisão 1 ed São Paulo Cengage Learning 2004 7 DUDA Richard O HART Peter E STORK David G Pattern classification and scene analysis 2nd ed New York J Wiley Sons c2001 8 Bodin L Golden B Assad A and Ball M Routing and Scheduling of veicles and crews Special edition of Computer and Operations Research col 10 n2 1983 9 Bronson R Pesquisa Operacional São Paulo Schaum McGrawHill do Brasil Ltda 1985 10 Murty K Linear and Combinatorial Programming Robert E Krieger Publishing Company Malabar Florida 1985 11 Steiner MT A Notas de Aulas Importante Este material tem finalidade única e exclusivamente didática e serve apenas como notas de apoio às aulas da disciplina de Métodos Quantitativos para Tomada de Decisão do curso de Graduação de Engenharia de Produção Este material não pode ser utilizado como referência bibliográfica e muito menos comercialmente Recomendase consultar as seguintes obras