Braess’s Paradox in Wireless Networks: The Danger of Improved Technology

Michael Dinitz and Merav Parter

Abstract: When comparing new wireless technologies, it is common to consider the effect that they have on the capacity of the network (defined as the maximum number of simultaneously satisfiable links).  For example, it has been shown that giving receivers the ability to do interference cancellation, or allowing transmitters to use power control, never decreases the capacity and can in certain cases increase it by Omega(log (Delta Pmax)), where Delta is the ratio of the longest link length to the smallest transmitter-receiver distance and Pmax is the maximum transmission power.  But there is no reason to expect the optimal capacity to be realized in practice, particularly since maximizing the capacity is known to be NP-hard.  In reality, we would expect links to behave as self-interested agents, and thus when introducing a new technology it makes more sense to compare the values reached at game-theoretic equilibria than the optimum values.
In this paper we initiate this line of work by comparing various notions of equilibria (particularly Nash equilibria and no-regret behavior) when using a supposedly “better” technology.  We show a version of Braess’s Paradox for all of them: in certain networks, upgrading technology can actually make the equilibria \emph{worse}, despite an increase in the capacity.  We construct instances where this decrease is a constant factor for power control, interference cancellation, and improvements in the SINR threshold beta, and is Omega(log Delta) when power control is combined with interference cancellation.  However, we show that these examples are basically tight: the decrease is at most O(1)for power control, interference cancellation, and improved beta, and is at most
O(log Delta) when power control is combined with interference cancellation.
Guest: Michael Dinitz
Host: Yvonne-Anne Pignolet

Distributed Protocols for Leader Election: a Game-Theoretic Perspective

Ittai Abraham, Danny Dolev, and Joseph Y. Halpern

Abstract. We do a game-theoretic analysis of leader election, under the assumption
that each agent prefers to have some leader than to have no leader at all. We
show that it is possible to obtain a fair Nash equilibrium, where each agent has
an equal probability of being elected leader, in a completely connected network,
in a bidirectional ring, and a unidirectional ring, in the synchronous setting. In
the asynchronous setting, Nash equilibrium is not quite the right solution concept.
Rather, we must consider ex post Nash equilibrium; this means that we
have a Nash equilibrium no matter what a scheduling adversary does. We show
that ex post Nash equilibrium is attainable in the asynchronous setting in all the
networks we consider, using a protocol with bounded running time. However,
in the asynchronous setting, we require that n > 2. We can get a fair e-Nash
equilibrium if n = 2 in the asynchronous setting, under some cryptographic assumptions
(specifically, the existence of a pseudo-random number generator and
polynomially-bounded agents), using ideas from bit-commitment protocols. We
then generalize these results to a setting where we can have deviations by a coalition
of size k. In this case, we can get what we call a fair k-resilient equilibrium
if n > 2k; under the same cryptographic assumptions, we can a get a k-resilient
equilibrium if n = 2k. Finally, we show that, under minimal assumptions, not
only do our protocols give a Nash equilibrium, they also give a sequential equilibrium
[23], so players even play optimally off the equilibrium path.

Guests: Danny Dolev and Joseph Y. Halpern

Host: Stefan Schmid

Metastability of Logit Dynamics for Coordination Games

Vincenzo Auletta, Diodato Ferraioli, Francesco Pasquale, Giuseppe Persiano


Logit Dynamics [Blume, Games and Economic Behavior, 1993] is a randomized best response dynamics for strategic games: at every time step a player is selected uniformly at random and she chooses a new strategy according to a probability distribution biased toward strategies promising higher payoffs. This process defines an ergodic Markov chain, over the set of strategy profiles of the game, whose unique stationary distribution is the long-term equilibrium concept for the game. However, when the mixing time of the chain is large (e.g. exponential in the number of players), the stationary distribution loses its appeal as equilibrium concept, and the transient phase of the Markov chain becomes important. In several cases it happens that on a time-scale shorter than mixing time the chain is “quasi-stationary”, meaning that it stays close to some small set of the state space, while in a time-scale multiple of the mixing time it jumps from one quasi-stationary configuration to another; this phenomenon is usually called “metastability”.
In this paper we give a quantitative definition of “metastable probability distributions” for a Markov chain and we study the metastability of the Logit dynamics for some classes of coordination games. In particular, we study no-risk-dominant coordination games on the clique (which is equivalent to the well-known Glauber dynamics for the Ising model) and coordination games on a ring (both the risk-dominant and no-risk-dominant case). We also describe a simple “artificial” game that highlights the distinctive features of our metastability notion based on distributions.

Guest: Francesco Pasquale

Host: Merav Parter