Mathemagical Gaming

Overthinking

2009-06-18T18:31:00.000-07:00

There are a few things about Game Theory that always tend to fall down when the models are tested with actual people being rational actors. In most cases, the players will act in "sub-optimal" ways. In Prisoner's Dilemma trials, people tend to keep quiet as opposed to ratting. In Centipede Game trials, players continue playing for several turns.

While there are certainly many reasons for this sort of behaviour, and many theses are written on the subject of limited rationality, non-perfect information, etc, I think a lot of this behaviour boils down to one thing: When making actual decisions, humans tend to not overthink. And really, that's what Game Theory is a lot of the time: Taking a situation where there are consequences and rewards for acting in certain ways and finding the optimal way to play. But humans just don't do that kind of overthinking when actually sitting down to play one of these games.

People who do such overthinking(they might rather think of it as being efficient) are always flabbergasted by amateurs and underthinkers who pull off an amazing move despite their inefficiency. Watch a professional poker player play an amateur and you'll see what I mean.

One of my favourite examples of where this kind of overthinking works against someone also comes from one of my favourite webcomics: The Order of the Stick. Specifically, this comic, where Redcloak the Goblin is interrogating O'Chul the Paladin.

Redcloak is making a terrible leap in his logic: That everyone thinks the same way he does, that everyone makes their decisions based on optimality. He even comments a couple comics later that "Apparently, [the paladins] reserved their efficiency for killing goblin women and children."

Redcloak is unable to comprehend that decisions are made for a whole host of reasons beyond simply greedy optimality; in this case, the decision was made as part of a final promise between friends.

So the moral of the story is: Don't overthink things. You should still think through your actions, prepare for contingencies, etc, but don't overdo it. Only Game Theorists and computers have time for that sort of math.

The God Game

2008-12-07T12:24:00.000-08:00

Yes, yes, it's been a while. Travel got in the way.

I had a conversation on a discussion board I frequent about the nature of God. What does God want? How do your reconcile free will? All that jazz.

I then had a thought that since we were discussing possible motivations and actions of God, some Game Theory might be in order. So if one is willing to look beyond the fallacy of applying human definitions to a deity, here is some analysis to help explain why God does or does not do something.

There are three basic assumptions about any given Game Theoretic player:
1. They know the rules of the game. While this is a problematic assumption for real world experiments, I think it's pretty safe for God.
2. They are self interested. That is, they are most interested in improving their personal utility. This is tricky and we will get to it later.
3. They are rational. They can compute and compare the different options available to them. Depending how much potency you ascribe to God or Gods, this can be a pretty safe assumption.

But because God is not mortal, one must discuss what other assumption we can ascribe to God.
Omniscience is common. In this context, it would mean supreme rationality. God has no need to compute and compare options in order to find the optimal solution, God just knows. Thus, God knows what the optimal solution is in each possible situation and has no reason to not do it.
Omnipotence is also common. But what would this mean as far as Game Theory is concerned? Basically, it means God can cheat. God can change the number, nature, value, etc of the players, the options, etc to whatever. If this is so, why would God not do this?

But we must come back to the issue of self-interest. What is God interested in? Often people will ascribe human emotions and motivations to the Gods of their mythos(Greek and Norse Gods are great examples) and as a result, their goals are not unlike human goals on a grander scale. Thus there is not much surprise that Gods like that are often jerks. Greek Gods in particular were notoriously spiteful.

But what really is the goal of God?

Since God is often portrayed as a creator, it would also make sense to think of God in a Mechanism Design situation, as a central authority manipulating a game so that the players act in a specific way. This is actually a very apt position for God.

Omniscience and Omnipotence still beg the age-old questions, though. Why not interfere? Why such poor design? What is the goal? And thus the question of motivation comes back.

While we can't necessarily assume what God's interest is, we can be sure that God is doing it optimally.

Throw the Fight.

2007-07-13T08:54:00.000-07:00

A staple of sports movies and conspiracies, paying off someone to give up a competition has its own interesting game theoretic psychology.

For simplicity, I will consider a 2-person competition, from the eyes of one competitor, ie, the one getting bribed.

Game: Player P is in a 2-person competition(boxing, chess, whatever) where he has a percentage chance of winning equal to w, the prize for winning being worth c, the prize for losing being 0(for simplicity).

P is approached by some people who have vested interests in P losing. They offer P a reward of b for losing on purpose.

P now has a choice to make, and so we will look at a couple cases depending on P's attitudes to determine whether or not P should take this offer.

CASE 1: P cares only for his own utility.
In this case, it's a fairly simple matter of comapring possibilities.
If he denies the bribe, his expected utility is w*c. If he takes the bribe,his utility is b.
If b>=w*c, then it is clear P should take the bribe, because while c by itself may be greater than b, there is still the chance that P will lose anyway, getting a utility of zero.
If b<(w*c), then it is simply a matter of how much of a gambler P is. If w is greater than 1/2, then it is wise to decline the bribe, since then he would have a good chance to win c. If w is less than 1/2, then it is wiser to take the bribe, since the sure prize of b is better than a slim chance of winning c.
But, as I said, it depends on how much of a gambler P is.

CASE 2: P discounts utility for pride.
IE, P has a distaste for the dishonesty of the bribe. She would prefer to win or lose by her own power.
There is a discount factor d, where d is P's "pride". It is added when she refuses, and subtracted when she accepts the bribe.
So, her expected utility for not taking the bribe increases is w*(c+d) + (1-w)d = (w*c)+d.
Her utility for taking the bribe is b-d.
If b>=(w*c)+2d, then b-d>=(w*c)+d and we are in a similar situation to above. This represents the "everyone has their price" situation. P would be hard pressed to refuse such an offer, since her "pride" has been factored into the bribe.
If (w*c)+d <= b < (w*c)+2d, then b-d<(w*c)+d, but it's still not a clear cut decision, because (w*c)+d is still only an expected utility. "That's pride fuckin' wit' you" as Marcellus Wallace from Pulp Fiction would say. There's no clear decision to make here, unfortunately, and such decisions are tests of one's character.

All this is not even taking into account possible legal repercussions of the bribe, but I think this is a decent enough simulation with out it. Pride in a competition is a tricky thing, and even if you are unscrupulous and selfish, there are still insufficient prices.

Until next time, cheers.

Stratergy

2007-07-03T09:50:00.000-07:00

Being the Game Theoretic guy that I am, I thought I might do a little tribute to some great lesser-known strategic games out there.
Risk, Chess and the classics are obvious choices, but these are some of the more recent or marginalized games.

Bear in mind, this is not necessarilly strategy games, but real games of strategy.

1. Illuminati. Easily Steve Jackson's best game. The rules, while a little tricky at first, are straightforward once underway. Lots of underhanded wheeling and dealing can go on, each different illuminati you can play has different and preferred tactics, and the game can go on for quite a while. You can spend lots of hours on this game, and be amused the whole time, thanks in part to Jackson's tounge-in-cheek game design. A great game all around. I highly recommend picking it up.

2. Settlers of Catan. A relative newcomer, this game is HUGE here at Waterloo. It seemed to be almost singly responsible for most of my residence to give up video games in exchange for board games for a long time. The rules are very starightforward, the game is very efficient and fast paced, and there are countless strategies and permutations of the game. Plus there's always the hilarity that ensues from asking "Got wood for sheep?"

3. Imperialsim. A turn based computer strategy game where you play as a great power, and you have to turn it into the dominant force in the world, whether through conquest or diplomacy. The trick is in managing your resources and securing trade routes. Unlike many nation-competing strategy games out there, this is one where it is possible(though difficult) to win without firingt a single shot. If you are so far ahead of the rest of the world in technology, economy and infrastructure, then the AI tends to leave you alone. This game is incredibly addicitive. Hard to find, though.

4. Fluxx. The game with the ever changing rules. This is a card game where you don't so much act until you fulfill the requirements to win, you change around the requirements until you win. A very different kind of strategy paradigm. The best moves are those where you change the rules during your turn to put you far ahead, then change them at the end of your turn to make things horrible for your opponents.

Any other lesser know great strategy games out there? I'm always on the lookout.

"The Talk" part 2

2007-06-05T07:21:00.000-07:00

Well, I made some huge blunders.
1. A teen's decision to have sex is in no way correlated to the info they have. I have no idea what I was smoking when I thought that.
2. There really is no game here. Peers will tell eaach other anything for bragging rights, parents generally avoid saying much beyond the basics, and the kids themselves usually couldn't care less.

So that's part 2, me admitting my mistakes.

Forgive the time discrepancy, personal issues for the lose.

"The Talk" part 1

2007-05-16T18:05:00.000-07:00

Birds do it, Bees do it, Humans do it.

Being the social animals that we are, sex is a normal part of everyday human existance. But why is "the Talk" stereotyped to the point where parents are unwilling to say a thing? The extent of a talk I got was, almost verbatim: "Don't be stupid. Use a condom."

There must be some sort of game going on here.

PLAYERS: Parents we will refer to as one player, for simplicity's sake. Child will be another player. We will assume that the child is around 11 years old because most schools start their sex-ed courses then. Peers will be another player, because as the stereotype goes, kids learn more from their friends about sex than their parents.

ACTIONS: Parents have a continuum of actions, reprsenting the amount of information to provide. This info will be represented with the letter i, and will belong to the closed interval [0,1], i=0 means the parents tell nothing, i=1 means they tell everything(anyone have a doctor as a mother/father?).
Peers will likewise have a continuum of actions, but kids can be a font of very unreliable info. Their info will be represented by the letter p, and will belong to the closed interval [-1/2, 1/2]. p=0 again represents no info. p=-1/2 means REALLY bad info, p=1/2 means decent info.
Now for the Child. They will have an choice of being sexually active or not, with the outcome/utility of that being a random number dependent on the info available, and their choice dependent on the info they have. Due to sex-ed, we will assume that the Child has an initial info of 1/4.

GAME: There is a cost for the Parents associated with giving the talk, possibly representing embarrassment or awkwardness. We will say that the cost is equal to the info given. Parents will also have a cost if the Child becomes sexually active and becomes pregnant(or gets someone pregnant) or gets an STI, which we will say is -10. Parents will have a benefit associated with their child becoming sexually active and having a healthy relationship(though this may be unrealistic, it helps ensure that the parents can have positive utility), which we will say is 2.
The Peers get a benefit for any p=/=0(bragging) that is equal to |p|(It doesn't matter how good the info is, but how much you have). They likewise, however, get a cost associated with their friend getting pregnant/STI that we will say is -5(not as bad as parents, but still sucks).

Now for the interesting part, the Child. We will assume that, like many kids, that they don't listen much to what their parents say, so i is only worth 1/2 of its value. We will also assume that, like many kids, they trust their friends. Hence, p is worth its absolute value. Total info, T, is therefore equal to 1/4 + |p| + (1/2)i. We are, unfortunately, assuming that all of this info is independent, which is not terribly accurate, but it makes the math much easier.

So, the Child will always become active if T > 1. They have lots of info and are just waiting to try it out.
The Child for sure will not become active if T < 3/4. They just aren't sure and need more info.
If T is in [3/4, 1], then they will pecome active with probability T.

The outcome for the Child of all this is
Not Active: 0. No change.
Active, but problems arise(pregnancies/STIs/whatever): -5
Active, but no problems arise: 2. Sex is fun, I ain't gonna lie.
Active, no problems, healthy relationship: 5. Sex is even better with love.(oh man, do I sound sappy)

Now, for some PROBABILITIES.
Problems: 1/4 + p + i. If you're well informed, problems are unlikely. If this total is <0, then treat it as 0, can never be more than .99 as there is always the possibility for a problem. "Failing" this probability roll means a problem arose.
Healthy relationship: 1/4 + i. As much as kids may not realise it, the parents probably know a fair bit about relationships. This total is never treated as greater than .95 because, again, some people are just unlucky.

This is a pretty big pill to swallow, but is a decent starting point. In the next part, I'll talk strategies.

The Chore Rotation

2007-05-08T13:34:00.000-07:00

Live with anyone, anywhere, and you will run into this sort of situation. Things need to get done to help keep wherever you're living in reasonable/clean/respectable/whatever condition, and you want everyone to be a part of it, at least in theory.

I personally had to deal with some of this recently, so this was the first topic that came to mind. I was also discussing this with my girlfriend, so I figured it deserved mentioning.

For ease of analysis, I will look at the case where the chore in question is cleaning, though it extends easily to more general chores. I will also consider the two player case, though, again, the multi-player case is a pretty natural extension.

I guess I need to state my ASSUMPTIONS, and these will likely be the same for any situation I describe: Players are rational(in rough non-technical terms, can do a lot of computations really fast), self interested(will always act to increase their own utility), and are informed(know all the rules, alternatives and outcomes of the game).

Rational is an okay assumption in games where there are not many outcomes, so not many problems there.
Self-interested is a pretty good assumption considering how most people act in real life.
Informed is tricky. For small games with few alternatives it's reasonable, but it's still tricky. I'll try to avoid it when I can.

SETUP: Each player has two choices: clean(A) or don't clean(B). There is a benefit associated with having a clean house, we'll call it H, which is >0. However, there is a cost associated with cleaning. We'll call this C. The benefit to a dirty house is 0.

GAME1: House is cleaned each week. Each player is in charge of cleaning half the house, and the part of the house that is cleaned rotates between each player each week. There is a "gentleman's agreement" that cleaning will get done that both players agree to, ie, they are going against the self-interested assumption. This agreement also includes that when cleaning gets done, the whole house must be cleaned in a given week.(This is a fairly common agreemen among housemates)

The utility for both players in this case is H - C. We will assume that H>C so that there is net positive utility to a clean house.
Things are going along swimingly. However, one week Player 1(p1) is unable to clean for whatever reason. They have only option D, and so have to do it. Player 2(p2) decides that this week, she will do the cleaning.

p1 utility = H, p2 utility = H -2C. H - 2C could be <0, but this is only for one week.

The next week, however, p1 is able to clean, but the agreement before is nulled since she couldn't clean before. She is now self interested once again. Her utility from the last week is H which is > H - C, so she has no incentive to start cleaning again.(perhaps she is lying to the other player, continuing her story from the week prior)
p2 is now in a difficult position. If H - 2C > 0, then she will likely still clean, since if she doesn't clean, her utility is 0. This is stll unfair, as H > H -2C, so p2 is still getting a raw deal.
If H - 2C < 0, then she won't clean either, since her utility will increase from a number less than 0 to 0.
At this point the players are in a Nash equilibrium. There is no incentive to single-handedly start cleaning again until H - 2C > 0.

At that point people get angry and start yelling at each other to clean.

GAME2: Similar to above, each player is in charge of half the house, but it does not rotate. The benefit to half a clean house is obviously (1/2)H. The agreement this time is that each person cleans only the half of the house they are responsible for.(Another common agreement)

The utility for both players adhering to the agreement is once again H - C which is > 0.

Let's say a similar thing happens here, that p1 can't clean for one week for whatever reason. p2 then cleans her half, and gets a utility of (1/2)H - C. This could be less than, equal to, or greater than 0, as before. If we multiply these expressions by 2, we get H - 2C is greater than, less than, or equal to 0, depending. We are in the same situation as before.

Thus, we get into situations where once the agreement/system breaks, the players end up in a Nash Equilibrium where no one is willing to start the system back up.

The philosphy I follow with regards to cleaning is thus: Clean up after yourself. Not only does this keep your own personal space clean, it helps keep public spaces clean, and shifts blame of dirtiness to the other players. It puts you on what I call the "high horse", where a player is in a position to incentivize(read: guilt) other players into action.

Any other cleaning strategies out there?

In the beginning...

2007-05-08T11:17:00.000-07:00

There was darkness, chaos and ignorance.

One day, there came the light, and the light was understanding, and the understanding was light. Chuck "Orcus" McPhail had come.

Okay, enough pretention. It just had to be done, sorry.

As a recent graduate of the University of Waterloo's prestgious Faculty of Mathematics, I like to think I have a handle on things. Specifically math.

My final year at UW, I took two courses in particular that opened up my eyes to some interesting possibilities: a course in Game Theory, and a course that dealt a lot with Mechanism Design(algorithmic Game Theory).

Take players, alternatives, outcomes, preferences and some assumptions about interaction and you're ready to do some analysis. I fell in love with this topic and it is easily my favourite branch of mathematics, a lot of my final year of study being related to how these things work within Graph Theory.

But more to the point, once I learned all that, I started seeing all sorts of everyday situations that can be modelled in Game Theoretic terms. And so, we come to the point.

Here, I will do some analysis of everyday/political/economical/stupid/amusing situations that I come up with as if they were strategic games. Sometimes I hope to be insightful, most of the time I will just be thinking on-screen.(Someone needs to find a better computer equivalent to "thinking out-loud")

Cheers.