This paper considers a problem where multiple users make repeated decisions based on their own observed events. The events and decisions at each time step determine the values of a utility function and a collection of penalty functions. The goal is to make distributed decisions over time to maximize time average utility subject to time average constraints on the penalties. An example is a collection of power constrained sensor nodes that repeatedly report their own observations to a fusion center. Maximum time average utility is fundamentally reduced because users do not know the events observed by others. Optimality is characterized for this distributed context. It is shown that optimality is achieved by correlating user decisions through a commonly known pseudorandom sequence. An optimal algorithm is developed that chooses pure strategies at each time step based on a set of time-varying weights.
The framework of partial knowledge at each user is similar in spirit to a @cite_9 @cite_14 . There, the goal is to design competitive strategies that lead to a Nash equilibrium. This is significantly different from the goal of the current paper. The current paper is not concerned with competition or equilibrium. Rather, there is a single utility function that all users desire to maximize. Distributed algorithms are developed to maximize time average utility subject to time average penalty constraints.
@cite_9 @cite_14
2109100253 1528676759
This paper considers a time-varying game with N players. Every time slot, players observe their own random events and then take a control action. The events and control actions affect the individual utilities earned by each player. The goal is to maximize a concave function of time average utilities subject to equilibrium constraints. Specifically, participating players are provided access to a common source of randomness from which they can optimally correlate their decisions. The equilibrium constraints incentivize participation by ensuring that players cannot earn more utility if they choose not to participate. This form of equilibrium is similar to the notions of Nash equilibrium and correlated equilibrium, but is simpler to attain. A Lyapunov method is developed that solves the problem in an online max-weight fashion by selecting actions based on a set of time-varying weights. The algorithm does not require knowledge of the event probabilities. A similar method can be used to compute a standard correlated equilibrium, albeit with increased complexity. A game-theoretic model for studying power control in multicarrier code-division multiple-access systems is proposed. Power control is modeled as a noncooperative game in which each user decides how much power to transmit over each carrier to maximize its own utility. The utility function considered here measures the number of reliable bits transmitted over all the carriers per joule of energy consumed and is particularly suitable for networks where energy efficiency is important. The multidimensional nature of users' strategies and the nonquasi-concavity of the utility function make the multicarrier problem much more challenging than the single-carrier or throughput-based-utility case. It is shown that, for all linear receivers including the matched filter, the decorrelator, and the minimum-mean-square-error detector, a user's utility is maximized when the user transmits only on its "best" carrier. This is the carrier that requires the least amount of power to achieve a particular target signal-to-interference-plus-noise ratio at the output of the receiver. The existence and uniqueness of Nash equilibrium for the proposed power control game are studied. In particular, conditions are given that must be satisfied by the channel gains for a Nash equilibrium to exist, and the distribution of the users among the carriers at equilibrium is characterized. In addition, an iterative and distributed algorithm for reaching the equilibrium (when it exists) is presented. It is shown that the proposed approach results in significant improvements in the total utility achieved at equilibrium compared with a single-carrier system and also to a multicarrier system in which each user maximizes its utility over each carrier independently Dynamic spectrum access can significantly improve the spectrum utilization. For wireless service providers, the emergence of dynamic spectrum access brings new opportunities and challenges. The flexible spectrum acquisition gives a particular provider the chance to easily adapt its system capacity to fit end users' demand. However, the competition among several providers for both spectrum and end users complicates the situation. In this paper, we propose a general three-layer spectrum market model for the future dynamic spectrum access system, in which the interaction among spectrum holder, wireless service providers and end users are considered. We study a duopoly situation, where two wireless service providers participate in bandwidth competition in spectrum purchasing and price competition to attract end users, with the aim of maximizing their own profit. We believe we are the first one to explicitly study the relation of these two competitions in dynamic spectrum market. We formulate the wireless service providers' competition as a non-cooperative two-stage game. We first analyze the static game when full information is available for providers. Under general assumptions about the price and demand functions, a unique pure Nash equilibrium is identified as the outcome of the game, which shows the stability of the market. We further evaluate the market efficiency of the equilibrium in a symmetric case, and show that the gap with the social optimal is bounded within a small constant ratio. When the market information is limited, we provide myopically optimal adjustment algorithms for the providers. With such strategies, short term price updating converges to the Nash equilibrium of the given subgame, while long term bandwidth updating converges to a point close to the Nash equilibrium of the full game. We study in this paper a noncooperative approach for sharing resources of a common pool among users, wherein each user strives to maximize its own utility. The optimality notion is then a Nash equilibrium. First, we present a general framework of systems wherein a Nash equilibrium is Pareto inefficient, which are similar to the 'tragedy of the commons' in economics. As examples that fit in the above framework, we consider noncooperative flow-control problems in communication networks where each user decides its throughput to optimize its own utility. As such a utility, we first consider the power which is defined as the throughput divided by the expected end-to-end packet delay, and then consider another utility of additive costs. For both utilities, we establish the non-efficiency of the Nash equilibria.