The Computer Science Colloquium

Andrey Garnaev
(St. Petersburg State University)

"Jamming and transmission games"

In this report we study some wireless problems. In the optimization framework there is a single decision maker who assigns network resources and in the game framework players share the network resources according to Nash equilibrium. The solution of these problems is based on so-called water-filling technique, which in turn uses bisection method for solution of non-linear equations for Lagrange multiplies. Here we provide a closed form solution to the optimization water-filling problem, which allows us to solve it in a finite number of operations. Also, we will consider two wireless problems from game theoretical point of view, namely (1) we will consider jamming in wireless networks with transmission cost for both transmitter and jammer. (2) We will consider a transmission game and we will produce a closed form solution for the Nash equilibrium of this game. In addition, to its analytical beauty, the explicit solution allows one to study limiting cases when the crosstalk coefficient is either small or large. Furthermore, it turns out that the convergence of Iterative Water Filling Algorithm slows down when the crosstalk coefficient is large. Using the closed form solution, we can avoid this problem. Finally, we compare the non-cooperative approach with the cooperative approach.

The Colloquium is supported by generous contributions from the Bloomberg, Information Builders, Inc., and Netlogic, Inc.