Why using Game Theory in communication networks?
Introduction of game theory concepts
Patrick Maill´e and Bruno Tuffin Institut MinesTelecom/Telecom
Bretagne, Inria Rennes BretagneAtlantique IRISA Seminar on
Network Economics, May 31, 2012
Outline
Introduction: the (economic) evolution of networks
Basic concepts of game theory
Pricing and congestion/demand control Interdomain issues
5 Summary
From centralization to decentralization
Networking has switched from the centralized telephone network to
the decentralized Internet (scalability reason)
. Decentralization (or deregulation) is a key factor
.In such a situation:
From the decentralization, there is a general envisaged/advised
behavior
But each selfish user can try to modify his behavior at his
benefits and at the expense of the network performance.
Example: TCP configuration
How to analyze this, and how to control and prevent such a
thing? It is the purpose of noncooperative game theory.
Competitive actors: not only users
The Internet has also evolved from an academic to a
commercial network with providers in competition for
customers and services.
As a consequence, users are not the only competitive actors, but
also
network providers: several providers propose the same type of
network access;
Applications/service providers/content providers: the same type
of application can be proposed by several entities (ex: search
engines...)
Platforms/technologies: you may access the Internet from
ADSL, WiFi, 3G, WiMAX, LTE...All those interacting actors
have to be considered
Why changing the pricing scheme?
Increase of Internet traffic due to
o increasing number of subscribers
o more and more demanding applications.
Congestion is a consequence, with erratic QoS.
Increasing capacity difficult if not impossible in access
networks (last mile problem)
Also, flat rate pricing is unfair and does not allow service
differentiation.
Subject of debate...
But new contexts require new economic paradigms.
Convergence: requires new pricing offers
Convergence of technologies and services: all services (web
browsing, telephony, television) can be used on all technologies
(Fixed, WiFi, 3G, LTE...).
o How to charge fairly and efficiently those different
technologies, with their different characteristics?
o New technology: new issues to solve.
Would it be possible to propose a pricing scheme involving
several technologies at the same time?
Marketing point of view from operators: propose grouped offers
(bundles) to attract customers to services they would not
consider otherwise.
A new issue: dealing with competition among providers
Most works on pricing are dealing with a monopoly, but
o Competition forces providers to decide about prices and
offers depending on competitors’ ones.
o Some a priori promising pricing schemes may not resist to
competition.
Sometimes providers even operate on different technologies
(Fixed, WiFi, 3G, LTE...), or on several simultaneously.
Also, impact of competition on capacity investment? Do they
have interest in investing (especially when congestion pricing is
used)?
Sending endtoend traffic through other (selfish)
nodes/networks
Here not a direct competition for customers, but providers have
to pay other domains for forwarding their traffic and ensure
endtoend delivery (similar problems arise in ad hoc networks).
How to design a selfmanaged network, with proper pricing
incentives to forward traffic?
Still unsolved: what are the optimal strategies of operators, in
order to propose the best investments, in terms of :
1. Investment on capacity: bandwidth for a domain or mobile
network...
2. Investment on products: new services.
3. Investment on technology: new link between two domains,
new base station, new WiFi hotspot...
Regulation: is it required?
Free market can lead to an \inefficient" mechanism.
Regulation can enforce providers to drive to the proper
situation.
Ex: to enforce providers to reduce retention time and authorize
churn.
New regulation/political issue: network neutrality
o Network providers want to win on both sides: to charge users
but also content providers, or degrade their services.
o They do not want application providers not associated to
them to congest their network.
o Political debate: all players should be allowed the same
access.
Actors are then not free to do whatever we want.
Basic concepts of game theory
What it changes
While before optimization was the tool for routing, QoS
provisionning, interactions between players has to be taken into
account.
Game theory: distributed optimization: individual users make
their own decisions. "Easier" than to solve NPhard problems
(approximation).
We need to look at a stable point (Nash equilibrium) for
interactions.
Tools used before in Economics, Transportation...
and has recently appeared in telecommunications.
We may have paradoxes (Braess paradox) that can be studied
that way.
A way to control things: to introduce pricing
incentives/discouragements (TBC).
Typical networking applications
P2P networks: a node tries to benefit from others, but limits its
available resource (free riding)
Grid computing: same issue, try to benefit from others’
computing power, while limiting its own contribution.
Routing games: each sending node tries to find the route
minimizing delay, but intermediate links are shared with other
flows (interactions).
Ad hoc networks: what is the incentive of nodes to forward
traffic of neighbors? If no one does, no traffic is successfully
sent.
Congestion control game (TCP...): why reducing your sending
rate when congestion is detected?
Power control in wireless networks: maximizing your power will
induce a better QoS, but at the expense of others’ interferences.
Transmission games (WiFi...): if collision, when to resubmit
packets?
Basic definitions
Game theory: set of tools to understand the behavior of
interacting decision makers or players.
Classical assumption: players are rational: they have well
defined objectives, and they take into account the behavior of
others.
In this course: strategic or normal games, players play
(simultaneously) once and for all.
There are also branches called:
o extensive games, for which players play sequentially;
o repeated games for which they can change their choices
over time;
o Bayesian games, evolutionary games...
General modeling tools
Interactions of players through network performance. Tools:
o queueing analysis or
o signal processing.
The action of a player has an impact on the output of other
players, and therefore on their own strategies.
They all have to play strategically.
Each player i (user or provider) represented by its utility
function ui(x) representing quantitatively its level of satisfaction
(in monetary units for instance) when actions profile is x = (x i)i,
where xi denotes the action of player i.
Strategic Games
A strategic game Γ consists of:
o A finite set of players, N.
o A set Ai of actions available to each player.
o For each player a utility function, (payoffs) characterizing
the gain/utility from a state of the game.
Players make decisions independently, without information
about the choice of other players.
We note Γ
For two players: description via a table, with payoffs
corresponding to the strategic choices of users:
