NASA Logo, National Aeronautics and Space Administration

Introduction

We recently proved that game theory and statistical physics are identical when cast in terms of information theory.

We call the associated formalism Probability Collectives (PC). PC opens many new lines of research, and provides new approaches to problems in distributed control and distributed optimization.

Overview

Intuitively, players in a game and their reward functions are mathematically identical to particles in a system and their energy functions. Games with varying numbers of agents are analogous to physical systems with varying numbers of particles. Quantified bounded rationality of agents is formally identical to the temperature of particles.

This deep identity opens a hybrid field where the techniques of game theory and statistical physics can be combined and exploited (e.g., for discrete, continuous, mixed, and constrained optimization).

A New State of the Art

Collaborators at Ames, Oxford, Stanford, Berkeley, Los Alamos, GE, and BAE Systems have been investigating the extremely rich theory arising from this hybridization, with applications in areas such as distributed optimization and control of multi-agent systems.

Algorithms developed to date have always far outperformed conventional techniques in simulation, and this performance has been verified in a few hardware demonstrations. The techniques also "are adaptive, robust, and fault tolerant. They also scale well, giving increasing benefits as system size grows.

In these algorithms, agents in the "collective" strive for a global objective -- perhaps multiple simultaneous objectives -- by pursuing their own best interests. Previously, designing individual (or "local") control laws to achieve this has been difficult.

(For details, see our Publications page.)

Applications

The PC approach is widely applicable, with minimal (or even no) hand-tuning. Potential applications include:
* Flaplet arrays to stabilize aircraft wings.
* Design of other aircraft structures and systems.
* Adaptive programming of nanocomputers.
* Control of network routers.
* Discrete, continuous, mixed, and constrained optimization.
* Function optimization via parallel algorithms.
* Airline fleet assignment.
* Investment and computational economics.
* Nonlinear time series analysis.
* Population biology studies.
* Coordination of human teams.
* Control of UAV clusters or agent teams.
* Control of robots for space station construction.
* and more...

Team

Principal Investigator
David Wolpert

Other Contributors
Nicolas E. Antoine (Airbus/Stanford)
Stefan Bieniawski (Stanford)
Ilan Kroo (Stanford)
Chiu Fan Lee (Oxford)
Bill Macready (Dwave Systems/NASA)
Dave Nicholson (BAE Systems)
Dev Rajnarayan (Stanford)
Charlie E. M. Strauss (LANL)

Links

David Wolpert's Home Page
PhD Thesis on Flutter Suppression
Stanford Probability Collectives Site
Collectives Workshop, 2003
Stanford AA Design Group

First Gov logo
NASA Logo - nasa.gov