Manipulating the Concepts

Exercise 1: Game coordination and threshold model

Why there is three parts in this assignment: Each part fulfills one of the objectives of the class:

• Manipulate concepts: Getting Familiar with the technical concepts used in class, by reproducing similar arguments. Being proficient by manipulating the object to answer some small-size problem.

You are expected to answer this question rigorously, the answer can be quite short as long as it contains all the required argument to justify your answer.

• Experience the concepts in real case: Being able to reproduce these concepts on real or synthetic data. Study their properties in real examples.
• Connect the concepts to real-life: Interpret a problem you find in light of the notions you have learned. Develop some critical eye to determine how the concepts introduced are useful in practice.

How to read this assignment: Exercise levels are indicated as follows

() “elementary”: the answer is not strictly speaking obvious, but it fits in a single sentence, and it is an immediate application of results covered in the lectures.

Use them as a checkpoint: it is strongly advised to go back to your notes if the answer to one of these questions does not come to you in a few minutes.

(y) “intermediary”: The answer to this question is not an immediate translation of results covered in class, it can be deduced from them with a reasonable effort.

Use them as a practice: how far are you from the answer? Do you still feel uncomfortable with some of the notions?

which part could you complete quickly?

(#) “tortuous”: this question either requires an advanced notion, a proof that is long or inventive, or it is still open.

Use them as an inspiration: can you answer any of them? does it bring you to another problem that you can answer

or study further? It is recommended to work on this question only AFTER you are done with the rest!

Exercise 1: Game coordination and threshold model 

Motivation: This exercice allows you to bridge simple coordination games, also referred to as cooperative game, with threshold model seen in the course. A coordination game is any type of game where players choose from the same set of strategies and turn out to have higher payoff when they make the same choice.

Assume that each player can choose either strategy A or B. Strategy A may for example denote the adoption of an innovation. We suppose that players are connected to each other according to a graph G = (V,E) where V denotes the set of all players and an edge (u,v) is in E if and only if two players are connected.

Every edge (u,v) corresponds to a game where players u and v are involved. In particular they all receive a pay-off for this game which only depends on which strategy each of this player has chosen according to the following table:

                                                                                                  v chooses A         v chooses B

Exercise 2: Adoption with neighbor effect and renewed decision

u chooses A        a             0 u chooses B    0                b

where we assume that a and b are two real numbers such that a > b.

The total payoff receives by a user is the result of her payoff on all games she is involved in (i.e., , she is involved by one game for each incident edge).

1. () Given that all players except u has decided their strategy (which could either be A or B), and that u knows their choices, under which conditions will u rationally choose to play strategy A or B?

We consider an infinite sequence of games indexed by time t = 0,1,2,.... We assume that at time t a user decides her strategy to maximize her payoff when all other players plays the same strategy as at time t ? 1 (which is her last observation).

2. () Let us assume that a set of players always choose to play strategy A independently of others, and that all other players initially play strategy B. How would you describe the evolution of this system with time t? Can you compare it to one seen in the course?

Exercise 2: Adoption with neighbor effect and renewed decision 

Motivation Adoption of an innovation (like an online service) could be promoted by encouraging users to start the service for free. One can distinguish a permanent promotion (where users could access the service for free forever) and temporary promotion where they have a free period. Clearly the first form of promotion (which is the one we studied in class) can only do better. On the other hand, and especially for service paid by subscription, the second option seems cheaper overall to organize. The exercise answers the following question “Could this form of promotion be significantly less efficient?”

In this exercise, we propose to show that, according to macroscopic metric (i.e., , the ability for a finite set of players to create an infinite cascade of adoption), the two are equivalent.

As in the previous exercice, we consider a set of users V that are connected together along edges of a graph G = (V,E). We consider an infinite amount of time slots t = 0,1,2,.... We assume that all users have an adoption threshold ? which characterizes their behavior as follows: during a time slot t, a user observes how many of her friends used the service and renew her subscription for time slot t + 1 if only if at least a fraction ? of her friend have used the service during time slot t.

In the temporary promotion model we consider an extreme version where initially a set of users S₀ are proposed to use the service for free for a single time slot. At the end of this time slot, they may or may not renew the service depending on what they have observed and the threshold rule defined above, just like any other nodes in the network. The only effect of the promotion is to increase the set of users during the first time slot.

In the targeted permanent promotion model we assume that an initial set of users S₀ are proposed the service for free for an unlimited amount of time, while all other users who may use the service or not decides to do so according to the threshold rule defined above.

In the general permanent promotion model, we assume that any user who decides to use the service once will receive a free subscription in all subsequent time slot. All users who have never used the service may decide to adopt it or not according to the threshold rule defined above.

Let us denote by S_t for t = 0,1,... the set of users that decide to subscribe to the service during time slot t in the temporary promotion model. Let us define for each subset A ? V the function f_? as

                                   f_?(A) = { v ? V |            at least a fraction q ? ? of neighbors of v are in A         } .