Game Theory for Software Engineers

Kyle Stewart
4 min readMay 6, 2017

--

In the long run we are all dead.

- John Maynard Keynes

A Simplified Timeline of Economics and Market Design

  • In 1776, Adam Smith published the Wealth of Nations, founding classical economic theory, advocating that markets function best with minimal interference.
  • In the 1930’s, John Maynard Keynes published General Theory; arguing that employment is a function of demand and governments could intervene in markets during periods of under-employment. And, in response to the Great Depression, the U.S. government put those ideas to work with large scale public works projects.
  • In 1951, John Nash published a mathematic proof of a solution concept, Nash Equilibrium, where non-cooperative market participants could follow rational self-interest that does not result in an optimal allocation of resources.
  • 1961, Vickery proved that a second-price auction was incentive-compatible and Pareto optimal; meaning that participants were incentivized to participate truthfully and results in the most efficient allocation of resources.
  • 1994, the U.S. government auctioned radio spectrum licenses for first time using a custom built simultaneous ascending auction that was designed by a team of academic game theorists.
  • 1998, Sergey Brin and Larry Page published The PageRank Citation Ranking Bringing Order to the Web. Although Brin and Page did not implement game theoretical models into their algorithm, the goal of PageRank’s design accounted for participant incentives and made it “virtually immune to manipulation by commercial interests”.

Conventional wisdom regarding markets has evolved to where intervention and market design are not only acceptable, but differentiate products and determines which businesses succeed or fail.

What is Game Theory?

Game theory is “the study of mathematical models of conflict and cooperation between intelligent rational decision-makers” (Roger Myerson, Game Theory: Analysis of Conflict, Harvard University Press, 1991). Which can be translated into people speak as estimating market outcomes by modeling the decisions market participants make and the incentives that drive those decisions.

Much of game theory involves mathematical models that are inaccessible for non-PhD and difficult to apply in the real world. However, the core concepts of examining market participant incentives and designing a market around those incentives to achieve a desired outcome is intuitive. Some of the results, however, are less intuitive which is why some study of game theory is helpful.

The Flatiron Dilemma

A recent event at Flatiron [not a true story] provides a good example of how game theory can be applied in the real world. An audit of student labs identified two students, Alice and Bob, who passed labs by deleting specs. A further investigation into Alice and Bob’s activities revealed evidence that the two had conspired to steal source code to sell to a competing coding bootcamp. To encourage the students to confess, Flatiron separated Alice and Bob and offered each the following deal:

  • If one student confessed and the other denied, both would be dismissed with the confessing student receiving a $12,000 refund and the denying student receiving no refund.
  • If both confessed, both would be dismissed and receive a $4,000 refund.
  • If neither confessed, both would be dismissed for the deleted spec violation and receive an $8,000 refund.

Alice and Bob’s payoff matrix is as follows:

Classic economic theory suggests Bob and Alice’s rational self-interest and the invisible hand will lead them to deny because it creates the best result for the market, a total refund of $16,000. Assuming Alice and Bob can not collude, examining Alice and Bob’s decision trees will reveals this will not be the result.

  • If Alice believes Bob will confess (left side), then she will also confess because $4,000 > 0.
  • If Alice believes Bob will deny (right side), then she will still confess because $12,000 > $8,000.

Regardless of whether Bob confesses or denies, the dominant strategy for Alice will be to confess. Examining Bob’s decisions tree yields the same result.

  • If Bob believes Alice will confess (left side), then he will also confess because $4,000 > 0.
  • If Bob believes Alice will deny (right side), then he will still confess because $12,000 > $8,000.

This is an example is commonly known as the prisoner’s dilemma. Any market or system that benefits from co-operation needs to deal with this issue to be successful.

How to Beat the Prisoner’s Dilemma

In our example, confess is the dominate strategy, despite deny being the best strategy for the students collectively. To change the dominate strategy to deny without changing the payoffs in the game requires adding an additional incentive. In nature, evolution rewards the desire for social connection over self-interest with more resources and the self-interested eventually die off. Discussion boards have added reputation and status to incentive communal behaviors, without having to wait millions of years.

Trolling and fake news is a problem on social networks, so why don’t social networks add more robust reputation systems. Because the dominate strategy for a social network is to grow their user base and sell more advertising. A incentive system that reduces a user base will be less appealing. In the Flatiron example, Flatiron’s dominate strategy was for the students to confess, so they separated the Alice and Bob to discourage co-operation.

Learn More About Game Theory

  • Game Theory Online is an online introductory course on game theory taught by two Stanford University and one University of British Columbia professors.

--

--

Kyle Stewart

Managing Partner | Altmirai LLC | Cryptoasset Custody Solutions | www.altmirai.com