Crate t4t

Tit-for-tat: a game theory toolbox

Tit-for-tat (t4t) is a game theory library with a focus on experimentation over formal analysis. It supports defining games and strategies, then executing them repeatedly in order to collect and observe the results.

The companion crate t4t-games provides some example games and strategies.

Design goal: expressiveness over performance

This library prioritizes expressiveness over performance. It aims to provide a powerful set of abstractions for building arbitrary games and strategies.

This tradeoff is easy to see in the representation of normal-form games, which are represented not as a matrix of payoffs, but as a function from generic move profiles to generic payoffs. This enables normal-form games of arbitrary size, between arbitrary numbers of players, and with arbitrary move and utility values, but is somewhat less efficient than a simple payoff matrix of numbers.

A subtler but more extreme case of this tradeoff is in how games are executed. The Game trait is quite generic, and implementers of this trait do not implement the execution of their game directly, but rather produce a description of how their game is executed. This is much less efficient, but enables generically transforming the execution of a game, for example, defining new games that modify the behavior of existing games.

An example of this capability in action is the Repeated type, which transforms any game into a repeated game, modifying the original game’s state and execution to enable players of the game to see the history of games played so far.

Of course, all things being equal, I’d still like things to run as fast as possible! However, if your application deals only with 2x2 numeric, normal-form games, and you need to run billions of iterations, this might not be the library you’re looking for.

This is a work in progress!

The library is very much a work-in-progress and will continue expanding and evolving.

The type- and method-level documentation is very good in places, minimal in others. The top-level documentation that you’re reading now is sorely missing some good examples to get you started–sorry!

Normal-form games are in good shape, and repeated games are solid for perfect-information games. You can define players and strategies for these games, and they can be played.

There is a lot of infrastructure in place for sequential and state-based types, but the library is still missing the main top-level types to make this convenient to use.

Still to come and low-hanging fruit are convenient mechanisms to run “tournaments” (e.g. play a game with all combinations of players drawn from a set of entrants). Long-term, I’d like to add ways to visualize game executions and build games and strategies interactively, but we’ll see!

Modules

• for1
  Defines indexes into a collection of type PerPlayer<T, 1>.
• for2
  Defines indexes into a collection of type PerPlayer<T, 2> and a move type for 2-player games.
• for3
  Defines indexes into a collection of type PerPlayer<T, 3> and a move type for 3-player games.
• for4
  Defines indexes into a collection of type PerPlayer<T, 4> and a move type for 4-player games.
• for5
  Defines indexes into a collection of type PerPlayer<T, 5>.
• for6
  Defines indexes into a collection of type PerPlayer<T, 6>.
• for7
  Defines indexes into a collection of type PerPlayer<T, 7>.
• for8
  Defines indexes into a collection of type PerPlayer<T, 8>.
• for9
  Defines indexes into a collection of type PerPlayer<T, 9>.
• for10
  Defines indexes into a collection of type PerPlayer<T, 10>.
• for11
  Defines indexes into a collection of type PerPlayer<T, 11>.
• for12
  Defines indexes into a collection of type PerPlayer<T, 12>.
• for13
  Defines indexes into a collection of type PerPlayer<T, 13>.
• for14
  Defines indexes into a collection of type PerPlayer<T, 14>.
• for15
  Defines indexes into a collection of type PerPlayer<T, 15>.
• for16
  Defines indexes into a collection of type PerPlayer<T, 16>.

Structs

• Context
  The strategic context in which a player makes a move during a game.
• Distribution
  A weighted probability distribution over a set of discrete elements, such as moves.
• Dominated
  Captures a domination relationship between moves in a simultaneous move game.
• Error
  An error that occurred while playing a game and the current state when it occurred.
• History
  For repeated games, a history of previously played games.
• Normal
  A game represented in normal form.
• Past
  An iterator over past events while playing a game.
• Payoff
  A collection containing the utility values awarded to each player at the end of a game.
• PerPlayer
  A collection that stores one element corresponding to each player in a game.
• PlayedMoves
  An iterator over the moves played in a game.
• Player
  A player consists of a name and a strategy.
• PlayerIndex
  An index into a per-player collection that is guaranteed to be in-range for a game with P players.
• PlayerIndexes
  An iterator that produces all player indexes of a given index type.
• Ply
  A ply is a single move played during a sequential game.
• PossibleMoves
  An iterator over the possible moves at a particular point in a game with a finite move set.
• PossibleOutcomes
  An iterator over all possible outcomes of a normal-form game.
• PossibleProfiles
  An iterator over all pure strategy profiles for a normal-form game.
• Profile
  A pure strategy profile for a simultaneous game: one move played by each player.
• Repeated
  A finitely repeated or iterated version of game G.
• RepeatedState
  The intermediate state of a repeated game.
• SequentialOutcome
  A (potential) outcome of a sequential game.
• Simultaneous
  A game in which each player plays a single move without knowledge of the other players’ moves.
• SimultaneousOutcome
  A (potential) outcome of a simultaneous game.
• Strategy
  A strategy is a function from an intermediate game context to a move.
• Summary
  Tracks the number of moves played so far in a game.
• Transcript
  A transcript of the moves played (so far) in a sequential game.
• Turn
  One step in the specification of a game’s execution.

Enums

• Action
  The next action to performed while playing a game.
• ErrorKind
  The kind of error that occurred.

Traits

• Game
  A root trait that all games implement, mostly used for its associated types.
• Move
  A trait that collects the trait requirements of moves.
• NextTurn
  A function that yields the next turn in the game, given the current state and the result of the previous turn.
• Outcome
  A (potential) outcome of a game. A payoff combined with a record of the moves that produced it.
• Record
  A record of moves played during a game.
• State
  A trait that collects the trait requirements of a game state.
• Utility
  A trait that collects the trait requirements of payoff utility values.

Type Aliases

• Players
  A per-player collection of players, ready to play a game.
• Plies
  An iterator over the plies in a game.