EXT. CLUB - NIGHT

Game theory

Upchurch takes in the scene. UPCHURCH (cont'd) ... but the big money snatches tend to put you in contact with a higher class of lowlife. If they know their business -- and it looks to me like they do -- we'll be looking at simultaneous movement, expected payoffs, bargaining strategies... lots of variables. CHARLIE (O.S.) What you're talking about is imperfect information games. They turn to see CHARLIE, walking up --

Game theory is a branch of mathematics that
deals with the analysis of games (*i.e.*, situations involving parties with conflicting interests). The principles
of game theory find applications to complicated games, such as checkers and chess, as well as
real-world problems as diverse as economics, property division (we, and Charlie, will have more to say on the particular
property of "cake" very shortly), politics, and warfare.

Game theory has two distinct branches: combinatorial and classical.

Combinatorial game theory covers two-player games of perfect knowledge such as checkers and chess (as mentioned above), in addition to games such as Connect-Four, go, nim, and tic-tac-toe. Notably, combinatorial games have no chance element, players can see the entire set of plays and moves possible for each opponent, and players take turns.

In classical game theory, players move, bet, or strategize simultaneously. Both hidden information and chance elements
are frequent features in this game theory branch, which is also a branch of economics. In such an imperfect
information game, players must act without complete knowledge of what other players can do. A few examples are
rock-scissors-paper, *Battleship*, *Kriegspiel*, poker, bridge,
*Monopoly*, *Scrabble*, the stock market, real estate, currency trading, and auctions. For these games,
economic game theory and computational game theory are used to maximize advantage or profit.

Tabu search

CHARLIE You got it. Assuming that the kidnappers are experienced -- or have benefited from the experience of other kidnappers -- we might use an optimization method called a Tabu Search. (off Upchurch's look) It's a way to exclude bad data -- the places the kidnappers won't go -- to isolate where they will. UPCHURCH I guess that's why they call it "tabu." CHARLIE (cont'd) Charlie nods, then -- The kidnappers are really... like a group of hikers -- AUDIENCE VISION - A group of hikers check a map, a DESTINATION circled -- then start marching through the woods -- The hikers trek along a trail -- past beautiful glades, avoiding dangerous cliffs, heading toward the waterfall -- CHARLIE (V.O.) (cont'd) A Tabu Search will pinpoint the optimal route the hiker's will choose...

The essential idea of a tabu search (which is a category of so-called meta-heuristics) is to "forbid" search
moves to points already visited in the search space, at least for the upcoming few steps. In a tabu search, one
therefore allows new inferior solutions to be temporarily accepted in order to avoid paths already investigated. This
approach can lead to exploring new regions of the space of all possible solutions, with the goal of finding a solution
by globalized search. Tabu search has traditionally been applied to combinatorial optimization (*e.g.*,
scheduling, routing, traveling
salesman) problems. The technique can be made, at least in principle, directly applicable to continuous global optimization problems by a
discrete approximation of the problem, but other extensions are also possible.

In light of the above, the scenario described in Charlie's analogy is not really a tabu search. A better example of a tabu search might be a technique sometimes used by computers to solve mazes constructed on a square grid with straight walls. (For some commentary on mazes, see the Math Notes from Episode 406, "In Security.") In this approach, the height of a square is increased by one each time it is visited, and subsequent explorations are made by following the path with the lowest height at each step. This approach can be visualized as building up a set of ramps, then always traveling in the downhill direction until either the exit of the maze or a local minimum is reached.

Furthermore, since there are so many variables to take into account, the tabu search Charlie wants to use must also operate in a very high-dimensional space (where each variable can be considered a single dimension). There are many different things that Charlie could predict: how, when, how much money the kidnappers want, what other things they might want, how they will behave in case they don't get what they want, and so on. In general, searches in very high-dimensional spaces are notoriously difficult (this phenomenon is known as the "curse of dimensionality"). Charlie might therefore be wise to use a few other mathematical techniques in addition to, or in preparation for, doing a tabu search.

In particular, Charlie could reduce the problem to a simpler lower-dimensional one by carrying out a Karhunen-Loeve decomposition (principle component analysis), or by using functional analysis techniques to embed the problem in an infinite-dimensional problem. Interestingly, many problems become easier to solve in infinitely many dimensions than in many dimensions. The whole theory of Hilbert spaces and Banach spaces deals with this infinite-dimensional case. We'll comment more on infinite-dimensional spaces in a forthcoming episode.

Bayesian priors

CHARLIE The ransom negotiation cut short, so I'm going to need to re-think my Tabu Search. (checks his papers) Maybe if I weight the data with a Bayesian prior --

Bayesian priors are an advanced topic in probability theory. To understand Bayesian priors, first consider the question, "Will the
weather be cloudy tomorrow?" A prediction can be made based on past history by estimating *P*(cloudy),
the probability that the skies will be cloudy, by the fraction of cloudy days that followed all similar previous days,
*N*(cloudy)/*N*(total similar). While a so-called frequentist approach might stop there, a Bayesian approach
would try to make a theory about the weather. Let *P*(theory|data) be the conditional probability of the
theory given the data. From there, Bayes'
theorem can be used:

Here, *P*(theory) is the prior confidence that the theory was true. Both the theory and the confidence can be
adapted. For a spam filter, the theory is used to assign confidences to a message, usually based on the
vocabulary, programming, and source of the message. As an example, large flashing red text is a strong
spam indication. Training a Bayesian spam filter has two aspects. First, flagging a message as spam will
strengthen the Bayesian prior, *P*(theory). Second, flagging a false positive will modify and strengthen
the theory.

Heron's fountain

Charlie, carrying files and papers under his arm, enters to find Amita helping LARRY tweak the height of the main chamber on Larry's HERO'S FOUNTAIN (an apparatus made of two vertically stacked jars, half filled with water, and connected by an air hose and a funnel). All centered in a Zen Rock Garden. CHARLIE Please tell me you didn't buy that in a head shop. Larry looks askance -- LARRY Actually, Charles, you can't find this in any shop. I've constructed my own Hero's Fountain. OFF Charlie's look -- AMITA ...Named for Hero of Alexandria. The Greek mathematician and engineer. Once we get the pressure right, the water will start to flow under its own power. CHARLIE And how's this part of your achieving Zen?

Hero (or Heron) of Alexandria was a mathematician and engineer who lived AD 10-70. Among other items, he invented the first steam engine, the first vending machine, and the first windmill. Hero's fountain is now a classic demonstration of both hydraulics and pneumatics.

Heron's formula

In mathematics, Heron is perhaps best known for Heron's formula, which gives the area of a triangle in terms of the lengths of its three
sides. This formula is also known as Hero's formula. Given the lengths of the sides *a*, *b*, and *c* and
the semiperimeter (*i.e.*, half the
perimeter),

of a triangle, Heron's formula gives the area *Δ* as

Heron's formula may be stated beautifully using the general formalism of the Cayley-Menger determinant:

Here, the object delimited by vertical bars is an important mathematical construct in linear algebra known as a determinant. The value of a 2×2 determinant is defined to be

A *k*×*k* determinant can be expanded "by minors" to obtain

A so-called minor of *A* is obtained by taking the determinant of *A* with row *i* and column *j* crossed out.

For example, for a 3×3 matrix, the above formula gives

The procedure can then be iteratively applied to calculate the minors in terms of subminors, etc.

Expressing the side lengths *a*, *b*, and *c* in terms of the radii *a'*, *b'*, and *c'*
of the mutually tangent circles centered on the vertices (which define the Soddy circles)

gives the particularly pretty form

Heron's proof is ingenious but extremely convoluted, bringing together a sequence of apparently unrelated geometric
identities and relying on the properties of cyclic quadrilaterals and right triangles. Heron's proof can be found in Proposition 1.8 of his work *Metrica* (ca. 100
BC-AD 100). This manuscript was lost for centuries until a fragment was discovered in 1894 and a complete copy in 1896.
More recently, writings of the Arab scholar Abu'l Raihan Muhammed al-Biruni have credited the formula to Heron's
predecessor Archimedes (whose accomplishments we discussed in the Math Notes for Episode
403, "Hollywood Homicide"), prior to 212 BC.

A much more accessible algebraic proof proceeds from the law of cosines:

Then

giving

Heron's formula contains the well-known Pythagorean theorem as a degenerate case.

INT. FBI - WAR ROOM - DAY

Minimax theorem

CHARLIE I think what he's trying to say is Pierce has violated his own rules of corporate Game Theory. It's standard Minimax -- like a tug of war -- BEGIN AUDIENCE VISION -- TWO TEAMS OF EIGHT align at opposite ends of a rope -- CHARLIE (V.O.) (cont'd) -- a demonstration of brute strength by two opposing groups. The object being to pull one's opponent across the center line first. In a spirited display, both teams pull on the rope -- taut. CHARLIE (V.O.) (cont'd) However, after the competition begins -- Both teams are evenly matched, the rope barely budging in either direction. -- one team can embarrass the other by letting go of the rope-- One team releases the rope -- the other team jerks their end and falls flat on their asses. The other team laughs. CHARLIE (V.O.) (cont'd) That team humiliates their opposition... but they've lost. The team pick themselves up and celebrates their win -- END AUDIENCE VISION. CHARLIE (cont'd) Pierce has let go of the rope... struck back in the way least likely to achieve a positive result.

The minimax theorem (where minimax refers to minimization of the maximum result obtained by another player) is the fundamental theorem of game theory. It states that every finite, zero-sum, two-person game has optimal mixed strategies. (Here, a mixed strategy is a collection of moves together with a corresponding set of weights that are followed probabilistically in the playing of a game.) The minimax theorem was first proved by the famous mathematician and father of modern computing, John von Neumann, in 1928.

To state the theorem formally, let **X** and **Y** be mixed strategies for players *A* and *B* and let
*A* be the payoff matrix. Then

where *v* is called the value of the game and
*X* and *Y* are called the solutions. It also turns out that if there is more than one optimal mixed strategy,
there are infinitely many.

In the closing scene of the Season 4 opening episode "Trust Metric," Charlie mentioned that he used the minimax theorem in an attempt to derive an equation describing friendship.

Minimax approximations

In general, a minimax approximation
is a minimization of the maximum error for a fixed number of terms. In approximation theory, the most common minimax
approximation is the minimax polynomial,
which gives the approximating polynomial that has the smallest maximum deviation from the true function. Such
polynomials are closely approximated by the Chebyshev polynomials of the
first kind *T _{n}*(

INT. CALSCI - CHARLIE'S OFFICE - DAY

Cake-cutting theory

UPCHURCH (re: decoder) Not quite what I imagined reading your more ethereal musings on Cake- Cutting Theory, Professor. CHARLIE Sometimes cake is a series of algorithms to formulate an analysis. And sometimes cake is just... cake.

The study of fair division problems is known as cake-cutting theory. It can be mathematically shown that it is always possible to "fairly"
divide a cake among *n* people using only vertical cuts. Furthermore, it is possible to cut and divide a cake such
that each person believes that everyone has received 1/*n* of the cake according to his (or her) own measure.
Finally, if there is some piece on which two people disagree, then there is a way of partitioning and dividing a cake
such that each participant believes that he has obtained more than 1/*n* of the cake according to his own measure.

The general cake-cutting method for two people (say, Alice and Bob) is that Alice cuts the cake, and Bob chooses which piece he wants ("divide and choose").

For three people (Alice, Bob, and Carl), Alice cuts one piece, Bob cuts the remainder, and Carl then chooses one of the three pieces. Alice then makes adjustments on the remainder, and Bob chooses. Alice gets the last plate.

Ignoring the height of the cake, the cake-cutting problem is really a question of fairly dividing a circle into *n*
equal-area pieces using cuts in its plane. One method that proves fair cake cutting is always possible relies on the
Frobenius-König theorem,
which is a beautiful result in combinatorial matrix theory that is probably one of Amita's favorites!

Determining the maximum number of pieces in which it is possible to divide a circle for a given number of cuts is called
the circle cutting or pancake
cutting problem. (For another mathematical pancake problem, and one with a very surprising contributor to the research
literature on the subject, see the pancake
sorting problem.) The minimum number of pieces is always *n* + 1, where *n* is the number of cuts, and it
is always possible to obtain any number of pieces between the minimum and maximum. The first cut creates 2 regions, and
the *n*th cut creates *n* new regions, so it can easily be shown that the maximum number of pieces is given by
(*n*^{2} + *n* + 2)/2.

The problem of dividing a circle by lines can also be generalized to dividing a plane by circles.
As can be seen above, the maximal numbers of regions obtained from *n* = 1, 2, 3, 4, ... circles are given by 2, 4, 8, 14, ....
The astute reader may note that the *n* = 3 case looks strangely familiar. In fact, this configuration
corresponds to the most commonly encountered case of a Venn diagram, a subject on which we will have more to say in the Math
Notes for Episode 412, "Power." The alert reader may also be interested in attempting to derive the simple
formula giving the maximal number of regions obtained for *n* circles (if so, you may wish to refrain from clicking
the links above until you have obtained your solution).

Of course, dividing the plane by circles can also be generalized to dividing a plane by ellipses, where
ellipses have been previously discussed in the math notes for Episode 401, "Trust
Metric." The maximal numbers of regions obtained from *n* = 1, 2, 3, 4, ... ellipses are given
by 2, 6, 14, 26, .... There is again a very simple formula giving the maximal number of regions.

While Charlie can probably solve intersection-maximizing problems in his head, they can require great ingenuity for
people with lesser gifts. In particular, consider the more challenging problem of cutting a cylinder into a maximum number of
pieces by *n* oblique cuts.

References

Barlow, R. *Developments in Bayesian Priors.* 2005.

Brams, S. J.; Jones, M. A.; and Klamler, C. "Better Ways to Cut a Cake." *Not. Amer. Math. Soc.* **53**, 1314-1321, 2006.

Brams, S. J. and Taylor, A. D. "An Envy-Free Cake Division Protocol." *Amer. Math. Monthly* **102**, 9-19, 1995.

Brams, S. J. and Taylor, A. D. *Fair Division: From Cake-Cutting to Dispute Resolution.* New York: Cambridge University Press, 1996.

Glover, F. and Laguna, M. *Tabu Search.* Dordrecht, Netherlands: Kluwer, 1996.

Glover, F.; Taillard, E.; and De Werra, D. "A User's Guide to Tabu Search." *Ann. Oper. Res.* **41**, 3-28, 1993.

Osman, I. H. and Kelly, J. P. (Eds.). *Meta-Heuristics: Theory and Applications.* Dordrecht, Netherlands: Kluwer, 1996.

Piwakowski, K. "Applying Tabu Search to Determine New Ramsey Numbers." *Electronic J. Combinatorics* **3**, No. 1, R6, 1-4, 1996.
http://www.combinatorics.org/Volume_3/Abstracts/v3i1r6.html

Robertson, J. and Webb, W. *Cake Cutting Algorithms: Be Fair If You Can.* Wellesley, MA: A K Peters, 1998.

Stromquist, W. "How to Cut a Cake Fairly." *Amer. Math. Monthly* **87**, 640-644, 1980.

Venn, J. "On the Diagrammatic and Mechanical Representation of Propositions and Reasonings." *Dublin Philos. Mag. J. Sci.* **9**, 1-18, 1880.

Voss, S.; Martello, S.; Osman, I. H.; and Roucairol, C. (Eds.). *Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization.* Dordrecht, Netherlands: Kluwer, 1999.