Foraging swarms as Nash equilibria of dynamic games

Nash equilibria in human sensorimotor interactions explained by Q-learning with intrinsic costs

The Nash equilibrium concept has previously been shown to be an important tool to understand human sensorimotor interactions, where different actors vie for minimizing their respective effort while engaging in a multi-agent motor task. However, it is not clear how such equilibria are reached. Here, we compare different reinforcement learning models to human behavior engaged in sensorimotor interactions with haptic feedback based on three classic games, including the prisoner's dilemma, and the symmetric and asymmetric matching pennies games. We find that a discrete analysis that reduces the continuous sensorimotor interaction to binary choices as in classical matrix games does not allow to distinguish between the different learning algorithms, but that a more detailed continuous analysis with continuous formulations of the learning algorithms and the game-theoretic solutions affords different predictions. In particular, we find that Q-learning with intrinsic costs that disfavor deviations from average behavior explains the observed data best, even though all learning algorithms equally converge to admissible Nash equilibrium solutions. We therefore conclude that it is important to study different learning algorithms for understanding sensorimotor interactions, as such behavior cannot be inferred from a game-theoretic analysis alone, that simply focuses on the Nash equilibrium concept, as different learning algorithms impose preferences on the set of possible equilibrium solutions due to the inherent learning dynamics.

Construction of Barrier in a Fishing Game With Point Capture

This paper addresses a particular pursuit-evasion game, called as "fishing game" where a faster evader attempts to pass the gap between two pursuers. We are concerned with the conditions under which the evader or pursuers can win the game. This is a game of kind in which an essential aspect, barrier, separates the state space into disjoint parts associated with each player's winning region. We present a method of explicit policy to construct the barrier. This method divides the fishing game into two subgames related to the included angle and the relative distances between the evader and the pursuers, respectively, and then analyzes the possibility of capture or escape for each subgame to ascertain the analytical forms of the barrier. Furthermore, we fuse the games of kind and degree by solving the optimal control strategies in the minimum time for each player when the initial state lies in their winning regions. Along with the optimal strategies, the trajectories of the players are delineated and the upper bounds of their winning times are also derived.

Game Design and Analysis for Price-Based Demand Response: An Aggregate Game Approach

In this paper, an aggregate game is adopted for the modeling and analysis of energy consumption control in smart grid. Since the electricity users' cost functions depend on the aggregate energy consumption, which is unknown to the end users, an average consensus protocol is employed to estimate it. By neighboring communication among the users about their estimations on the aggregate energy consumption, Nash seeking strategies are developed. Convergence properties are explored for the proposed Nash seeking strategies. For energy consumption game that may have multiple isolated Nash equilibria, a local convergence result is derived. The convergence is established by utilizing singular perturbation analysis and Lyapunov stability analysis. Energy consumption control for a network of heating, ventilation, and air conditioning systems is investigated. Based on the uniqueness of the Nash equilibrium, it is shown that the players' actions converge to a neighborhood of the unique Nash equilibrium nonlocally. More specially, if the unique Nash equilibrium is an inner Nash equilibrium, an exponential convergence result is obtained. Energy consumption game with stubborn players is studied. In this case, the actions of the rational players can be driven to a neighborhood of their best response strategies by using the proposed method. Numerical examples are presented to verify the effectiveness of the proposed methods.

A Clustering-Based Approach to Enriching Code Foraging Environment

Developers often spend valuable time navigating and seeking relevant code in software maintenance. Currently, there is a lack of theoretical foundations to guide tool design and evaluation to best shape the code base to developers. This paper contributes a unified code navigation theory in light of the optimal food-foraging principles. We further develop a novel framework for automatically assessing the foraging mechanisms in the context of program investigation. We use the framework to examine to what extent the clustering of software entities affects code foraging. Our quantitative analysis of long-lived open-source projects suggests that clustering enriches the software environment and improves foraging efficiency. Our qualitative inquiry reveals concrete insights into real developer's behavior. Our research opens the avenue toward building a new set of ecologically valid code navigation tools.

Optimal Group Size for Software Change Tasks: A Social Information Foraging Perspective

Group size is a key factor in collaborative software development and many other cybernetic applications where task assignments are important. While methods exist to estimate its value for proprietary projects, little is known about how group size affects distributed and decentralized cybernetic applications and in particular open source software (OSS) development. This paper presents a novel approach in which we frame developers' collective resolution of OSS change tasks as a social information foraging problem. This new perspective enables us to predict the optimal group size and quantify group size's effect on individual performance. We test the theory with data mined from two projects: 1) Firefox and 2) Mylyn. This paper not only uncovers the mismatch of optimal and actual group sizes, but also reveals the association of optimality with improved productivity. In addition, the social-level productivity gain is observed as project evolves. We show this paper's impact by extending the frontiers of knowledge in two areas: 1) social coding and 2) recommendation systems.

Solving Potential Games With Dynamical Constraint

We solve N -player potential games with dynamical constraint in this paper. Potential games with stable dynamics are first considered followed by one type of potential games without inherently stable dynamics. Different from most of the existing Nash seeking methods, we provide an extremum seeking-based method that does not require explicit information on the game dynamics or the payoff functions. Only measurements of the payoff functions are needed in the game strategy synthesis. Lie bracket approximation is used for the analysis of the proposed Nash seeking scheme. A singularly semi-globally practically uniformly asymptotically stable result is presented for potential games with stable dynamics and an ultimately bounded result is provided for potential games without inherently stable dynamics. For first-order perturbed integrator-type dynamics, we employ an extended-state observer to deal with the disturbance such that better convergence is achievable. Stability of the closed-loop system is proven and the ultimate bound is quantified. Numerical examples are presented to verify the effectiveness of the proposed methods.

Sufficient and Necessary Open-Loop Stackelberg Strategy for Two-Player Game With Time Delay

This paper is concerned with both difference and differential leader-follower games with time delay. The problem remains challenging although the leader-follower game for delay-free system has been well studied in the past decades. The main obstacle encountered is the noncausality of strategy design caused by the delay. The key technique developed to overcome the difficulty is the introduction of the new co-states which capture the future information of the control and the new state which contains the past effects. The novel contributions of this paper are as follows. First, the sufficient and necessary solvability condition is given to ensure the existence of a unique open-loop Stackelberg strategy for the difference game. Second, the open-loop strategy is explicitly obtained in terms of decoupled and symmetric Riccati equations. Last but not least, a unique strategy for continuous time systems is also given by applying the techniques developed in this paper.