Cette page appartient aux archives web de l'EPFL et n'est plus tenue à jour.
This page belongs to EPFL's web archive and is no longer updated.

Human Computation

S. Jain and D. Parkes, 2012, A game-theoretic analysis of games with a purpose, To appear in ACM TEAC

Posted by Katherine Skirving Larson on Wednesday 18 April 2012 at 16:27
The paper poses a theoretical model for one of the "games with a purpose". The game is mainly the cooperative game of labeling images. The paper proposes two models of the utility function. The first models the current implementations of the game. This awards frequent (or early) matches of labels irrespective of how descriptive (infrequent general words) they are. This results in labels that are redudant (synonymous) and generic (high-frequency low-entropy) tags. The second model attempts to overcome this problem by awarding more points to words that are less frequent (in the provided language model).

The paper starts by giving the necessary definitions of the game (modeled as two stages) followed by some strong characterizations of the equilibria of the game under the two utility models. In brief, under the first model, equilibria lead players to invest low effort and play words in roughly decreasing order of frequency (except if all words are equiprobable, then there is another equilibrium and both equilibria are weak), matching exactly the observed experimental outcome. The situation is worst under the Zipfian distribution (believed to be the distribution of the English vocabulary). Under the second model, it is shown that the equilibrium involves the players playing with low effort (only frequent words) in increasing order of frequency. Some further conditions on the utility function lead to another equilibrium involving the players playing all words in increasing order of frequency.
Posted by Abdallah Alaaeldin Abdelaziz Elguindy on Wednesday 25 April 2012 at 13:58
The work aim to characterize the equilibrium of ESP: an enjoyable game specially designed for human to perform image labeling. The game present an image to two (random) players, where each of them has to type what she thinks the other player will label the image.

In the characterization, the author proceed in two directions: 1) same reward for any matched word, and 2) higher reward for less frequent word (appear in English language). It is shown that in 1), the equilibrium will be that the user want to match as early as possible, and they begin their guess with relatively frequent words. Whereas in 2), as expected, users try their best to obtain high rewards by first providing less frequent words.

However, the game itself, when it is played, contain more subtleties. In particular, there is a learning factor play a role. In particular, from my own experience playing this game (in gwap.com) slowly I discovered that typing color-word (dominant color in the image) is one of our most useful strategy. Then, the next research question to ask: instead of considering in word level only, will we have different results if word-topics play a role?

The work in "Games With a Purpose" still continue and game theory analysis result for those games will complete the cycle between understanding players' motivation/strategy and designing games with this understanding in mind.
Posted by Tri Kurniawan Wijaya on Friday 27 April 2012 at 7:11
This paper gives the analysis of games with a purpose using game theoretical framework. More precisely, the paper studies ESP game: two player game for labeling images on the web. Authors offered simple game model, in which player can choose the amount of effort they want to invest when playing games. Also, authors analyzes two models of payoffs, match early preferences and rare words preferences. First one reflects the scenario when players try to find match as early as possible, while the later one describes the scenario when players try to find not so "common" match. Without going into formalism presented in the paper, we can say that the match early preferences encourages players to adopt low effort and play decreasing frequency strategies (i.e. players prefers to use more frequent words). However, if matching speed is not as relevant as having an infrequent match, then one should use rare words preferences model. In that case playing words in order of increasing frequency dominates the strategy of playing words in decreasing frequency order, i.e. this model promotes matching on low frequency words. Moreover, the paper shows that high effort is a Bayesian-Nash equilibrium for Zipfian distribution over words frequencies under utility function that satisfies additive discount property. Zipfian distribution is important because distribution of frequencies of words in English language is close to it.
Posted by Goran Radanovic on Sunday 29 April 2012 at 21:43
This paper proposes a game theoretic model for the ESP game and analyses the equilibrium of the model. The ESP game is modeled as a two-stage game of imperfect information. At the first stage, a player chooses an effort level, and at the second stage she chooses a permutation on a sampled dictionary from the universe of words. The effort level determines the set of words which will be sampled from the universe. If a player chooses a low effort level, the dictionary is sampled without replacement from the top X words, and if she chooses a high effort level the dictionary is sampled without replacement from the whole universe. It is assumed that each word in the universe is associated with a frequency and the universe is sorted in the decreasing order of frequencies.
Two preference models are considered. In match-early preferences the player is agnostic to the matched words and only prefers having a match as soon as possible. In contrast, in the rare-words preferences the player only cares about which word is matched. Under match-early preferences playing low level effort and then playing words of the sampled dictionary in the decreasing order of frequencies is an ordinal Bayesian-Nash equilibrium for any distribution over the universe except the uniform distribution. Under rare-words preferences playing high level effort and then playing words of the sampled dictionary in the ascending order of frequencies is an ordinal Bayesian-Nash equilibrium for Zipfian distributions over the universe and for any additive and multiplicative utility functions. Using rare-words preferences is in fact a remedy for the problem of users selecting only common words which results in low quality image labeling dataset, but the key challenge is how to design a pointing scheme that encourages the players to adopt the rare-words preferences.
Posted by Mehdi Riahi on Tuesday 1 May 2012 at 15:34