Le hasard fait bien les choses

Corinne Touati

Inria

Janvier 2013

<figure><img src="image_1.png" /></figure>
## Definition (Roger Myerson, "Game Theory, Analysis of Conflicts")

"Game theory can be defined as the study of mathematical models of conflict and cooperation between intelligent rational decision-makers. Game theory provides general mathematical techniques for analyzing situations in which two or more individuals make decisions that will influence one another's welfare."

* Branch of optimization

* Multiple actors with different objectives

* Actors interact with each others
Example

► 2 boxers fighting.

► Each of them bet $1 million.

► Whoever wins the game gets all the money...

<figure><img src="image_2.png" /></figure>

<figure><img src="image_3.png" /></figure>

Question: Elements of the Game

What are the player actions and strategies?

What are the players corresponding payoffs?

What are the possible outputs of the game?

What are the players set of information?

How long does a game last?

Are there chance moves?

Are the players rational?
► Alvin Roth (2012, 1951) – experimental GT

► Lloyd Shapley (2012, 1923) – fair sharing, potential games

► Roger B. Myerson (2007, 1951) – eq. in dynamic games

► Leonid Hurwicz (2007, 1917-2008) – incentives

► Eric S. Maskin (2007, 1950) – mechanism design

► Robert J. Aumann (2005, 1930) – correlated equilibria

► Thomas C. Schelling (2005, 1921) – bargaining

► William Vickrey (1996, 1914-1996) – pricing

► Robert E. Lucas Jr. (1995, 1937) – rational expectations

► John C. Harsanyi (1994, 1920-2000) – Bayesian games, eq. selection

► John F. Nash Jr. (1994, 1928) – NE, NBS

► Reinhard Selten (1994, 1930) – Subgame perf. eq., bounded rationality

► Kenneth J. Arrow (1972, 1921) – Impossibility theorem

► Paul A. Samuelson (1970, 1915-2009) – thermodynamics to econ.

(Jorgen Weibull - Chairman 2004-2007)

(more info on http://lcm.csa.iisc.ernet.in/gametheory/nobel.html)
## Economy:

* Pricing mechanisms

* Auctions

## Politics:

* Fight against terrorism

* Negotiation and dispute resolution, bargaining

* Effect of electoral rules to politicians' strategies

## Biology:

* Cancer cells propagation

* Genetics and population evolution

## And many others:

* Evolutionary psychology (social sciences)

* Intellectual right properties (law)

* Policy responses to global warming and climate change...
► Rien à voir avec les jeux vidéos
* Rien à voir avec les jeux vidéos

* Les protagonistes ne sont pas des humains: téléphones, ordinateurs...
* Rien à voir avec les jeux vidéos

* Les protagonistes ne sont pas des humains: téléphones, ordinateurs...

Popularité croissante dans les grands systèmes distribués depuis les années 90 du fait de:

* L'augmentation du nombre des protagonistes

* L'accroissement et la complexification des systèmes

* La dynamicité
* Rien à voir avec les jeux vidéos

* Les protagonistes ne sont pas des humains: téléphones, ordinateurs...

Popularité croissante dans les grands systèmes distribués depuis les années 90 du fait de:

* L'augmentation du nombre des protagonistes

* L'accroissement et la complexification des systèmes

* La dynamicité

⇒ on a besoin de méthodes automatisées pour concevoir, gérer les systèmes et évaluer les performances
1. Individual Versus Collective Interest

* Matrix Games - Nash Equilibria

* Population Games - Wardrop Equilibria

* Conclusion

* Application: Performance Analysis

2. Designing Efficient Control Mechanisms

* Objective: Fair Sharing of Resources

* Direct Method: Protocol Implementation

* Indirect Method: Modifying the game

3. Conclusion
1. Individual Versus Collective Interest

* Matrix Games - Nash Equilibria

* Population Games - Wardrop Equilibria

* Conclusion

* Application: Performance Analysis

2. Designing Efficient Control Mechanisms

* Objective: Fair Sharing of Resources

* Direct Method: Protocol Implementation

* Indirect Method: Modifying the game

3. Conclusion
<table><tr><td></td><td>Prisoner B stays Silent</td><td>Prisoner B Betrays</td></tr><tr><td>A stays Silent</td><td>Each serves 6 months</td><td>Prisoner A: 10 years<br>Prisoner B: goes free</td></tr><tr><td>A Betrays</td><td>Prisoner A goes free<br>Prisoner B: 10 years</td><td>Each serves 5 years</td></tr></table>

What is the best interest of each prisoner?

What is the output (Nash Equilibrium) of the game?
Cost for Prisoner B

(B,S)

<figure><img src="image_4.png" /></figure>

(B,B)

<figure><img src="image_5.png" /></figure>

(S,S)

<figure><img src="image_6.png" /></figure>

(S,B)

<figure><img src="image_7.png" /></figure>

Cost for Prisoner A

What are the
optimal points?

What is the
equilibrium?
<figure><img src="image_8.png" /></figure>

What are the
optimal points?

What is the
equilibrium?
**Definition: (Finite or Matrix) Game.**

* $N$ players, finite number of actions

* Payoffs of players (depend of each other actions and) are real valued

* Stable points are called Nash Equilibria

**Definition: Nash Equilibrium.**

In a NE, no player has incentive to unilaterally modify his strategy.

strategy

<figure><img src="image_9.png" /></figure>

$s^*$ is a Nash equilibrium iff:

$$ \forall p, \forall s_p, u_p(s_1^*, \dots, s_p^*, \dots, s_n^*) \ge u_p(s_1^*, \dots, s_p^*, \dots, s_n^*) $$

payoff

<figure><img src="image_10.png" /></figure>

In a compact form:

$$ \forall p, \forall s_p, u_p(s_{-p}^*, s_p^*) \ge u_p(s_{-p}^*, s_p) $$
Find the Nash equilibria of these games (with pure strategies)

## The prisoner dilemma

<table><thead><tr><th></th><th>collaborate</th><th>deny</th></tr></thead><tbody><tr><th>collaborate</th><td>(1, 1)</td><td>(3, 0)</td></tr><tr><th>deny</th><td>(0, 3)</td><td>(2, 2)</td></tr></tbody></table>
Find the Nash equilibria of these games (with pure strategies)

## The prisoner dilemma

<table><thead><tr><th></th><th>collaborate</th><th>deny</th></tr></thead><tbody><tr><th>collaborate</th><td>(1, 1)</td><td>(3, 0)</td></tr><tr><th>deny</th><td>(0, 3)</td><td>(2, 2)</td></tr><tr><td colspan="3">⇒ not efficient</td></tr></tbody></table>

## Battle of the sexes

<table><thead><tr><th>Paul / Claire</th><th>Opera</th><th>Foot</th></tr></thead><tbody><tr><th>Opera</th><td>(2, 1)</td><td>(0, 0)</td></tr><tr><th>Foot</th><td>(0, 0)</td><td>(1, 2)</td></tr></tbody></table>
Find the Nash equilibria of these games (with pure strategies)

## The prisoner dilemma

<table><thead><tr><th></th><th>collaborate</th><th>deny</th></tr></thead><tbody><tr><th>collaborate</th><td>(1, 1)</td><td>(3, 0)</td></tr><tr><th>deny</th><td>(0, 3)</td><td>(2, 2)</td></tr><tr><td colspan="3">⇒ not efficient</td></tr></tbody></table>

## Battle of the sexes

<table><thead><tr><th>Paul / Claire</th><th>Opera</th><th>Foot</th></tr></thead><tbody><tr><th>Opera</th><td>(2, 1)</td><td>(0, 0)</td></tr><tr><th>Foot</th><td>(0, 0)</td><td>(1, 2)</td></tr><tr><td colspan="3">⇒ not unique</td></tr></tbody></table>
Find the Nash equilibria of these games (with pure strategies)

## The prisoner dilemma

<table><thead><tr><th></th><th>collaborate</th><th>deny</th></tr></thead><tbody><tr><th>collaborate</th><td>(1, 1)</td><td>(3, 0)</td></tr><tr><th>deny</th><td>(0, 3)</td><td>(2, 2)</td></tr><tr><th>⇒ not efficient</th><td></td><td></td></tr></tbody></table>

## Battle of the sexes

<table><thead><tr><th>Paul / Claire</th><th>Opera</th><th>Foot</th></tr></thead><tbody><tr><th>Opera</th><td>(2, 1)</td><td>(0, 0)</td></tr><tr><th>Foot</th><td>(0, 0)</td><td>(1, 2)</td></tr><tr><th>⇒ not unique</th><td></td><td></td></tr></tbody></table>

## Rock-Scisor-Paper

<table><thead><tr><th>1/2</th><th>P</th><th>R</th><th>S</th></tr></thead><tbody><tr><th>P</th><td>(0, 0)</td><td>(1, -1)</td><td>(-1, 1)</td></tr><tr><th>R</th><td>(-1, 1)</td><td>(0, 0)</td><td>(1, -1)</td></tr><tr><th>S</th><td>(1, -1)</td><td>(-1, 1)</td><td>(0, 0)</td></tr></tbody></table>
Find the Nash equilibria of these games (with pure strategies)

## The prisoner dilemma

<table><thead><tr><th></th><th>collaborate</th><th>deny</th></tr></thead><tbody><tr><th>collaborate</th><td>(1, 1)</td><td>(3, 0)</td></tr><tr><th>deny</th><td>(0, 3)</td><td>(2, 2)</td></tr><tr><td colspan="3">⇒ not efficient</td></tr></tbody></table>

## Battle of the sexes

<table><thead><tr><th>Paul / Claire</th><th>Opera</th><th>Foot</th></tr></thead><tbody><tr><th>Opera</th><td>(2, 1)</td><td>(0, 0)</td></tr><tr><th>Foot</th><td>(0, 0)</td><td>(1, 2)</td></tr><tr><td colspan="3">⇒ not unique</td></tr></tbody></table>

## Rock-Scisor-Paper

<table><thead><tr><th>1/2</th><th>P</th><th>R</th><th>S</th></tr></thead><tbody><tr><th>P</th><td>(0, 0)</td><td>(1, -1)</td><td>(-1, 1)</td></tr><tr><th>R</th><td>(-1, 1)</td><td>(0, 0)</td><td>(1, -1)</td></tr><tr><th>S</th><td>(1, -1)</td><td>(-1, 1)</td><td>(0, 0)</td></tr><tr><td colspan="4">⇒ No equilibrium</td></tr></tbody></table>
**Definition: Mixed Strategy Nash Equilibria.**

A mixed strategy for player $i$ is a probability distribution over the set of pure strategies of player $i$.

An equilibrium in mixed strategies is a strategy profile $\sigma^*$ of mixed strategies such that: $\forall p, \forall \sigma_i, u_p(\sigma_{-p}^*, \sigma_p^*) \ge u_p(\sigma_{-p}^*, \sigma_p)$.

**Theorem 1.**

Any finite $n$-person noncooperative game has at least one equilibrium $n$-tuple of mixed strategies.
## Definition: Mixed Strategy Nash Equilibria.

A mixed strategy for player $i$ is a probability distribution over the set of pure strategies of player $i$.

An equilibrium in mixed strategies is a strategy profile $\sigma^*$ of mixed strategies such that: $\forall p, \forall \sigma_i, u_p(\sigma_{-p}^*, \sigma_p^*) \ge u_p(\sigma_{-p}^*, \sigma_p)$.

## Theorem 1.

Any finite $n$-person noncooperative game has at least one equilibrium $n$-tuple of mixed strategies.

## Consequence:

* The players mixed strategies are independent randomizations.

* In a finite game, $u_p(\sigma) = \sum_a (\prod_{p'} \sigma_{p'}(a_{p'})) u_i(a)$.

* In a finite game, $\sigma^*$ is a Nash equilibrium iff $\forall a_i$ in the support of $\sigma_i^*$, $a_i$ is a best response to $\sigma_{-i}^*$.
Find the Nash equilibria of these games (with mixed strategies)

## The prisoner dilemma

<table><thead><tr><th></th><th>collaborate</th><th>deny</th></tr></thead><tbody><tr><th>collaborate</th><td>(1, 1)</td><td>(3, 0)</td></tr><tr><th>deny</th><td>(0, 3)</td><td>(2, 2)</td></tr></tbody></table>
Find the Nash equilibria of these games (with mixed strategies)

## The prisoner dilemma

<table><thead><tr><th></th><th>collaborate</th><th>deny</th></tr></thead><tbody><tr><th>collaborate</th><td>(1, 1)</td><td>(3, 0)</td></tr><tr><th>deny</th><td>(0, 3)</td><td>(2, 2)</td></tr></tbody></table>

⇒ No strictly mixed equilibria

## Battle of the sexes

<table><thead><tr><th>Paul / Claire</th><th>Opera</th><th>Foot</th></tr></thead><tbody><tr><th>Opera</th><td>(2, 1)</td><td>(0, 0)</td></tr><tr><th>Foot</th><td>(0, 0)</td><td>(1, 2)</td></tr></tbody></table>
Find the Nash equilibria of these games (with mixed strategies)

## The prisoner dilemma

<table><thead><tr><th></th><th>collaborate</th><th>deny</th></tr></thead><tbody><tr><th>collaborate</th><td>(1, 1)</td><td>(3, 0)</td></tr><tr><th>deny</th><td>(0, 3)</td><td>(2, 2)</td></tr></tbody></table>

⇒ No strictly mixed equilibria

## Battle of the sexes

<table><thead><tr><th>Paul / Claire</th><th>Opera</th><th>Foot</th></tr></thead><tbody><tr><th>Opera</th><td>(2, 1)</td><td>(0, 0)</td></tr><tr><th>Foot</th><td>(0, 0)</td><td>(1, 2)</td></tr></tbody></table>

$\sigma_1 = (2/3, 1/3)$, $\sigma_2 = (1/3, 2/3)$

## Rock-Scisor-Paper
Find the Nash equilibria of these games (with mixed strategies)

## The prisoner dilemma

<table><thead><tr><th></th><th>collaborate</th><th>deny</th></tr></thead><tbody><tr><th>collaborate</th><td>(1, 1)</td><td>(3, 0)</td></tr><tr><th>deny</th><td>(0, 3)</td><td>(2, 2)</td></tr></tbody></table>

⇒ No strictly mixed equilibria

## Battle of the sexes

<table><thead><tr><th></th><th>Paul / Claire</th><th>Opera</th><th>Foot</th></tr></thead><tbody><tr><th>Opera</th><td>(2, 1)</td><td>(0, 0)</td><td></td></tr><tr><th>Foot</th><td>(0, 0)</td><td>(1, 2)</td><td></td></tr></tbody></table>

$\sigma_1 = (2/3, 1/3)$, $\sigma_2 = (1/3, 2/3)$

## Rock-Scisor-Paper

<table><thead><tr><th>1/2</th><th>P</th><th>R</th><th>S</th></tr></thead><tbody><tr><th>P</th><td>(0, 0)</td><td>(1, -1)</td><td>(-1, 1)</td></tr><tr><th>R</th><td>(-1, 1)</td><td>(0, 0)</td><td>(1, -1)</td></tr><tr><th>S</th><td>(1, -1)</td><td>(-1, 1)</td><td>(0, 0)</td></tr></tbody></table>
Find the Nash equilibria of these games (with mixed strategies)

## The prisoner dilemma

<table><thead><tr><th></th><th>collaborate</th><th>deny</th></tr></thead><tbody><tr><th>collaborate</th><td>(1, 1)</td><td>(3, 0)</td></tr><tr><th>deny</th><td>(0, 3)</td><td>(2, 2)</td></tr></tbody></table>

⇒ No strictly mixed equilibria

## Battle of the sexes

<table><thead><tr><th></th><th>Paul / Claire</th><th>Opera</th><th>Foot</th></tr></thead><tbody><tr><th>Opera</th><td>(2, 1)</td><td>(0, 0)</td><td></td></tr><tr><th>Foot</th><td>(0, 0)</td><td>(1, 2)</td><td></td></tr></tbody></table>

$$ \sigma_1 = (2/3, 1/3), \sigma_2 = (1/3, 2/3) $$

## Rock-Scisor-Paper

<table><thead><tr><th>1/2</th><th>P</th><th>R</th><th>S</th></tr></thead><tbody><tr><th>P</th><td>(0, 0)</td><td>(1, -1)</td><td>(-1, 1)</td></tr><tr><th>R</th><td>(-1, 1)</td><td>(0, 0)</td><td>(1, -1)</td></tr><tr><th>S</th><td>(1, -1)</td><td>(-1, 1)</td><td>(0, 0)</td></tr></tbody></table>

$$ \sigma_1 = \sigma_2 = (1/3, 1/3, 1/3) $$
1. Individual Versus Collective Interest

* Matrix Games - Nash Equilibria

* Population Games - Wardrop Equilibria

* Conclusion

* Application: Performance Analysis

2. Designing Efficient Control Mechanisms

* Objective: Fair Sharing of Resources

* Direct Method: Protocol Implementation

* Indirect Method: Modifying the game

3. Conclusion
**Question:** A flow of users goes from A to B, with rate of 6 (thousands of people / sec). Each driver has two possible routes to go from A to B. Who takes which route?

<figure><img src="image_11.png" /></figure>

* 2 possible routes

* the needed time is a function of the number of cars on the road (congestion)
**Question:** A flow of users goes from A to B, with rate of 6 (thousands of people / sec). Each driver has two possible routes to go from A to B. Who takes which route?

<figure><img src="image_12.png" /></figure>

Which route will one take?

The one with minimum cost
**Question:** A flow of users goes from A to B, with rate of 6 (thousands of people / sec). Each driver has two possible routes to go from A to B. Who takes which route?

<figure><img src="image_13.png" /></figure>

Which route will one take?

The one with minimum cost

Cost of route "north":
**Question:** A flow of users goes from A to B, with rate of 6 (thousands of people / sec). Each driver has two possible routes to go from A to B. Who takes which route?

<figure><img src="image_14.png" /></figure>

Which route will one take?

The one with minimum cost

Cost of route "north":

$$10 * x + (x + 50) = 11 * x + 50$$
**Question:** A flow of users goes from A to B, with rate of 6 (thousands of people / sec). Each driver has two possible routes to go from A to B. Who takes which route?

<figure><img src="image_15.png" /></figure>

Which route will one take?

The one with minimum cost

Cost of route "north":

$$10 * x + (x + 50) = 11 * x + 50$$

Cost of route "south":
**Question:** A flow of users goes from A to B, with rate of 6 (thousands of people / sec). Each driver has two possible routes to go from A to B. Who takes which route?

<figure><img src="image_16.png" /></figure>

Which route will one take?

The one with minimum cost

Cost of route "north":

$$10 * x + (x + 50) = 11 * x + 50$$

Cost of route "south":

$$(y + 50) + 10 * y = 11 * y + 50$$
**Question:** A flow of users goes from A to B, with rate of 6 (thousands of people / sec). Each driver has two possible routes to go from A to B. Who takes which route?

<figure><img src="image_17.png" /></figure>

**Which route will one take?**

The one with minimum cost

**Cost of route "north":**

$$10 * x + (x + 50) = 11 * x + 50$$

**Cost of route "south":**

$$(y + 50) + 10 * y = 11 * y + 50$$

**Constraint:** $x + y = 6$
**Question:** A flow of users goes from A to B, with rate of 6 (thousands of people / sec). Each driver has two possible routes to go from A to B. Who takes which route?

<figure><img src="image_18.png" /></figure>

**Which route will one take?**

The one with minimum cost

**Cost of route "north":**

$$10 * x + (x + 50) = 11 * x + 50$$

**Cost of route "south":**

$$(y + 50) + 10 * y = 11 * y + 50$$

**Constraint:** $x + y = 6$

**Conclusion?** What if everyone makes the same reasoning?
**Question:** A flow of users goes from A to B, with rate of 6 (thousands of people / sec). Each driver has two possible routes to go from A to B. Who takes which route?

<figure><img src="image_19.png" /></figure>

**Which route will one take?**

The one with minimum cost

**Cost of route "north":**

$$10 * x + (x + 50) = 11 * x + 50$$

**Cost of route "south":**

$$(y + 50) + 10 * y = 11 * y + 50$$

**Constraint:** $x + y = 6$

**Conclusion? What if everyone makes the same reasoning?**

We get $x = y = 3$ and everyone receives 83
A new road is opened! What happens?

<figure><img src="image_20.png" /></figure>
A new road is opened! What happens?

If no one takes it, it cost is

<figure><img src="image_21.png" /></figure>
A new road is opened! What happens?

If no one takes it, it cost is 70! so
rational users will take it... 😊

<figure><img src="image_22.png" /></figure>
A new road is opened! What happens?

<figure><img src="image_23.png" /></figure>

If no one takes it, it cost is 70! so
rational users will take it... 😊

Cost of route "north":
A new road is opened! What happens?

<figure><img src="image_24.png" /></figure>

If no one takes it, it cost is 70! so
rational users will take it... 😊

Cost of route “north”:

$$10 * (x + z) + (x + 50) = 11 * x + 50 + 10 * z$$
A new road is opened! What happens?

<figure><img src="image_25.png" /></figure>

If no one takes it, it cost is 70! so
rational users will take it... 😊

Cost of route “north”:

$$10 * (x + z) + (x + 50) =$$

$$11 * x + 50 + 10 * z$$

Cost of route “south”:
A new road is opened! What happens?

<figure><img src="image_26.png" /></figure>

If no one takes it, it cost is 70! so
rational users will take it... 😊

Cost of route “north”:

$$10 * (x + z) + (x + 50) =$$

$$11 * x + 50 + 10 * z$$

Cost of route “south”:

$$11 * y + 50 + 10 * z$$
A new road is opened! What happens?

<figure><img src="image_27.png" /></figure>

If no one takes it, it cost is 70! so
rational users will take it... 😊

Cost of route “north”:

$$10 * (x + z) + (x + 50) =$$

$$11 * x + 50 + 10 * z$$

Cost of route “south”:

$$11 * y + 50 + 10 * z$$

Cost of “new” route:
A new road is opened! What happens?

<figure><img src="image_28.png" /></figure>

If no one takes it, it cost is 70! so
rational users will take it... 😊

Cost of route “north”:

$$10 * (x + z) + (x + 50) =$$

$$11 * x + 50 + 10 * z$$

Cost of route “south”:

$$11 * y + 50 + 10 * z$$

Cost of “new” route:

$$10 * x + 10 * y + 21 * z + 10$$
A new road is opened! What happens?

<figure><img src="image_29.png" /></figure>

If no one takes it, it cost is 70! so
rational users will take it... 😊

**Cost of route “north”:**

$$10 * (x + z) + (x + 50) =$$

$$11 * x + 50 + 10 * z$$

**Cost of route “south”:**

$$11 * y + 50 + 10 * z$$

**Cost of “new” route:**

$$10 * x + 10 * y + 21 * z + 10$$

**Conclusion?**

We get $x = y = z = 2$ and
everyone gets a cost of **92**!
In le New York Times, 25 Dec., 1990, Page 38, What if They Closed 42d Street and Nobody Noticed?, By GINA KOLATA:

ON Earth Day this year, New York City's Transportation Commissioner decided to close 42d Street, which as every New Yorker knows is always congested. "Many predicted it would be doomsday," said the Commissioner, Lucius J. Riccio. "You didn't need to be a rocket scientist or have a sophisticated computer queuing model to see that this could have been a major problem." But to everyone's surprise, Earth Day generated no historic traffic jam. Traffic flow actually improved when 42d Street was closed.
1. Individual Versus Collective Interest

* Matrix Games - Nash Equilibria

* Population Games - Wardrop Equilibria

* Conclusion

* Application: Performance Analysis

2. Designing Efficient Control Mechanisms

* Objective: Fair Sharing of Resources

* Direct Method: Protocol Implementation

* Indirect Method: Modifying the game

3. Conclusion
Prisoner Dilemma / Braess paradox show:

* Inherent conflict between **individual** interest and **global** interest

* Inherent conflict between **stability** and **optimality**

Typical problem in economy: free-market economy versus regulated economy.
Prisoner Dilemma / Braess paradox show:

* Inherent conflict between **individual** interest and **global** interest

* Inherent conflict between **stability** and **optimality**

Typical problem in economy: free-market economy versus regulated economy.

Suppose that you are a network operator. The different users compete to access the different system resources. Should you intervene?

* NO if the Nash Equilibria exhibit good performance

* YES otherwise
"Free-Market":

<figure><img src="image_30.png" /></figure>
## "Regulated Market":

<figure><img src="image_31.png" /></figure>
1. Individual Versus Collective Interest

* Matrix Games - Nash Equilibria

* Population Games - Wardrop Equilibria

* Conclusion

* Application: Performance Analysis

2. Designing Efficient Control Mechanisms

* Objective: Fair Sharing of Resources

* Direct Method: Protocol Implementation

* Indirect Method: Modifying the game

3. Conclusion
* Multiple applications execute concurrently on heterogeneous platforms and *compete* for CPU and network resources.

* A *fair sharing* of resources amongst users is done at the *system layer* (network, OS).

* We analyze the behavior of *non-cooperative schedulers* that maximize their own utility.

Master-worker platform:

<figure><img src="image_32.png" /></figure>

Applications' profiles:

<figure><img src="image_33.png" /></figure>

$A_1$

<figure><img src="image_34.png" /></figure>

$A_2$

<figure><img src="image_35.png" /></figure>

$A_3$

Such applications are typical *desktop grid applications* (SETI@home, Einstein@Home, processing data of the Large Hadron Collider)...
A routing problem is a triplet:

► A graph $G = (N, A)$ (the network)

► A set of flows $d_k, k \in K$ and $K \subset N \times N$ (user demands)

► latency funtions $\ell_a$ for each link

<figure><img src="image_36.png" /></figure>

**Theorem 2.**

In networks with affine costs
[Roughgarden & Tardos,
2002],

$$C^{WE} \leq \frac{4}{3} C^{SO}.$$

⇒ In affine routing,
selfishness leads to a near
optimal point.
Suppose that the system could be in 2 states $w_1$ and $w_2$, with probability $P(w_1) = P(w_2) = 1/2$.

<table><thead><tr><th>(w<sub>1</sub>)</th><th>a</th><th>b</th></tr></thead><tbody><tr><th>a</th><td>(0, 0)</td><td>(6, -3)</td></tr><tr><th>b</th><td>(-3, 6)</td><td>(5, 5)</td></tr></tbody></table>

<table><thead><tr><th>(w<sub>2</sub>)</th><th>a</th><th>b</th></tr></thead><tbody><tr><th>a</th><td>(-20, -20)</td><td>(-7, -16)</td></tr><tr><th>b</th><td>(-16, -7)</td><td>(-5, -5)</td></tr></tbody></table>

What is the Nash Equilibria if:

* No player knows the system's state:

* Both players are informed:

* Only player 1 knows:
Suppose that the system could be in 2 states $w_1$ and $w_2$, with probability $P(w_1) = P(w_2) = 1/2$.

<table><thead><tr><th>(w<sub>1</sub>)</th><th>a</th><th>b</th></tr></thead><tbody><tr><th>a</th><td>(0, 0)</td><td>(6, -3)</td></tr><tr><th>b</th><td>(-3, 6)</td><td>(5, 5)</td></tr></tbody></table>

<table><thead><tr><th>(w<sub>2</sub>)</th><th>a</th><th>b</th></tr></thead><tbody><tr><th>a</th><td>(-20, -20)</td><td>(-7, -16)</td></tr><tr><th>b</th><td>(-16, -7)</td><td>(-5, -5)</td></tr></tbody></table>

What is the Nash Equilibria if:

* No player knows the system's state:
  EN: (b, b), utility: (0, 0)

* Both players are informed:
  EN: ((a, a)|w1), ((b, b)|w2), utilité: (-2.5, -2.5)

* Only player 1 knows:
  EN: ((a, a)|w1), ((b, a)|w2), utilité: (-8, -3, 5)

Information can be detrimental!
1. Individual Versus Collective Interest

* Matrix Games - Nash Equilibria

* Population Games - Wardrop Equilibria

* Conclusion

* Application: Performance Analysis

2. Designing Efficient Control Mechanisms

* Objective: Fair Sharing of Resources

* Direct Method: Protocol Implementation

* Indirect Method: Modifying the game

3. Conclusion
1. Individual Versus Collective Interest

* Matrix Games - Nash Equilibria

* Population Games - Wardrop Equilibria

* Conclusion

* Application: Performance Analysis

2. Designing Efficient Control Mechanisms

* Objective: Fair Sharing of Resources

* Direct Method: Protocol Implementation

* Indirect Method: Modifying the game

3. Conclusion
* Aims at predicting the outcome of a bargain between 2 (or more) players

* The players are bargaining over a set of goods

* To each good is associated for each player a utility (for instance real valued)

Assumptions:

* Players have identical bargaining power

* Players have identical bargaining skills

Then, players will eventually agree on an point considered as “fair” for both of them.
Let $S$ be a feasible set, closed, convex, $(u^*, v^*)$ a point in this set, enforced if no agreement is reached.

A fair solution is a point $\phi(S, u^*, v^*)$ satisfying the set of axioms:

1. (Individual Rationality) $\phi(S, u^*, v^*) \geq (u^*, v^*)$ (componentwise)

2. (Feasibility) $\phi(S, u^*, v^*) \in S$

3. (Pareto-Optimality) $\forall (u, v) \in S, (u, v) \geq \phi(S, u^*, v^*) \rightarrow (u, v) = \phi(S, u^*, v^*)$

4. (Independence of Irrelevant Alternatives) $\phi(S, u^*, v^*) \in T \subset S \Rightarrow \phi(S, u^*, v^*) = \phi(T, u^*, v^*)$

5. (Independence of Linear Transformations) Let $F(u, v) = (\alpha_1 u + \beta_1, \alpha_2 v + \beta_2)$, $T = F(S)$, then $\phi(T, F(u^*, v^*)) = F(\phi(S, u^*, v^*))$

6. (Symmetry) If $S$ is such that $(u, v) \in S \Leftrightarrow (v, u) \in S$ and $u^* = v^*$ then $\phi(S, u^*, v^*) \stackrel{\text{def}}{=} (a, b)$ is such that $a = b$
## Proposition: Nash Bargaining Solution

There is a unique solution function $\phi$ satisfying all axioms:

$$ \phi(S, u^*, v^*) = \max_{u,v}(u - u^*)(v - v^*) $$

## Proof.

**First case:** Positive quadrant
right isosceles triangle

**Second Case:** General case

<figure><img src="image_37.png" /></figure>

<figure><img src="image_38.png" /></figure>
## Proposition: Nash Bargaining Solution

There is a unique solution function $\phi$ satisfying all axioms:

$$ \phi(S, u^*, v^*) = \max_{u,v}(u - u^*)(v - v^*) $$

## Proof.

**First case:** Positive quadrant
right isosceles triangle

**Second Case:** General case

<figure><img src="image_39.png" /></figure>

<figure><img src="image_40.png" /></figure>
## Proposition: Nash Bargaining Solution

There is a unique solution function $\phi$ satisfying all axioms:

$$ \phi(S, u^*, v^*) = \max_{u,v}(u - u^*)(v - v^*) $$

## Proof.

**First case:** Positive quadrant
right isosceles triangle

**Second Case:** General case

<figure><img src="image_41.png" /></figure>

<figure><img src="image_42.png" /></figure>
## Proposition: Nash Bargaining Solution

There is a unique solution function $\phi$ satisfying all axioms:

$$ \phi(S, u^*, v^*) = \max_{u,v}(u - u^*)(v - v^*) $$

## Proof.

**First case:** Positive quadrant
right isosceles triangle

**Second Case:** General case

<figure><img src="image_43.png" /></figure>
## Proposition: Nash Bargaining Solution

There is a unique solution function $\phi$ satisfying all axioms:

$$ \phi(S, u^*, v^*) = \max_{u,v}(u - u^*)(v - v^*) $$

## Proof.

**First case:** Positive quadrant
right isosceles triangle

**Second Case:** General case

<figure><img src="image_44.png" /></figure>
## Proposition: Nash Bargaining Solution

There is a unique solution function $\phi$ satisfying all axioms:

$$ \phi(S, u^*, v^*) = \max_{u,v}(u - u^*)(v - v^*) $$

## Proof.

**First case:** Positive quadrant
right isosceles triangle

**Second Case:** General case

<figure><img src="image_45.png" /></figure>

<figure><img src="image_46.png" /></figure>

<figure><img src="image_47.png" /></figure>

<figure><img src="image_48.png" /></figure>
## Proposition: Nash Bargaining Solution

There is a unique solution function $\phi$ satisfying all axioms:

$$ \phi(S, u^*, v^*) = \max_{u,v}(u - u^*)(v - v^*) $$

## Proof.

**First case:** Positive quadrant
right isosceles triangle

**Second Case:** General case

<figure><img src="image_49.png" /></figure>

<figure><img src="image_50.png" /></figure>
## Proposition: Nash Bargaining Solution

There is a unique solution function $\phi$ satisfying all axioms:

$$ \phi(S, u^*, v^*) = \max_{u,v}(u - u^*)(v - v^*) $$

## Proof.

**First case:** Positive quadrant
right isosceles triangle

**Second Case:** General case

<figure><img src="image_51.png" /></figure>

<figure><img src="image_52.png" /></figure>
## Proposition: Nash Bargaining Solution

There is a unique solution function $\phi$ satisfying all axioms:

$$ \phi(S, u^*, v^*) = \max_{u,v}(u - u^*)(v - v^*) $$

## Proof.

**First case:** Positive quadrant
right isosceles triangle

**Second Case:** General case

<figure><img src="image_53.png" /></figure>

<figure><img src="image_54.png" /></figure>
## Proposition: Nash Bargaining Solution

There is a unique solution function $\phi$ satisfying all axioms:

$$ \phi(S, u^*, v^*) = \max_{u,v}(u - u^*)(v - v^*) $$

## Proof.

**First case:** Positive quadrant
right isosceles triangle

**Second Case:** General case

<figure><img src="image_55.png" /></figure>

<figure><img src="image_56.png" /></figure>
❶ Individual Rationality

❷ Feasibility

❸ Pareto-Optimality

❹ Independence of
Linear
Transformations

❺ Symmetry
④ Individual Rationality

⑤ Feasibility

⑥ Pareto-Optimality

⑦ Independence of
Linear
Transformations

⑧ Symmetry

$$+ \left\{ \begin{array}{ll} \textcircled{4} \text{ Independant to irrelevant alternatives Nash (NBS) / Proportional Fairness} & \displaystyle \prod (u_i - u_i^d) \\ \textcircled{4} \text{ Monotony} & \text{Raiffa-Kalai-Smorodinsky /} \\ & \max-\min \\ & \text{Recursively } \max\{u_i | \forall j, u_i \le u_j\} \\ \textcircled{4} \text{ Inverse Monotony} & \text{Thomson / global Optimum} \\ & \text{(Social welfare)} \\ & \max \sum u_i \end{array} \right. $$
1. Individual Versus Collective Interest

* Matrix Games - Nash Equilibria

* Population Games - Wardrop Equilibria

* Conclusion

* Application: Performance Analysis

2. Designing Efficient Control Mechanisms

* Objective: Fair Sharing of Resources

* Direct Method: Protocol Implementation

* Indirect Method: Modifying the game

3. Conclusion
Imagine a system with:

* $n$ individual users aiming at optimizing their throughput $x_n$

* A routing matrix $A$ giving the set of paths followed by each connection: $A_{i,j} = \begin{cases} 1 & \text{if connection } i \text{ uses link } j \\ 0 & \text{otherwise} \end{cases}$

* Capacity constraints on each link $C_l$

* What is the Nash equilibrium of the game? What protocol does it correspond to?

* How can we implement fairness in a distributed way?
## Example: A simple network with 3 links

<figure><img src="image_57.png" /></figure>

$$n_{0 \to 2} = 2, n_{1 \to 2} = 3, n_{2 \to 3} = 4$$

Throughput of flow i:

$$ \frac{\lambda_i \cdot \text{capa}}{\lambda_1 + \lambda_2} $$
### Hypothesis:

Ring topology network, $N$ identical links with capacity $C$.

Source $i$ uses links $i$ and $i + 1 \pmod{N}$.

<figure><img src="image_58.png" /></figure>

### Link equations:

$$ egin{cases} \lambda_2' = \frac{\lambda_2 C}{\lambda_2 + \lambda_1'} = \frac{C}{1 + \lambda_1'/\lambda_2} \\ \lambda_2'' = \frac{\lambda_2' C}{\lambda_3 + \lambda_2'} = \frac{C^2}{C + \lambda_3(1 + \frac{\lambda_1'}{\lambda_2})} \end{cases} $$
<figure><img src="image_59.png" /></figure>

(namUDP.mpeg)

Hypothesis $\lambda \gg C$

Exit throughput of flow i:

$$ \lambda'' = \frac{C^2}{C + \lambda(1 + \lambda'/\lambda)}, \quad \text{and} $$

$$ \frac{\lambda'}{\lambda} = \frac{1}{2} \left( \sqrt{1 + \frac{4C}{\lambda}} - 1 \right) \sim \frac{C}{\lambda} $$

Then $\lambda'' \sim \frac{C^2}{\lambda}$
This is network collapse:

* The network is full

* Little or no useful information is going through (here

$$\lambda'' \sim \frac{C^2}{\lambda} \rightarrow_{\lambda \rightarrow \infty} 0)$$

Observed in 1984 (cf RFC 896) with TCP flows: the protocol detects a loss, so it retransmits the packet, hence increasing its incoming throughput...

Since then a flow control mechanism has been implemerted in
TCP 😊

Why hadn't we observe this kind of phenomena before with
telephony?
* N individual users aiming at optimizing their throughput $x_n$

* A routing matrix $A$ giving the set of paths followed by each connection: $A_{i,j} = \begin{cases} 1 & \text{if connection } i \text{ uses link } j \\ 0 & \text{otherwise} \end{cases}$

* Capacity constraints on each link $C_\ell$

* User utility function $f_n: \mathbb{R}^+ \to \mathbb{R}^+$ that are increasing and strictly concave.

The flow control problem is:

<figure><img src="image_60.png" /></figure>
4 connections / 3 links.

<figure><img src="image_61.png" /></figure>

$$ \begin{cases} x_1 + x_0 \le 1, \\ x_2 + x_0 \le 1, \\ x_3 + x_0 \le 1. \end{cases} $$

⇒ 4 variables and 3 (in)equalities.

How to choose $x_0$ among the Pareto optimal points?

<figure><img src="image_62.png" /></figure>

(Nota: in this case the utility set is the same as the strategy set)
4 connections / 3 links.

<figure><img src="image_63.png" /></figure>

$$ \begin{cases} x_1 + x_0 \le 1, \\ x_2 + x_0 \le 1, \\ x_3 + x_0 \le 1. \end{cases} $$

⇒ 4 variables and 3 (in)equalities.

How to choose $x_0$ among the Pareto
optimal points?

<figure><img src="image_64.png" /></figure>

$$ \begin{cases} x_0 = 0.5, \\ x_1 = x_2 = x_3 = 0.5 \end{cases} \quad \text{Max-Min fairness} $$

$$ \begin{cases} x_0 = 0, \\ x_1 = x_2 = x_3 = 1 \end{cases} \quad \text{Social Optimum} $$

$$ \begin{cases} x_0 = 0.25, \\ x_1 = x_2 = x_3 = 0.75 \end{cases} \quad \text{Proportionnal Fairness} $$

(Nota: in this case the utility set is the same as the strategy set)
* $N$ individual users aiming at optimizing their throughput $x_n$

* A routing matrix $A$ giving the set of paths followed by each connection: $A_{i,j} = \begin{cases} 1 & \text{if connection } i \text{ uses link } j \\ 0 & \text{otherwise} \end{cases}$

* Capacity constraints on each link $C_\ell$

* User utility function $f_n: \mathbb{R}^+ \to \mathbb{R}^+$ that are increasing and strictly concave.

The flow control problem is:

<figure><img src="image_65.png" /></figure>

How to (efficiently and in a distributed manner) solve this?
Flow control algorithm: AIMD (Additive Increase Multiplicative Decrease)

* Window $w_n$: number of packets of a connection that can be outstanding at any time (i.e. for which no ack has been received yet)

* The Round Trip Time (RTT$_n$) of connection n (supposed independent of the load)

* Additive increase: at each RTT, increase the window size by 1 if there is no mark

* Multiplicative decrease: at each marked packet, halve the window size
Flow control algorithm: AIMD (Additive Increase Multiplicative Decrease)

► Source rate: $x_n(t) = w_n(t)/RTT_n$

► Loss probability: $q_n = 1 - \prod_{\ell, A_{n,\ell}=1} (1-p_\ell) \approx \sum_{\ell, A_{n,\ell}=1} p_\ell$

► Between two packet emissions:

$$ \Delta t \approx \frac{1}{x_n(t)} = \frac{RTT_n}{w_n(t)} $$

$$ w_n(t + \Delta t) - w_n(t) \approx \frac{1}{w_n(t)} \underbrace{(1 - q_n(t))}_{\text{received packet}} - \frac{w_n(t)}{2} \underbrace{q_n(t)}_{\text{lost packet}} $$

$$ \Rightarrow \frac{dx_n}{dt}(t) = \frac{1 - q_n(t)}{RTT_n^2} - \frac{1}{2}q_n(t)x_n^2(t) $$
Hence, the AIMD flow control of TCP follows dynamics:

$$ \frac{dx_n}{dt}(t) = \frac{1 - q_n(t)}{RTT_n^2} - \frac{1}{2}q_n(t)x_n^2(t) $$

Using tools from control theory (Lyapunov function), one can establish that it maximizes over $x$ function

$$ W(x) = \sum_n \underbrace{\frac{\sqrt{2}}{RTT_n} \operatorname{atan}\left(\frac{x_n RTT_n}{\sqrt{2}}\right)}_{\text{Utility } f_n(x_n)} - \sum_{\ell} \underbrace{\int_0^{\sum_m A_{m,\ell} x_m} p_{\ell}(y) dy}_{\text{link cost } LC_{\ell}} $$
Hence, the AIMD flow control of TCP follows dynamics:

$$ \frac{dx_n}{dt}(t) = \frac{1 - q_n(t)}{RTT_n^2} - \frac{1}{2}q_n(t)x_n^2(t) $$

Using tools from control theory (Lyapunov function), one can establish that it maximizes over $x$ function

$$ W(x) = \sum_n \underbrace{\frac{\sqrt{2}}{RTT_n} \operatorname{atan}\left(\frac{x_n RTT_n}{\sqrt{2}}\right)}_{\text{Utility } f_n(x_n)} - \sum_{\ell} \underbrace{\int_0^{\sum_m A_{m,\ell} x_m} p_{\ell}(y) dy}_{\text{link cost } LC_{\ell}} $$
1. Individual Versus Collective Interest

* Matrix Games - Nash Equilibria

* Population Games - Wardrop Equilibria

* Conclusion

* Application: Performance Analysis

2. Designing Efficient Control Mechanisms

* Objective: Fair Sharing of Resources

* Direct Method: Protocol Implementation

* Indirect Method: Modifying the game

3. Conclusion
<figure><img src="image_66.png" /></figure>

Mobile

<figure><img src="image_67.png" /></figure>

<figure><img src="image_68.png" /></figure>

<figure><img src="image_69.png" /></figure>

<figure><img src="image_70.png" /></figure>

<figure><img src="image_71.png" /></figure>

<figure><img src="image_72.png" /></figure>

Base station
?

<figure><img src="image_73.png" /></figure>

Mobile

<figure><img src="image_74.png" /></figure>

<figure><img src="image_75.png" /></figure>

<figure><img src="image_76.png" /></figure>

Base station
<figure><img src="image_77.png" /></figure>
<figure><img src="image_78.png" /></figure>

<figure><img src="image_79.png" /></figure>

<figure><img src="image_80.png" /></figure>
## Context

* The cells of different technologies overlap (LTE, WiFi, Wimax, etc)

* Mobiles are multi-technology compatible

* Protocols:
  * Multi-homing: having several connections active at once
  * Vertical Handover: to switch from one technology to another

## Goal

Find an association algorithm between mobiles and base stations that is:

* distributed

* optimal
► A set $\mathcal{N}$ of mobiles.

► A set $\mathcal{I}_n$ of Base Stations (BS) that $n \in \mathcal{N}$ can connect to.

► $s_n \in \mathcal{I}_n$ choice of mobile $n$.

► $\ell^i$: load (vector) of BS $i$: $\ell_n^i = \begin{cases} 1 & \text{if } s_n = 1 \\ 0 & \text{else.} \end{cases}$

► $u_n(\ell^i)$: throughput of mobile $n$ given the load of cell $i$.
► A set $\mathcal{N}$ of mobiles.

► A set $\mathcal{I}_n$ of Base Stations (BS) that $n \in \mathcal{N}$ can connect to.

► $s_n \in \mathcal{I}_n$ choice of mobile $n$.

► $\ell^i$: load (vector) of BS $i$: $\ell_n^i = \begin{cases} 1 & \text{if } s_n = 1 \\ 0 & \text{else.} \end{cases}$

► $u_n(\ell^i)$: throughput of mobile $n$ given the load of cell $i$.

Association game.

$(\mathcal{N}, \mathcal{I}, \mathcal{U})$
Original Game.

$(N, I, U)$

New Game.

$(N, I, R)$

How to design games so as to serve one's purpose is the object of
**mechanism design**
Step 1: Creating Fake Games

<figure><img src="image_81.png" /></figure>

How to design games so as to serve one's purpose is the object of
mechanism design
Step 2: Choosing a dynamics converging to the Nash equilibria

1. We switch to mixed strategies:

► $q_{n,i} \stackrel{\text{def}}{=} \mathbb{P}[s_n = i]$.

► $q_n = (q_{n,i})_{i \in \mathcal{I}_n}$: **strategy** of mobile $n$.

2. We choose the replicator dynamics:

$$ \frac{dq_{n,i}}{dt} = q_{n,i} \left( \bar{u}_{n,i}(q) - \sum_{j \in \mathcal{I}_n} q_{n,j} \bar{u}_{n,j}(q) \right). $$

expected utility on $i$

average expected utility

Theorem: (in potential games):

► The replicator dynamics converges to a set of Nash equilibria.

► Objective function is increasing along the trajectories (**Lyapunov function**).
Algorithm: stochastic approximation of the replicator dynamics

For all $n \in \mathcal{N}$:

► Choose initial strategy $q_n(0)$.

repercussion utility

► At each time epoch $t$:

► Choose $s_n$ according to $q_n(t)$.

► Update: $q_n(t+1) = q_n(t) + \epsilon r_n(\ell^{s_n}(s)) (1_{s_n=i} - q_{n,i}(t))$.

constant step size
$$ \begin{cases} 1 & \text{if } s_n = i \\ 0 & \text{otherwise} \end{cases} $$

<figure><img src="image_82.png" /></figure>

Simple computation for the mobile.
<figure><img src="image_83.png" /></figure>

Evolution of one user's strategy that can connect to 5 cells.
<figure><img src="image_84.png" /></figure>

Arrivals and departures: evolution of the global throughput with white Gaussian noise.
1. Individual Versus Collective Interest

* Matrix Games - Nash Equilibria

* Population Games - Wardrop Equilibria

* Conclusion

* Application: Performance Analysis

2. Designing Efficient Control Mechanisms

* Objective: Fair Sharing of Resources

* Direct Method: Protocol Implementation

* Indirect Method: Modifying the game

3. Conclusion
**Jeux** : situations de décisions interactives dans lesquelles l'utilité (bien-être) de chaque individu dépend des décisions des autres.

**Théorie des jeux** : théorie de la décision (rationnelle) d'agents stratégiquement interdépendants

**Jeux coopératifs**

Vision globale
consensus efficace et équitable

**Jeux Non-cooperatifs**

Comportement individuel
converge (ou non) vers un équilibre

**Mécanismes:**

recherche de règles du jeu pour obtenir des comportements satisfaisants.
Il existe bien d'autres modèles de jeux :

* **Jeux répétés**: on rejoue plusieurs fois le même jeu (ex. le tarot en 100 points). Le but est d'alors maximiser le revenu moyen.

* **Jeux dynamiques**: les joueurs jouent à tour de rôle. L'ensem-ble des stratégies dépend alors des étapes précédentes du jeu.

* **Jeux évolutionnaires**: inspiré des approches Darwinistes. Se compose d'un jeu interne (entre les individus) et d'un jeu externe (le processus évolutionnaire).

* **Jeux stochastiques**: jeu dynamique (=évoluant dans le temps) dans lequel les transitions sont probabilistes: le nouvel état est déterminé par une distribution de probabilité dépendant de l'état courant et des actions choisies (Markov Decision Process).

* **Équilibres de Stackelberg**: jeu entre deux joueurs aux rôles asymétriques: un meneur et un suiveur (utilisé par exemple dans les mécanismes de tarification des e-services). Autres modèles liés: compétition de Bertrand, compétition de Cournot.
* **Mechanism design:** how to design rules of a game so as to achieve a specific outcome, even though each player is selfish.

* **Auctions:** resource allocation in P2P, frequency allocation in wireless.

* **Impact of non-cooperative players in a cooperative environment:** free-riders of P2P, UDP clients in TCP networks.

* **Fair division or cake cutting problem:** how to divide resource such that all recipients believe that they have received their fair share

* **Election:** Plurality voting systems are not necessarily fair.

* **Stable marriages:** Problem of finding a matching.

* **Super-modular games:** utility functions are such that higher choices by one player make one's own strategy higher look relatively more desirable.

* **Games with incomplete information or Bayesian games:** some player have private information about something relevant to their decision making

* **Games with imperfect information:** players do not perfectly observe the actions of other players.