Tempo de Convergência para o Equilı́brio de Nash
nos Jogos Empacotamento de Itens e
Balanceamento de Carga
André L. Vignatti
orientador: Flávio K. Miyazawa
Instituto de Computação
Universidade Estadual de Campinas
Mar 2010
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
Visão Geral
1 Motivação
2 Empacotamento Egoı́sta Sequencial
3 Empacotamento Egoı́sta Simultâneo
4 Balanceamento de Carga Assı́ncrono
5 Conclusão
IC-UNICAMP – Mar 2010 – – A. Vignatti
2/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
Sumário
1 Motivação
2 Empacotamento Egoı́sta Sequencial
3 Empacotamento Egoı́sta Simultâneo
4 Balanceamento de Carga Assı́ncrono
5 Conclusão
IC-UNICAMP – Mar 2010 – – A. Vignatti
3/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
Exemplo: Como ir para CURITIBA de ônibus
Suponha que:
• Vários grupos vão a Curitiba com ônibus alugado.
• Pessoas do mesmo grupo vão juntas no mesmo ônibus
• Até uma data limite, um grupo pode mudar para outro
ônibus, se houver espaço suficiente
• O preço do ônibus é dividido igualmente entre seus passageiros
• Há uma configuração inicial
IC-UNICAMP – Mar 2010 – – A. Vignatti
4/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
IC-UNICAMP – Mar 2010 – – A. Vignatti
5/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
IC-UNICAMP – Mar 2010 – – A. Vignatti
6/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
IC-UNICAMP – Mar 2010 – – A. Vignatti
7/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
Principais motivações vêm da Internet
• Internet: recursos compartilhados por vários usuários
• Usuários: podem cooperar a/ou competir pelos recursos
• Usuários tem um comportamento egoı́sta
Exemplo
• Escalonamento de pacotes em slots para transmissão
• Escalonamento de Tarefas em sistemas distribuı́dos
• Alocação de banda
A
B
C
D
• Empacotar dados em pacotes ATM para ligações de telefone
pela Internet
IC-UNICAMP – Mar 2010 – – A. Vignatti
8/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
Sumário
1 Motivação
2 Empacotamento Egoı́sta Sequencial
3 Empacotamento Egoı́sta Simultâneo
4 Balanceamento de Carga Assı́ncrono
5 Conclusão
IC-UNICAMP – Mar 2010 – – A. Vignatti
9/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
Problema:
• m recipientes com capacidade C e mesmo custo
• n itens nos recipientes
• cada item i tem peso wi e é controlado por um jogador egoı́sta
• Hj é o peso total dos itens no recipiente j, onde Hj ≤ C
Estratégia: Como um jogador escolhe um recipiente:
wi
• O preço que o jogador i paga por usar o recipiente j é H
j
• Há incentivo para i migrar de j para j 0 se
wi
wi
<
H j 0 + wi
Hj
que é equivalente a
Hj 0 + wi > Hj
IC-UNICAMP – Mar 2010 – – A. Vignatti
10/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
Objetivos:
• do sistema: minimizar o número de recipientes usados
• do jogador: permanecer em um recipiente onde não há
incentivo de migrar
equilı́brio de Nash: Configuração onde nenhum item tem
incentivo de migrar
• Pode existir várias configurações em equilı́brio de Nash
IC-UNICAMP – Mar 2010 – – A. Vignatti
11/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
Questões Interessantes:
• O jogo converge para o equilı́brio de Nash?
• Se SIM: Qual o número de passos até alcançar o equilı́brio de
Nash?
• E sobre a solução dos jogadores X solução ótima?
IC-UNICAMP – Mar 2010 – – A. Vignatti
12/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
Convergência para o Equilı́brio de Nash
Considere os recipientes ordenados pela carga em ordem
não-crescente
IC-UNICAMP – Mar 2010 – – A. Vignatti
13/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
Convergência para o Equilı́brio de Nash
Nova configuração ordenada é sempre lexicograficamente maior
IC-UNICAMP – Mar 2010 – – A. Vignatti
14/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
Número de passos até o equilı́brio de Nash
Theorem: (Bilò’06) Com pesos inteiros, o equilı́brio de Nash é
2
alcançado em no máximo n2 wmax
passos, onde wmax é o peso do
item mais pesado.
• Pergunta do Bilò’: “Esse resultado é justo (apertado)?”
IC-UNICAMP – Mar 2010 – – A. Vignatti
15/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
Jogo de Balanceamento de Carga
Os itens vão para máquinas mais leves
IC-UNICAMP – Mar 2010 – – A. Vignatti
16/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
Jogo de Balanceamento de Carga
Obs: o movimento inverso é uma migração válida no
empacotamento
IC-UNICAMP – Mar 2010 – – A. Vignatti
17/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
Balanceamento de Carga X Empacotamentode Itens
Def.: A melhor-resposta é a melhor estratégia para um jogador
num determinado estado do jogo.
Theorem: Se os jogadores usam a melhor-resposta para fazer a
migração, então existe uma instância
do jogo balanceamento de
√
n
carga que precisa pelo menos 2 passos para alcançar o equilı́brio
de Nash.
Corolary: Existe uma instância
do jogo empacotamente de itens
√
n
que precisa pelo menos 2 passos para alcançar o equilı́brio de
Nash.
• E se considerarmos a melhor-resposta no jogo de
empacotamento de itens?
IC-UNICAMP – Mar 2010 – – A. Vignatti
18/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
Tempo de convergência com melhor-resposta e
capacidade infinita
Theorem: Usando a estratégia de melhor-resposta, existe uma
instância do jogo de empacotamento de itens que precisa de Ω(n2 )
passos para alcançar o equilı́brio de Nash.
Theorem: Usando a estratégia de melhor-resposta, com pesos
inteiros e recipientes com capacidade infinita, o equilı́brio de Nash
é alcançado em O(n2 ) passos.
IC-UNICAMP – Mar 2010 – – A. Vignatti
19/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
Número de passos para alcançar o equilı́brio de Nash
Theorem: Usando a estratégia de melhor-resposta, com pesos
inteiros, o equilı́brio de Nash é alcançado em
2
O(min{mwmax
+ nwmax , n2 wmax }) passos, onde wmax é o peso do
item mais pesado.
IC-UNICAMP – Mar 2010 – – A. Vignatti
20/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
Sumário
1 Motivação
2 Empacotamento Egoı́sta Sequencial
3 Empacotamento Egoı́sta Simultâneo
4 Balanceamento de Carga Assı́ncrono
5 Conclusão
IC-UNICAMP – Mar 2010 – – A. Vignatti
21/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
Introdução
Definição: Jogo Empacotamento Simultâneo
• m recipientes b1 , . . . , bm com custos e capacidades iguais.
• n itens com tamanho 1.
• Não há controle central.
• Cada item é controlado por um jogador egoı́sta.
• nt (b): # itens atribuı́dos ao recipiente b no tempo t.
Estrategias e Preferências
Quais são as preferências sobre as estratégias?
• Jogador i paga 1/nt (b) ao usar o recipiente b.
• Como o jogador é egoı́sta, ele quer migrar para um recipiente b0 se
1
1
<
.
nt (b 0 ) + 1
nt (b)
• Ou seja, ele migra de b para b0 se nt (b0 ) + 1 > nt (b).
IC-UNICAMP – Mar 2010 – – A. Vignatti
22/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
Introdução
Definição: Jogo Empacotamento Simultâneo
• m recipientes b1 , . . . , bm com custos e capacidades iguais.
• n itens com tamanho 1.
• Não há controle central.
• Cada item é controlado por um jogador egoı́sta.
• nt (b): # itens atribuı́dos ao recipiente b no tempo t.
Estrategias e Preferências
Quais são as preferências sobre as estratégias?
• Jogador i paga 1/nt (b) ao usar o recipiente b.
• Como o jogador é egoı́sta, ele quer migrar para um recipiente b0 se
1
1
<
.
nt (b 0 ) + 1
nt (b)
• Ou seja, ele migra de b para b0 se nt (b0 ) + 1 > nt (b).
IC-UNICAMP – Mar 2010 – – A. Vignatti
22/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
Ambiente Distribuı́do
Ambiente Distribuı́do
• Analisamos o caso de ambiente distribuı́do.
• Todos os itens decidem ao mesmo tempo!
• Nenhuma informação é trocada entre os jogadores.
• Contrasta com o Elementary Step System (ESS)
Vantagens
• Mais próximo de situações práticas.
• A implementação do ESS pode ser muito cara.
• ESS tem tempo de convergência limitado por Ω(n).
IC-UNICAMP – Mar 2010 – – A. Vignatti
23/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
Ambiente Distribuı́do
Ambiente Distribuı́do
• Analisamos o caso de ambiente distribuı́do.
• Todos os itens decidem ao mesmo tempo!
• Nenhuma informação é trocada entre os jogadores.
• Contrasta com o Elementary Step System (ESS)
Vantagens
• Mais próximo de situações práticas.
• A implementação do ESS pode ser muito cara.
• ESS tem tempo de convergência limitado por Ω(n).
IC-UNICAMP – Mar 2010 – – A. Vignatti
23/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
Equilı́brio de Nash
Conceito de Solução
O conceito de solução considerada é o equilı́brio de Nash.
Os jogadores conseguem alcançar o equilı́brio de Nash?
• Não, se eles não seguirem regras.
• Assim, os jogadores precisam seguir protocolos.
IC-UNICAMP – Mar 2010 – – A. Vignatti
24/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
Equilı́brio de Nash
Conceito de Solução
O conceito de solução considerada é o equilı́brio de Nash.
Os jogadores conseguem alcançar o equilı́brio de Nash?
• Não, se eles não seguirem regras.
• Assim, os jogadores precisam seguir protocolos.
IC-UNICAMP – Mar 2010 – – A. Vignatti
24/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
Protocolos & Tempo de Convergência
Protocolos
• Protocolos deterministicos não são justos.
• Protocolos devem ser suficientemente simples para os
jogadores “aderirem” a eles.
A Pergunta Principal: Tempo de Convergência
• Suponha que nós definimos um protocolo que alcança o
equilı́brio de Nash.
• Qual é o tempo necessário para alcançar o equilı́brio?
IC-UNICAMP – Mar 2010 – – A. Vignatti
25/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
As ações de “Desfazer”
• Como os itens podem migrar simultaneamente, passos
inviáveis pode ocorrer.
Duas abordagens foram propostas:
1 Pode-se desfazer um passo inviável;
2
Passos inviáveis não são permitidos.
IC-UNICAMP – Mar 2010 – – A. Vignatti
26/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
Exemplo
begin
t=1
while Dt (b1 ) > 0 do
forall {j ∈ b2 } in parallel do
move j to b1 with probability
Dt ( b1)
Dt (b1 )
nt (b2 )
t =t +1
end
n t (b2)
b1
b2
IC-UNICAMP – Mar 2010 – – A. Vignatti
27/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
Resultados
Teorema (2 recipientes - movimentos inviáveis podem ser desfeitos)
Usando o protocolo proposto, um equilı́brio de Nash é alcançado
em O(log log n) passos, com alta probabilidade.
Teorema (vários recipientes - movimentos inviáveis podem ser
desfeitos)
Usando o protocolo proposto, um equilı́brio de Nash é alcançado
em O(log n) passos, com alta probabilidade.
Teorema (vários recipientes - SEM desfazer movimentos inviáveis)
Usando o protocolo proposto, um equilı́brio de Nash é alcançado
em O(nm) passos, com alta probabilidade.
IC-UNICAMP – Mar 2010 – – A. Vignatti
28/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
Resultados - Menos Informação
• A suposição que os itens sabem quais recipientes ficarão
cheios requer saber a carga de todos os recipientes.
• Também projetamos protocolos para o caso de menos
informação global.
• I.e., um item sabe a carga do seu próprio recipiente e pode
somente inspecionar a carga de um recipiente adicional.
IC-UNICAMP – Mar 2010 – – A. Vignatti
29/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
Resultados - Menos Informação
Teorema (vários recipientes - menos informação)
Se é permitido desfazer movimentos, então o protocolo proposto
alcança o equilı́brio de Nash em O(m log n) passos, com alta
probabilidade.
Teorema (vários recipientes - menos informação)
Se não é permitido desfazer movimentos, então o protocolo
proposto alcança o equilı́brio de Nash em O(n3 m) passos, com alta
probabilidade.
IC-UNICAMP – Mar 2010 – – A. Vignatti
30/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
Sumário
1 Motivação
2 Empacotamento Egoı́sta Sequencial
3 Empacotamento Egoı́sta Simultâneo
4 Balanceamento de Carga Assı́ncrono
5 Conclusão
IC-UNICAMP – Mar 2010 – – A. Vignatti
31/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
Introdução
Definição: Jogo Balanceamento Assı́ncrono
• Grafo G = (V , E ).
• Nodo i ∈ V tem peso wi e velocidade si (sistema heterogêneo).
• A carga do nodo i é dada por `i = wi /si .
• O peso pode ser dividido em partes de tamanho infinitesimal.
• Um nodo pode enviar uma quantidade arbitrária de peso aos seus
vizinhos.
• Um nodo sabe somente a informação de carga dos seus vizinhos.
• Cada nodo é controlado por um jogador egoı́sta.
IC-UNICAMP – Mar 2010 – – A. Vignatti
32/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
Definições
Regra Fundamental
Dizemos que um jogador i está ε-satisfeito se
`i ≤ (1 + ε)3 `j , ∀j ∈ N(i),
onde N(i) é a vizinhança de i.
ε-equilı́brio de Nash
A rede está em ε-equilı́brio de Nash se todos jogadores estão
ε-satisfeitos.
IC-UNICAMP – Mar 2010 – – A. Vignatti
33/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
Assincronia nas Decisões
• Nos jogos de empacotamento, consideramos os modelos ESS
e com ações simultâneas.
• Ou seja, implicitamente consideramos a existência de um
relógio global no sistema (sistema sı́ncrono).
• No jogo de balanceamento, iremos desconsiderar a existência
de relógio global (sistema assı́ncrono).
• Assim, o modelo considerado é muito mais próximo de
situações reais.
IC-UNICAMP – Mar 2010 – – A. Vignatti
34/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
Regras
Se não houverem regras, os jogadores não alcançam o equilı́brio!
Na criação de regras, algumas perguntas importantes:
• Para quem enviar a carga?
• Quanto enviar de carga?
• Como enviar a carga?
As regras são aplicadas localmente em cada nodo.
IC-UNICAMP – Mar 2010 – – A. Vignatti
35/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
Algoritmo Equalitário
O primeiro dos três algoritmos (conjunto de regras) é chamado de
Algoritmo Equalitário.
• Envia carga para os vizinhos que o tornam insatisfeito.
• Envia o excesso de carga com relação à média (de todos os
vizinhos).
• Divide o excesso a ser enviado igualmente entre os vizinhos
selecionados.
IC-UNICAMP – Mar 2010 – – A. Vignatti
36/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
Algoritmo Equalitário
Teorema (Convergência)
Em redes assı́ncronas e heterogêneas, se cada jogador usar as
regras definida pelo Algoritmo Equalitário, então o sistema alcança
o equilı́brio de Nash.
IC-UNICAMP – Mar 2010 – – A. Vignatti
37/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
Algoritmo do Passo Limitado
A idéia deste algoritmo é evitar as altas flutuações de carga.
• Para isso, devemos limitar a quantidade de carga que um
nodo pode enviar/receber.
• Isso é feito usando duas regras: Inércia e Passo Limitado.
Regra da Inércia
Um nodo i só pode enviar carga para um nodo j se `i > (1 + ε)3 `j .
Regra do Passo Limitado
Seja `ti a carga do nodo i no instante t. Então
• `ti /(1 + ε) ≤ `t+1
≤ (1 + ε)`ti .
i
• `ti ≥ η, onde η é um número pequeno.
IC-UNICAMP – Mar 2010 – – A. Vignatti
38/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
Algoritmo do Passo Limitado
Teorema
Se os envios de carga são não-nulos e satisfazem as regras de
Inércia e Passo Limitado, então o sistema converge para um
ε-equilı́brio de Nash.
• Devemos construir regras nos nodos para que respeitem as
regras de Inércia e Passo Limitado.
IC-UNICAMP – Mar 2010 – – A. Vignatti
39/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
Algoritmo de Passo Limitado
As regras de Inércia e Passo Limitado são garantidas por três
algoritmos:
• SEND: sinaliza o envio de uma quantidade de carga
• RECEIVE: autoriza o envio de uma certa quantidade de carga
• LISTENER: envia de fato a carga autorizada
IC-UNICAMP – Mar 2010 – – A. Vignatti
40/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
Algoritmo de Passo Limitado
Lema
O Algoritmo SEND respeita as regras de Inércia e Passo Limitado.
Lema
O Algoritmo RECEIVE respeita as regras de Inércia e Passo
Limitado.
Lema
O Algoritmo LISTENER respeita as regras de Inércia e Passo
Limitado.
Teorema
Em redes assı́ncronas e heterogênas, se usarmos o protocolo
definido pelos Algoritmos SEND, RECEIVE e LISTENER, então o
sistema alcança um ε-equilı́brio de Nash.
IC-UNICAMP – Mar 2010 – – A. Vignatti
41/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
Algoritmo Agressivo
• Algoritmo que não se preocupa com altas flutuações.
• Não usa muita informação da vizinhança.
• Dá prioridade a nodos com baixa carga, e ao mesmo tempo
faz o balanceamento de carga dos vizinhos.
• COMO?
IC-UNICAMP – Mar 2010 – – A. Vignatti
42/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
Algoritmo Agressivo - Técnica de Encher com Água
100
80
60
60
50
50
40
40
20
20
20
10 10
10 10
(a)
(b)
20
0
20
60
60
50
60
60
50
40
40
20
20
20
20
10 10
(c)
IC-UNICAMP – Mar 2010 – – A. Vignatti
10 10
(d)
43/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
Algoritmo Agressivo
begin
Let S = {j ∈
N(i) : (1 + ε)3 `j < `i }
P
Let x =
pi + j∈S pj
P
si + j∈S sj
Let ∆ = (`i − x)si
water-fill(∆, S)
end
Algorithm 1: Algorithm for player i
IC-UNICAMP – Mar 2010 – – A. Vignatti
44/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
Algoritmo Agressivo
Teorema
Em redes assı́ncronas e heterogênas, se usarmos o Algoritmo
Agressivo, então o sistema alcança um ε-equilı́brio de Nash.
IC-UNICAMP – Mar 2010 – – A. Vignatti
45/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
9000
8000
7000
6000
5000
4000
3000
2000
1000
0
num. of steps to Nash eq.
num. of steps to Nash eq.
Resultados das Simulações
aggressive
egalitarian
0
10 20 30 40 50 60 70 80 90 100
200
175
150
125
100
75
50
25
0
aggressive
egalitarian
4 8 16
num. of nodes
64
128
num. of nodes
(a) scale-free
num. of steps to Nash eq.
32
(b) hypercube
36000
32000
28000
24000
20000
16000
12000
8000
4000
0
aggressive
egalitarian
0
10 20 30 40 50 60 70 80 90 100
num. of nodes
(c) path
IC-UNICAMP – Mar 2010 – – A. Vignatti
46/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
180000
160000
140000
120000
100000
80000
60000
40000
20000
0
bounded step
0
10 20 30 40 50 60 70 80 90 100
num. of nodes
(d) scale-free
IC-UNICAMP – Mar 2010 – – A. Vignatti
num. of steps to Nash eq.
num. of steps to Nash eq.
Resultados das Simulações
25000
22500
20000
17500
15000
12500
10000
7500
5000
2500
0
bounded step
48 16
32
64
128
num. of nodes
(e) hypercube
47/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
Sumário
1 Motivação
2 Empacotamento Egoı́sta Sequencial
3 Empacotamento Egoı́sta Simultâneo
4 Balanceamento de Carga Assı́ncrono
5 Conclusão
IC-UNICAMP – Mar 2010 – – A. Vignatti
48/50
Motivação Empacotamento Egoı́sta Sequencial Empacotamento Egoı́sta Simultâneo Balanceamento de Carga Assı́ncrono Conc
Conclusão
• Apresentamos resultados sobre o tempo de convergência para
o equilı́brio de Nash.
• Consideremos dois problemas: empacotamento de itens e
balanceamento de carga.
• Consideramos 3 formas distintas de sincronia: passo-a-passo,
paralelo, assı́ncrono.
• Futuras direções da pesquisa: variantes, generalizações e casos
particulares de cada um dos problemas.
Grande pergunta em aberto
Dada a motivação prática dos problemas, como aplicar nossos
resultados no mundo real?
IC-UNICAMP – Mar 2010 – – A. Vignatti
49/50
Obrigado!
[email protected]
André Luı́s Vignatti
[email protected]
Flávio Keidi Miyazawa