Game of Theorems

This article is part of a series on The Structure of Theorems. See also:
1. Theorems’ Almanack; 2. The Greatest Theorem; 3. Game of Theorems

Few (currently) practicing mathematicians – in my experience – deign to concern themselves with issues surrounding set theory and the foundations of mathematics. In these areas reside the very definitions upon which the rest of our discipline rests; in any case, our discipline proceeds nonetheless, despite its practitioners’ regrettable ignorance. Mathematicians are pragmatic people. In 1949, Bourbaki – perhaps apprehending a subtle need to defend itself – titled a paper Foundations of Mathematics for the Working Mathematician [1].

This state of affairs, unfortunate as it is, explains the surprise and intrigue I often feel when I take time to explore foundational issues. The definition of the so-called Axiom of Determinacy particularly struck me. This set-theoretic axiom is formulated in terms of a certain type of two-player game – an infinite sequential game, in fact, in which two players take turns playing integers, leading ultimately to a sequence of integers of infinite length. The axiom (indeed, it’s something we might choose to suppose) states that every such game – that is, every choice of a victory set, a distinguished collection of possible infinite sequences whose members define the winning outcomes for the first player – is determined, in the sense that one player or the other in the game has a dominant strategy.

I’ll explain these terms below. The important thing, here, is that this mathematical property is defined by the existence of dominant strategies for a certain class of two-player games. This intrusion of an apparently economic, or game-theoretic, notion – that of the two-player game – into mathematics surprised me.

This intrusion, in retrospect, should have been less than surprising. Continue reading

Lesson Time

This article is part of a series entitled Everyday Game Theory. See also:
1. The Escalator’s Dilemma; 2. Electoral College; 3. Passing Curiosity; 4. Lesson Time

This is (a slightly modified version of) a text message exchange which recently occurred between my violin teacher and me.

  1. Teacher: “Can we meet today instead of tomorrow?”
  2. Me: “That’d be great!”
  3. Teacher: “Cool, see you this afternoon.”
  4. Me: “Ok.”

It would not have been acceptable for me to fail to respond to my teacher’s message (1). If I didn’t respond, my teacher would have no way to know whether I ever received her message – and, hence, whether to come today or tomorrow.

Neither would it have been ok, for that matter, for my teacher to let the conversation end at message (2). Until I receive her confirmation (3), I can in no way be sure whether she has seen or acknowledged my message (2). In other words, with her message (3) unsaid, it could remain the case, for all I know, that my teacher, as yet unaware of my response (2), imagines me unaware of (1) and still intent to come tomorrow.

Even after I received my teacher’s message (3), though, it was important for me to send the further message (4). After all, until she receives my message (4), my teacher may well imagine me unaware of her message (3). In that situation — her thought process might go — I would, unaware of her confirmation (3), be liable to suspect her unaware of my response (2), and hence unsure of my receipt of (1), and so liable to come tomorrow.

Why doesn’t this continue? Continue reading

Theorems’ Almanack

This article is part of a series on The Structure of Theorems. See also:
1. Theorems’ Almanack; 2. The Greatest Theorem; 3. Game of Theorems

Theorems are the hallmark of the mathematical trade. In them reside mathematical rigor, mathematics’ unspoken holy grail. They also possess a kind of mystique. “I’m scared of upper-division math classes,” I once overheard a student say. “It’s all proofs.”

Theorems, independent of their mathematical content, are interesting in their own right, because they delineate the mathematical landscape. Open a textbook of mathematics, and you’ll find the difficult universe of mathematics, once uncharted and unknown, arrayed and packaged before your eyes. “Theorem: ___________. Proof: _____________.

I attempt here to understand mathematical theorems, in a purely logical sense: for what they are, for what they do, and for what role they play. Continue reading

Russian Cryptosystems

You’re surfing the internet on a random Tuesday, when suddenly, you receive an unexpected email.

“What holiday package?” you mutter to yourself, as your finger hovers over the delete button. “On second thought, I should check this out,” you decide seconds later, recalling your tendency to browse Amazon after a few too many drinks.

“Tracking…tracking…wait, what?” Suddenly, all your active windows close: your email browser, solitaire, and even that word document you were kind-of working on. They’re replaced by a single window, displaying the notice below.

Continue reading

Ground Control to Major Reform

This article is part of a series on Health Policy. See also:

  1. Ground Control to Major Reform
  2. Hospital Salaries Could Cut Care Costs
  3. The Appropriate Practice Scope of Chiropractic May Be a Political Question, Not a Scientific One

The United Network for Organ Sharing (UNOS) runs the nationwide waiting list for donor kidneys. 100,000 Americans currently sit on this list; unfortunately, 50% will die before a kidney arrives, as wait times can exceed 10 years.  Further, since the number of recipients is growing faster than the number of donors, the wait time, and consequently the mortality rate, can only be expected to increase. (1)

But there’s hope! Recent updates to the UNOS donor kidney allocation policy might drastically reduce wait times.

Larry Swilling took to the streets for fear that his wife was losing the race with the waiting list. He found a donor just a month ago.

Continue reading

Rise of the Silicon Dynasty

blood vomit

The final position of the famous “Blood-Vomiting Game” of 1835 *

Chess computer programs have been beating our grandmasters since 1997. One game, though, still eludes artificial intelligence. This is the ancient Chinese game of Go. Despite its incredibly simple rules, master Go players still destroy our best computers.

Is man’s dominance temporary? Or will Go always be our territory?

The exploration of why humans still win at Go, and whether or not they always will, promotes discussion about game theory, computation and human psychology.

Continue reading

X’s and O’s

We all remember TicTacToe as the simplest game from our childhood.  But nothing is simple in computer science.  If you were assigned the task of designing a computer program that could beat a human at TicTacToe, how would you go about doing it?  Feel free to stop and think about it for a second.

My first choice was to build an algorithm that dealt step-by-step with each possible scenario: a sort of priority checklist.  If one priority is achieved, then the move is immediately made, and the rest of the priorities aren’t even considered.  Thus the order of the priority list is important; the most urgent ones must be at the top.  The list of priorities went something like this:

  1. If victory is immediately possible, make the winning move.
  2. If the enemy’s victory is immediately possible, block their winning move.
  3. If a fork is possible, make the fork.  A fork is a move that creates two possible ways to win.  Thus the enemy will follow step 2 but will only be able to block one possibility; you will then follow step 1 to win.
  4. If the enemy is in danger of making a fork, you must prevent this, with one of two options:
    1. Create a counterthreat.  The enemy will then have to obey step 2, preventing him from reaching step 3.  Note that this only works if the enemy’s response as per step 2 isn’t the same move he was about to make anyway as per step 3.  If the enemy’s answer to your counterthreat is the same as his original fork move, then you will be forked anyway.
    2. Block the enemy’s fork by moving in the location of his potential forking move.
  5. General strategies for good play, such as playing the center and playing the corner opposite to one your opponent occupies.

Continue reading