1st International ICST Workshop on Game theory for Communication networks

Research Article

Closed form solutions for water-filling problems in optimization and game frameworks

Download523 downloads
  • @INPROCEEDINGS{10.4108/gamecomm.2007.2030,
        author={Eitan Altman and Konstantin Avrachenkov and Andrey Garnaev},
        title={Closed form solutions for water-filling problems in optimization and game frameworks},
        proceedings={1st International ICST Workshop on Game theory for Communication networks},
        proceedings_a={GAMECOMM},
        year={2010},
        month={5},
        keywords={},
        doi={10.4108/gamecomm.2007.2030}
    }
    
  • Eitan Altman
    Konstantin Avrachenkov
    Andrey Garnaev
    Year: 2010
    Closed form solutions for water-filling problems in optimization and game frameworks
    GAMECOMM
    ICST
    DOI: 10.4108/gamecomm.2007.2030
Eitan Altman1,*, Konstantin Avrachenkov1,*, Andrey Garnaev2,*
  • 1: INRIA BP93 2004 route des Lucioles 06902 Sophia Antipolis FRANCE
  • 2: St. Petersburg State University Universitetskii pr 35 Peterhof St Petersburg 198504 RUSSIA
*Contact email: altman@sophia.inria.fr, k.avrachenkov@sophia.inria.fr, agarnaev@rambler.ru

Abstract

We study power control in optimization and game frameworks. 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 La-grange multiplies. Here we provide a closed form solution to the water-filling problem, which allows us to solve it in a finite number of operations. Also, we produce a closed form solution for the Nash equilibrium in symmetric Gaussian interference game. In addition, to its mathematical beauty, the explicit solution allows one to study limiting cases when the crosstalk coefficient is either small or large. We provide an alternative simple proof of the convergence of the Iterative Water Filling Algorithm. 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 and show that the non-cooperative approach results in a more fair resource distribution.