Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userClosed form solutions for symmetric water filling games
144
0
0.0
(
0
)
Added by
Konstantin Avrachenkov
Publication date
2007
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic 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 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 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 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.
rate research
Read More
This paper considers a non-cooperative game in which competing users sharing a frequency-selective interference channel selfishly optimize their power allocation in order to improve their achievable rates. Previously, it was shown that a user having the knowledge of its opponents channel state information can make foresighted decisions and substantially improve its performance compared with the case in which it deploys the conventional iterative water-filling algorithm, which does not exploit such knowledge. This paper discusses how a foresighted user can acquire this knowledge by modeling its experienced interference as a function of its own power allocation. To characterize the outcome of the multi-user interaction, the conjectural equilibrium is introduced, and the existence of this equilibrium for the investigated water-filling game is proved. Interestingly, both the Nash equilibrium and the Stackelberg equilibrium are shown to be special cases of the generalization of conjectural equilibrium. We develop practical algorithms to form accurate beliefs and search desirable power allocation strategies. Numerical simulations indicate that a foresighted user without any a priori knowledge of its competitors private information can effectively learn the required information, and induce the entire system to an operating point that improves both its own achievable rate as well as the rates of the other participants in the water-filling game.
We provide, to the best of our knowledge, the first computational study of extensive-form adversarial team games. These games are sequential, zero-sum games in which a team of players, sharing the same utility function, faces an adversary. We define three different scenarios according to the communication capabilities of the team. In the first, the teammates can communicate and correlate their actions both before and during the play. In the second, they can only communicate before the play. In the third, no communication is possible at all. We define the most suitable solution concepts, and we study the inefficiency caused by partial or null communication, showing that the inefficiency can be arbitrarily large in the size of the game tree. Furthermore, we study the computational complexity of the equilibrium-finding problem in the three scenarios mentioned above, and we provide, for each of the three scenarios, an exact algorithm. Finally, we empirically evaluate the scalability of the algorithms in random games and the inefficiency caused by partial or null communication.
This note presents techniques to analytically solve double integrals of the dilogarithmic type which are of great importance in the perturbative treatment of quantum field theory. In our approach divergent integrals can be calculated similar to their convergent counterparts after identifying and isolating their singular parts.
We consider a star-topology wireless network for status update where a central node collects status data from a large number of distributed machine-type terminals that share a wireless medium. The Age of Information (AoI) minimization scheduling problem is formulated by the restless multi-armed bandit. A widely-proven near-optimal solution, i.e., the Whittles index, is derived in closed-form and the corresponding indexability is established. The index is then generalized to incorporate stochastic, periodic packet arrivals and unreliable channels. Inspired by the index scheduling policies which achieve near-optimal AoI but require heavy signaling overhead, a contention-based random access scheme, namely Index-Prioritized Random Access (IPRA), is further proposed. Based on IPRA, terminals that are not urgent to update, indicated by their indices, are barred access to the wireless medium, thus improving the access timeliness. A computer-based simulation shows that IPRAs performance is close to the optimal AoI in this setting and outperforms standard random access schemes. Also, for applications with hard AoI deadlines, we provide reliable deadline guarantee analysis. Closed-form achievable AoI stationary distributions under Bernoulli packet arrivals are derived such that AoI deadline with high reliability can be ensured by calculating the maximum number of supportable terminals and allocating system resources proportionally.
In this paper, we present a method for finding approximate Nash equilibria in a broad class of reachability games. These games are often used to formulate both collision avoidance and goal satisfaction. Our method is computationally efficient, running in real-time for scenarios involving multiple players and more than ten state dimensions. The proposed approach forms a family of increasingly exact approximations to the original game. Our results characterize the quality of these approximations and show operation in a receding horizon, minimally-invasive control context. Additionally, as a special case, our method reduces to local gradient-based optimization in the single-player (optimal control) setting, for which a wide variety of efficient algorithms exist.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
