Transcript Presentation

Game Theory and Computer Networks:
a useful combination?
Christos Samaras, COMNET Group, DUTH
Game Theory:
general theory of rational behavior
What constitutes/characterizes a game:
- group of players
(more than 1 decision-maker)
- interaction
(interdependence: when a player acts, at least one other player is affected)
- strategic
(a player takes this interdependence into account before deciding what action
to take)
- rational
(a player chooses her best action)
consider...
some players that simultaneously transmit data
(a transport entity = a player)
they all share the same network channel
(low bandwidth)
each player chooses a strategy
(e.g. conservative/aggressive behavior)
every player is rational
Let the game begin !
(but... what are the rules of the game?)
WHO…
WHAT…
GAME
RULES
they are playing
(available strategies)
is playing (group of players)
WHEN…
each player gets to play
(order of playing)
HOW
MUCH…
they stand to gain or lose
In game theory it is standard to
assume COMMON KNOWLEDGE
about the rules
Visiting again our Internet Game, we have some answers:
WHO… ?
a transport protocol (= an Internet player)
WHAT… ?
transmit data
(aggressively, conservatively, etc.)
WHEN… ?
HOW MUCH… ?
no turns, no rounds…
(asynchronously)
gain? lose?
Utility Function
Utility Function (= Payoff Function)
…specifies the PAYOFF to a player for every possible strategy combination that
he – and the others – might pick. (Internet game: a player's payoff depends on
his transmission rate and congestion/delay experienced by his packets)
The independent variable in such a function is the player’s strategy.
So… what’s the best strategy?
Strategy_3
100
80
60
Payoff
40
20
0
0
1
2
3
Strategy
4
5
Dominant Strategy: strategy Si strongly dominates all
other strategies of player i if the payoff to Si is strictly greater
than the payoff to any other strategy, regardless of which
strategy is chosen by the other player(s). (the best strategy)
Dominance Solvability: a strategy S1 is dominated by
Solutions...
(to a game)
another strategy S2, if the latter does at least as well as S1
against every strategy of the other players, and against some
it does strictly better. (try to find an undominated strategy: it’s
a good choice)
Nash Equilibrium: a player selects the best strategy
(which yields him the highest payoff possible) assuming what
his opponents' strategy choice will be. A strategy combination
(which comprises a strategy choice for each player) is a
Nash equilibrium if each player’s strategy is a best response
against his opponents’ choices in that combination.
Game Variations
Extensive Games
... players take turns; the possible actions a player can take on his turn depend on the
previous actions taken by himself and the other players
Repeated Games
... a standard game that is played repeatedly
Signaling Games
... the players can signal each other and share some of their intended play, or private
information
Bargaining Games
... includes states for making binding offers which the other player(s) can reject or accept
Games with Incomplete Information
... the players have to take actions without having full information on the different factors
that influence their utility
Internet Equilibrium
Game: Internet congestion control
Some characteristics of the “Internet Game”:
- repeated games
- distributed environment
- conditions and number of players change rapidly
Internet equilibrium is
not achieved by rational contemplation
but by interaction and adaptation
...in an environment where conditions (and player populations) change rapidly
(and in which changes in strategies incur costs).
Nash equilibrium
… is not (always) the solution to look for
Why?
efficiency, fairness are NOT GUARANTEED by Nash equilibrium
actually, a standard solution concept (like Nash equilibrium)
DOES NOT APPLY to an asynchronous and distributed
environment like the Internet
MORE SOPHISTICATED concepts of equilibria are
more appropriate for the context of the Internet
A "perfect" design:
Given desired goals, design a game
(strategy sets and payoffs) in such a
clever way that individual players,
motivated solely by self-interest, end up
achieving the designer's goals.
A (more or less) tangible goal:
Develop a reasonably faithful game-theoretic model of Internet congestion control for
which (an approximation of) TCP/IP is a Nash equilibrium.
To be defined...
-
PAYOFF to each player (for instance: a player tries more but gains less)
what kind of PENALTY for selfish/greedy players?
WHO is responsible for penalizing a player? and HOW? (network: regulating role?)
desired GOALS:
1. for the network/Internet (better bandwidth utilization?
lower delays provision? fairness above all?)
2. for the players (better throughput/goodput? less packet losses/packet
retransmissions? smooth data transfer?)
Some facts about the Internet Congestion Game
• not a "common knowledge" game
• asynchronous, repeated games in a distributed environment
• payoff function not known (nor the payoff functions of the opponents)
• little a priori info (about other players/payoff function(s))
• little or no knowledge of the underlying network topology
• conditions change constantly
what next?
The aforementioned scheme calls for network rules and actions
(which will motivate the behavior of players)
...in this context we have selected TCP Vegas (throughput estimation mechanism)
remarks / ideas for proceeding:
- network/Internet should not be vulnerable to greedy users
- Nash equilibria are not necessarily achieved (as a result of learning)
- nature of learning and convergence in the Internet
- reasonable "learning" behavior
Any questions?