How functional programming fits with game theory

Algebraic types, pattern matching, partial application and list operations make functional languages suitable for writing programs which anyone can understand.

10 years ago, I started to learn programming because I was interested in game theory, and couldn’t find a way to create the payoff-table of the Prisoners’ Dilemma (PD) in Excel, let alone create the formula to find the Nash equilibrium in the payoff table.

From Python to Elm

After some searching for a suitable programming language for beginners, I ended up with Python. I found the concept of Computer Programming for Everybody, formulated by Python founder Guido van Rossum, intriguing, and decided Python is the way to go. After some months of learning, I was able to write the program for finding the Nash equilibrium of PD, in 60 lines of code, using two Python classes.

I was really proud of myself.

In the last couple of years I was learning functional programming languages.

I began with the DAML smart contract language. When I realized DAML is based on Haskell, I learnt Haskell to be able to write better DAML code, and soon realized that functional programming in itself is worth pursuing, due to its elegance and its type system which filters out most bugs and makes refactoring a breeze.

Recently, I learnt the Elm UI language, which rightly advertises itself as “A delightful language for reliable web apps”.

Business friendly programming

From a business perspective, a major advantage of functional languages is algebraic datatypes (or custom types as they call it in Elm). It’s much more powerful than just Enums.

For instance, a piece of card can be modelled through the following types (using Elm syntax, which is similar to but simpler than DAML or Haskell, the “pipe” or “|” character separates alternatives, the space stands for function application):

type Card = StandardCard Value Suit | Joker
type Suit = Hearts | Spades | Diamonds | Clubs
type Value = Two | Three | … | Jack | Queen | King | Ace

Example:

queenOfHearts = StandardCard Queen Hearts

You can pattern match on the specific values, in DAML and Haskell you can even use the native ordering of the Value type for free. You can easily implement recursive types like binary trees:

type Tree Int = Empty | Node Int (Tree Int) (Tree Int)

where Empty stands for the lack of a left or right subtree, Node has an Int (in our example, but could be any other type) value, and has a (potentially empty) left and right subtree.

Back to the Nash equilibrium

The other day, it occurred to me the 10 year old question: how can I represent the PD payoff table and find in it the Nash equilibrium. Can I do it better now with functional programming, than a decade ago with Python? Out of the three functional languages I know by now, I used Elm, because of its simplicity and elegance.

After some thinking, I came up with a solution which is much shorter and easier to understand than my Python code was back then.

Functional languages don’t have classes, because they don’t need them.

They do have algebraic types, pattern matching, partial application and (one- or higher dimensional) mapping, which help a lot in writing concise and easy-to-understand code.

The heart of my solution is the payOff function, which is a simple representation of the PD payoff table.

This is a textbook representation of the payoff table of PD:

Source: Games of Strategy, 2nd edition (Avinash Dixit, Susan Skeath)

For the function representation, if we apply a simple trick, we don’t even need the players. If we use as first argument the own move of some player, and as second argument the other player’s move, the function is the same for both players, due to the symmetry of the table. This trick, due to partial application, which is a consequence of currying if functional languages, makes it very easy to iterate over the other player’s moves, and compare the list of outcomes for the move in question vs the alternative move.

A move is optimal for a player, when it’s better than the alternative, no matter what the other player’s move is. A Nash equilibrium exists, if both players have one or more optimal moves.

In this particular case:

• If the other player cooperates, I’m better off defecting, because in the latter case I get 1 year instead of 3 years.
• If the other player defects, I’m also better off defecting, because in the latter case I get 10 years instead of 25 years.

The Elm code for representing the payoff table and checking wether a move is optimal (again, this is symmetric for the players) is the following:

And the sad result, which we all know from the disasters it causes in our world: