Behrouz Touri

Ali Khanafer, Behrouz Touri, Tamer Başar

We study the interaction between a network designer and an adversary over a dynamical network. The network consists of nodes performing continuous-time distributed averaging. The goal of the network designer is to assist the nodes reach consensus by changing the weights of a limited number of links in the network. Meanwhile, an adversary strategically disconnects a set of links to prevent the nodes from converging. We formulate two problems to describe this competition where the order in which the players act is reversed in the two problems. We utilize Pontryagin's Maximum Principle (MP) to tackle both problems and derive the optimal strategies. Although the canonical equations provided by the MP are intractable, we provide an alternative characterization for the optimal strategies that highlights a connection with potential theory. Finally, we provide a sufficient condition for the existence of a saddle-point equilibrium (SPE) for this zero-sum game.

Shinkyu Park, Behrouz Touri, Marcos M. Vasconcelos

We investigate a coordination model for a two-stage collective decision-making problem within the framework of global games. The agents observe noisy signals of a shared random variable, referred to as the fundamental, which determines the underlying payoff. Based on these signals, the agents decide whether to participate in a collective action now or to delay. An agent who delays acquires additional information by observing the identities of agents who have chosen to participate in the first stage. This informational advantage, however, comes at the cost of a discounted payoff if coordination ultimately succeeds. Within this decision-making framework, we analyze how the option to delay can enhance collective outcomes. We show that this intertemporal trade-off between information acquisition and payoff reduction can improve coordination and increase the efficiency of collective decision-making.

Xinran Zheng, Leonardo Massai, Massimo Franceschetti et al.

Network centrality is a foundational concept for quantifying the importance of nodes within a network. Many traditional centrality measures--such as degree and betweenness centrality--are purely structural and often overlook the dynamics that unfold across the network. However, the notion of a node's importance is inherently context-dependent and must reflect both the system's dynamics and the specific objectives guiding its operation. Motivated by this perspective, we propose a dynamic, task-aware centrality framework rooted in optimal control theory. By formulating a problem on minimum energy control of average opinion based on Laplacian dynamics and focusing on the variance of terminal state, we introduce a novel centrality measure--termed U-centrality--that quantifies a node's ability to unify the agents' state. We demonstrate that U-centrality interpolates between known measures: it aligns with degree centrality in the short-time horizon and converges to a new centrality over longer time scales which is closely related to current-flow closeness centrality. This work bridges structural and dynamical approaches to centrality, offering a principled, versatile tool for network analysis in dynamic environments.

Xinran Zheng, Tara Javidi, Behrouz Touri

We propose a general framework for distributed stochastic optimization under delayed gradient models. In this setting, $n$ local agents leverage their own data and computation to assist a central server in minimizing a global objective composed of agents' local cost functions. Each agent is allowed to transmit stochastic-potentially biased and delayed-estimates of its local gradient. While a prior work has advocated delay-adaptive step sizes for stochastic gradient descent (SGD) in the presence of delays, we demonstrate that a pre-chosen diminishing step size is sufficient and matches the performance of the adaptive scheme. Moreover, our analysis establishes that diminishing step sizes recover the optimal SGD rates for nonconvex and strongly convex objectives.

Shankara Narayanan Krishna, Aviral Kumar, Fabio Somenzi et al.

A constant-rate multi-mode system is a hybrid system that can switch freely among a finite set of modes, and whose dynamics is specified by a finite number of real-valued variables with mode-dependent constant rates. Alur, Wojtczak, and Trivedi have shown that reachability problems for constant-rate multi-mode systems for open and convex safety sets can be solved in polynomial time. In this paper, we study the reachability problem for non-convex state spaces and show that this problem is in general undecidable. We recover decidability by making certain assumptions about the safety set. We present a new algorithm to solve this problem and compare its performance with the popular sampling based algorithm rapidly-exploring random tree (RRT) as implemented in the Open Motion Planning Library (OMPL).

Ben McCamish, Vahid Ghadakchi, Arash Termehchy et al.

As most users do not precisely know the structure and/or the content of databases, their queries do not exactly reflect their information needs. The database management systems (DBMS) may interact with users and use their feedback on the returned results to learn the information needs behind their queries. Current query interfaces assume that users do not learn and modify the way way they express their information needs in form of queries during their interaction with the DBMS. Using a real-world interaction workload, we show that users learn and modify how to express their information needs during their interactions with the DBMS and their learning is accurately modeled by a well-known reinforcement learning mechanism. As current data interaction systems assume that users do not modify their strategies, they cannot discover the information needs behind users' queries effectively. We model the interaction between users and DBMS as a game with identical interest between two rational agents whose goal is to establish a common language for representing information needs in form of queries. We propose a reinforcement learning method that learns and answers the information needs behind queries and adapts to the changes in users' strategies and prove that it improves the effectiveness of answering queries stochastically speaking. We propose two efficient implementation of this method over large relational databases. Our extensive empirical studies over real-world query workloads indicate that our algorithms are efficient and effective.