Abstract In this paper we introduce a capacity allocation game which models the problem of maximizing network utility from the perspective of distributed noncooperative agents. Motivated by the idea of self-managed networks, in the developed framework the decision-making entities are associated with individual transmission links, deciding on the way they split capacity among concurrent flows. An efficient decentralized algorithm is given for computing a strongly Pareto-optimal strategies, constituting a pure Nash equilibrium. Subsequently, we discuss the properties of the introduced game related to the Price of Anarchy and Price of Stability. The paper is concluded with an experimental study.
@cite_48: We study bandwidth allocation at base stations of a wireless network as a non-cooperative game between different wireless users. A user demands bandwidth from the base stations it has access to by submitting bids. Once the bidding process is complete, a base station distributes its bandwidth to the users in proportion to their bids. Users are assumed to be budget constrained and price anticipating, and split their wealth across base stations so as to maximize their individual bandwidths. In this paper, we study the properties of Nash Equilibrium (NE) for this bandwidth allocation game. For the special case where each user can access all base stations, we argue that there exists a unique NE, at which the bandwidth obtained by any user is proportional to its wealth. For a more general scenario where a user may be able to access only a subset of all base stations, we compare the NE of the game to the max-min fair bandwidth allocation. We show that although the NE may not be max-min fair in general, the bandwidth allocation at NE becomes arbitrarily close to max-min fair allocation as the number of users is increased, while keeping the number of base stations fixed.
@cite_56: A user located in a congested area of a wireless LAN may benefit by moving to a less-crowded area and using a less-loaded access point. This idea has gained attention from researchers in recent literature [A. Balachandran, P. Bahl, G. Voelker, Hot-spot congestion relief in public-area wireless networks, in: IEEE WMCSA, Callicoon, NY, June 2002; M. Satyanarayanan, Pervasive computing: visions and challenges, IEEE Personal Communications 8 (4) (2001) 10-17]. However, its effectiveness and stability are questionable. Each user selects the access point that offers the optimal trade-off between load and distance to be traveled. Since users are selfish, a user's selection may adversely impact other users, in turn motivating them to change their selections. Also, future user arrivals and exits may invalidate current selections. This paper presents the first game-theoretic analysis of this idea. We model access point selection as a game, characterize the Nash equilibria of the system and examine distributed myopic selections that naturally mimic selfish users. We analytically and empirically assess the impact of user diversity and dynamic exit patterns on system behavior. The paper contributes to a deeper understanding of the costs, benefits and stability of such a solution in various usage scenarios, which is an essential pre-requisite for real-world deployment.
@cite_72: While the Quality of Service (QoS) offered to users may be enhanced through innovative protocols and new technologies, future trends should take into account the efficiency of resource allocation and network terminal cooperation as well. Game theory techniques have widely been applied to various engineering design problems in which the action of one component has impact on (and perhaps conflicts with) that of any other component. Therefore, game formulations are used, and a stable solution for the players is obtained through the concept of equilibrium. This survey collects applications of game theory in wireless networking and presents them in a layered perspective, emphasizing on which fields game theory could be effectively applied. To this end, several games are modeled and their key features are exposed.
@cite_13: The behavior of a given wireless station may affect the communication capabilities of a neighboring one, notably because the radio communication channel is usually shared in wireless networks. In this tutorial, we carefully explain how situations of this kind can be modelled by making use of game theory. By leveraging on four simple running examples, we introduce the most fundamental concepts of non-cooperative game theory. This approach should help students and scholars to quickly master this fascinating analytical tool without having to read the existing lengthy, economics-oriented books; it should also assist them in modelling the problems of their own.
@cite_11: We propose to add a new dimension to existing wireless multimedia communications systems by enabling competing stations to proactively engage in the resource management game by adapting their cross-layer transmission strategies. For this, we model wireless stations (WSTAs) as rational and selfish players competing for available wireless resources in a dynamic game. We focus on polling-based wireless LAN (WLAN) networks, where developing an efficient solution for managing the available transmission opportunities is of paramount importance. The resource allocation game is coordinated by a network moderator, which deploys a novel resource management based on the Vickrey-Clarke-Groves (VCG) mechanism to determine a) the amount of time to be allocated to the various users and b) the transmission cost associated to the allocated resources. The transmission cost is referred to in the VCG mechanism as "transfer" and depends not on the used resources, but rather on the inconvenience (in terms of utility impact) that it causes to other WSTAs. The transfer is introduced in order to discourage WSTAs from lying about their resource requirements. Importantly, this proposed dynamic resource management approach for wireless multimedia applications changes the passive way stations are currently adapting their cross-layer strategies by enabling them to selfishly influence the wireless systems dynamics by proactively adapting their packet scheduling strategies, error protection strategies, etc. Hence, each wireless station can play the resource management game by adapting its multimedia transmission strategy depending on the experienced channel conditions, derived video quality, attitude towards risk, willingness to pay for resources and available information about the wireless network. Our simulations show that using the VCG mechanism the WSTAs do not have any incentives to lie about their resource requirements as otherwise they will be severely penalized by a high transfer. We also show that deploying advanced cross-layer strategies for playing the resource management game significantly benefit the WSTAs' received video quality. The willingness-to-pay for resources is introduced to provide WSTAs a tool to gather additional resources whenever they need to transmit an important (part of a) video sequence by agreeing to pay for resources an increased cost. A novel risk-aware scheduling scheme is also proposed that provides WSTAs the ability to dynamically avoid network congestion and hence, reduce their incurred transfer
Currently, the game-theoretical framework is also extensively studied in the context of wireless networks @cite_13 . For instance, in @cite_48 bandwidth allocation problem for a class of wireless networks is investigated. The uniqueness of Nash equilibrium for some particular network topologies is shown. It is also stated that some of the presented results may be also generalized for different cases. In @cite_56 the problem of choosing an access point by a mobile user is considered from the perspective of this approach. Similar frameworks for issues in wireless networks categorized under corresponding OSI Layers (namely: physical, data link, network and transport layers) are presented in @cite_72 . The VCG auctions were also applied to the wireless networks, e.g. in @cite_11 it is proposed for the resource allocation problem in multimedia wireless networks.