Computando o Equilı́brio de Nash para estratégias de
agregação na recomendação de itens para grupos de usuários
Lucas Augusto M. C. Carvalho, Hendrik T. Macedo
1
Programa de Pós-Graduação em Ciência da Computação
Universidade Federal de Sergipe, Brasil
[email protected], [email protected]
Abstract. Most work in progress regarding Group Recommenders seems to focus on how to combine the individual models of group members rather than
providing a model to the group itself. A major difficulty in such approach is how
to define an aggregation strategy of individual preferences to ensure, among
other things, maximizing group overall satisfaction. In this paper we propose a
non-cooperative game theory approach to group recommender systems. While
group members may be seen as game competitors, the different aggregation strategies proposed so far represent the set of possible actions. Satisfying the whole
group becomes thus a problem of finding Nash equilibria. Experiments using
MovieLens dataset and a satisfaction utility function have shown good results if
compared to such obtained from state-of-the-art’s approaches, specially to those
concerned with heterogeneous groups.
Resumo. A maior parte das pesquisas sobre recomendação para grupos se concentra no estudo sobre métodos de combinação de modelos individuais de seus
membros em detrimento da definição de um modelo para o grupo em si. A maior
dificuldade de tal abordagem é como definir uma estratégia de agregação individual que assegure, entre outras coisas, a maximização da satisfação média
do grupo. Neste artigo é proposta uma abordagem baseada na teoria dos jogos não-cooperativos para sistemas de recomendação para grupos. Enquanto
membros do grupo podem ser vistos como competidores em um jogo, as diferentes estratégias de agregação podem fornecer o conjunto de possı́veis ações.
Satisfazer o grupo como um todo torna-se então um problema de encontrar o
equilı́brio de Nash. Experimentos com a base de dados do MovieLens e uma
função de média aritmética para cálculo da previsão de satisfação do grupo
com a recomendação, apresentou resultados satisfatórios comparado ao das estratégias de agregação do estado-da-arte, especialmente quando as avaliações
entre os membros do grupo são mais heterogêneas.
1. Introdução
Sistemas de recomendação tradicionais realizam sugestões personalizadas de itens
ainda não avaliados pelo usuário e que são de potencial interesse para o mesmo
[Adomavicius e Tuzhilin 2005]. Baseado no histórico de itens previamente avaliados por
um usuário, um sistema de recomendação constrói um perfil representativo dos interesses
deste. A similaridade deste perfil com o de outros usuários do sistema (filtragem colaborativa) ou com outros itens da base (filtragem baseada em conteúdo) é então utilizada para
recomendação de itens inéditos para o usuário em questão [Burke 2002].
Em cenários onde grupos de pessoas compartilham o mesmo local ou interesse,
recomendação individual não é a mais adequada. A recomendação de um restaurante
para um almoço de negócios, a recomendação de um destino de viagem para uma turma
de amigos ou ainda a recomendação de um filme para a famı́lia são exemplos de cenários
onde a recomendação para grupo é mais apropriada. A recomendação para grupo considera as preferências dos membros de um grupo para realizar a recomendação. Entre
as dificuldades que se apresentam está o fato de que membros do grupo podem possuir
preferências diferentes ou até mesmo conflitantes. Para solução deste problema, a abordagem que tem recebido mais atenção na literatura cientı́fica é a agregação de preferências
individuais [Masthoff 2004, Jameson e Smyth 2007].
Para escolha de uma estratégia de agregação de preferência individual, faz-se necessário considerar as caracterı́sticas do grupo e da aplicação em questão. A maioria
dos sistemas de recomendação para grupo utiliza apenas um método de agregação de
preferência individual. Entretanto, uma estratégia mal escolhida, que não se adeque às
caracterı́sticas dos grupos que utilizam a aplicação, pode causar baixa satisfação dos itens
recomendados para os membros do grupo.
Uma das possı́veis soluções para minimizar o problema da escolha da estratégia
de agregação é o sistema possibilitar a seleção de métodos de agregação de preferência
para cada decisão [Jameson 2004]. O sistema poderia permitir que usuários decidam qual
mecanismo de agregação deve ser utilizado, tanto antes de uma recomendação ser feita
ou durante um processo iterativo de requisição de recomendações e ajustes da função
de agregação. A criação de métodos de seleção de estratégias de acordo com as caracterı́sticas do grupo vem sendo estudada na literatura [Senot et al. 2010]. Resultados
dos estudos mostram que membros de um grupo não são alheios as estratégias adotadas. De fato, eles procuram um equilı́brio entre a escolha mais justa para o grupo
e a sua preferência particular, apesar de não possuı́rem uma estratégia clara para isso
[Masthoff 2004].
[Senot et al. 2010] compara diferentes estratégias de agregação com o objetivo de
criar um framework de seleção automática da estratégia de agregação que mais se adeque
às caracterı́sticas do grupo [Senot et al. 2010]. Para isso, perfis de agregação são gerados
a partir das estratégias de agregação e comparados, a partir do cálculo de similaridade,
com um perfil de referência. O objetivo é definir qual estratégia de agregação mais se
aproxima desse perfil de referência com base nas diferentes caracterı́sticas dos grupos. O
trabalho, entretanto, não propõe qualquer nova estratégia de agregação.
[Bekkerman et al. 2006] aplica uma metodologia de negociação cooperativa para
a solução do problema de recomendação para grupo. Cada usuário é representado por um
agente negociador, todos com o mesmo comportamento. Uma vez que as recomendações
individuais são obtidas, o processo de negociação se inicia.
Este artigo propõe uma abordagem baseada em um jogo não-cooperativo de
informações imperfeitas para recomendação para grupos. Esta abordagem modela os
itens retornados pelas estratégias de agregação como ações do jogo e a recomendação
como um problema de encontrar o equilı́brio de Nash. Ao contrário do trabalho de
[Bekkerman et al. 2006], onde dentro de uma negociação o agente pode aceitar ou recusar uma oferta, em nossa abordagem o cálculo do equilı́brio de Nash seleciona de forma
racional o conjunto de itens.
Para validar a abordagem, experimentos com a base do MoviesLens1 foram realizados. Estes experimentos compararam a satisfação de grupos homogêneos e heterogêneos de diferentes tamanhos com a recomendação utilizando o equilı́brio de Nash
como estratégia de agregação e a satifação desses mesmos grupos com a recomendação
utilizando diversas outras estratégias de agregação de preferência individual encontradas
na literatura. A satisfação dos grupos foi calculada a partir de uma função de utilidade que
utiliza como base de cálculo o valor da previsão de preferência individual dos membros
do grupo para os itens recomendados.
A seção 2 introduz sistemas de recomendação para grupos e as estratégias de
agregação mais discutidas na literatura. Na seção 3, definimos formalmente o problema
da recomendação para grupos como um jogo não-cooperativo de informações imperfeitas
onde os itens a serem recomendados são frutos dos equilı́brios de Nash computados. A
seção 4 descreve os experimentos realizados com a base MovieLens e resultados obtidos
são devidamente discutidos. Finalmente, a seção 5 traz algumas conclusões e possibilidades de trabalhos futuros.
2. Sistema de Recomendação para Grupos
Apesar de sistemas de recomendação tradicionalmente recomendarem itens para usuários
individuais, há um crescente aumento de pesquisas na linha de recomendação para grupos
de usuários [Masthoff 2011, Jameson e Smyth 2007]. Sistemas de Recomendação para
grupo geram recomendações com o objetivo de satisfazer um grupo de usuários com
interesses potencialmente conflitantes. Os domı́nios com mais destaque na utilização de
recomendação para grupos são: filme, viagem, música, programas de TV e restaurante.
A necessidade de escolha de um método de agregação é a diferença mais estudada entre recomendação para grupos e recomendação para indivı́duos. Apesar das várias
abordagens de agregação diferirem na maneira de manipular e representar as preferências
dos usuários, praticamente todas fazem uso de um dos três esquemas: (1) agrega um
conjunto de recomendações individuais, (2) constroi um modelo de preferência do
grupo, (3) agrega as avaliações/preferências para itens particulares.
Masthoff [Masthoff 2004] enumera diversas estratégias de agregação de preferência individual baseadas na Social Choice Theory [Sen 1986, Pennock et al. 2000].
A problemática relacionada a social choice ou group decision making é decidir o que é
melhor para um grupo dado a opinião dos indivı́duos pertencentes ao mesmo grupo.
Antes de apresentar as estratégias é preciso saber que cada uma possui vantagens
e desvatagens e a comparação entre elas necessita de critérios de qualidade bem definidos.
Entre alguns critérios que podem ser adotados estão [Jameson e Smyth 2007]:
• Maximizar satisfação média: pode ser observado por uma função que computa
algum tipo de média das previsões de satisfação para cada membro para usar como
base de seleção dos itens candidatos.
• Minimizar miséria: deve evitar uma solução que deixe um ou mais membros
muito insatisfeitos com a recomendação.
1
http://www.grouplens.org/node/73/
• Assegurar algum grau de justiça: uma solução que satisfaz todo mundo igualmente bem é em geral preferı́vel a uma que satisfaz alguns em detrimento dos
outros.
Entre as principais estratégias de agregação definidas na Social Choice Theory,
estão:
• Average: assume uma importância igual para todos os membros do grupo e computa a média da satisfação de todo o grupo para qualquer item dado. A desvantagem desta estratégia é sua grande dependência das dimensões do grupo. Para
grupos com poucos membros, por exemplo, a opinião de cada membro tem maior
impacto na média.
• Fairness: items de maior preferência para todos os usuários são selecionados.
Quando itens são avaliados igualmente por um usuário, a opinião dos outros
usuários é levada em consideração. A fundamentação lógica desta estratégia é
que não é tão ruim aceitar algo que não é de seu agrado desde que você também
receba algo de seu agrado como compensação.
• Plurality Voting: o usuário sempre seleciona o item com maior preferência individual em um sistema de votação. Apesar de satisfazer a maioria do grupo,
eventualmente alguns membros permanecem insatisfeitos.
• Least Misery: assume a avaliação do membro menos satisfeito com um item
dado como o valor da satisfação para todo o grupo. A desvantagem dessa estratégia é que um item em que todos os membros estão pouco satisfeitos pode
ser recomendado no lugar de um item onde apenas um usuário está muito insatisfeito e os demais muito satisfeitos, podendo ocorrer miséria para todo o grupo na
recomendação.
• Most Pleasure: assume a avaliação do membro mais satisfeito com um item dado
como o valor da satisfação para todo o grupo. A desvantagem dessa estratégia
é que qualquer avaliação menos satisfatória para este item por parte dos outros
membros não terá nenhum efeito na recomendação.
• Utilitarian Multiplicative: os valores das avaliações dos membros para um dado
item são multiplicados e quanto maior esse valor, mais relevante o item será na
lista de recomendação para o grupo. Possui a mesma desvantagem da estratégia
Average.
• Average Without Misery Strategy: gera uma nova lista de avaliações com as
médias das avaliações individuais dos membros do grupo para um dado item,
porém retira os itens que possuam qualquer avaliação de preferência abaixo de
um valor mı́nimo.
Os diferentes tipos de grupos influenciam na maneira com que os usuários avaliam o resultado da estratégia de agregação adotada. No Polylens [O’Connor et al. 2002],
formado por grupos permanentes, a estratégia adotada Least Misery foi bem aceita por
77% dos usuários; o fato dos membros se conhecerem previamente acaba contribuindo
para tentarem evitar com relativo sucesso a insatisfação uns dos outros.
Outra caracterı́stica do grupo que deve ser analisada na escolha das estratégias
de agregação é a homogeneidade e heterogeneidade entre os membros do grupo. Na
avaliação do YU’s TV RECOMMENDER [Yu et al. 2006], a estratégia de agregação Average funcionou bem para grupos próximos da homogeneidade, porém o resultado piorou
significativamente quando o grupo se aproximou da heterogeneidade.
De acordo com [Senot et al. 2011], essas estratégias de agregação podem ser divididas em três categorias:
• estratégias baseadas em consenso: considera as preferências de todos os membros do grupo (ex: Average, Average without Misery, Fairness e Multiplicative).
• estratégias baseada em maioria: utiliza os itens mais populares entre os membros do grupo (ex: Plurality Voting).
• estratégias borderline: considera somente um subconjunto de itens, em perfis
individuais, baseados nas regras de usuários ou qualquer outro critério relevante.
Entre as estratégias nesta categoria destaca-se a estratégia Dictatorship, que usa
somente a preferência de um único membro que impõe seu gosto para o resto do
grupo. As estratégias Least Misery e Most Pleasure consideram apenas o menor e
o maior nı́vel de interesse, respectivamente, entre os membros do grupo.
3. Definição do Problema
Seja I = {i1 , i2 , ..., in } e U = {u1 , u2 , ..., uk } o conjunto de todos os itens e todos os
usuários respectivamente. Considere G o conjunto de todos os grupos que podem ser
formados por U com pelo menos 2 membros e, portanto, |G| = 2k − k − 1. Considere,
finalmente, g ∈ G, sendo |g| definido como o número m de membros do grupo g. Se, por
exemplo, um grupo é composto pelos usuários u1 , u2 e u3 , então este pode ser expresso
como g = {u1 , u2 , u3 } e |g| = 3.
Assuma p(u, i) como a avaliação para o item i fornecida pelo usuário u, e p(u, i) =
0, se o usuário u não avaliou o item i. Considere p̂(u, i) como a previsão de avaliação do
item i para o usuário u. A previsão de avaliação p̂(u, i) é obtida de uma função de previsão
p̂ que utiliza mais comumente uma função de similaridade entre itens s : I x I → R e/ou
entre usuários s : U x U → R.
A lista de itens recomendados R é definida pelos x melhores itens avaliados pelo
grupo com base em uma estratégia de agregação. As estratégias de agregação fazem uso
do valor da avaliação ou da previsão de avaliação do item pelo membro do grupo. No
exemplo da estratégia de agregação Average, representada na Equação 1, utilizou-se a
previsão de avaliação para o cálculo:
m
P
Ri = average(p̂(u, i)) =
p̂(uj , i)
j=1
m
(1)
Para cada estratégia, Ri retorna uma tupla que fornece um valor associado ao item
i que é utilizado para gerar um ranking entre os itens, onde os x primeiros itens formam
o conjunto R de recomendação para o grupo.
Dado um conjunto recomendação R de x itens para o grupo g, a satisfação média
desta recomendação para o usuário u, onde u ∈ g, é calculada pela função de utilidade
representada pela Equação 2:
x
P
S(u, R) =
p̂(u, ij )
j=1
x
(2)
O valor da satisfação média da recomendação R de tamanho x para o grupo g de
tamanho m é calculada pela função de utilidade representada pela Equação 3:
m
P
S(g, R) =
S(uj , R)
j=1
m
(3)
A maximização do S(g, R) significa a maximização da satisfação média dos membros do grupo para a lista de itens de recomendação.
A proposta deste artigo é modelar como um jogo de informações imperfeitas na
forma normal a seleção dos itens para recomendação para o grupo como o problema de
encontrar os equilı́brios de Nash no jogo.
Um jogo na forma normal é composto por uma tupla (m, A, f), onde:
• m é o número de jogadores, indexado por j;
• A = A1 x ... x Am , onde Aj é o conjunto finito de ações disponı́veis para o jogador
j; Cada vetor a = (a1 , ..., am ) ∈ A é conhecido como perfil de ações.
• f = (f1 , ..., fm ) onde fj : A → R é uma função de utilidade (ou payoff) para o
jogador j.
Seja Raj o conjunto de itens de tamanho x retornados pela estratégia da ação aj do jogador
j. Para o cálculo da função payoff para cada jogador, considera-se a união apenas do item
de maior preferência para o usuário j do conjunto de itens retornado pela estratégia aj . A
união está representada na Equação 4.
R=
m
[
Raj
(4)
j=1
A função payoff (Equação 5) calcula a satisfação do membro u do grupo com o
resultado das ações escolhidas por todos os jogadores em uma dada estratégia do jogo.
|R|
P
f=
p̂(u, iw )
w=1
|R|
, onde iw ∈ R
(5)
Intuitivamente, o jogador membro do grupo deseja encontrar a estratégia de
agregação que maximize o resultado da sua função payoff. Um equilı́brio de Nash é
um perfil de estratégia estável: não há qualquer incentivo para que o jogador desvie da
estratégia pertencente ao equilı́brio.
As ações disponı́veis no jogo foram escolhidas entre os itens retornados pelas
estratégias de agregação ao invés de todos os itens possı́veis de serem recomendados.
Esta decisão procura se aproximar mais da realidade dos usuários considerando o resultado de um experimento com participantes que mostrou que indivı́duos usam algumas
das estratégias de agregação apresentadas na seção 2, principalmente as estratégias Average, Average Without Misery e Least Misery [Masthoff 2004]. Este mesmo experimento
mostrou que os participantes se preocupam com o equilı́brio entre justiça e atender suas
próprias preferências.
O equilı́brio com a justiça na abordagem deste artigo é buscado através do uso
de diferentes estratégias de agregação como ações do jogo. Já para atender as próprias
preferências dos membros do grupo, a função payoff considera exclusivamente as preferências do jogador na escolha do item de maior preferência entre os itens retornados
pela estratégia de agregação como ação do jogo de fato e também no cálculo do equilı́brio.
Consequentemente, cada jogador possui um perfil de ações diferentes e, portanto, para as
mesmas estratégias, os jogadores podem escolher itens diferentes como a ação de fato do
jogador.
Quando ocorre do cálculo do equilı́brio retornar mais de um equilı́brio de Nash
para o grupo, significando que mais de um conjunto diferente de itens pode ser recomendado para o grupo, a escolha de qual desses conjunto será recomendado é realizada
através do uso de uma função de média harmônica (Equação 6). Esta função realiza o
cálculo a partir das preferências dos membros do grupo para o conjunto de itens de cada
um dos equilı́brios de Nash. O conjunto que possui a maior média harmônica, será escolhido como o conjunto a ser recomendado para o grupo. A decisão de utilizar uma
média harmônica também considerou a justiça entre os membros do grupo, visto que ao
contrário da média aritmética, a média harmônica ”’prioriza”’ conjuntos de valores de
menor variância.
n
harmonic(x) = P
n
1
i=1
(6)
xi
4. Experimento
Por ser bastante utilizada em vários outros estudos de recomendação para grupos, mesmo
não havendo informações sobre grupos de usuários, a base de dados do MovieLens foi
escolhida para validação da abordagem. Essa base de dados possui no total 943 usuários,
1.682 filmes e 100.000 avaliações no intervalo de 1 a 5.
Na primeira etapa do experimento, utilizando como base as avaliações individuais p(u, i) dos usuários, gerou-se uma lista de previsão de avaliação de todos os filmes
ainda não assistidos por cada usuário. As previsões de avaliação foram geradas a partir de um algoritmo de filtragem colaborativa baseado em KNN (K-Nearest Neighbor)
[Dasarathy 1991].
Após a geração das previsões de avaliação, pode-se notar, como apresentado na
Figura 1(a), que a distribuição dos valores das previsões obtidas das avaliações da base
do MovieLens tendem para valores altos, com média de 4,01 e desvio padrão de 0,41.
Esta distribuição representa o cenário 1 do experimento. Para se contrapor a este cenário,
gerou-se uma outra distribuição artificial com média de 2,5 e desvio padrão 1,01 para os
valores das previsões de avaliação para os mesmos itens do cenário 1, com o objetivo
de representar uma distribuição mais próxima de uma distribuição normal e com valores
mais dispersos pela escala de avaliação, conforme observa-se na Figura 1(b).
No experimento, os itens potencialmente a serem recomendados para cada grupo
pertencem ao conjunto de items que não foram avaliados por nenhum membro do grupo.
Por tanto, eles são obtidos a partir da intersecção das listas de itens de previsão de
avaliação de cada usuário do grupo. Os itens pertencentes a esta lista e os valores das
(a)
(b)
Figura 1. Histogramas de previsão de avaliação para diferentes cenários.
previsões que definem as preferências individuais dos usuários do grupo no experimento
serão utilizadas nas estratégias de agregação de preferências.
Como a base do MovieLens não possui grupos definidos, fez-se necessário a
formação automática dos grupos. Nesta etapa, os usuários da base do MovieLens foram
agrupados, utilizando o vetor de previsão de preferência de cada usuário, em 31 clusters
com centróide aleatórios com base no método K-Means. Criou-se um conjunto de cluster
para cada um dos cenários do experimento. A partir desses clusters, foram selecionados
aleatoriamente membros para formar dois tipos de grupos: homogêneo, contendo usuários
do mesmo cluster e heterogêneo, contendo usuários de clusters diferentes. Foram ainda
gerados 20 grupos desses dois tipos com 3, 5 e 7 número de membros. Efetuaram-se então
10 execuções para cada cenário nessas configurações do experimento.
Na quarta etapa do experimento, as estratégias de agregação selecionadas como
ações disponı́veis para o jogo (Average, Least Misery e Plurality Vote) foram aplicadas para a criação dos perfis de agregação do grupo. Estas estratégias de agregação
foram consideradas especificamente por estarem em categorias diferentes segundo
[Senot et al. 2010], e com isso apresentarem diferentes itens como resultados.
Para construção dos jogos na forma normal e cálculo do equilı́brio de Nash,
utilizou-se a ferramenta Gambit [McKelvey et al. 2010] e a sua interface na linguagem
Python. Para o experimento deste artigo, calculou-se apenas o equilı́brio de Nash para
as estratégias puras. Experimentos futuros podem considerar o cálculo dos equilı́brios de
Nash para estratégias mistas.
Após o calculo, comparou-se o resultado da estratégia de agregação do equilı́brio
de Nash com as estratégias de agregação: Least Misery (L.M.), Average (Ave.), Average
Without Misery (A.W.M), Multiplicative (M.), Most Pleasure (M.P.), Fairness (F.) e Plurality Vote (P.V.). O resultado baseou-se no cálculo da satisfação a partir da função de utilidade (Equação 3) dos itens recomendados para o grupo por cada estratégia de agregação.
4.1. Resultados do cenário de experimentação 1
O resultado do experimento neste cenário, que utiliza a previsão de avaliação a partir das
avaliações dos usuários da base do MovieLens, é apresentado nas Tabelas 1, 2 e 3. Este
cenário responde a pergunta: qual o desempenho da estratégia de agregação utilizando
o equilı́brio de Nash em relação às demais estratégias de agregação, considerando um
cenário em que as avaliações e as previsões de avaliação se concentram em valores altos
da escala de avaliação, como é o caso da base do MovieLens?
Tabela 1. Previsão de satisfação média para grupos de 3 membros.
Tipo
S
L.M.
Ave.
A.W.M.
M
M.P.
F
P.V.
Equilibrium
µ
σ
µ
Hetero.
σ
4.632
0.152
4.588
0.169
4.675
0.135
4.637
0.149
4.675
0.135
4.637
0.149
4.675
0.135
4.637
0.149
4.488
0.189
4.473
0.170
4.695
0.154
4.642
0.182
4.591
0.169
4.551
0.193
4.653
0.164
4.616
0.159
Homo.
Tabela 2. Previsão de satisfação média para grupos de 5 membros.
Tipo
S
L.M.
Ave.
A.W.M.
M
M.P.
F
P.V.
Equilibrium
µ
σ
µ
Hetero.
σ
4.456
0.167
4.422
0.152
4.509
0.156
4.473
0.139
4.509
0.156
4.473
0.139
4.509
0.156
4.473
0.139
4.371
0.189
4.385
0.152
4.536
0.187
4.489
0.164
4.410
0.241
4.340
0.208
4.484
0.159
4.442
0.137
Homo.
Tabela 3. Previsão de satisfação média para grupos de 7 membros.
Tipo
S
L.M.
Ave.
A.W.M.
M
M.P.
F
P.V.
Equilibrium
µ
σ
µ
Hetero.
σ
4.357
0.213
4.307
0.161
4.404
0.216
4.343
0.170
4.404
0.216
4.343
0.170
4.404
0.216
4.343
0.170
4.323
0.206
4.303
0.161
4.450
0.238
4.379
0.175
4.277
0.259
4.215
0.167
4.374
0.218
4.319
0.165
Homo.
Nessas três tabelas é possı́vel verificar que por utilizarem uma distribuição com
valores de previsão de avaliação concentrados nos valores 4 e 5 como preferência individual dos usuários para os itens, as estratégias baseada em consenso obtiveram melhores
resultados do que todas as demais estratégias, inclusive melhor que a estratégia utilizando
o equilı́brio de Nash. A estratégia de agregação Fairness obteve o melhor resultado auxiliado pelo fato de retornar menos itens que as demais estratégias e com isso obteve uma
melhor previsão de satisfação média.
A estratégia utilizando equilı́brio de Nash para este cenário obteve desempenho
melhor comparado à estratégia baseada em maioria representada pela Plurality Voting e
também melhor desempenho comparado às estratégias baseadas em borderline representadas pela Least Misery e Most Pleasure.
O experimento também confirmou, assim como em diversos outros estudos
[Senot et al. 2010], que o aumento na quantidade de membros nos grupos leva a uma
diminuição na satisfação média do grupo para o conjunto de recomendação. Esta
diminuição na satisfação ocorre em todas as estratégias e nos dois cenários do experimento, pois há uma diminuição do consenso com o aumento do número de membros.
4.2. Resultados do cenário de experimentação 2
O resultado do experimento neste cenário utiliza a distribuição artificial dos valores de
previsão de avaliação dos itens mais próxima da distribuição normal do que a distribuição
do cenário 1. Pode-se considerar que os grupos gerados nesse cenário tendem a ser no
geral mais heterogêneos com relação às previsões de avaliação dos itens do que no cenário
1. O resultado é apresentado nas tabelas 4, 5 e 6. Este cenário responde a pergunta:
como se comporta a estratégia de agregação utilizando o equilı́brio de Nash em relação às
demais estratégias considerando um cenário em que as avaliações dos itens tendem para
valores mais esparsados na escala de avaliação?
Tabela 4. Previsão de satisfação média para grupos de 3 membros.
Tipo
S
L.M.
Ave.
A.W.M.
M
M.P.
F
P.V.
Equilibrium
µ
σ
µ
Hetero.
σ
3.361
0.903
3.314
0.730
3.718
0.957
3.685
0.456
3.702
0.992
3.442
1.383
3.706
0.979
3.586
0.822
3.241
0.848
3.275
0.466
3.513
0.912
3.520
0.445
3.427
0.912
3.449
0.502
3.658
0.949
3.637
0.464
Homo.
Tabela 5. Previsão de satisfação média para grupos de 5 membros.
Tipo
S
L.M.
Ave.
A.W.M.
M
M.P.
F
P.V.
Equilibrium
µ
σ
µ
Hetero.
σ
2.961
0.750
2.830
0.449
3.264
0.785
3.152
0.305
3.238
0.847
2.747
1.402
3.252
0.804
3.050
0.523
2.924
0.724
2.867
0.305
3.086
0.738
3.038
0.277
3.112
0.768
3.023
0.310
3.206
0.776
3.103
0.307
Homo.
Tabela 6. Previsão de satisfação média para grupos de 7 membros.
Tipo
S
L.M.
Ave.
A.W.M.
M
M.P.
F
P.V.
Equilibrium
µ
σ
µ
Hetero.
σ
2.705
0.691
2.602
0.352
2.955
0.718
2.787
0.320
2.896
0.790
2.144
1.438
2.938
0.757
2.713
0.419
2.726
0.665
2.643
0.289
2.848
0.683
2.738
0.293
2.854
0.712
2.692
0.340
2.899
0.714
2.724
0.311
Homo.
Nessas últimas três tabelas é possı́vel verificar que o resultado para este cenário
da estratégia de agregação utilizando o equilı́brio de Nash obteve um melhor resultado do
que o cenário 1 em comparação ao desempenho das demais estratégias de agregação.
Neste cenário, a estratégia de agregação utilizando equilı́brio de Nash ficou com
desempenho inferior apenas comparado à estratégia Average para qualquer número de
membros e tipos de grupo. Porém, ao contrário do cenário 1, neste cenário a estratégia
de agregação utilizando o equilı́brio de Nash obteve melhor desempenho do que as estratégias Multiplicative e Average Without Misery quando calculado a satisfação para grupos heterogêneos.
Neste cenário, a estratégia de agregação utilizando equilı́brio de Nash não obteve
desempenho melhor do que a estratégia Fairness, mesmo recomendando mais itens do
que essa estratégia, somente para 7 membros e para grupos heterogêneos. Esse melhor
desempenho especı́fico da estratégia Fairness foi obtido devido ao aumento na diferença
no número de itens retornados entre a estratégia utilizando o equilı́brio de Nash e a estratégia Fairness.
A estratégia utilizando equilı́brio de Nash obteve desempenho melhor comparado
às estratégias baseadas em borderline e baseadas em maioria, assim como ocorreu no
cenário 1.
5. Conclusão
Neste artigo, o problema da recomendação de itens para grupos de pessoas foi definido
como um jogo não-cooperativo. Equilı́brio de Nash foi utilizado para seleção do conjunto
de itens a serem recomendados para o grupo visando o satisfazer a escolha mais justa
para o grupo e as preferências individuais de seus membros. As estratégias de agregação
Average, Plurality Vote e Least Misery foram escolhidas para fornecer os itens utilizados como ação do jogo, como forma de priorizar a justiça. A justiça também foi buscada na seleção do conjunto de itens em equilı́brio de Nash que seriam retornados como
recomendação para o grupo. A satisfação da preferência dos membros do grupo foi buscada através do cálculo do equilı́brio que considera apenas as preferências de cada usuário
de forma racional.
Experimentos foram realizados com a base MovieLens e compararam a abordagem utilizando a identificação dos equilı́brios com as estratégias Least Misery, Average,
Average Without Misery, Multiplicative, Most Pleasure, Fairness e Plurality Vote que representam o Estado da Arte da pesquisa em recomendação para grupos.
Resultados mostraram que na satisfação alcançadada, a abordagem do equilı́brio
obteve um resultado melhor, comparado às demais estratégias de agregação, no cenário
em que os valores de previsão de avaliação estão distribuı́dos de forma mais esparsa pela
escala de valores do que no cenário em que os valores de previsão de avaliação estão
concentrados em valores altos da escala de avaliação.
Este melhor resultado no segundo cenário deve-se a previsão de avaliação dos itens
serem distribuı́da de forma mais esparsa entre a escala de valores, ou seja, as avaliações
entre os membros, mesmo em grupos homogêneos (membros no mesmo cluster), tendem a ser mais heterogêneas do que no cenário 1. Portanto, quanto mais heterogêneo as
avaliações entre os grupos, melhor o desempenho da estratégia baseada no equilı́brio em
comparação com as demais estratégias.
Novos experimentos estão sendo realizados com o intuito de demonstrar quantas e
quais são as melhores estratégias de agregação para seleção dos itens a serem utilizados no
cálculo do equilı́brio de Nash. Outras métricas de qualidade, como Justiça e Minimização
de Miséria, também serão utilizadas para avaliar a qualidade da proposta.
Referências
Adomavicius, G. e Tuzhilin, A. (2005). Toward the next generation of recommender
systems: a survey of the state-of-the-art and possible extensions. IEEE Transactions
on Knowledge and Data Engineering, 17(6):734–749.
Bekkerman, P., Kraus, S., e Ricci, F. (2006). Applying cooperative negotiation methodology to group recommendation problem. In Felfernig, A. e Zanker, M., editors,
Proceedings of Workshop on RecSys in ECAI 2006, pages 72–75, Riva del Garda, Italy.
Burke, R. (2002). Hybrid Recommender Systems: Survey and Experiments. Jornal of
UMUAI, 12(4):331–370.
Dasarathy, B. W. (1991). Nearest Neighbor (NN). Los Alamitos, CA. IEEE Computer
Society Press.
Jameson, A. (2004). More than the sum of its members: challenges for group recommender systems. In Proceedings of AVI ’04, page 48, New York, USA. ACM Press.
Jameson, A. e Smyth, B. (2007). Recommendation to Groups. In Brusilovsky, P., Kobsa,
A., e Nejdl, W., editors, The Adaptive Web (LNCS), volume 4321 of LNCS, pages
596–627. Springer Berlin Heidelberg, Berlin, Heidelberg.
Masthoff, J. (2004). Group Modeling: Selecting a Sequence of Television Items to Suit a
Group of Viewers. Jornal of UMUAI, 14(1):37–85.
Masthoff, J. (2011). Group recommender systems: combining individual models. In
Ricci, F., Rokach, L., Shapira, B., e Kantor, P. B., editors, Recommender Systems
Handbook, page 677. Springer US, Boston, MA.
McKelvey, R. D., McLennan, A. M., e Turocy, T. L. (2010). Gambit: Software Tools for
Game Theory.
O’Connor, M., Cosley, D., Konstan, J. A., e Riedl, J. T. (2002). PolyLens: A Recommender System for Groups of Users. In Prinz, W., Jarke, M., Rogers, Y., Schmidt,
K., e Wulf, V., editors, ECSCW 2001, pages 199–218. Kluwer Academic Publishers,
Dordrecht.
Pennock, D. M., Horvitz, E., e Giles, C. L. (2000). Social choice theory and recommender
systems: Analysis of the axiomatic foundations of collaborative filtering. In Proc. 17th
AAAI.
Sen, A. (1986). An adaptive in-vehicle multimedia recommender for group users . In
Handbook of Mathematical Economics, volume 3. Elsevier Science.
Senot, C., Kostadinov, D., Bouzid, M., Picault, J., e Aghasaryan, A. (2011). Evaluation
of Group Profiling Strategies. In Proceedings of the 22nd Int. Joint Conf. on Art. Int.,
pages 2728 –2733, Barcelona. the Association for the Adv. of Art. Int. (AAAI).
Senot, C., Kostadinov, D., Bouzid, M., Picault, J., Aghasaryan, A., e Bernier, C. (2010).
Analysis of Strategies for Building Group Profiles. In Bra, P., Kobsa, A., e Chin, D.,
editors, UMAP, volume 6075 of LNCS, pages 40–51. Springer Berlin Heidelberg.
Yu, Z., Zhou, X., Hao, Y., e Gu, J. (2006). TV Program Recommendation for Multiple
Viewers Based on user Profile Merging. Jornal of UMUAI, 16(1):63–82.