Sleeping Experts in Wireless Networks

Johannes Dams, Martin Hoefer and Thomas Kesselheim

Abstract: We consider capacity maximization algorithms for wireless networks with changing availabilities of spectrum. There are n sender-receiver pairs (called links) and k channels. We consider an iterative round-based scenario, where in each round the set of channels available to each link changes. Each link independently decides about access to one available channel in order to implement a successful transmission. Transmissions are subject to interference and noise, and we use a general approach based on affectance to define which attempts are successful. This includes recently popular interference models based on SINR.
Our main result is that efficient distributed algorithms from sleeping-expert regret learning can be used to obtain constant-factor approximations if channel availability is stochastic and independently distributed among links. In general, sublinear approximation factors cannot be obtained without the assumption of stochastic independence among links. A direct application of the no-external regret property is not sufficient to guarantee small approximation factors.

Guest: Johannes Dams
Host: Yvonne-Anne Pignolet

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

The Cost of Radio Network Broadcast for Different Models of Unreliable Links

Mohsen Gaffari, Nancy Lynch, Calvin Newport

Abstract: We study upper and lower bounds for the global and local broadcast problems in the dual graph model combined with different strength adversaries. The dual graph model is a generalization of the standard graph-based radio network model that includes unreliable links controlled by an adversary. It is motivated by the ubiquity of unreliable links in real wireless networks. Existing results in this model assume an offline adaptive adversary – the strongest type of adversary considered in standard randomized analysis. In this paper, we study the two other standard types of adversaries: online adaptive and oblivious. Our goal is to find a model that captures the unpredictable behavior of real networks while still allowing for efficient broadcast solutions.

Guest: Calvin Newport
Host: Yvonne-Anne Pignolet

The Notion of a Rational Convex Program, and an Algorithm for the Arrow-Debreu Nash Bargaining Game

Vijay Vazirani

Abstract: We introduce the notion of a rational convex program (RCP) and we classify the known RCPs into two classes: quadratic and logarithmic. The importance of rationality is that it opens up the possibility of computing an optimal solution to the program via an algorithm that is either combinatorial or uses an LP-oracle. Next we define a new Nash bargaining game, called ADNB, which is derived from the linear case of the Arrow-Debreu market model. We show that the convex program for ADNB is a logarithmic RCP, but unlike other known members of this class, it is non-total.
Our main result is a combinatorial, polynomial time algorithm for ADNB. It turns out that the reason for infeasibility of logarithmic RCPs is quite different from that for LPs and quadratic RCPs. We believe that our ideas for surmounting the new difficulties will be useful for dealing with other non-total RCPs as well. We give an application of our combinatorial algorithm for ADNB to an important “fair” throughput allocation problem on a wireless channel. Finally, we present a number of interesting questions that the new notion of RCP raises.


Guest: Vijay Vazirani
Host: Zvi Lotker