Person has left EURECOM
- VU Quan dong
Thesis
Learning in Blotto games and applications to modeling attention in social networks
Background and PhD topic description:
The Colonel Blotto game is a fundamental model of strategic resource allocation: two players
allocate a xed amount of resources to a xed number of battle elds with given values, each
battle eld is then won by the player who allocated more resources to it, and each player maximizes
the aggregate value of battle elds he wins. It recently gained a very high interest in theoretical
and applied research communities because of its potential to model many important problems of
resource allocation in strategic settings ranging from international war to computer security. In
particular, it provides a good model of competition for attention of users in social networks. There,
battle elds correspond to users and their values correspond to the value of convincing the users (e.g.,
in advertisement, it would be the value of the product bought by the user). Theoretical solutions
of the Colonel Blotto game could therefore enable important progresses in designing strategies
to allocate resources optimally to capture the attention of users in a social network, a topic of
high importance in the online world with applications for instance to advertisement campaigns or
information propagation.
Applications of the Colonel Blotto game, however, have remained limited so far mostly due to
the lack of solutions of the game in realistic cases. Indeed, although it was originally proposed by
Borel in 1921 [2], the rst Nash equilibrium solution of the game was given in 1950 [6] in a simple
1
case (2 or 3 battle elds). In 2006, a Nash equilibrium solution was given for an arbitrary number
of battle elds [9] (see also a survey in [10]), but only if all battle elds have the same value, which is
not realistic in applications. In our recent work, we proposed rst ideas towards a Nash equilibrium
solution for arbitrary battle elds values [11], and towards a Nash equilibrium solution of the Blotto
game on a graph [8]; but those ideas need to be developed to reach a general Nash equilibrium
solution useful in the application to competition for attention of users in social networks.
Another barrier for applications is that the Nash equilibrium solution assumes complete infor-
mation on the players payo s, which is not always appropriate. The machine learning community
has been very active in recent year to develop sequential learning methods in order to adjust the
strategies while learning the unknown payo parameters, in particular in the classical setting of the
multi-armed bandit problem [3, 5]. These methods, however, are not adapted in a competitive en-
vironment such as the one modeled by the Colonel Blotto game and developing learning algorithms
in fully game-theoretic settings is currently an open problem.
The overall goal of this thesis will be to develop solutions of the Blotto games in order to use it
to model competition for attention of users in social networks. Speci cally, we will look to address
the two key barriers mentioned above, that is:
(i) First, we will look for a general Nash equilibrium solution. In particular, we will include
arbitrary battle eld values, more than two players (in order to be able to model more than
two competitors) and to take into account externalities on a graph (i.e., the fact that winning
a battle eld has an e ect on the value of neighboring battle elds in the social network).
We will leverage preliminary ideas mentioned above and propose and analyze heuristics to
compute approximate Nash equilibria in cases where the exact solution is not possible.
(ii) Second, we will develop sequential learning methods adapted to the game-theoretic setting
where several competitors are concurrently performing a learning task whose outcome depends
on each other; and apply those to design strategies for the competitors to dynamically adjust
their resource allocation while learning the users value. To this end, we will combine ideas from
the multi-armed bandit literature [3, 5] with game theoretic ideas from repeated games [1, 4,
12] (see also [7]).
