Teoria dos jogos Algorítmica e Otimização Combinatóriaatol/mac499/ic/teoria_dos_jogos/... · 2010-03-11 · Teoria dos jogos Algorítmica e Otimização Combinatória Atol Fortin

Teoria dos jogos Algorítmica eOtimização Combinatória

Atol Fortin de OliveiraOrientadora: Cristina Gomes Fernandes

Instituto de Matemática e EstatísticaUniversidade de São Paulo

Trabalho de Conclusão de Curso - 2009

Atol Fortin de Oliveira Teoria dos jogos Algorítmica e Otimização Combinatória

Problemas estudados

Casamentos estáveisLeilões para publicidade associada à buscaAlocação de bens indivisívei*Leilões combinatórios *


Casamentos estáveisLeilões para publicidade associada à busca

ProblemaDefiniçõesAlgoritmo para encontrar uma solução estávelPropriedades

Conteúdo

1 Casamentos estáveisProblemaDefiniçõesAlgoritmo para encontrar uma solução estávelPropriedades

2 Leilões para publicidade associada à buscaProblemaDefiniçõesIdeia do algoritmo




Casamentos estáveis

Dados um conjunto H de homens e um conjunto de Mmulheres de tamanho n.Dada uma ordem de preferência de cada pessoa parapessoas do outro grupo.Queremos encontrar um casamento estável entre H e M.




Conteúdo






Ordem de preferência

Notação : h1 �m h2

Então, para toda mulher m de M temos sua ordem depreferência sobre os homens de H:h1 �m h2 �m h3 �m · · · �m hi �m · · · �m hn.




Estabilidade - Par bloqueador

Um grupo de casamentos é estável se não existe um parbloqueador.Um par (h1, m2) é bloqueador em uma determinadaalocação se existem dois casais (h1, m1) e (h2, m2) tal que:m2 �h1 m1 e h1 �m2 h2




Exemplo de um grupo de casamentos

Considerando as seguintes ordens de preferência

h1: m2 �h1 m1 �h1 m3h2: m1 �h2 m3 �h2 m2h3: m1 �h3 m2 �h3 m3m1: h1 �m1 h3 �m1 h2m2: h3 �m2 h1 �m2 h2m3: h1 �m3 h3 �m3 h2

O grupo de casamentos (h1, m1), (h2, m2), (h3, m3) não éestável.Temos o par bloqueador (h1, m2).




Conteúdo






Algoritmo

Vamos ver apenas uma ideia do algoritmo da PropostaMasculina.

Algum homem solteiro faz uma prosposta à mulher demaior preferência que ainda não o rejeitou.A mulher que recebe a prosposta decide se preferecontinuar com seu atual marido, ou se aceita a novaproposta.O algoritmo termina quando não existem mais homenssolteiros.




Simulando para o exemplo


Começamos com a alocação vazia (h1, ∗), (h2, ∗), (h3, ∗).






O homem h1 faz proposta à mulher m2 que o aceita. Temos aalocação (h1, m2), (h2, ∗), (h3, ∗).






O homem h2 faz proposta à mulher m1 que o aceita. Temos aalocação (h1, m2), (h2, m1), (h3, ∗).






O homem h3 faz proposta à mulher m1 que o aceita, rejeitandoo homem h2. Temos a alocação (h1, m2), (h2, ∗), (h3, m1).






O homem h2 faz proposta à mulher m3 que o aceita. Temos aalocação (h1, m2), (h2, m3), (h3, m1), chegando ao fim doalgoritmo.




Conteúdo






Propriedades

O algoritmo encontra uma solução em tempo O(n2).A solução encontrada é um grupo de casametos estável.O algoritmo encontra um grupo de casamentos ótimopara os homens.O algoritmo é à prova de estratégia para os homens.




Ótimo masculino

O algoritmo encontra um grupo de casamentos X ótimopara os homens.Ou seja, não existe um grupo de casamentos Y estável talque Y (h) �h X (h), para todo h ∈ H.




Prova de estratégia

E também, o algoritmo é à prova de estratégia para oshomens.Ou seja, nenhum homem pode se beneficiar ao declararum ordem de preferência que não seja sua realpreferência.



ProblemaDefiniçõesIdeia do algoritmo

Conteúdo






Leilões para publicidade associada à busca

Problema do google.




Leilões para publicidade associada à busca

Dado um conjunto I de compradores de tamanho n.Dado um conjunto J de itens de tamanho k .Dados preços mínimos ri,j .Dados valores ideais vi,j .Dados preços máximos mi,j .Queremos encontrar uma alocação ótima de itens aoscompradores.




Conteúdo






Alocação ótima

Uma alocação é ótima se não existe nenhuma outraalocação que deixe todos os compradores mais felizes.(sem piorar a satisfação de nenhum deles)




Conteúdo






Ideia do algoritmo

O algoritmo consiste em encontrar caminhos alternantesde peso mínimo em um grafo bipartido definido peloscompradores e pelos itens.O algoritmo é polinomial em n e k .O algoritmo encontra uma solução ótima.O algoritmo é à prova de estratégia.


Conclusão

Finalizando

Os algoritmos foram implementados e as propriedadesgarantidas por eles foram testadas e confirmadas, dentrodo possível.Ainda falta concluir algumas provas.Podemos estudar as variantes e extensões de cadaproblema.


Documents

Teoria dos jogos Algorítmica e Otimização Combinatóriaatol/mac499/ic/teoria_dos_jogos/... · 2010-03-11 · Teoria dos jogos Algorítmica e Otimização Combinatória Atol Fortin