I have no idea what this illustration is supposed to be, so we're gonna call it a pigoner's dilemma. pic.twitter.com/LGKEhoOV36

— William Spaniel (@gametheory101) August 11, 2016

Dr. Vincent Knight tweeted back the image depicts an experiment where pigs played game theory.

William Spaniel found the image is a book cover (clearer image here: https://img1.doubanio.com/lpic/s6972287.jpg). The book’s title translates to “Game Theory In Our Daily Life” (博弈论的诡计全集) and the author is Wang Chun Yong. I found the book is listed on Amazon.ca and also several copies listed on Taobao.

So what do pigs have to do with game theory? I found an English reference in the book Games, Strategies, and Managers by John McMillan.

The game: pigs in a box

A pair of pigs, one dominant and one subordinate, are in a box and have a chance to be rewarded with food. At one end of the box is a lever which releases food when pressed. The twist is the food is released at the other end of the box. The pig that presses the lever is at a disadvantage as the other pig can get to the food first.

We can model the game using some numbers. If the dominant pig presses the lever, the subordinate pig can eat 80 percent of the food before the dominant pig can arrive and take the rest. If the subordinate pig presses the lever, then the dominant pig can take all the food as the subordinate pig races across the box. If neither pig presses the lever, then neither pig gets any food. And if both are adjacent when the lever is pressed, the dominant pig can eat 70 percent of the food.

Suppose the food is worth 10 units, it takes 1 unit of energy to press the lever and rush to the other side of the box to fight for the food. The game then has the following payouts.

How should the two pigs act if they reason like game theorists? Let’s solve this game and then see how pigs actually behave in an experiment.

Solving for the Nash equilibrium

Consider the choice of the subordinate pig. If the dominant pig presses the lever, then the subordinate pig is better off not pressing the lever and raiding the food to get 8. If the dominant pig does not press the lever, then the subordinate pig is better not pressing, because it is better to get 0 than to get -1 from getting no food and expending energy.

Notice the subordinate pig has a dominant strategy of not pressing the lever. These best responses are depicted by overlines in the appropriate cells of not pressing the lever.

What should the dominant pig do? For completeness, let us consider each choice of the subordinate pig. If the subordinate pig presses the lever, the dominant pig would rather not press the lever and get all 10 units of food. If the subordinate pig does not press the lever, then the dominant pig should press the lever to get a payoff of 1 versus a payoff of 0 for not pressing.

These best responses are depicted by underlines in the appropriate cells.

The unique Nash equilibrium of this game is the cell with both an overline and an underline, in which both pigs are playing a best response. This corresponds to the dominant pig pressing the lever, the subordinate pig not pressing the lever.

The subordinate pig gets 8 while the dominant pig gets only 1.

How pigs actually played

Baldwin and Messe did this experiment and published about it in 1979. While pigs do not actually write the matrix game and solve it, they can learn optimal behavior. The researchers found the dominant pigs did almost all of the pressing. In other words, the pigs acted just as game theory predicted they would! While pigs do not know game theory, there is a role of game theory to predicting animal behavior (read how dung flies optimally exit a war of attrition, for example).

The lesson: strength can be a weakness!

The game is also interesting from a business perspective. Typically we think dominance translates into strategic strength: the stronger animal should beat the weaker one. But in this game, strength is a weakness! The dominant pig ends up with almost no food compared to the subordinate pig.

Why is this happening? The strategic problem is the dominant pig is too dominant. If there is a fight for food, the subordinate pig knows that it will get nothing. So the subordinate pig never wants to waste time pressing the lever and fighting for the food.

As a consequence, the dominant pig settles for pressing the lever to get a little bit of food.

The subordinate pig’s “protest” to not press the lever steals the power and overwhelms the physical strength of the dominant pig.

Sources for this experiment at at the end of this post; I want to mention a couple items from the news first.

Game Theory News 1: Nash’s Nobel Up For Auction

John Nash’s Nobel Prize is set to be auctioned by October 17 and expected to sell between $2 to $4 million. It appears to be a standard open outcry bidding. Time to apply your game theory knowledge: it’s a weakly dominant strategy to bid up to your valuation!

NY Times
http://www.nytimes.com/2016/08/31/arts/john-nash-nobel-medal-to-be-auctioned-at-sothebys.html?_r=0

Sotheby’s
http://www.sothebys.com/en/news-video/blogs/all-blogs/Bibliofile/2016/08/john-f-nash-jr-nobel-prize-economic-studies.html

Game Theory News 2: Reinhard Selten Dies At 85

Selten shared the 1994 Nobel Prize with John Nash, who passed away last year. Selten proposed the idea of subgame perfect Nash equilibria–a refinement to the Nash equilibrium that excludes non-credible threats. Selten is also known for his work on “bounded rationality”–a more realistic assumption than the standard infinite reasoning capability–and he is considered a founding father in experimental economics.

Bloomberg
http://www.bloomberg.com/news/articles/2016-09-01/reinhard-selten-game-theorist-who-won-nobel-prize-dies-at-85

New York Times
http://www.nytimes.com/2016/09/04/business/economy/reinhard-selten-whose-strides-in-game-theory-led-to-a-nobel-dies-at-85.html?_r=0

A Fine Theorem (more details of work)
https://afinetheorem.wordpress.com/2016/09/01/reinhard-selten-and-the-making-of-modern-game-theory/?utm_source=twitterfeed&utm_medium=twitter

Sources For Pigs Experiment Game Theory

Baldwin, B. A., and G. B. Meese. “Social Behaviour in Pigs Studied by Means of Operant Conditioning.” Animal Behaviour 27 (1979): 947-957. https://www.researchgate.net/publication/256111949_Social_behaviour_in_pigs_studied_by_means_of_operant_conditioning

Games, Strategies, and Managers. John McMillan

Rational Pigs
http://www2.owen.vanderbilt.edu/lukefroeb/2003/mgt722/topics/game/game.html#3

GameTheory101 Tweet
https://twitter.com/gametheory101/status/763842095933190144

Thanks to Patrons!

Kyle
Brian M. Mooney

You can support me and this site at Patreon.

These are all examples of a game theory topic known as fair division, and I have posted about them before:

• Splitting The Bill At Restaurants Using Game Theory
• How Game Theory Solved A Religious Mystery
• How A $3 Billion Empire Was Divided Up Using Game Theory
• Fair Division Jif Peanut Butter Commercial

What is the fairest procedure to allocate a divisible item? The mathematical problem is described by analogy to a group of people cutting a cake to share. Everyone in a group wants the best slice of the cake for himself, but each person might want a slightly different part of the cake (frosting, toppings, fillings, etc.).

A new paper possibly has solved the problem of cake-cutting for any number of people. Furthermore, the procedure is bounded, which means it can be accomplished in a finite number of cuts, albeit the bound is very large. Before I get into that, let me take a step back and describe a bit about cake cutting.

Article and video summary of the paper

Marcus Strom summarizes the topic very nicely at the Sydney Morning Herald: Fair allocation: Algorithm that cuts cakes and may settle Trump divorces

There is also a very nicely done video by Jack Fisher:

The tricks to cutting cake fairly

If you can’t watch the video, I offer some commentary below.

Summary of previous cake-cutting research

What is a fair division? There are many notions of fairness. One sensible condition is that no one would prefer someone else’s slice of cake over his own. This is known as an envy-free solution.

When there are just 2 people, the problem is readily solved and has been known for thousands of years. The method is “I cut, you choose.” One person cuts the cake into two pieces, and the other person chooses which piece he wants. The person who chooses obviously prefers his slice, and the person who cuts the cake will divide it so he equally favors either piece. This solution is envy-free. And the procedure is efficient–it only requires 1 cut of the cake.

What happens when there are 3 people? An envy-free division can be found through the Selfridge-Conway procedure, but it is much more complicated procedure and might involve up to 5 cuts of the cake.

This is also a method for 4 people known as the Brams-Taylor-Zwicker procedure. This is even more complicated and might involve up to 11 cuts of the cake.

What if there are more people? Under some assumptions, it can be proven that envy-free divisions always exist. The theorem is theoretical, however, as it guarantees the existence but it does not specify a method to find a solution.

The first method to find an envy-free division in a finite number of cuts is the Brams-Taylor procedure. There is also the Robertson-Webb protocol which leads to an envy-free division, and it also has the property the division is near-exact: everyone agrees the slices are roughly the same proportion of the entire cake.

But there is a problem with these methods: while they are finite, there is no bound on the number of cuts. This poses a practical problem that the cake-cutting might require too much time to achieve. This also poses a computational problem: the division might take too long to compute, making it impractical as an arbitration tool.

A bounded method

A possible solution comes from a new paper by mathematicians at The University of New South Wales, Haris Aziz and Simon Mackenzie. The paper claims to have a procedure that results in an envy-free solution for any number of people in a bounded number of cuts. While the paper has not yet been peer-reviewed, game theorist Steven Brams (of the Brams-Taylor procedure) said the solution could be a “major breakthrough.”

The solution involves a total of 5 algorithms. There is a main protocol which calls upon other algorithms, which might call on themselves or other algorithms. The key is that each protocol is bounded so the algorithm will ultimately stop after a specific number of times.

Unlike the “I cut, you choose” method, this protocol is not easy to describe in a few sentences. But such an algorithm can still be useful: it could be programmed, and once participants describe their preferences, the computer could calculate an envy-free division.

While the procedure is bounded, it is a very large bound and could take a lot of cuts. For n people, the bound is described in terms of a power tower of n, that is n raised to the power of n multiple times.

The procedure is bounded by n raised to itself 5 times number of cuts. So for 4 people, the theoretical number of cuts is smaller than 4^(4^(4^(4^(4^4)))), which WolframAlpha computes as 10^(10^(10^(10^153.9069975479678))).

This is an insanely large number, and this is only for the case of 4 people!

That is not to say the number of cuts is that large–the bound is not optimized and is an upper estimate. For 4 people, for example, the procedure might terminate much quicker, like the Selfridge-Conway procedure, which involves at most 5 cuts.

The bad news is the proven bound on the number of cuts is astronomically large. The good news is the bound is finite, and the method might inspire further research to reduce the bound, leading to a practical method for computing envy-free divisions.

Sources and further reading

I cut, you choose
https://en.wikipedia.org/wiki/Divide_and_choose

3 person envy-free Selfridge-Conway
https://en.wikipedia.org/wiki/Selfridge%E2%80%93Conway_discrete_procedure

4 person envy-free Brams-Taylor-Zwicker
https://en.wikipedia.org/wiki/Brams%E2%80%93Taylor%E2%80%93Zwicker_procedure

4 or more envy-free Brams-Taylor
https://en.wikipedia.org/wiki/Brams%E2%80%93Taylor_procedure

4 or more envy-free and near exact Robertson-Webb
https://en.wikipedia.org/wiki/Robertson%E2%80%93Webb_protocol

Sydney Morning News
http://www.smh.com.au/technology/sci-tech/fair-allocation-algorithm-that-cuts-cakes-and-may-settle-trump-divorces-20160502-gokmwt

The tricks to cutting cake fairly
https://vimeo.com/167087265

Haris Aziz blog post
http://haris-aziz.blogspot.com/2016/04/a-general-bounded-envy-free-protocol.html

A Discrete and Bounded Envy-free Cake Cutting Protocol For Any Number of Agents, by Haris Aziz and Simon Mackenzie
http://arxiv.org/pdf/1604.03655.pdf

Milind Tambe is a professor at the University of Southern California. In the following talk, he explains the many applications of game theory for security in security ports and airports, reducing the flow of illegal weapons and drugs, and protecting the environment and wildlife.

I really enjoyed this talk and would suggest it when you have the time.

Security Games Talk By Milind Tambe

If you cannot watch at the moment, or short on time, you can skim through the slides available from the Simons Institute: [Slides from Milind Tambe Talk] Security Games: Key Algorithmic Principles, Deployed Applications and Research Challenges.

I have included a few comments about the talk after the jump.

The goal is not perfect security

Each application is an example of a security game: defenders have to allocate limited resources in advance against attackers that can take their time to find vulnerabilities and then make their move. Because attackers move second, this is a sequential game (Stackelberg), and because defenders and attackers hold private information, this is a game of incomplete information (Bayesian).

Professor Tambe points out the goal is not to have 100 percent security. You can almost always send a red team to identify vulnerabilities.

The point of game theory security is to increase the cost for attackers. This makes it harder for attackers to wage a successful plan, and they might decide to abandon the plan or choose another target.

You can think about this by analogy to home security. It is not possible to completely prevent robbers from ever breaking into your home. A homeowner instead settles for increasing the cost to a robbery by having a home security system, keeping doors locked, and hiding valuables or securing them in a bank safety deposit box. A robber might still be able to break into the home, but it takes more time to plan the attack, there is a higher chance of getting caught, and the reward may be small. If a neighborhood starts seeing robberies, then the town might send more cops to patrol. The goal is not 100 percent security; the goal is to make it harder to wage an attack.

Proven applications

What’s remarkable is that game theory has proven success in so many areas. For example, the U.S. Coast Guard used the game theory algorithms to randomize patrols against reduce illegal fishing; and Ugandan rangers used a similar framework to randomize patrols against animal poachers.

Why is randomization so effective? The reason is we tend to fall in predictable patterns, making it easier to game our security methods. Research backs up the intuition.

A controlled field test was conducted at the Los Angeles Metra Rail that staged adversaries against patrolling agents. One set of patrols followed the pure randomization schedule of game theory. Another set got the randomization schedule, but it allowed its human sheriffs to choose another path if desired. Over 21 days of patrol in identical conditions, the game theory schedule showed about a 50% increase in captures, warnings, and issuing violations. When defense is randomized, attackers find it harder to avoid being detected.

You might think it’s dangerous if we let attackers know that security is random. But in fact, that’s the beauty of a randomized strategy: it works even if you announce that you are doing it. In rock-paper-scissors, if you play against a computer that randomizes its choices, you will never average winning more than 1/3 of the time. This is the kind of strategy that can help defenders in Bayesian Stackelberg games where attackers have the advantage of moving second. If the defenders can randomize, it does not matter if the attackers learn that.

Incidentally, each application of the game theory scheduling has had a clever acronym. The U.S. Coast Guard used a system called PROTECT (Port Resilience Operational / Tactical Enforcement to Combat Terrorism), the Los Angeles Airport had a system called ARMOR (Assistant for Randomized Monitoring Over Routes), and the Uganda rangers were protecting wildlife with PAWS (Protection Assistant For Wildlife Security).

There is also scope to use game theory for cyber security as well as to reduce street crime. It’s fascinating to see how game theory can help improve security.

Here again is a link to the talk and the slides.

Security Games Talk By Milind Tambe

If you cannot watch at the moment, or short on time, you can skim through the slides available from the Simons Institute: [Slides from Milind Tambe Talk] Security Games: Key Algorithmic Principles, Deployed Applications and Research Challenges.