Game Theory and Databases

CASE 1

Two members of a criminal gang are arrested and imprisoned. Each prisoner is in solitary confinement with no means of speaking to or exchanging messages with the other. The police admit they don’t have enough evidence to convict the pair on the principal charge. They plan to sentence both to a year in prison on a lesser charge. Simultaneously, the police offer each prisoner a Faustian bargain. Each prisoner is given the opportunity either to betray the other, by testifying that the other committed the crime, or to cooperate with the other by remaining silent. Here’s how it goes:

  • If A and B both betray the other, each of them serves 2 years in prison
  • If A betrays B but B remains silent, A will be set free and B will serve 3 years in prison (and vice versa)
  • If A and B both remain silent, both of them will only serve 1 year in prison (on the lesser charge)

One of the most common examples of game theory is The Prisoner’s Dilemma.

With the recent announcement of 2014 Nobel laureates we have one more Economist who has contributed to Game theory. Game theory is the mathematical model used to identify behaviour patterns for elements participating in a scenario. It is commonly used to provide an answer to how a system will behave given a set of boundary conditions and rules that need to be followed by each participant usually to control a resource or achieve a desirable end result.

The use of Game theory in databases especially within BI is documented in Decision Tree Mining Model. I once read a book that implemented Game theory in such a way that at the end of each chapter the reader is given a choice, based on his choice he is redirected to different pages resulting in a different ending. Interestingly, regardless of the choice you make the author was able to narrow down the choices to result in one of 3 different ending. Therefore while simulating the idea of choice the game essentially didn’t provide any (the author could just as easily provide a unified ending to the story regardless of interim choices).

Game theory is used everywhere from bargaining to nuclear end game as well as market power analysis. In Retail a simple example could be as follows

CASE 2

In an online retail chain we have 2 scenarios

Scenario/ OutComePurchase nothingPurchase for additional 100$
A shopper has zero store credits and is offered a 30$ discount on a purchase of an additional 100$ worth of products.Highly LikelyVery unlikely
A shopper has 30$ store credits and is being asked to shop for an additional 100$ worth of products against which 30$ can be redeemed.More LikelyHighly Likely

Here the only difference is the perception of the shopper in the first case they see it as losing a 100 bucks while in the second case they see it as using 30 Bucks.

The same thing applies to a number of different scenarios in business as well.

CASE 3

A company has a Project Manager position that needs to be filled. There are 10 candidates, they improve productivity fighting for the same position but only one of them win resulting in a 10X performance gain for the company and 0 percent promotion scope for the remaining 9.

Or the 10 of them decide not to improve performance resulting in a 0 percent performance gain for the company and the same 0 percent promotion scope of 9 out of 10, presuming the company will still fill the position with 1 out of the 10 candidates.

Human nature shows the first scenario is more common. Common sense tells us the second scenario is more beneficial.

BI has been used to validate actual data against predicted results for such end game theories. Dynamically assigning weights to outcomes to make them more or less desirable can be used to strongly skew to the result in a particular direction which is what we call bargaining.

It’s a fascinating topic and just as complicated.