Santa Fe Institute

SFI / NMC Program on Combining Information Theory and Game Theory

Organizers: David Wolpert (SFI External Faculty), Simon DeDeo (SFI Omidyar Fellow), Nils Bertschinger (Max Planck), Eckehard Olbrich (Max Planck), Eric Smith (SFI External Faculty), Luis Bettencourt (SFI)

How a single agent (human, firm, animal, etc.) behaves typically depends on what information it has about its environment, and on its preferences. Accordingly, the joint behavior of multiple interacting agents can depend strongly on the information available to the separate agents, both about one another, and about external random variables. Precisely how the joint behavior depends on the information available to the agents is determined by the preferences of those agents. So in general there is a strong interplay among the preferences of all the agents, their behavior, and the information structure connecting them.

One tool that might help us understand this interplay is Shannon information theory. In Shannon information theory, information is a function of a distribution. Increasing the amount of information in a distribution means making that distribution more tightly concentrated. This definition applies not only if the support of the distribution shrinks or expands, but also if it moves.

Another tool that might help us understand the interplay is game theory. In contrast to Shannon information theory, game theory does not quantify information in terms of properties of probability distributions. Rather the information available to a player is quantified as an "information set," specifying a set of states the world might be in. The amount of information available to a player increases if such an information set shrinks. In contrast to the case with Shannon information theory, the change in information for moving an information set is undefined.

There are other differences between information theory and game theory. For example, whereas the foundations of Shannon information theory concern a single player (the designer of a communication network), the foundations of game theory concern multiple players.

Reconciling the different perspectives on information in Shannon information theory and game theory could have many benefits. Most directly, it may help us understand the interplay among the preferences of a set of interacting players, their behavior, and the information structure connecting them. As potential examples, it might help us address issues like the following:

1. How do information theoretic quantifications of the joint behavior of a set of interacting players (e.g., mutual information between actions of pairs of them) vary with changes to the preferences of those players?

2. Can relating the philosophical foundations of the two fields improve them? For example, as Shannon himself emphasized, Shannon information is purely "syntactic," quantifying the amount of information in a distribution purely by how concentrated it is. Can the utility functions of game theory—which depend not just on how concentrated a distribution is, but also on where it is concentrated—be used to define a "semantic" variant of Shannon information?

3. Can relating the mathematical formalisms of the two fields improve them? For example, are there analogs of the powerful theorems of information theory for game-theoretic quantities, e.g., game theoretic versions of results concerning rate distortion tradeoffs, the data processing inequality, etc.?

More generally, greater understanding of the relation between information theory and game theory may generate breakthroughs in many disciplines, including economics, political science, cognitive sciences and artificial intelligence.

Full web page here.

Co-hosted by HomeAway, Inc.

Held at 1110 W 5th Street, Suite 300, Austin, TX