Closed form solutions for water-filling problems in optimization and game frameworks
Closed form solutions for water-filling problems in optimization and game frameworks
复制标题
优化和游戏框架中注水问题的封闭式解决方案
DOI：
10.1007/s11235-010-9308-0
复制
发表时间：
2007
影响因子：
2.5
通讯作者：
A. Garnaev
中科院分区：
文献类型：
--
作者：
E. Altman;Konstantin Avrachenkov;A. Garnaev
我们研究优化和游戏框架中的功率控制。在优化框架中，有一个决策者分配网络资源，而在博弈框架中，用户根据纳什均衡共享网络资源。这些问题的解决基于所谓的注水技术，该技术又使用二分法来求解拉格朗日乘子的非线性方程。在这里，我们为注水问题提供了一个封闭形式的解决方案，这使我们能够通过有限数量的操作来解决它。此外，我们还为任意数量用户的对称高斯干扰博弈中的纳什均衡生成了一个封闭形式的解。尽管游戏是对称的，但仍存在由用户可用资源数量引起的内在层次结构。我们使用这种层次结构来执行游戏的连续缩减。除了其数学之美之外，显式解还允许人们研究串扰系数较小或较大时的极限情况。我们提供了迭代注水算法收敛性的另一种简单证明。此外，结果表明，当串扰系数较大时，迭代注水算法的收敛速度变慢。使用封闭式解决方案，我们可以避免这个问题。最后，我们将非合作方法与合作方法进行比较，结果表明非合作方法可以实现更公平的资源分配。
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 users 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 multipliers. 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 with an arbitrary number of users. Even though the game is symmetric, there is an intrinsic hierarchical structure induced by the quantity of the resources available to the users. We use this hierarchical structure to perform a successive reduction of the 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.