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_19: We consider a Wireless Sensor Network where each sensor device is able to harvest energy from the environment, and randomly accesses the channel to transmit packets of random importance to a fusion center. If a collision occurs, the transmission fails and all packets involved are discarded. We design distributed transmission schemes where each sensor node, based on its own energy level and the importance of its own data packet, decides whether to transmit the packet or remain idle, so as to maximize the network utility, defined as the average long-term aggregate network importance of the data packets successfully reported to the fusion center. Due to the generally non-convex structure of the optimization problem, we resort to approximate solutions. In particular, we use a mathematical artifice based on a game theoretic formulation of the multiaccess problem, where each sensor node is a player that attempts to selfishly maximize the network utility. We characterize the Symmetric Nash Equilibrium (SNE) of this game, where all the sensor nodes employ the same policy. We prove the existence and uniqueness of the SNE, and we show that it is a local maximum of the original optimization problem. Moreover, we derive an algorithm to compute it.
  @cite_17: Sequential Decision Making in Decentralized Systems by Ashutosh Nayyar Chair: Demosthenis Teneketzis We study sequential decision making problems in cooperative systems where different agents with different information want to achieve a common objective. The sequential nature of the decision problem implies that all decisions can be arranged in a sequence such that the information available to make the t decision only depends on preceding decisions. Markov decision theory provides tools for addressing sequential decision making problems with classical information structures. In this thesis, we introduce a new approach for decision making problems with non-classical information structures. This approach relies on the idea of common information between decision-makers. Intuitively, common information consists of past observations and decisions that are commonly known to the current and future decision makers. We show that a common information based approach can allow us to discover new structural results of optimal decision strategies and provide a sequential decomposition of the decision-making problems. We first demonstrate this approach on two specific instances of sequential problems, namely, a real-time multi-terminal communication system and a decentralized control system with delayed sharing of information. We then show that the common information methodology applies more generally to any
summary: Recent work in @cite_17 derives structural results for distributed optimization in Markov decision systems with delayed information. Such problems exhibit gaps between centralized and distributed scheduling. The use of in @cite_17 is similar in spirit to the assumption in the current paper that each user observes its own random event @math . The work @cite_17 derives a sufficient statistic for dynamic programming. It does not consider time average constraints and its solutions do not involve correlated scheduling via a pseudorandom sequence. Recent work in @cite_19 considers distributed reporting of events with different qualities, but considers a more restrictive class of policies that do not use correlated scheduling. The current paper treats a different model than @cite_17 and @cite_19 , and shows that correlated scheduling is necessary in systems with constraints. Further, the current paper provides complexity reduction results under a preferred action property (Section ) and provides an online algorithm that does not require a-priori knowledge of event probabilities (Section ).