Signal Processing - January 2016 - 40

that frequency-dependent fitness introduces a strategic aspect to
and Yelp rating data will be used to discuss how users can learn
evolution, EGT becomes an essential component of a mathematical
from each other's interactions for better strategic decision making.
and computational approach to biological contexts, such as genes,
On the mechanism design, how to design the mechanism to collect
viruses, cells, and humans. Recently,
high-quality data with low cost from
EGT has also become of increased
crowdsourcing will be illustrated [19].
IncentIve mechanIsms reFer
interest to economists, sociologists,
Using these frameworks, we can theoto schemes that aIm to steer
anthropologists, and social scientists.
retically analyze and predict user
user BehavIors throuGh the
Here, we show how the evolutionary
behaviors through equilibrium analyaLLocatIon oF varIous Forms
game theory is deployed to study
sis. And, based on the analysis, one
oF rewarDs such as monetary
users' repetitive and evolutionary
can optimize in a systematic way the
rewarDs, vIrtuaL poInts,
behavior in social systems.
design of incentive mechanisms for
anD reputatIon status.
In the setting of our consideration,
social networks to achieve a wide
the social system user topology can be
range of system objectives and analyze
treated as a graph structure, and the user with a new decision can be
their performances accordingly. Finally, recent related works on
regarded as the mutant. By considering the decision-making process
the intersection of learning and strategic decision making will be
as the mutant-spreading process [to forward or not to forward when
surveyed and discussed.
an event (mutation) takes place], the graphical evolutionary game
provides us with an analytical means to find the evolutionary dynamuser BehavIor moDeLInG anD anaLysIs
ics and equilibrium of user behavior.
In DecIsIon LearnInG
In this section, we will address decision learning from the user's
GRAPHICAL EVOLuTIONARy GAME FRAMEWORK
point of view. Both the evolutionary and sequential user behaviors
In EGT, the utility of a player is referred to as fitness [22]. Specifiare commonly exhibited in social systems. How learning with stracally, the fitness U is a linear combination of the baseline fitness
tegic decision making may arise from both settings will be illustrated, first with information diffusion over online social networks
(B) representing the player's inherent property and the player's
using the graphical evolutionary game framework from Twitter
payoff (U), which is determined by the predefined payoff matrix
and MemeTracker data, and then with the optimal restaurant
and the player's interactions with others as follows:
strategy using the Chinese-restaurant-game framework from both
Groupon deals and Yelp ratings, respectively.
U = (1 - a) B + aU,
(1)
EVOLUTIONARY USER BEHAVIOR: GRAPHICAL
EVOLUTIONARY GAME FRAMEWORK
One typical user behavior in social systems is the repetitive and
evolutionary decision making. A good example is that users
repetitively decide whether to post information or not on online
social networks. Figure 3 shows the top 50 threads in the news
cycle with highest volume for the period of 1 August-31 October
2008, where each thread consists of all new articles and blog
posts containing a textual variant of a particular quoted phrase.
The five large peaks between late August and late September
corresponding to the Democratic and Republican National Conventions illustrate the spread of comments and phrasing by candidates. Notice that the information forwarding is often not
unconditional. One has to make a decision on whether or not to
do so based on many factors, such as if the information is exciting or if friends are interested in it, etc. Other examples include
repetitive online purchasing and review posting.
We find that, in essence, the repetitive and evolutionary decisionmaking process on social systems follows the evolution process in
natural ecological systems [21]. It is a process that evolves from one
state at a particular instance to another when information is shared
and a decision is made. Thus, the evolutionary game is an ideal tool
to model and analyze the social system users' repetitive and evolutionary behavior. Evolutionary game theory (EGT) is an application
of the mathematical theory of games to the interaction-dependent
strategy evolution in populations [21]. Arising from the realization

where the combining weight a is called the selection intensity.
One can interpret that one's fitness is not only determined by
one's own strength, but also from one's environment affecting
with a selection intensity a. The case that a " 0 represents the
limit of weak selection [23], while a " 1 denotes strong selection.
The selection intensity can also be time varying, e.g., a = be - ft,
which means that the contribution of game interaction decreases
with time.
With the fitness function, the EGT studies and characterizes
how a group of players converge to a stable equilibrium after a
period of strategic interactions. Such a final equilibrium state is
called the evolutionarily stable state (ESS), which is "a strategy
such that, if all members of the population adopt it, then no
mutant strategy could invade the population under the influence of natural selection" [21]. In other words, even if a small
fraction of players may not be rational and take out-of-equilibrium strategies, ESS is still a locally stable state. How to find
the ESSs is an important issue in EGT. One common approach
is to find the stable points of the system state dynamic, which is
known as replicator dynamics. The corresponding underlying
physical meaning is that, if adopting a certain strategy can lead
to a higher fitness than the average level, the proportion of population adopting this strategy will increase, and the increasing
rate is proportional to the difference between the average fitness
with this strategy and the average fitness of the whole population. Note that when the total population is sufficiently large

IEEE SIGNAL PROCESSING MAGAZINE [40] jANuARy 2016

Table of Contents for the Digital Edition of Signal Processing - January 2016