Search

We consider games of incomplete information in which the players' payoffs depend both on a privately observed type and an unknown but common "state of nature". External to the game, a data provider knows the state of nature and sells information to the players, thus solving a joint information and mechanism design problem: deciding which information to sell while eliciting the player' types and collecting payments. We restrict ourselves to a general class of symmetric games with quadratic payoffs that includes games of both strategic substitutes (e.g. Cournot competition) and strategic complements (e.g. Bertrand competition, Keynesian beauty contest). By to the Revelation Principle, the sellers' problem reduces to designing a mechanism that truthfully elicits the player' types and sends action recommendations that constitute a Bayes Correlated Equilibrium of the game. We fully characterize the class of all such Gaussian mechanisms (where the joint distribution of actions and private signals is a multivariate normal distribution) as well as the welfare- and revenue- optimal mechanisms within this class. For games of strategic complements, the optimal mechanisms maximally correlate the players' actions, and conversely maximally anticorrelate them for games of strategic substitutes. In both cases, for sufficiently large uncertainty over the players' types, the recommendations are deterministic (and linear) conditional on the state and the type reports, but they are not fully revealing.

In addition to its public health crisis, COVID-19 pandemic has led to the shutdown and closure of workplaces with an estimated total cost of more than $16 trillion. Given the long hours an average person spends in buildings and indoor environments, this research article proposes data-driven control strategies to design optimal indoor airflow to minimize the exposure of occupants to viral pathogens in built environments. A general control framework is put forward for designing an optimal velocity field and proximal policy optimization, a reinforcement learning algorithm is employed to solve the control problem in a data-driven fashion. The same framework is used for optimal placement of disinfectants to neutralize the viral pathogens as an alternative to the airflow design when the latter is practically infeasible or hard to implement. We show, via simulation experiments, that the control agent learns the optimal policy in both scenarios within a reasonable time. The proposed data-driven control framework in this study will have significant societal and economic benefits by setting the foundation for an improved methodology in designing case-specific infection control guidelines that can be realized by affordable ventilation devices and disinfectants.

The COVID-19 pandemic began over two years ago, yet schools, businesses, and other organizations are still struggling to keep the risk of disease outbreak low while returning to (near) normal functionality. Observations from these past years suggest that this goal can be achieved through the right balance of mitigation strategies, which may include some combination of mask use, vaccinations, viral testing, and contact tracing. The choice of mitigation measures will be uniquely based on the needs and available resources of each organization. This article presents practical guidance for creating these policies based on an analytical model of disease spread that captures the combined effects of each of these interventions. The resulting guidance is tested through simulation across a wide range of parameters and used to discuss the spread of disease on college campuses.

Access to capital is a major constraint for economic growth in the developing world. Yet those attempting to lend in this space face high defaults due to their inability to distinguish creditworthy borrowers from the rest. In this paper, we propose two novel scoring mechanisms that incentivize community members to truthfully report their signal on the creditworthiness of others in their community. We first design a truncated asymmetric scoring-rule for a setting where the lender has no liquidity constraints. We then derive a novel, strictly-proper VCG scoring mechanism for the liquidity-constrained setting. Whereas Chen et al. [2011] give an impossibility result for an analogous setting in which sequential reports are made in the context of decision markets, we achieve a positive result through appeal to interim beliefs about the reports of others in a setting with simultaneous reports.Moreover, the use of VCG methods allows for the integration of linear belief aggregation methods., Comment: 17 pages, submitted to WINE

In this work, inspired by secret sharing schemes, we introduce a privacy-preserving approach for network consensus, by which all nodes in a network can reach an agreement on their states without exposing the individual state to neighbors. With the privacy degree defined for the agents, the proposed method makes the network resistant to the collusion of any given number of neighbors, and protects the consensus procedure from communication eavesdropping. Unlike existing works, the proposed privacy-preserving algorithm is resilient to node failures. When a node fails, the method offers the possibility of rebuilding the lost node via the information kept in its neighbors, even though none of the neighbors knows the exact state of the failing node. Moreover, it is shown that the proposed method can achieve consensus and average consensus almost surely, when the agents have arbitrary privacy degrees and a common privacy degree, respectively. To illustrate the theory, two numerical examples are presented., Comment: 14 pages, 5 figures

The transition kernel of a continuous-state-action Markov decision process (MDP) admits a natural tensor structure. This paper proposes a tensor-inspired unsupervised learning method to identify meaningful low-dimensional state and action representations from empirical trajectories. The method exploits the MDP's tensor structure by kernelization, importance sampling and low-Tucker-rank approximation. This method can be further used to cluster states and actions respectively and find the best discrete MDP abstraction. We provide sharp statistical error bounds for tensor concentration and the preservation of diffusion distance after embedding. We further prove that the learned state/action abstractions provide accurate approximations to latent block structures if they exist, enabling function approximation in downstream tasks such as policy evaluation.

We address the problem of learning the parameters of a stable linear time invariant (LTI) system or linear dynamical system (LDS) with unknown latent space dimension, or order, from a single time--series of noisy input-output data. We focus on learning the best lower order approximation allowed by finite data. Motivated by subspace algorithms in systems theory, where the doubly infinite system Hankel matrix captures both order and good lower order approximations, we construct a Hankel-like matrix from noisy finite data using ordinary least squares. This circumvents the non-convexities that arise in system identification, and allows accurate estimation of the underlying LTI system. Our results rely on careful analysis of self-normalized martingale difference terms that helps bound identification error up to logarithmic factors of the lower bound. We provide a data-dependent scheme for order selection and find an accurate realization of system parameters, corresponding to that order, by an approach that is closely related to the Ho-Kalman subspace algorithm. We demonstrate that the proposed model order selection procedure is not overly conservative, i.e., for the given data length it is not possible to estimate higher order models or find higher order approximations with reasonable accuracy., Comment: Restructuring the paper

We argue that the mathematical structure, enabling certain cascading and emergent phenomena to intuitively emerge, coincides with Galois connections. We introduce the notion of generative effects to formally capture such phenomena. We establish that these effects arise, via a notion of a veil, from either concealing mechanisms in a system or forgetting characteristics from it. The goal of the work is to initiate a mathematical base that enables us to further study such phenomena. In particular, generative effects can be further linked to a certain loss of exactness. Homological algebra, and related algebraic methods, may then be used to characterize the effects., Comment: 37 pages

We consider the problem of robustness in large consensus networks that occur in many areas such as distributed optimization. Robustness, in this context, is the scaling of performance measures, e.g. H2-norm, as a function of network dimension. We provide a formal framework to quantify the relation between such performance scaling and the convergence speed of the network. Specifically, we provide upper and lower bounds for the convergence speed in terms of robustness and discuss how these bounds scale with the network topology. The main contribution of this work is that we obtain tight bounds, that hold regardless of network topology. The work here also encompasses some results in convergence time analysis in previous literature., Comment: 7 pages, 3 figures, IEEE American Control Conference 2018 (Accepted; To be published)

We study a model for cascade effects over finite networks based on a deterministic binary linear threshold model. Our starting point is a networked coordination game where each agent's payoff is the sum of the payoffs coming from pairwise interactions with each of the neighbors. We first establish that the best response dynamics in this networked game is equivalent to the linear threshold dynamics with heterogeneous thresholds over the agents. While the previous literature has studied such linear threshold models under the assumption that each agent may change actions at most once, a study of best response dynamics in such networked games necessitates an analysis that allows for multiple switches in actions. In this paper, we develop such an analysis and construct a combinatorial framework to understand the behavior of the model. To this end, we establish that the agents behavior cycles among different actions in the limit and provide three sets of results. We first characterize the limiting behavioral properties of the dynamics. We determine the length of the limit cycles and reveal bounds on the time steps required to reach such cycles for different network structures. We then study the complexity of decision/counting problems that arise within the context. Specifically, we consider the tractability of counting the number of limit cycles and fixed-points, and deciding the reachability of action profiles. We finally propose a measure of network resilience that captures the nature of the involved dynamics. We prove bounds and investigate the resilience of different network structures under this measure., Comment: 49 pages, 2 figures

Robustness of distributed routing policies is studied for dynamical flow networks, with respect to adversarial disturbances that reduce the link flow capacities. A dynamical flow network is modeled as a system of ordinary differential equations derived from mass conservation laws on a directed acyclic graph with a single origin-destination pair and a constant inflow at the origin. Routing policies regulate the way the inflow at a non-destination node gets split among its outgoing links as a function of the current particle density, while the outflow of a link is modeled to depend on the current particle density on that link through a flow function. The dynamical flow network is called partially transferring if the total inflow at the destination node is asymptotically bounded away from zero, and its weak resilience is measured as the minimum sum of the link-wise magnitude of all disturbances that make it not partially transferring. The weak resilience of a dynamical flow network with arbitrary routing policy is shown to be upper-bounded by the network's min-cut capacity, independently of the initial flow conditions. Moreover, a class of distributed routing policies that rely exclusively on local information on the particle densities, and are locally responsive to that, is shown to yield such maximal weak resilience. These results imply that locality constraints on the information available to the routing policies do not cause loss of weak resilience. Some fundamental properties of dynamical flow networks driven by locally responsive distributed policies are analyzed in detail, including global convergence to a unique limit flow., Comment: 32 pages, 5 figures, journal submission

Cortisol is released to relay information to cells to regulate metabolism and reaction to stress and inflammation. In particular, cortisol is released in the form of pulsatile signals. This low-energy method of signaling seems to be more efficient than continuous signaling. We hypothesize that there is a controller in the anterior pituitary that leads to pulsatile release of cortisol, and propose a mathematical formulation for such controller, which leads to impulse control as opposed to continuous control. We postulate that this controller is minimizing the number of secretory events that result in cortisol secretion, which is a way of minimizing the energy required for cortisol secretion; this controller maintains the blood cortisol levels within a specific circadian range while complying with the first order dynamics underlying cortisol secretion. We use an ℓ[subscript 0]-norm cost function for this controller, and solve a reweighed ℓ[subscript 1[-norm minimization algorithm for obtaining the solution to this optimization problem. We use four examples to illustrate the performance of this approach: (i) a toy problem that achieves impulse control, (ii) two examples that achieve physiologically plausible pulsatile cortisol release, (iii) an example where the number of pulses is not within the physiologically plausible range for healthy subjects while the cortisol levels are within the desired range. This novel approach results in impulse control where the impulses and the obtained blood cortisol levels have a circadian rhythm and an ultradian rhythm that are in agreement with the known physiology of cortisol secretion. The proposed formulation is a first step in developing intermittent controllers for curing cortisol deficiency. This type of bio-inspired pulse controllers can be employed for designing non-continuous controllers in brain-machine interface design for neuroscience applications., National Science Foundation (U.S.). Graduate Research Fellowship, National Institutes of Health (U.S.) (DP1 OD003646), National Institutes of Health (U.S.) (1-R01-GM104948-03), National Science Foundation (U.S.) (0836720), National Science Foundation (U.S.) (EFRI-0735956)

The primary concerns of this paper are twofold: understanding the value of storage in the presence of ramp constraints and exogenous energy prices, and understanding the implications of the associated optimal storage management policy for qualitative and quantitative characteristics of storage response to real-time prices. The optimal policy, along with the associated finite-horizon time-averaged value of storage, are analytically characterized in this paper. An analytical upper bound on the infinite-horizon time-averaged value of storage is also derived. This bound is valid for any achievable realization of prices when the support of the distribution is fixed, and highlights the dependence of the value of storage on ramp constraints and storage capacity. It is shown that while the value of storage is a non-decreasing function of price volatility, due to the finite ramp rate, the value of storage saturates quickly as the capacity increases, regardless of volatility. To study the implications of the optimal policy, computational experiments are presented that suggest optimal utilization of storage can, in expectation, induce a considerable amount of price elasticity near the average price. Then, a computational framework is presented for characterization of the behavior of storage as a function of price and the state of charge, which illustrates a steep buy/sell phase transition in the price-state plane., National Science Foundation (U.S.). Graduate Research Fellowship, MIT Energy Initiative (Seed Grant), Charles Stark Draper Laboratory

Original manuscript: March 25, 2011, Strong resilience properties of dynamical networks are analyzed for distributed routing policies. The latter are characterized by the property that the way the outflow at a non-destination node gets split among its outgoing links is allowed to depend only on local information about the current particle densities on the outgoing links. The strong resilience of the network is defined as the infimum sum of link-wise flow capacity reductions making the asymptotic total inflow to the destination node strictly less than the total outflow at the origin. A class of distributed routing policies that are responsive to local information is shown to yield the maximum possible strong resilience under such local information constraints for an acyclic dynamical network with a single origin-destination pair. The maximal achievable strong resilience is shown to be equal to the minimum node residual capacity of the network. The latter depends on the limit flow of the unperturbed network and is defined as the minimum, among all the non-destination nodes, of the sum, over all the links outgoing from the node, of the differences between the maximum flow capacity and the limit flow of the unperturbed network. We propose a simple convex optimization problem to solve for equilibrium flows of the unperturbed network that minimize average delay subject to strong resilience guarantees, and discuss the use of tolls to induce such an equilibrium flow in traffic networks. Finally, we present illustrative simulations to discuss the connection between cascaded failures and the resilience properties of the network., National Science Foundation (U.S.). Office of Emerging Frontiers in Research and Innovation (Grant 0735956), United States. Air Force Office of Scientific Research (Grant FA9550-09-1-0538)

We infer local influence relations between networked entities from data on outcomes and assess the value of temporal data by formulating relevant binary hypothesis testing problems and characterizing the speed of learning of the correct hypothesis via the Kullback-Leibler divergence, under three different types of available data: knowing the set of entities who take a particular action; knowing the order that the entities take an action; and knowing the times of the actions., United States. Air Force. Office of Scientific Research (Contract FA9550-09-1-0420).

We consider a dynamical formulation of network flows, whereby the network is modeled as a switched system of ordinary differential equations derived from mass conservation laws on directed graphs with a single origin-destination pair and a constant inflow at the origin. The rate of change of the density on each link of the network equals the difference between the inflow and the outflow on that link. The inflow to a link is determined by the total flow arriving to the tail node of that link and the routing policy at that tail node. The outflow from a link is modeled to depend on the current density on that link through a flow function. Every link is assumed to have finite capacity for density and the flow function is modeled to be strictly increasing up to the maximum density. A link becomes inactive when the density on it reaches the capacity. A node fails if all its outgoing links become inactive, and such node failures can propagate through the network due to rerouting of flow. We prove some properties of these dynamical networks and study the resilience of such networks under distributed routing policies with respect to perturbations that reduce link-wise flow functions. In particular, we propose an algorithm to compute upper bounds on the maximum resilience over all distributed routing policies, and discuss examples that highlight the role of cascading failures on the resilience of the network., National Science Foundation (U.S.). Office of Emerging Frontiers in Research and Innovation (ARES Grant 0735956), United States. Air Force Office of Scientific Research (Grant FA9550-09-1-0538)

How can we effectively model situations with large alphabets? On a pragmatic level, any engineered system, be it for inference, communication, or encryption, requires working with a finite number of symbols. Therefore, the most straight-forward model is a finite alphabet. However, to emphasize the disproportionate size of the alphabet, one may want to compare its finite size with the length of data at hand. More generally, this gives rise to scaling models that strive to capture regimes of operation where one anticipates such imbalance. Large alphabets may also be idealized as infinite. The caveat then is that such generality strips away many of the convenient machinery of finite settings. However, some of it may be salvaged by refocusing the tasks of interest, such as by moving from sequence to pattern compression, or by minimally restricting the classes of infinite models, such as via tail properties. In this paper we present an overview of models for large alphabets, some recent results, and possible directions in this area.

Author's final manuscript: September 29, 2011, This paper examines the value of storage in securing reliability of a system with uncertain supply and demand, and supply friction. The storage is frictionless as a supply source, but it cannot be filled up instantaneously. The focus is on application to an energy network in which the nominal supply and demand are assumed to match perfectly, while deviations from the nominal values are modeled as random shocks with stochastic arrivals. Due to friction, the random shocks cannot be tracked by the main supply sources. Storage, when available, can be used to compensate, fully or partially, for the surge in demand or sudden drop in supply. The problem of optimal utilization of storage with the objective of maximizing system reliability is formulated as minimization of the expected discounted cost of blackouts over an infinite horizon. It is shown that when the stage cost is linear in the size of the blackout, the optimal policy is myopic in the sense that all shocks will be compensated by storage up to the available level of storage. However, when the stage cost is strictly convex, it may be optimal to curtail some of the demand and allow a small blackout in the interest of maintaining a higher level of reserve, which may help avoid a large blackout in the future. The value of storage capacity in improving reliability, as well as the effects of the associated optimal policies under different stage costs on the probability distribution of blackouts are examined., National Science Foundation (U.S.), Siemens-MIT Alliance