Alfredo Garcia - US grants

This research project will study optimization algorithms rooted in the ideas of game theory in the context of complex network optimization, and particularly decentralized network optimization. Probably the central issue in managing such decentralized networks has been how to set prices so as to motivate the competing users to evolve to an overall system optimal configuration. The research will investigate the powerful paradigm of economic competition in the framework of artificial dynamic games that are played off-line, resulting in an algorithm that is potentially practical for large-scale systems optimization. The basic paradigm that will be investigated derives from Fictitious Play which is an adaptive procedure wherein each player assumes that other players will play according to the empirical distribution of their previous plays. The Fictitious Play method is a novel paradigm for optimization that draws from several distinct disciplines and application areas, including classical optimization, game theory, transportation science, and queueing network protocols. The robust nature of the algorithm allows for the ill-structured black box models of real systems which seldom exhibit the kind of smoothness properties that classical optimization methods demand. Its applicability in the context of two important real-world systems: a) internet traffic routing protocols and b) dynamic route guidance will be tested.

Complex networks optimization is an important capability in a society increasingly dominated by ever more complex networks of people and machines. Examples include intelligent transportation systems, computer networks, and supply chains of customers and suppliers. The success of the research will lead to the development of a theoretical basis for the optimization of such complex-structured systems. The applicability of the proposed algorithmic paradigm of game theory through its application to realistic problems arising in the design and operation of the communications and transportation networks will be tested and refined. This research will not only lead to potential improvements in these application arenas but will also necessitate significant interactions with industry and government to insure realism for the models and data developed.

In the first part of our proposal, we study the long run reliability (or security of supply) of electricity markets under price caps. This (and other forms or market intervention) cast doubts on the market ability to provide new capacity in a socially efficient manner (scale, technology and timing). We propose to develop a dynamic game model of investment. A full characterization of equilibrium investment will shed light on a number of contentious issues in the restructuring debate. Examples include; the possibility of "boom and bust" cycles in equilibrium, a potential technology bias with harmful effects on the environment, and the need to incorporate capacity markets.

In the second part of our proposal we study learning algorithms as potentially powerful computational tools for electricity markets. The complexity of electricity markets calls for the incorporation of some form of bounded rationality in the modeling efforts. However, when players use simple, adaptive (possibly sub-optimal) rules, repeated interaction may induce equilibrium outcomes in the long run. Although, many "agent based" simulation models have been advocated for analyzing electricity markets, they lack solid theoretical support on issues such as convergence and/or the nature of equilibrium. In this proposal we will represent competition in electricity markets under certain congestion management protocols, as games with a special structure, i.e. "potential games'. For this class of games, the class of "fictitious play" learning algorithms has been proven to converge with probability one. Computational tests a large-scale model will serve to validate and assess the practicality of the class of strategic learning models proposed.

As is clear from the emergence of the Internet, the national electric power grid, and other large-scale network infrastructures, engineering systems today are increasingly reliant on distributed control authority and coordination between subsystems. Typically, coordination is achieved in engineering systems through the specification of ad hoc protocols for relatively well-defined (constrained) interactions between distributed systems. As information systems become more integrated into society, however, we find that existing protocols are not adequately tuned for new applications and/or unexpected situations. Though issues of decentralized control and planning are becoming more prevalent in the engineering systems we build today, there unfortunately appears to be little in the way of underlying guiding principles and theory for designing and operating such systems. Notions of game theory and decentralized control go only part way toward revealing the basic problems associated with distributed engineering systems, especially in situations where distributed agents/players/actors all recognize the same performance objective and would work together except for the problem of having little or no opportunities to coordinate their actions because of limited communication. In this project, the PI's goal is to derive an enhanced understanding of coordination without explicit communication by posing a new class of sequential decision processes, known as coordination processes, whose analysis will provide new theoretical insights and new algorithmic approaches in decentralized systems and distributed planning applications. The mathematical framework the PI team will investigate is rooted in the theory of controlled Markov processes and dynamic games, thus providing a firm foundation for new results, including new solution concepts and new algorithmic approaches for identifying optimal coordination strategies. The PI team will focus their efforts broadly on two subclasses of coordination problems: transient coordination processes where all actors seek to drive an underlying system to a terminal state with minimum cost; repeated play coordination processes where the objective is to learn optimal coordination strategies that tend to minimize the average cost perceived in repeated instances of a coordination problem. The PI team will evaluate their solution concepts and algorithmic procedures in the context of two illustrative applications, a robotic planning problem and an Internet traffic engineering problem, both of which require autonomous agents (actors) to coordinate without opportunities for explicit communication.

Broader Impact: This work will impact diverse research communities, including those for control theory, game theory, and decision sciences. The results should find application in diverse sectors
of engineering and computer science, including the design of new MAC-layer protocols, the design of better conflict resolution algorithms in distributed collaboration tools and peer-to-peer applications, the design and control of transportation resource management systems, and in future sensor management systems.

With the continuing growth of the use of the Internet for business purposes, the consequences of a possible cyber attack that could create a large scale outage of long time duration is an increasingly important economic issue. In 2003, the President's National Strategy to Secure Cyberspace stated that government action is warranted where alleged "market failures result in underinvestment in cyber security". However, there is scant empirical evidence and/or theoretical support for such "market failure". While there exists a large body of technical literature on cyber security, research on the economics of cyber security is still in its very early stages.

This project contributes to a better understanding of the economics of Internet security through a combination of theoretical and empirical research efforts. First, the economic motivations for investment in added Internet security by Internet Service Providers (ISPs) are analyzed using game theoretic models. Customer's sensitivity to quality of service and depreciation of investments in added security play key roles in determining the ISPs' investment incentives. However, these incentives may not be perfectly aligned with the social value (derived from Internet usage) at stake during a cyber attack. Empirical research is undertaken to estimate to what extent private incentives for investment may lead to a situation of underinvestment in cyber security.

The results of this research project will have a broader impact in informing the process of regulatory policy-making towards securing cyberspace. In addition, the interplay between the economic and
technological issues associated with the provision of Internet will be the subject of a number of educational initiatives both at graduate and undergraduate levels. These include: a graduate seminar on cyber security, new material for existing courses in E-commerce and the economics of engineering systems and "Capstone" projects (senior theses). The research findings will be reported in the project web site (http://www.people.virginia.edu/~ag7s/economics_of_internet_security.htm

The telecommunications industry is on the verge of major structural change. Historically, the industry's regulator has allocated licenses for the utilization of well-defined bands within the available spectrum. Unlike other commodities, no secondary market for the spectrum has ever developed. Technological limitations as well as legal and regulatory constraints may have contributed to this fact. Today the evidence clearly points to a situation of relative under-utilization of the spectrum. A "cognitive radio network" (CRN) is a new paradigm for wireless communications aimed at enabling a more efficient use of the spectrum. This research project focuses on two significant technical and regulatory issues which must be resolved to ensure successful deployment of cognitive radio networks.

The first issue relates to the network?s ability to manage interference in a distributed fashion without cooperation from the primary users. Here, the research tasks include the analysis, from a signal processing and algorithmic point of view, of various price-based schemes for dynamic spectrum allocation in a broad range of CRN scenarios under a variety of regulatory restrictions. The second relevant issue pertains to the design of a secondary market for the spectrum. The research investigates the analysis of various design choices taking into account specific spectrum sharing techniques and the associated behavior of sellers (i.e. primary users/primary network service providers (NSP)) and buyers (i.e. cognitive users).

The proposed work targets new models to (i) facilitate distributed spectrum sharing and spectrum decision in a broad range of CRN, and to (ii) provide additional insights into the operation of a secondary spectrum market which could prove useful for regulatory design.

This proposal seeks funding for the Center for Wireless Internet Center for Advanced Technology (WICAT) studies conducted by the Polytechnic Institute of New York site (lead), the University of Virginia site and the site at Auburn University. Funding Requests for Fundamental Research are authorized by an NSF approved solicitation, NSF 10-507. The solicitation invites I/UCRCs to submit proposals for support of industry-defined fundamental research.

This proposal is a comprehensive research project for significantly improving the capacity of wireless networks. In past decades, there has been an exponential growth of wireless devices and wireless networks. While wireless networks have brought us the convenience of mobility and new applications, they are limited by bandwidth bottlenecks. The industry and spectrum regulators are trying to allocate more bandwidth, but they still fall behind the bandwidth increases in wireless networks. Thus it is critically important to use spectrum resources more efficiently. The proposed work aims to decrease interference, including cooperative and cognitive networking. This research will not only make significant contributions to the research community, but also be very valuable for the wireless industry and spectrum regulators.

This proposal aims to eliminate wireless system bottlenecks using cooperative and cognitive technologies, with the potential of enabling a broad spectrum of new wireless applications. The PIs will exploit existing programs, such as NSF REUs and the collaboration with Tuskegee and Northern New Mexico College, which focus on including students from underrepresented groups in the research. The student body at NYU-Poly is quite diverse. Most of the requested funding is going toward student support. The Pisa lo intend to incorporate this work into the new graduate course at NYU-Poly and the new ABET-accredited program at Auburn. Dissemination is clearly outlined: reports to NSF, reports to their IAB, journal and conference papers and making the resulting software packages open source.

Efficient use of limited spectrum is emerging as a major issue in wireless systems. The proposed work focuses on technologies that provide better understanding of wireless networks and greatly enhance spectrum efficiency. with three coupled thrusts: (i) wireless network modeling; (ii) mechanisms for efficient spectrum sharing; and (iii) exploiting enhanced spectrum efficiency for wireless video communications. The project also includes an experimental research component in which the developed approaches will be implemented and tested on the cognitive radio testbed hosted at Virginia Tech and the cooperative networking testbed hosted at NYU-Poly.

The proposed research plans to systematically investigate several of the unique technical challenges and open problems in enhancing radio spectrum efficiency, and supporting emerging video services. This fundamental research will support the development of technologies that achieve new levels of efficiency and quality in wireless broadband services, and will help alleviate the wireless bandwidth limits now being experienced. The work is supported by the Industry Advisory Board as well as individual industry members of the center and has the potential to extend the centers portfolio. The PIs plan to disseminate the work to their industry members and the broader industry and academic community via open-source software as wel as introduce the content within their degree and outreach programs.

The proposed center seeks to establish a new Industry/University Cooperative Research Center (I/UCRC) addressing broadband wireless access and applications. The center will focus on four areas: 1) enabling sharing up to many GHz of spectrum using technological advances and enabling platforms such as spectrum trading and auctions, and millimeter wave communications; 2) co-existence of heterogeneous devices (e.g. radar and communication systems); 3) providing connectivity for new applications such as wireless devices in the hospitals of the future, bringing wireless into the hospital in novel ways; and (d) improving electronic warfare technologies that address national-security issues.

The new center addresses an area of critical economic and has the potential to support development of broadband wireless as a platform for innovation as addressed in the White House PCAST Report. The proposed center has the potential to link a diverse set of member companies across the broadband industry sector with university discovery in this area. Moreover, the center participants have a history of start-up initiation, and the opportunity from new starts to leverage the ecosystem created by the center is significant. The center plans to impact students via their conduct of center research, curriculum development and REU site development.

The term smart market refers to a market design in which clearing must be implemented by solving an optimization problem satisfying technical constraints that cannot otherwise be met via more traditional market structures (e.g. bilateral trading). All trading in a smart market is intermediated by a market manager in charge of clearing. Examples include electricity markets (where network capacity constraints must be satisfied while taking into account power flow) and spectrum auctions for allocating channels (where combinatorial optimization is needed to identify an efficient allocation). This project addresses the problem of designing smart markets when the solution of a non-trivial computational model has to be consulted to determine the feasibility of a given allocation profile. Since such a model is not transparent to the market manager, it is often referred to as a "black-box" model. As an example, the project will focus on the allocation of spectrum access under signaling technologies other than frequency division, which is an instance of this problem because a precise determination of communication capacity can only be obtained by consulting black-box models that take into account the effects of interference amongst users.

This project will focus on the design of smart markets to ensure the efficient allocation of black-box capacity under incomplete information regarding the users' willingness to pay for capacity. The designs considered are iterative in nature. The idea is to allow (at each iteration) a form of self-scheduling by users onto available resources followed by a black-box evaluation of excess capacity, which in turn informs price updates. A key design novelty pertains to the use of different time-scales for pricing (fast) vs. capacity allocation (slow) adjustments. Personalized incentives for each user (in the forms of additional payments or transfers) guarantee that it is a dominant strategy for users to truthfully report their demand throughout the process. Several additional research directions including noisy black-box model and non-convex feasible regions will be considered. Additionally, the application of the smart market designs to electricity markets with high levels of renewable capacity will be considered. If successful, the project will contribute to ensuring that the market dispatch of available resources meets a certain reliability target with highly intermittent nature of renewable output.

PROJECT SUMMARY Sleep apnea is a respiratory disorder that causes chronic intermittent hypoxia throughout the sleep cycle. Neuroimaging studies indicate that the hippocampus is particularly vulnerable to injury in sleep apnea. In addition to the involvement of this brain structure with spatial and recognition memory, hippocampal activity is coupled to and exerts influence on peripheral chemoreflexes and respiratory patterns. Thus, along with its cognitive effects, the neurophysiological changes in the hippocampus may contribute to the development of cardiovascular disease, the increased risk for stroke that occur with untreated sleep apnea. As the duration of untreated sleep apnea persists, the severity of the condition increases, as does the risk of developing increasingly significant cognitive deficit. We hypothesize that chronic intermittent hypoxia caused by sleep apnea triggers reactive oxygen species signaling, resulting in duration-dependent changes to hippocampal neurophysiology and, in turn, causing progressive degradation in hippocampal-based cognition. We test this hypothesis in a rodent model of sleep apnea in which animals are exposed to different durations of chronic intermittent hypoxia. We examine the resulting effects on hippocampal neurophysiology and neurogenesis, focusing on principal neurons involved in learning and memory pathways. In addition to dissecting the role of reactive oxygen species signaling in cognitive changes, we explore the mechanistic origin of this signaling and the potential interaction between cardio-respiratory organs (i.e., carotid bodies) and the hippocampus. The mechanistic insights gained from this work will inform the development of more effective therapies to prevent, or fully reverse, cognitive decline in a condition that affects the quality of life for many Americans.

One of the grand challenges in Artificial Intelligence (AI) and Machine Learning (ML) is building intelligent systems that can learn from data in real time. To learn from streaming data, there is need for novel approaches in online optimization and prediction. Current methods assume sequential availability of gradients (or loss), posing a practical hurdle in implementation. We propose two approaches to address this gap using model-based learning. These approaches are aimed at respectively exploiting, a distributed computing architecture (to divide the required computational effort) or a communications network (to efficiently aggregate disparate data). The collaborative online optimization algorithms and theoretic extensions introduced in this work have a broad range of applications domains such as speech recognition and computer vision, autonomous vehicles, transportation, neuroscience, and business analytics.

Most of classical ML algorithms have been developed under the assumption that data sets are already available in batch form. Transitioning from offline to online learning faces a major practical hurdle in many application domains where the closed-form of the objective function is unknown to the learner. When dealing with streaming data, this black-box property leads to a natural trade-off between delays (due to data or computation) and the speed and accuracy with which a model can be identified. A distributed computing architecture provides a way to reduce delays to obtain reasonably accurate models in the necessary timescale. We propose to study fast distributed asynchronous stochastic gradient approaches for online learning in which coordination between multiple workers (processors) interacting asynchronously is carefully engineered. Improved accuracy and speed may also be jointly achieved by a network of learners receiving different streams of data. Thus, we also consider decentralized models of online learning with multiple learning agents that communicate over a network. With the ability to share predictions or estimates with other agents in a network, the collective can aggregate disparate information in a way to outperform (in terms of accuracy and speed) any individually identified model. Finally, we consider the case in which data streams have graph structure. Streaming graph structure data arises in diverse application domains such as transportation networks, social networks and other networks found in biology, where the graph captures the correlation in data. The proposal includes the development of a new graduate course aimed at providing engineering students with working knowledge on state-of-the-art distributed online optimization techniques.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.