text: 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.
  @cite_14: This exciting and pioneering new overview of multiagent systems, which are online systems composed of multiple interacting intelligent agents, i.e., online trading, offers a newly seen computer science perspective on multiagent systems, while integrating ideas from operations research, game theory, economics, logic, and even philosophy and linguistics. The authors emphasize foundations to create a broad and rigorous treatment of their subject, with thorough presentations of distributed problem solving, game theory, multiagent communication and learning, social choice, mechanism design, auctions, cooperative game theory, and modal logics of knowledge and belief. For each topic, basic concepts are introduced, examples are given, proofs of key results are offered, and algorithmic considerations are examined. An appendix covers background material in probability theory, classical logic, Markov decision processes and mathematical programming. Written by two of the leading researchers of this engaging field, this book will surely serve as THE reference for researchers in the fastest-growing area of computer science, and be used as a text for advanced undergraduate or graduate courses.
  @cite_7: 
  @cite_9: A Course in Game Theory presents the main ideas of game theory at a level suitable for graduate students and advanced undergraduates, emphasizing the theory's foundations and interpretations of its basic concepts. The authors provide precise definitions and full proofs of results, sacrificing generalities and limiting the scope of the material in order to do so. The text is organized in four parts: strategic games, extensive games with perfect information, extensive games with imperfect information, and coalitional games. It includes over 100 exercises.
  @cite_23: If it is common knowledge that the players in a game are Bayesian utility maximizers who treat uncertainty about other players' actions like any other uncertainty, then the outcome is necessarily a correlated equilibrium. Random strategies appear as an expression of each player's uncertainty about what the others will do, not as the result of willful randomization. Use is made of the common prior assumption, according to which differences in probability assessments by different individuals are due to the different information that they have (where "information" may be interpreted broadly, to include experience, upbringing, and genetic makeup). Copyright 1987 by The Econometric Society. (This abstract was borrowed from another version of this item.) (This abstract was borrowed from another version of this item.) (This abstract was borrowed from another version of this item.) (This abstract was borrowed from another version of this item.) (This abstract was borrowed from another version of this item.) (This abstract was borrowed from another version of this item.) (This abstract was borrowed from another version of this item.) (This abstract was borrowed from another version of this item.) (This abstract was borrowed from another version of this item.) (This abstract was borrowed from another version of this item.) (This abstract was borrowed from another version of this item.) (This abstract was borrowed from another version of this item.) (This abstract was borrowed from another version of this item.) (This abstract was borrowed from another version of this item.) (This abstract was borrowed from another version of this item.) (This abstract was borrowed from another version of th (This abstract was borrowed from another version of this item.)
  @cite_5: Information flow in a telecommunication network is accomplished through the interaction of mechanisms at various design layers with the end goal of supporting the information exchange needs of the applications. In wireless networks in particular, the different layers interact in a nontrivial manner in order to support information transfer. In this text we will present abstract models that capture the cross-layer interaction from the physical to transport layer in wireless network architectures including cellular, ad-hoc and sensor networks as well as hybrid wireless-wireline. The model allows for arbitrary network topologies as well as traffic forwarding modes, including datagrams and virtual circuits. Furthermore the time varying nature of a wireless network, due either to fading channels or to changing connectivity due to mobility, is adequately captured in our model to allow for state dependent network control policies. Quantitative performance measures that capture the quality of service requirements in these systems depending on the supported applications are discussed, including throughput maximization, energy consumption minimization, rate utility function maximization as well as general performance functionals. Cross-layer control algorithms with optimal or suboptimal performance with respect to the above measures are presented and analyzed. A detailed exposition of the related analysis and design techniques is provided.
  @cite_15: This text presents a modern theory of analysis, control, and optimization for dynamic networks. Mathematical techniques of Lyapunov drift and Lyapunov optimization are developed and shown to enable constrained optimization of time averages in general stochastic systems. The focus is on communication and queueing systems, including wireless networks with time-varying channels, mobility, and randomly arriving traffic. A simple drift-plus-penalty framework is used to optimize time averages such as throughput, throughput-utility, power, and distortion. Explicit performance-delay tradeoffs are provided to illustrate the cost of approaching optimality. This theory is also applicable to problems in operations research and economics, where energy-efficient and profit-maximizing decisions must be made without knowing the future. Topics in the text include the following: - Queue stability theory - Backpressure, max-weight, and virtual queue methods - Primal-dual methods for non-convex stochastic utility maximization - Universal scheduling theory for arbitrary sample paths - Approximate and randomized scheduling theory - Optimization of renewal systems and Markov decision systems Detailed examples and numerous problem set questions are provided to reinforce the main concepts. Table of Contents: Introduction Introduction to Queues Dynamic Scheduling Example Optimizing Time Averages Optimizing Functions of Time Averages Approximate Scheduling Optimization of Renewal Systems Conclusions
  @cite_20: We consider optimal control for general networks with both wireless and wireline components and time varying channels. A dynamic strategy is developed to support all traffic whenever possible, and to make optimally fair decisions about which data to serve when inputs exceed network capacity. The strategy is decoupled into separate algorithms for flow control, routing, and resource allocation, and allows each user to make decisions independent of the actions of others. The combined strategy is shown to yield data rates that are arbitrarily close to the optimal operating point achieved when all network controllers are coordinated and have perfect knowledge of future events. The cost of approaching this fair operating point is an end-to-end delay increase for data that is served by the network.
summary: This paper shows that an optimal distributed algorithm can be designed by having users correlate their decisions through an independent source of common randomness (Section ). Related notions of commonly shared randomness are used in game theory to define a , which is typically easier to compute than a standard Nash equilibrium @cite_7 @cite_23 @cite_14 @cite_9 . For the current paper, the shared randomness is crucial for solving the distributed optimization problem. This paper shows that optimality can be achieved by using a shared random variable with @math possible outcomes, where @math is the number of penalty constraints. The solution is computable through a linear program. Unfortunately, the linear program can have a very large number of variables, even for 2-user problems. A reduction to polynomial complexity is shown to be possible in certain cases (Section ). This paper also develops an online algorithm that chooses pure strategies every slot based on a set of weights that are updated at the end of each slot (Section ). The online technique is based on Lyapunov optimization concepts @cite_15 @cite_5 @cite_20 .