Artigos Científicos

Jogos cooperativos: uma introdução ao valor de Shapley

Cooperative games: an introduction to Shapley value

Gil Bracarense Leite

Gil Bracarense Leite

gilbracarense@id.uff.br

Universidade Federal Fluminense (UFF, Campus Volta Redonda). Brasil

Informe Econômico

Universidade Federal do Piauí, Brasil

ISSN: 1517-6258

ISSN-e: 2764-1392

Periodicidade: Semestral

vol. 44, núm. 1, pp. 17 - 41, 2022

ie@ufpi.edu.br

Recepção: 22 Junho 2020

Aprovação: 21 Março 2022

URL: http://portal.amelica.org/ameli/journal/750/75036607503660002/

DOI: https://doi.org/10.26694/1517-6258.441

UFPI

License Creative Commons
Este trabalho está sob uma Licença Internacional Creative Commons Atribuição 4.0.

Modelo de publicação sem fins lucrativos para preservar a natureza acadêmica e aberta da comunicação científica

ePub gerado a partir de XML JATS4R

Resumo: : Neste trabalho objetiva-se fazer um esforço introdutório de caracterização dos jogos cooperativos com uma atenção especial ao conceito de solução do valor de Shapley que tem suas propriedades descritas em detalhes. Para cumprir esse objetivo são apresentados exemplos teóricos que podem ser resolvidos tanto cooperativamente quanto não cooperativamente, possibilitando uma comparação direta entre as duas abordagens da teoria dos jogos. Além disso, são descritas tradicionais aplicações do valor de Shapley em problemas práticos – jogos de alocação de custos e jogos de votação – de forma a aprofundar a compreensão sobre este conceito de solução. Ao mostrar os aspectos introdutórios e a praticidade do valor de Shapley acredita-se que este trabalho possa servir de ponto de partida para futuras aplicações e discussões, uma vez que existem poucas obras no Brasil que tratam dos jogos cooperativos e seus conceitos de solução.

Palavras-chave: Teoria dos jogos, Jogos cooperativos, Valor de Shapley.

Abstract: In this paper we aim to introduce the cooperative games with a special focus to the concept of Shapley value solution that has its properties described in detail. There are presented theoretical examples that can be solved both cooperatively and non-cooperatively, enabling a direct comparison between the two approaches of game theory. In addition, usual applications of Shapley value in practical problems like cost allocation games and voting games are described in order to intensify the understanding of this solution concept. By presenting the introductory characteristics and practicality of Shapley value, this paper can be used as reference for future applications and discussions about cooperative games and their solution concepts since there are few studies available in Brazil on this topic.

Keywords: Game theory, Cooperative games, Shapley value.

Introdução

Os agentes econômicos têm a possibilidade de interagir estrategicamente em uma ampla variedade de formas e muitas delas têm sido estudadas por meio da teoria dos jogos. Desde seu desenvolvimento formal a partir da segunda metade do século XX, a teoria dos jogos vem ganhando importância cada vez maior, e novas abordagens têm possibilitado sua aplicação não somente no campo da Economia, mas também em diversas outras áreas.

Segundo Osborne e Rubisntein (1994), um jogo é definido como a descrição de um processo de interação estratégica entre agentes racionais, sendo que sua abordagem teórica pode ser dividida em jogos não cooperativos e jogos cooperativos. De acordo com Montet e Serra (2003), em um jogo não cooperativo a única coalizão que de fato pode se formar é a que envolve o conjunto de todos os jogadores (chamada de grande coalizão). Além disso, como por definição os jogadores não se comunicam, há uma dificuldade em se manter acordos, ou, sob outra ótica, existe uma tentação em burlá-los. Por sua vez, nos jogos cooperativos considera-se que: é possível haver negociação entre jogadores; quaisquer coalizões intermediárias podem se formar – em que uma coalizão é um subconjunto não vazio do conjunto de jogadores; e os jogadores são capazes de se comprometer a seguir um curso de ações tão logo tenham alcançado um acordo.

Myerson (1991) explica que a possibilidade efetiva de existência de negociações entre coalizões de jogadores é a hipótese crucial que distingue jogos cooperativos dos não cooperativos[2]. Afirmar que os integrantes de uma coalizão podem efetivamente negociar, significa dizer que se houvesse uma mudança factível nas estratégias dos seus membros que beneficiasse a todos, então eles concordariam em realizá-la. Nos jogos cooperativos os jogadores podem conversar entre si para chegarem a um acordo e, o que é mais importante, há um estímulo para que esses acordos sejam são respeitados.

Um conhecido exemplo de jogo não cooperativo – o dilema dos prisioneiros – mostra de forma clara que quando não há estímulo para os jogadores adotarem uma estratégia cooperativa o resultado final é ineficiente. E caso os jogadores celebrassem um acordo, ambos teriam incentivo para burlá-lo, ou seja, há uma dificuldade em convencê-los a tornar a cooperação viável. São exatamente essas limitações que podem ser superadas pelas características do jogo cooperativo.

Um conceito de solução de destaque dos jogos cooperativos foi apresentado por Shapley (1953). De forma resumida, Serrano (2013) define o valor de Shapley como uma solução que prescreve um payoff único para cada jogador envolvido em uma situação de cooperação. Por se basear em axiomas relativamente simples, ser um conceito de solução de fácil entendimento e com vastas possibilidades de aplicação, o valor de Shapley se credencia como uma boa referência para ilustrar as características de um jogo cooperativo, bem como seus diferenciais frente às soluções não cooperativas.

Existem vários trabalhos que buscam apresentar de forma introdutória os jogos não cooperativos, dentre os quais se podem citar Dixit e Nalebuff (1991), Dixit, Skeath e Reiley Jr. (2004), e McMillan (1992). Como houve dificuldade em encontrar algo similar para a abordagem cooperativa, o presente trabalho tem como objetivo fazer um esforço inicial de popularização dos jogos cooperativos, apresentando-o de forma didática e minuciosa, com foco especial no conceito de solução do valor de Shapley, que tem suas propriedades descritas em detalhes. Para cumprir esse objetivo são apresentados exemplos teóricos – dilema dos prisioneiros e jogo de divisão do dólar – que podem ser resolvidos tanto cooperativamente quanto não cooperativamente, possibilitando uma comparação direta entre as duas abordagens. Além disso, são descritas tradicionais aplicações do valor de Shapley em problemas práticos – jogos de alocação de custos e jogos de votação – de forma a aprofundar a compreensão sobre este conceito de solução e, como texto introdutório, lançar luz para futuras aplicações.

Após esta introdução, o trabalho está organizado da seguinte maneira. A seção 2 apresenta as principais definições necessárias para a compreensão dos jogos cooperativos. A seção 3 detalha o valor de Shapley. A seção 4 mostra exemplos em que é possível comparar jogos cooperativos e não cooperativos, além de apresentar casos de aplicação do valor de Shapley. Por fim, a seção 5 traz as conclusões obtidas.

1 Jogos cooperativos: conceitos e definições

A cooperação entre os jogadores ou a formação de coalizões é um caminho para se alcançar resultados mais eficientes em negociações. Mas porque alguns jogadores se associariam? A justificativa para a existência de coalizões, segundo Aliprantis e Chakrabarti (2000), está no fato de que as alternativas propostas e implementadas por seus membros podem garantir a eles payoffs maiores do que receberiam caso não se associassem a nenhum outro jogador, indicando que existem ganhos ao se formar uma coalizão. Ademais, diferente dos jogos não cooperativos, na cooperação há a premissa de que os jogadores podem conversar entre si para buscar acordos, o que faz toda diferença no processo de negociação.

Ainda que favoreçam as negociações, a existência de coalizões traz desafios ao estudo dos jogos cooperativos, pois, como explicam Montet e Serra (2003), dificuldades naturais surgem devido ao fato de tratarem simultaneamente de várias questões, tais como: o processo de formação de uma coalizão (quais coalizões irão se formar?), a estabilidade de coalizões que enfrentam a entrada e/ou saída de jogadores e a alocação do excedente da cooperação entre os membros de uma coalizão em problemas de partilha de recursos.

Existem diferentes formas de representação de jogos. Como se vê em Gibbons (1992), as mais comuns são as formas normal e extensiva, usuais em jogos não cooperativos. A forma normal é a representação para jogos simultâneos indicada em uma matriz de ganhos que mostra as estratégias disponíveis e o payoff recebido pelos jogadores em cada combinação de estratégias que poderia ser escolhida por eles. A forma extensiva é a representação para jogos sequenciais indicada no formato de uma árvore, em que as ramificações simbolizam as opções de movimento dos jogadores. Na forma extensiva, são de comum conhecimento tanto os movimentos anteriores ao se decidir pelo próximo passo, quanto os payoffs resultantes de cada possível combinação de movimentos[3].

Já a representação do jogo cooperativo se dá por meio da chamada função característica, que é a forma pela qual se indica o valor de cada coalizão e se descrevem as possibilidades de cooperação. De acordo com Mas-Colell et al. (1995), a função característica apresenta uma descrição dos payoffs disponíveis para diferentes grupos de jogadores em um contexto em que acordos de compromisso entre eles são viáveis, o que é exatamente a essência da cooperação.

Para caracterizar um jogo cooperativo, algumas definições iniciais devem ser apresentadas. Seja um conjunto finito que representa o universo de jogadores, conhecido como grande coalizão. Cada subconjunto finito e não vazio de é chamado de coalizão. Para cada coalizão , especifica-se um conjunto contendo vetores de payoff de dimensões que são viáveis para a coalizão . Tem-se que é exatamente a função característica que designa um número real para cada coalizão , com e indicando o valor da grande coalizão[4]. Visto isso, um jogo cooperativo pode ser representado de forma resumida por onde é o conjunto de jogadores e é a função característica que associa um número real com cada subconjunto de

Sobre , o valor da coalizão, Montet e Serra (2003) afirmam que ele representa o máximo payoff que os membros de poderiam garantir independentemente das ações dos membros fora da coalizão, ou seja, assume-se que as ações tomadas pelos jogadores em não podem impedir de alcançar os vetores de payoff em , em que simboliza o conjunto complementar, ou seja, os jogadores que não estão em . Roth (1988) lembra que é exatamente a quantia que os integrantes de dividirão entre eles, sendo que essa partilha pode acontecer de qualquer modo viável.

Uma importante restrição sobre a função característica é que ela seja superaditiva (ou, equivalentemente, subaditiva se for uma função custo). De acordo com Roth (1988), jogos superaditivos são aqueles em que tudo que duas coalizões podem fazer de forma independente, a união delas pode fazer também. Como se vê na eq. (1), para quaisquer coalizões e contidas em , o valor alcançado pela união de ambas é pelo menos igual à soma dos valores que seriam alcançados individualmente.

então,

Montet e Serra (2003) afirmam que uma consequência da superaditividade é que é possível encontrar no conjunto viável de alocações da grande coalizão, uma alocação de payoffs que seja Pareto eficiente[5]. Portanto, em jogos superaditivos, o princípio da eficiência força a cooperação total[6].

Segundo Myerson (1991), uma vez que as interações entre as diferentes coalizões em jogos com jogadores podem ser extremamente complexas (um jogo com jogadores tem coalizões possíveis), a suposição simplificadora da utilidade transferível é utilizada nas análises dos jogos cooperativos representados na forma de função característica. O conceito de utilidade transferível assume a existência de um numerário, normalmente o dinheiro, que pode ser transferido livremente entre os jogadores, de modo que o payoff de um jogador aumenta em uma unidade para cada unidade de numerário que ele recebe.

Roth (1988) explica que isso significa que o payoff total da coalizão pode ser definido, simplesmente, como a soma dos payoffs de seus membros. Exatamente devido à suposição da utilidade transferível é que as possibilidades cooperativas de um jogo podem ser descritas por uma função característica que designa um único número para cada coalizão , número esse suficiente para descrever as alocações que podem ser obtidas pelos seus membros. Problemas de alocação de custo, ou qualquer outra barganha de valores monetários, são típicos exemplos de jogos de utilidade transferível, em que o valor pode ser livremente negociado entre os jogadores. Foi Aumann (1960) quem formalizou o conceito ao mostrar que utilidade transferível significa que a utilidade de cada jogador é uma função linear da quantidade de dinheiro.

De acordo com Peleg e Sudholter (2007), visto que as funções de utilidade dos jogadores são lineares e aumentam com o dinheiro, quando uma coalizão se forma ela pode dividir o valor entre os seus membros de qualquer forma viável, ou seja, as transferências entre jogadores são irrestritas já que é simplesmente a soma de vários valores monetários.

Deve-se observar que, apesar de ser mais prático modelar situações como se fossem de utilidade transferível, esta é uma suposição que pode em algumas ocasiões obscurecer características do ambiente econômico. Para superar essas limitações a teoria dos jogos tem se preocupado também com os jogos de utilidade não transferível, que fogem do escopo deste trabalho, mas, podem ser vistos por exemplo em Aumann e Peleg (1960) (que introduziram a questão) e em Peleg e Sudholter (2007).

As considerações vistas até aqui – cruciais para a compreensão dos jogos cooperativos e do valor de Shapley – devem muito ao trabalho de Jon von Neumann e Oskar Morgenstern que lançaram a maioria dessas bases na obra Theory of Games and Economic Behavior, de 1944. Como o próprio Shapley (1953) destaca, embora seu trabalho seja matematicamente autossuficiente, do ponto de vista conceitual ele tem seu fundamento na teoria de von Neumann e Morgenstern, dos quais herdou justamente as hipóteses vistas anteriormente: (i) a utilidade é transferível; (ii) os jogos são cooperativos; (iii) dado (i) e (ii) os jogos podem ser representados de forma adequada por funções características. Roth (1988) também cita o pioneirismo de von Neumann e Morgenstern e destaca que eles mostraram de forma exitosa que uma coalizão pode determinar acordos para distribuir seu valor na forma combinada pelos seus membros, sem a necessidade de modelar explicitamente as ações que os jogadores devem tomar para a realização desses acordos.

Após a especificação dos conceitos iniciais da teoria dos jogos cooperativos, o passo seguinte consiste em buscar identificar qual será o resultado de um processo de negociação entre jogadores, ou seja, identificar os payoffs finais recebidos por cada jogador, o que demanda a presença de conceitos de solução.

2 Conceitos de solução de jogos cooperativos

Serrano (2013) explica que na maior parte dos problemas envolvendo negociações as soluções se sustentam na forma da grande coalizão, em que a cooperação total é alcançada, o que é uma consequência dos jogos superaditivos. Assumindo essa hipótese, um conceito de solução deve simplesmente designar vetores de payoff em para cada jogo cooperativo.

Os payoffs que cada jogador recebe podem ser encontrados seguindo uma abordagem positiva ou normativa. Montet e Serra (2003) afirmam que na ótica positiva o foco recai sobre as propriedades estratégicas de estabilidade das coalizões. Sob esse ponto de vista, os jogos cooperativos seriam parte de um estudo mais amplo sobre acordos diretos entre agentes racionais negociando livremente. Por outro lado, na ótica normativa dos conceitos de solução a ênfase está nas propriedades das soluções que são atraentes de um ponto de vista ético. Sob essa visão, os jogos cooperativos são analisados como ferramenta para o estabelecimento do critério da justiça distributiva ou da equidade.

O core é um exemplo de solução positiva, enquanto o valor de Shapley é um exemplo de solução normativa. Contudo, mesmo que seja importante como fonte de conhecimento, Montet e Serra (2003) ressaltam que não se deve focar nessa separação, visto que não são necessariamente excludentes: considerações estratégicas podem estar presentes na interpretação normativa, assim como considerações de justiça e equidade na interpretação positiva.

2.1 Core

Ainda que o trabalho se concentre no valor de Shapley, é importante a título de comparação descrever o core. Montet e Serra (2003) afirmam que considerando os diversos conceitos de solução dos jogos cooperativos, possivelmente o core é o mais intuitivo e de mais fácil compreensão. De modo geral, uma vez que um acordo é alcançado no core nenhum jogador (ou conjunto de jogadores) pode se beneficiar se reagrupando, ou seja, a alocação de payoff encontrada via core é eficiente no sentido de Pareto.

Para definir formalmente o core, apresenta-se os conceitos de imputação e relação de domínio. De acordo com Mas-Colell et al. (1995), as imputações são vetores de payoff naturalmente identificados para análise como o conjunto que contém todos os resultados razoáveis para um jogo cooperativo. Define-se uma imputação em um jogo , denotada por , como sendo um vetor de payoffs que satisfaz as condições de racionalidade presentes na eq. (2) e eq. (3)

(2)

(3)

A primeira condição, racionalidade do grupo, incorpora ao mesmo tempo os requisitos de que os membros da grande coalizão alcancem o resultado (viabilidade): ; e que não haja nenhum resultado melhor (eficiência de Pareto): . A segunda condição, racionalidade individual, estabelece que a quantia alocada como payoff para qualquer indivíduo não deve ser menor do que ele ganharia atuando individualmente.

Por sua vez, a relação de domínio, conforme define Serrano (2013), refere-se ao poder que uma coalizão pode exercer por meio de sua habilidade de se manter, ou seja, de não ter seus resultados superados por nenhuma outra coalizão. Dessa forma, diz-se que é dominado por no âmbito da coalizão se é viável e proporciona maior payoff aos membros de do que . Formalmente, para , domina via se: e . Quando domina significa que os membros de podem melhorar seus payoffs por meio de seus próprios esforços.

Apresentados os conceitos de imputação e domínio tem-se, finalmente, a definição de core: o core de um jogo é um subconjunto do conjunto de imputações que não são dominadas.

Conforme Shapley (1971), o core é o conjunto de todos os payoffs viáveis para a grande coalizão sobre o qual nenhum indivíduo ou grupo pode melhorar. Ou seja, nenhum subconjunto de jogadores pode efetivamente reivindicar que eles obteriam resultados superiores atuando por conta própria. Segundo Osborne e Rubinstein (1994), um resultado do core é dito estável se nenhuma coalizão pode obter um resultado melhor para todos os seus membros. Caso contrário, se existe uma coalizão que pode melhorar um determinado resultado, ele é considerado instável.

Deve-se ressaltar, entretanto, que para alguns jogos o core pode ser vazio. Serrano (2013) explica que um jogo com o core vazio deve ser entendido como uma situação de forte instabilidade e vulnerabilidade dos payoffs propostos pela grande coalizão. Quando o core é vazio, Myerson (1991) afirma que não é possível esboçar qualquer conclusão sobre o jogo. Por outro lado, se o core consiste em um conjunto com grande número de elementos, então também há dificuldade em indicar qualquer alocação em particular.

Conclui-se, então, que o core tem a importante propriedade da estabilidade, já que seus payoffs não podem ser superados, mas, apresenta as limitações citadas: pode ser um conjunto vazio ou pode indicar um conjunto muito grande de resultados, o que dificulta sua aplicação na predição da solução de um jogo. Nesses casos, Myerson (1991) afirma que seria desejável que um jogo na forma de função característica apresentasse como resultado uma alocação de payoff única para cada jogador. O valor de Shapley atende a esse requisito[7].

Sobre a relação entre os dois conceitos de solução, Montet e Serra (2003) explicam que não obrigatoriamente o valor de Shapley precisa ser um membro do core, mesmo se o core não for vazio. Isso significa que o valor de Shapley pode fornecer uma alocação que não é estável. Entretanto, um tipo de jogo específico têm importantes propriedades que ajudam a superar essas limitações: os jogos convexos. Se o jogo for convexo o core é sempre não vazio e nesse caso foi mostrado por Shapley (1971) que o valor de Shapley não somente pertence ao core do jogo, como também é o centro de gravidade dos pontos extremos do mesmo[8].

2.2 Valor de Shapley

Segundo Roth (1988), o valor de Shapley é um conceito de solução que resume as reivindicações conflitantes que cada jogador enfrenta em um jogo cooperativo por meio de um único número que representa exatamente o valor de jogar o jogo. De acordo com o próprio Shapley (1953), objetivando resumir as complexas possibilidades enfrentadas pelos jogadores num jogo na forma de função característica, ele se ateve à resolução representada por um valor único de problemas de alocação entre os agentes que fazem parte de um jogo, quando se leva em consideração o valor de cada coalizão

Shapley (1953), então, define o valor do jogo como sendo uma função que associa com cada jogador em , uma alocação de payoff representada por um número real que deve atender às condições de quatro axiomas bastante intuitivos:

A1: Eficiência. . O axioma da eficiência diz que a soma das alocações de payoffs de todos os jogadores deve igualar , o valor total do jogo

A2: Simetria. Para qualquer permutação de tem-se que , para todo . Em que uma permutação é uma função que representa um rearranjo de jogadores. Isso significa que se houver um reordenamento de no jogo, seu valor não se altera, pois, o que importa na determinação do valor é como a função característica responde à presença de um jogador em uma coalizão. O axioma da simetria garante que jogadores tratados de forma idêntica pela função característica têm o mesmo valor

A3: Aditividade. Para quaisquer jogos e , para todo em , em que o jogo é definido por para qualquer coalizão . O axioma da aditividade diz que a solução para a soma de dois jogos deve ser igual à soma do que é recebido separadamente em cada um deles.

A4: Jogador dummy. Um jogador é dummy se para cada coalizão S que não faz parte, de modo que . Em que é a contribuição marginal de ao formar qualquer coalizão , ou seja, é quanto ele acrescenta ao se unir a outros jogadores. O axioma do jogador dummy diz que se um jogador não contribui com nada adicional a uma coalizão (além do seu próprio valor), a solução lhe reservará apenas seu valor individual .

Shapley (1953) demonstrou matematicamente que há um método de solução de valor único para jogos cooperativos de utilidade transferível satisfazendo esses quatro axiomas. É o que ficou conhecido como valor de Shapley, a função que designa para cada jogador . o payoff indicado na eq. (4).

(4)

onde é o número de elementos do conjunto de todos os jogadores, com ; designa o número de jogadores na coalizão ; e a expressão representa a contribuição marginal do jogador quando ele se associa a outros jogadores para formar a coalizão . É notável, concluiu o próprio autor, que não é necessária nenhuma condição adicional, além desses axiomas relativamente simples, para determinar o valor de forma única.

Myerson (1991) e Roth (1988) utilizam uma alegoria para interpretar essa fórmula, imaginando uma situação em que se planeja juntar todos os jogadores em uma sala, com a ressalva de que apenas um entrará por vez. Os jogadores se alinharão aleatoriamente em uma fila em frente à porta, lembrando que para jogadores existem formas diferentes deles se ordenarem nessa fila. Para qualquer conjunto em que o jogador não esteja contido, há maneiras distintas de ordenar os jogadores, de tal modo que é o conjunto de jogadores que estão na fila à frente de (e se associará a eles) e os restantes que irão sucedê-lo. Dessa forma, se os vários ordenamentos são considerados igualmente prováveis, é a probabilidade de que, quando entrar na sala, ele encontrará a coalizão à sua frente, sendo que nesse caso sua contribuição marginal para a coalizão (aqueles que já estão na sala) é .

Considerando a alegoria da entrada aleatória, o valor de Shapley de um jogador pode ser interpretado como sendo a contribuição marginal esperada a cada coalizão que ele puder se associar. Assim, segundo Hart (1989), se for esperado que um indivíduo acrescente pouco (muito) às coalizões, então o payoff alocado a ele tende a ser pequeno (grande). Nesse sentido, o valor de Shapley é classificado como uma regra que busca dividir um excedente de forma justa entre os participantes, em que o conceito de justiça não é o de equidade, mas a ideia de que o payoff que o indivíduo recebe é determinado por sua contribuição.

De acordo com Roth (1988), o valor de Shapley desde sua publicação em 1953 tem sido usado como conceito de solução em ampla variedade de contextos econômicos e despertado contínuo interesse dos estudiosos dos jogos cooperativos. Montet e Serra (2003) lembram que o valor de Shapley é uma medida relativamente fácil de computar e existe para todos os jogos cooperativos, o que é uma vantagem em relação ao core, que pode ser vazio. Para Hart (1989), a fórmula desenvolvida para o valor de Shapley é impressionante porque ela é consequência de axiomas básicos e porque a ideia de contribuição marginal na qual ela se baseia é fundamental em muitas análises econômicas.

3 Exemplos e aplicações

A fim de compreender as características de uma solução cooperativa, esta seção apresenta exemplos de cálculo do valor de Shapley em problemas que também podem ser resolvidos não cooperativamente, possibilitando que as duas abordagens dos jogos sejam confrontadas. Os exemplos são relativamente simples, o dilema dos prisioneiros e o jogo da divisão do dólar, se adequando ao objetivo desse trabalho de introduzir de forma acessível os jogos cooperativos. Todavia, acredita-se que podem servir de ponto de partida para a análise de problemas mais complexos. Ademais, são apresentados também os jogos de alocação de custos e jogos de votação, aplicações tradicionais do valor de Shapley que podem contribuir para aprofundar a compreensão deste conceito de solução e vislumbrar futuras aplicações.

3.1 Exemplo: dilema dos prisioneiros

a) Jogo não cooperativo

Por ser bastante conhecido, o dilema dos prisioneiros é um bom começo para demonstrar os obstáculos que a não possibilidade de se buscar acordos traz ao resultado de um jogo não cooperativo. Um exemplo comum do dilema dos prisioneiros, adaptado de Osborne e Rubinstein (1994) e Myerson (1991), é na análise de cartéis. Duas empresas de um mesmo ramo montam um cartel para aumentar os lucros por meio de um acordo em que ambas manteriam elevados os preços de seus produtos. A matriz de ganhos e as possibilidades de estratégias estão na Figura 1, que indica o lucro em milhões de dólares[9]. “Cooperar” significa manter um preço elevado e “Não Cooperar” significa reduzir o preço unilateralmente para capturar o mercado.

Figura 1 – O jogo do dilema dos prisioneiros

Figura 1

O jogo do dilema dos prisioneiros

|  | Empresa B
|  | Cooperar | Não Cooperar
Empresa A | Cooperar | 6 ; 6 | - 1 ; 8
| Não Cooperar | 8 ; -1 | 0 ; 0

elaborado pelo autor.

Se as empresas cooperarem cada uma terá um lucro de $ 6 milhões. Contudo, elas não têm incentivos para cumprir o acordo do cartel[10]. Se a Empresa . cobrar um preço elevado (Cooperar), valerá a pena para . empreender uma política de redução de preços (Não Cooperar) para conquistar o mercado e obter lucros individuais maiores ($ 8 milhões). Mas se . desconfia que . não vai cumprir o que foi acordado (ou seja, irá reduzir o preço), será melhor . também reduzir para não acabar com prejuízo de $1 milhão. No fim, se ambas seguirem esse raciocínio, o único equilíbrio de Nash deste processo de interação estratégica é quando as duas empresas escolhem “Não Cooperar”, resultando em um lucro zero para cada uma. Lembrando que um conjunto de estratégias é um equilíbrio de Nash se cada uma representa a melhor resposta para a estratégia do outro jogador, conforme definição de Gibbons (1992).

O equilíbrio de Nash desse jogo é um resultado não eficiente se comparado ao acordo do cartel, em que as empresas estariam em melhor situação ao obter um lucro de $ 6 milhões cada. O que o dilema dos prisioneiros mostra é que quando não há estímulo para que se adote uma estratégia cooperativa o resultado final é ineficiente, visto que há um incentivo para burlar o acordo. Essa limitação pode ser superada em uma estrutura de jogo cooperativo em que há a chance de os jogadores atingirem um acordo e, acima de tudo, respeitá-lo[11].

b) Jogo cooperativo

Pode-se encontrar um resultado cooperativo para o dilema dos prisioneiros através do valor de Shapley. Ressaltando que não se trata de um exemplo com todas as características observadas no jogo não cooperativo, pois, existem propriedades diferentes. O que se tem é um cálculo do valor de Shapley que aproveita os mesmos payoffs do exemplo do cartel. Há pelo menos duas formas de se pensar um jogo cooperativo com os dados da Figura 1:

1) Duas empresas de um mesmo ramo e com estruturas de custo idênticas formam um cartel e devem chegar a um acordo de como partilhar entre elas o lucro total da cooperação ($ 12 milhões). Caso não alcancem consenso elas acabarão com lucro zero, o resultado de desacordo.

2) Duas empresas de um mesmo ramo e com estruturas de custo idênticas têm a opção de atuarem individualmente como concorrentes no mercado, o que as levaria a obter um lucro zero, ou então, podem se unir e formar um cartel para atuar como uma só empresa monopolista, alcançando um lucro de $ 12 milhões que deve ser repartido entre elas.

Independente da interpretação escolhida o resultado do jogo cooperativo e sua estrutura não mudam, de modo que a função característica tem os valores indicados em (5) e (6).

(5)

(6)

Ou seja, atuando conjuntamente as empresas . e . alcançam um lucro de $ 12 milhões e atuando de forma individual (como concorrentes) elas obtêm apenas o chamado lucro zero ou normal[12]. Com essas informações, o valor de Shapley determina as alocações presentes na eq. (7) e eq. (8).

(7)

(8)

Em um jogo cooperativo o resultado seria a manutenção do acordo do cartel, com ambas as empresas obtendo um lucro de $ 6 milhões, repartindo igualmente os ganhos da cooperação. Foi visto que o equilíbrio de Nash do jogo não cooperativo não foi capaz de apontar essa solução, dada a dificuldade de se respeitar o acordo.

3.2 Exemplo: jogo de divisão do dólar

a) Jogo não cooperativo

Outra conhecida ilustração de jogo não cooperativo é o jogo de divisão do dólar, em que dois jogadores devem chegar num acordo sobre como dividir uma quantia de $ 1. Esse problema também pode ser analisado pelos jogos cooperativos, possibilitando mais uma vez uma comparação dos resultados.

Tem-se o seguinte exemplo adaptado de Gibbons (1992). Os jogadores e estão barganhando sobre como dividir uma nota de dólar. Ambos divulgam simultaneamente a quantia que eles desejariam, indicadas respectivamente por e , com a restrição de que . Se , então os jogadores recebem exatamente a quantia que divulgaram. Contudo, se , ambos recebem zero. Com essas informações pode-se encontrar o equilíbrio de Nash em estratégias puras para esse jogo[13].

Descrevendo de um modo formal, o conjunto de estratégias é dado por , os jogadores são e os payoffs são aqueles indicados em (9).

(9)

Para encontrar o resultado do jogo, inicia-se a análise sob a ótica do jogador A, mas, tendo em vista sua reação às escolhas de B. Se , qualquer ponto no conjunto é uma estratégia ótima para o jogador A. A explicação é como segue: se o jogador A jogar 0, tem-se que . Logo, o jogador A receberá 0 e B receberá $ 1. Qualquer outro valor que o jogador A jogar, a soma será maior que 1, de modo que ambos não ganharão nada. Portanto, se , seja qual for a estratégia que A adote entre ele receberá zero[14]. Por outro lado, se , então a estratégia ótima para o jogador A é dada por . A explicação é que ao jogar , o jogador A atende à restrição e recebe um valor positivo ao invés de um valor nulo. Dada essa descrição, a correspondência de melhor resposta de A é dada pela eq. (10)[15].

(10)

Analisando sob o ponto de vista do jogador B os procedimentos são análogos. Se , qualquer ponto no conjunto é uma estratégia ótima para B, pois ele sempre receberá 0. Por outro lado, se , a estratégia ótima para B é dada por , pois, assim ele ganhará um valor positivo. Dessa forma, a eq. (11) representa a correspondência de melhor resposta para B.

(11)

Pode-se encontrar o resultado desse processo de negociação representando graficamente as duas correspondências, onde é indicado pela linha cinza em tom claro e pela linha cinza em tom mais escuro na Figura 2.

Figura 2
Correspondência de melhor resposta e equilíbrio de Nash no jogo de divisão do dólar

elaborado pelo autor.

Os equilíbrios de Nash são identificados como as interseções das duas correspondências (quando as estratégias dos jogadores são reciprocamente as melhores respostas), o que inclui toda a linha diagonal em que a estratégia de um jogador é complementada pela do outro, somando o total de $ 1, e o ponto , em que ambos não ganham nada. Os resultados são indicados por

Portanto, a solução não cooperativa para a divisão do dólar não é única. Ela prevê como equilíbrio qualquer divisão de valores que somem $ 1 ou o resultado ineficiente em que ninguém ganha nada (porque ambos desejam tudo), fruto da dificuldade em se chegar a um acordo. Novamente, essas limitações podem ser evitadas em uma estrutura de jogo cooperativo.

b) Jogo cooperativo

Continuando com o caso dos dois jogadores que devem chegar num acordo sobre a divisão de uma nota de dólar, pode-se encontrar uma solução cooperativa para esse problema por meio do valor de Shapley. Claramente tem-se um jogo de utilidade transferível, visto que o payoff é uma função linear da quantidade de dinheiro.

Um jogo cooperativo de divisão do dólar pode ser pensado da seguinte forma. Os jogadores . e . devem obrigatoriamente chegar a um acordo sobre como partilhar a nota de dólar. Não havendo consenso, ambos não recebem valor algum. A função característica desse jogo pode ser descrita por (12) e (13).

(12)

(13)

E as alocações do valor de Shapley são dadas pela eq. (14) e eq. (15).

(14)

(15)

Na prática, um só cálculo seria suficiente, pois, o axioma da simetria garante a igualdade de valores entre os jogadores. Vê-se que o valor de Shapley provê uma solução perfeitamente razoável para um jogo como esse, dividindo igualmente a nota de dólar entre os dois participantes. Novamente reitera-se que esse resultado não acontece na solução não cooperativa para um exemplo idêntico.

3.3 Aplicação: jogo de alocação de custos

Deixando de lado comparações com jogos não cooperativos e concentrando-se nas aplicações, os jogos de alocação de custos representam um campo fértil para a utilização do valor de Shapley. Segundo Peleg e Sudholter (2007) um problema de alocação de custos pode ser resumido em um jogo onde é o conjunto de jogadores e é a função característica, que simboliza uma função custo. Para todo subconjunto , – o valor da coalizão – representa o menor custo de servir os membros de da forma mais eficiente.

Um exemplo interessante está em Young (1994) que analisou um plano do governo dos Estados Unidos de planejamento na bacia do rio Tennessee que consistiu na construção de uma série de barragens que atenderiam a múltiplos usos. O problema é exatamente como alocar os custos entre os diferentes usos dos recursos hídricos.

No projeto do governo americano foram estabelecidos níveis que uma barragem deveria atingir para atender a três usos: navegação (.), controle de inundação (.) e geração de energia (.) (uma barragem pode ser construída em diferentes alturas, dependendo dos usos a serem atendidos) e estimou-se o menor custo de construir uma barragem que atendesse aos diferentes alvos. Mais precisamente, para cada combinação dos três usos foi estimado o custo que cada coalizão teria para atingir os níveis almejados, conforme mostra a Tabela 1. Caracterizando como um jogo de alocação, os jogadores seriam exatamente os três diferentes usos da água, que estariam representados por agências ou empresas responsáveis por fornecer o serviço e às quais seriam alocados os custos do projeto.

Tabela 1

Jogo de alocação de custos: exemplo do reservatório de múltiplos usos

Coalizões | Custo (mil US$)
| 0
| 163.520,00
| 140.826,00
| 250.096,00
| 301.607,00
| 378.821,00
| 367.370,00
| 412.584,00

Young (1994, p. 1198).

A Tabela 1 pode ser lida da seguinte forma. Para construir uma barragem que atenda só a navegação, o custo seria de 163.520,00 (em mil US$, assim como os demais valores nessa seção). Para atender apenas ao controle de inundação, o custo seria de 140.826,00. E assim sucessivamente até chegar à última linha, que mostra que para construir uma barragem que atenda simultaneamente aos três usos, o custo seria de 412.584,00. Por que é possível utilizar o conceito de jogo cooperativo nesse exemplo? Os dados mostram que ao tratar os custos de forma conjunta, pode-se atender a cada uso da água com um custo individual menor, visto que . Ou seja, existem ganhos oriundos da coalizão. Com esses dados, o valor de Shapley para cada uso dos recursos hídricos é indicado por (os cálculos estão no ANEXO A):

Navegação

Controle de inundação:

Geração de energia:

As alocações do valor de Shapley denotam exatamente o custo a ser alocado para cada uso como parte do custo total de se realizar os projetos que atendam aos três objetivos simultaneamente. Percebe-se que a soma das alocações esgota o custo conjunto (412.584,00), como requer o axioma da eficiência. Além disso, cada alocação do valor de Shapley para determinado uso é inferior ao seu respectivo custo individual, o que significa que existem incentivos para a cooperação, ou, para tratar dos custos de forma conjunta.

Várias outras aplicações do valor de Shapley em problemas de alocação de custos são encontradas na literatura. Littlechild e Owen (1973) aplicaram o valor de Shapley no cálculo de taxas para a aterrissagem de aviões em aeroportos, estudando a divisão dos custos de infraestrutura de construção de uma pista de pouso. Fragnelli et al. (2000) estudaram a divisão dos custos de infraestrutura de construção de uma ferrovia na Europa. Loehman et al. (1979) trataram da alocação do custo da construção de um sistema regional de tratamento de água na bacia do rio Meramec, no estado americano do Missouri. E Young et al. (1982) estudaram a alocação do custo da construção de um sistema de abastecimento de água na região de Skane, na Suécia.

3.4 Aplicação: jogos de votação

Outra aplicação usual dos jogos cooperativos e do valor de Shapley é em jogos de votação. Este tipo de aplicação é uma situação particular do valor de Shapley quando ele é utilizado para calcular o poder de um jogador dentro de um jogo e é chamado de índice Shapley-Shubik, devido ao trabalho de Lloyd Shapley e Martin Shubik, de 1954, que propôs a aplicação do valor de Shapley à classe dos chamados jogos simples. Segundo Shapley e Shubik (1954), um jogo simples é representado por uma função característica que assume somente os valores 0 e 1, tal que uma coalizão é dita vencedora se e perdedora se . Os jogos simples são modelos naturais para situações de votação.

Um típico cenário de votação com jogadores pode ser representado pelo vetor , onde denota o número de votos do jogador e denota o número de votos necessários para uma coalizão ser vencedora. As coalizões vencedoras são aquelas com votos suficientes, isto é, é vencedor se e somente se

De acordo com Roth (1988), como a contribuição marginal em um jogo simples é sempre 0 ou 1, então um índice Shapley-Shubik de um jogador equivale à proporção de ordenamentos aleatórios no qual ele é um jogador essencial, ou seja, a proporção de ordenamentos nos quais o conjunto de jogadores que o precede forma uma coalizão perdedora que é transformada em vencedora (coalizão ) exatamente pela chegada de (em cada ordenamento de jogadores somente um é essencial). O índice Shapley-Shubik conta o número de vezes em que o jogador é essencial, ou seja, quantas vezes ele transforma uma coalizão perdedora em vencedora, o que representa o poder desse jogador.

Para compreender as características de um jogo de votação considera-se o processo de decisão em um parlamento, num exemplo adaptado de Serrano (2013) e Hart (1989). Suponha que existam 100 assentos e as decisões são tomadas por maioria simples: 51 votos são suficientes para uma lei ser aprovada. Existem 3 jogadores neste parlamento: dois grandes partidos (Partidos 1 e 2) e um pequeno partido (Partido 3). Cada um dos grandes partidos tem 48 assentos, enquanto o partido pequeno tem apenas 4.

Como a maioria simples torna uma coalizão vencedora (no sentido de aprovar uma lei), tem-se que a função característica dá origem aos valores de coalizão indicados pela Tabela 2. Uma coalizão tem valor 0 se ela não alcança a maioria para a aprovação da lei e tem valor 1 – tornando-se uma coalizão vencedora – se ela atinge a maioria necessária.

Tabela 2

Jogo de votação: exemplo do índice Shapley-Shubik

Coalizões | Valor
| 0
| 0
| 0
| 0
| 1
| 1
| 1
| 1

elaborado pelo autor.

Com esses dados obtêm-se as alocações do valor de Shapley (os cálculos estão no ANEXO B):

O resultado indica 33,33% de poder no parlamento para cada partido, com um poder total dos jogadores igual a 1, respeitando o axioma da eficiência. Apesar da elevada diferença de assentos entre os partidos grandes e o pequeno, os três são idênticos em termos de contribuição marginal para tornar uma coalizão vencedora. Para a contribuição marginal do jogador é positiva somente quando ele é o segundo a compor em sequência uma coalizão. Se for assumido que os Partidos 1 e 2 são rivais, o apoio do Partido 3 é determinante para tornar uma coalizão vencedora, o que explica a igual distribuição de poder entre os três, mesmo tendo quantidades diferentes de assentos. Ou seja, a rivalidade entre os partidos maiores pelos votos do pequeno aumenta o poder deste último.

Se houvesse uma mudança no sistema de voto de modo que fosse necessário dos assentos para passar uma lei, a situação seria diferente. Os Partidos 1 e 2 dividiriam o poder entre eles (50% para cada) e o Partido 3 seria um jogador dummy, pois, em nenhuma situação ele faria uma coalizão se tornar vencedora. Nota-se claramente como o valor de Shapley capta as mudanças na distribuição de poder devido a cada cenário político diferente. E percebe-se, novamente, que o poder de um partido não reflete a exata proporção de seus votos.

Exemplos do jogo de votação podem ser vistos no próprio artigo pioneiro de Shapley e Shubik (1954) que aplicaram sua metodologia na definição de poder dentro do conselho de segurança da ONU. Widgrén (1994) analisou o poder de voto no parlamento da União Europeia. Por sua vez, Straffin Jr. (1988) fez algumas simulações considerando a estrutura política e partidária americana.

Considerações finais

Este trabalho teve o objetivo de fazer um esforço introdutório de caracterização dos jogos cooperativos, especialmente do conceito de solução do valor de Shapley. Foram descritas as principais propriedades dessa solução, além de se apresentar exemplos que possibilitaram uma comparação direta entre as duas abordagens da teoria dos jogos, visto que podem ser solucionados tanto cooperativamente quanto não cooperativamente. Ademais, com o intuito de aprofundar a compreensão sobre o valor de Shapley, foram apresentadas algumas importantes aplicações em problemas práticos.

Na comparação direta entre as duas abordagens dos jogos, viu-se que a falta de incentivo para manter um acordo, ou, a tentação em burlar, faz com que o resultado na teoria dos jogos não cooperativos não seja o melhor para os jogadores. Já em um jogo cooperativo, com a possibilidade dos jogadores negociarem e manterem um acordo pode-se alcançar um resultado mais eficiente, ou seja, melhoram-se as perspectivas dos jogadores envolvidos em algum processo de barganha.

Isso pode de alguma forma ser trazido para a realidade, indicando que em circunstâncias onde há problemas econômicos ou disputas políticas para serem resolvidas por um conjunto de agentes, ainda que estes tenham interesses opostos, espera-se que a solução em que eles se encontram para estabelecer um acordo – desde que esteja em conformidade com a lei – forneça resultados melhores para todos os agentes envolvidos em comparação a um cenário em que eles tomariam decisões individualmente.

Em relação aos exemplos e aplicações que foram vistos, nos jogos do dilema dos prisioneiros, da divisão do dólar e da alocação de custos estão claros os ganhos oriundos da cooperação mostrando que os acordos são compensatórios. Já o jogo de votação tem características diferentes, o que não deixa de ser interessante, pois, mostra a versatilidade do valor de Shapley.

Apesar de bastante difundido em publicações internacionais, ainda existem poucas obras no Brasil que tratam dos jogos cooperativos e seus conceitos de solução. Ao mostrar a praticidade e os aspectos introdutórios do valor de Shapley espera-se que este trabalho possa servir de ponto de partida para futuras aplicações e maiores aprofundamentos, em que se pode analisar jogos mais complexos e abandonar algumas hipóteses simplificadoras que foram assumidas.

Dentre as possibilidades de estudos futuros, acredita-se que o valor de Shapley possa continuar sendo uma boa ferramenta a ser aplicada na política, analisando a força de possíveis coalizões partidárias em parlamentos e os movimentos estratégicos que podem decidir determinada votação. Outro bom campo de aplicação são as decisões relacionadas à alocação de custos de infraestrutura que envolvam diferentes agentes (países, estados, municípios e até indivíduos) e que precisam coordenar suas ações para dividir custos, como a construção de ferrovias, rodovias (incluindo a determinação de tarifas de pedágio aos diferentes usuários), pontes, hidrelétricas etc.

Mais especificamente, pode-se destacar os problemas econômicos relacionados a questões do meio ambiente como um campo fértil de aplicação para o valor de Shapley. A existência de múltiplos agentes envolvidos nos problemas ambientais e a necessidade que eles negociem e coordenem suas ações, por vias próprias ou por determinação de uma autoridade, pode abrir espaço para que sejam analisados por meio da teoria dos jogos cooperativos. Isso inclui, por exemplo, a construção de estações de tratamento de esgoto, alocação de custos de despoluição de recursos hídricos (na maioria das vezes partilhados por diferentes países ou municípios), construção de estações de tratamento de resíduos sólidos, entre outros.

ANEXO A – Cálculos do jogo de alocação de custos

ANEXO A
Cálculos do jogo de alocação de custos

elaborado pelo autor.

ANEXO B

ANEXO B
Cálculos do jogo de votação

elaborado pelo autor.

Referências

ALIPRANTIS, C. D.; CHAKRABARTI, S. K. Games and decision making . New York: Oxford University Press, 2000.

AUMANN, R. J. Linearity of unrestrictedly transferable utilities. Naval Research Logistics Quarterly , v. 7, n. 3, p. 281-284, 1960.

AUMANN, R. J.; PELEG, B. Von Neumann-Morgenstern solutions to cooperative games without side payments. Bulletin of the American Mathematical Society , v. 66, n. 3, p. 173-179, 1960.

DIXIT, A.; NALEBUFF, B. Thinking Strategically: The Competitive Edge in Business, Politics, and Everyday Life. New York: W. W. Norton & Company, 1991.

DIXIT, A.; SKEATH, S.; REILEY JR., D. Games of Strategy. New York: W. W. Norton & Company, 2004.

FRAGNELLI, V.; GARCÍA-JURADO, I.; NORDE, H.; PATRONE, F.; TIJS, S. How to share railways infrastructure costs? In: GARCÍA-JURADO, I.; NORDE, H.; PATRONE, F.; TIJS, S. Game practice: contributions from applied game theory. Dordrecht: Kluwer Academic, 2000.

GIBBONS, R. Game theory for applied economists . Princeton: Princeton University Press, 1992.

HART, S. Shapley value. In: EATWELL, J.; MILGRATE, M.; NEWMAN, P. The New Palgrave: Game Theory . New York: W W Norton, 1989.

LITTLECHILD, S. C.; OWEN, G. A simple expression for the Shapley value in a special case. Management Science , v. 20, n. 3, p. 370-372, 1973.

LOEHMAN, E.; ORLANDO, J.; TSCHIRHART, J.; WHINSTON, A. Cost allocation for a regional wastewater treatment system. Water Resources Research , v. 15, n. 2, p. 193-202, 1979.

MAS-COLELL, A.; WHINSTON, M.; GREEN, J. Microeconomic Theory .New York: Oxford University Press, 1995.

MCMILLAN, J. Games, Strategies and Managers: How Managers Can Use Game Theory to Make Better Business Decisions. New York: Oxford University Press, 1992.

MONTET, C.; SERRA, D. Game theory and economics . New York: Palgrave Macmillan, 2003.

MYERSON, R. B. Game theory: an analysis of conflict. Cambridge: Harvard University Press, 1991.

OSBORNE, M. J.; RUBINSTEIN, A. A course in game theory . Cambridge: MIT Press, 1994.

PELEG, B.; SUDHÖLTER, P. Introduction to the theory of cooperative games . New York: Springer Science & Business Media, 2007.

ROTH, A. The Shapley value: essays in honor of Lloyd S. Shapley . Cambridge: Cambridge University Press, 1988.

SERRANO, R. Lloyd Shapley’s matching and game theory. Scandinavian Journal of Economics , v. 115, n. 3, p. 599-618, 2013.

SHAPLEY, L. S. A value for n-person games. Contributions to the Theory of Games , v. 2, n. 28, p. 307-317, 1953.

SHAPLEY, L. S. Cores of convex games. International journal of game theory , v. 1, n. 1, p. 11-26, 1971.

SHAPLEY, L. S.; SHUBIK, M. A method for evaluating the distribution of power in a committee system. American Political Science Review , v. 48, n. 3, p. 787-792, 1954.

STRAFFIN JR., P. D. The Shapley-Shubik and Banzhaf power indices as probabilities. In: ROTH, A. The Shapley value: Essays in honor of Lloyd S. Shapley. Cambridge: Cambridge University Press, 1988.

VARIAN, H. R. Microeconomia: Princípios básicos. Rio de Janeiro: Editora Campus, 2003.

WIDGRÉN, M. Voting power in the EC decision making and the consequences of two different enlargements. European Economic Review , v. 38, n. 5, p. 1153-1170, 1994.

YOUNG, H. P. Cost allocation. In: AUMANS, R. J.; HART, S. Handbook of game theory with economic applications. v. 2. New York: Elsevier Science, 1994.

YOUNG, H. P.; OKADA, N.; HASHIMOTO, T. Cost allocation in water resources development. Water Resources Research , v. 18, n. 3, p. 463-475, 1982.