Rationalizing the Traveler’s Dilemma

Another recent article in Scientific American is about the Traveler’s Dilemma problem in game theory.

For those too lazy to click on any of those links, here’s the basic problem (taken from the Wikipedia article):

An airline loses two suitcases belonging to two different travelers. Both suitcases happen to be identical and contain identical antiques. An airline manager tasked to settle the claims of both travelers explains that the airline is liable for a maximum of $100 per suitcase, and in order to determine an honest appraised value of the antiques the manager separates both travelers so they can’t confer, and asks them to write down the amount of their value at no less than $2 and no larger than $100. He also tells them that if both write down the same number, he will treat that number as the true dollar value of both suitcases and reimburse both travelers that amount. However, if one writes down a smaller number than the other, this smaller number will be taken as the true dollar value, and both travelers will receive that amount along with a bonus/malus: $2 extra will be paid to the traveler who wrote down the lower value and a $2 deduction will be taken from the person who wrote down the higher amount. The challenge is: what strategy should both travelers follow to decide the value they should write down?

Traveler’s Dilemma can be seen as a generalization of the infamous Prisoner’s Dilemma problem (and in fact reduces to it if you replace $100 with $3 in the problem statement), and suffers the same perverse situation where rational players will make the choices that result in the worst outcomes for them.

Why’s that? Suppose you and the other player both pick $100, which results in both of you getting $100. However, if you pick $99 instead, you get $99 + $2 = $101, which is better, so you’d choose $99 instead of $100. (In fact, choosing $99 is always at least as good as, and sometimes better than, choosing $100.) But since the other player is also rational, he’ll also choose $99 instead of $100, and as a result both of you would get $99. Similarly, if you reduce your choice to $98, you would wind up with $98 + $2 = $100, which is better than $99. Of course, the other player also knows this, and will choose $98 instead of $99 as well. According to this analysis, the race-to-the-bottom continues until both you and your opponent choose $2, resulting in each of you only getting $2.

Another way to look at it is, whatever the other player picks, your best strategy is to underbid him by $1. Since he’s also playing rationally, he’ll try to do the same to you. As a result, you both pick the lowest choice possible, because any other choice will fare strictly worse against that same rational strategy — both players picking $2 is the Nash equilibrium.

However, this analysis is empiricly wrong. When you do a Traveler’s Dilemma with actual people, most don’t play the Nash equilibrium as we would expect from the above analysis. Instead, most of them choose a high dollar amount, typically somewhere between $90 and $100. According to the analysis, this is an irrational choice, but since most players play this way, the result is that they have a far better outcome than if they had picked $2, so the irrational choice is better.

So, is playing irrationally is the truly rational way to play? Or is there something wrong with our original analysis?

My hypothesis to explain what’s going on holds that the players are in fact playing rationally; it’s just that our game theoretic model isn’t properly considering the valuations the players are actually using.

I believe the game theoretic model for Traveller’s Dilemma makes a critical error in the assumptions it makes about the players: it assumes they are completely risk averse, unwilling to risk choosing anything other than the option with the highest guaranteed payoff. Note that choosing $2 is the only choice that guarantees the player will make at least $2 in the end; all other choices risk making $0 depending on how the other player chooses.

In reality, people are going to have some non-zero degree of risk tolerance; they’ll be willing to accept the risk of a non-optimal payoff for the chance of a larger one. Just how much risk a person is willing to accept depends on their own risk tolerance profile, and the dollar amounts at stake.

Here’s why I think rational real-world players tend to choose something in the $90s instead of the Nash equilibrium of $2. They understand that choosing $2 guarantees them a payoff of $2, but $2 is of little real-world value to most people. After all, what can you buy with just $2 anyway? However, the maximum possible payoff is $101, and they’d prefer a payoff closer to that than $2. But to get a payoff in the $90s, both players need to choose something in the $90s. A player doesn’t know with certainty what the other player will choose, but it’s likely the other player will see little value in $2 but a lot of value in the $90s. So, the player must choose whether or not to risk a guaranteed $2 for the chance to get $90 or so. Since $2 is almost worthless but $90 certainly isn’t, most players choose to take the risk.

This line of thinking doesn’t provide any obvious dollar amount a player is expected to choose, but does provide an escape from the race-to-the-bottom scenario in the traditional analysis. (In fact, if individual dollars aren’t very valuable to a player, he probably isn’t too concerned with getting $93 versus $95 anyway.) Since most people are willing to take the risk, chances are the risk does pay off, and both players come out much better than they would have if they had played the Nash equilibrium.

Like all good hypothesis, there is a way to test mine against the traditional model (and the null hypothesis of “people are dumb but like picking big numbers”. My hypothesis depends on the absolute dollar amounts involved in the game: it assumes that $2 is of little value to a player but $90+ is. The traditional model, however, does not. I predict that if the game were changed so that the allowed range ran from $2,000,000 to $100,000,000 and the bonus/malus was increased to $2,000,000 — in other words, multiply all dollar values by 1,000,000 — we would see most players play the Nash equilibrium instead of taking the risk.

Why? Because to most people, $2,000,000 is a lot of money, and risking losing that for the chance to gain $100,000,000 is a lot harder to swallow. Plus, when the decreasing marginal utility of money is considered, that $100,000,000 isn’t actually worth 50 times more than $2,000,000, whereas $100 would be seen as worth 50 times (or possibly more!) as much as $2. On top of that, it’s hard to wrap one’s mind around just how much $100,000,000 is; I could find a way to send $2,000,000 without too much difficulty, but $100,000,000? I’d have to really work to spend half of that before I die.

So in Traveller’s Dilemma x 106, a player is expected to be a lot more risk averse than before. And since both players must take the risk to see the payoff, few, if any, players are actually going to take it, it’s much less likely for the risk to actually pay off. As a result, most players will stick with the Nash equilibrium of $2,000,000 as the rational choice.

(By the way, if anyone wants to run this experiment with real money, I volunteer.)

So, Traveller’s Dilemma doesn’t show that people don’t act rationally, just that the game-theoretic model doesn’t properly consider risk tolerance of the players. Sure, people act irrationally all the time, but this situation isn’t one of them.

Paul v. Scientific American

[Editor’s note: Sent to the editors in question. By some corollary to Skitt’s Law, naturally, I managed to screw up the second set of page references in the copy I sent them. Sigh.]

In the June 2007 Scientific American article “Breaking Network Logjams”, the sidebar on page 83 claims “Still, when neither a nor b is 0, both receivers can retrieve the proper messages successfully.” Alas, selecting codes is not quite that easy: a and b must be relatively prime to 2m (where m is the number of bits per message). Only then is

a * X + b * Y = E (modulo 2m)

guaranteed to have a unique solution when all variables except either X or Y are known. a and b needing to be nonzero is merely a special case of this requirement.

Luckily, since 2m will never have any prime factors besides 2, choosing odd numbers for a and b guarantees they will be relatively prime to 2m. Although this means that a purely random choice for a and b will only work 25% of the time, it is trivial to restrict the random choice to only odd numbers to begin with.

The example on pages 82 and 83 in fact demonstrates what happens when a and b are chosen poorly. In the example, a = 3 is a safe choice, but b = 20 is poor, since 20 and 32 have a common factor (4). In solving

3 * 21 + 20 * Y = 23 (modulo 32)

there are four possible values for Y: 6, 14, 22, and 30. There is no way to tell which possible value for Y corresponds to Ben’s message; as a result, Carl is unable to receive Ben’s message reliably.

Talk about dedication

As you know, YouTube limits most video uploads to about 10 minutes in an effort to prevent people from uploading TV shows, movies, and/or whatnot in violation of copyright. To work around this, of course, many users simply split a video into segments, each of which are under the limit, and then just upload all the individual pieces separately.

Not that I’ve looked very hard, but the biggest number of segments I’ve seen for a single video is 116. Yes, one hundred sixteen. Granted, most of the segments fall far short of the 10 minute limit, but still, that’s a fair bit of work.

The video in question is a complete play-through of EarthBound. You can start watching it with the first segment, if you’ve got several hours to kill and would rather watch someone else play than play it yourself.

Fun fact: Giygas‘s dialogue during the final battle was inspired by a rape scene in a movie the game’s creator saw as a child after accidentally wandering into an adult movie theater. Well, maybe not fun for him, but a fact nonetheless.

Comments Off

Every dog has its 3.43 hours

A sample of what you’re in for if you instant message me.

Nevermind the fact that technically I started that.

So you want to complain about an ending?

Dear people complaining about the final episode of The Sopranos,

While I do appreciate your concerted efforts to knock Paris Hilton off the top spot on the Entertainment section on Google News, enough with the whining already. Seriously.

If you really want to complain about an ending, go watch The Prisoner. There’s a lot more in its final episode to go on about than just the very last scene, let me tell you.

Of course, even if you complain about The Prisoner’s ending instead, you’ll still be wrong. It’s not my fault you miss the point.


- PK


As anyone who was following last week’s announcements of the OMGWTF finalists, my own Ecumenicalculator failed to make the cut.

Apparently implementing a four-function calculator without using the language’s arithmetic operators — or numbers, for that matter — didn’t sufficiently tickle the first-round judges’ fancies. I don’t know if there’s going to be some kind of honorable mentions or anything, but implementing Church numerals and Lambda calculus in C++ to implement a calculator has got to be worth some props, right?

Now, some of the finalists look pretty good (judging from the writeups, at least). I do like the concept of an entry whose code base mimics a ailing multi-year development effort, and the one that does input through OCR and does computation symbolically on those user-defined “shapes”, and the one that implemented a virtual integrated circuit and then constructed the computation logic in terms of fundamental electronic components. So this post isn’t entirely sour grapes.

But several of the finalists are pretty hu-hum “let’s see how many pointless intermediate layers and Rube Goldberg chicanery I can fit in.” Yeah, there’s a WTF element to them, but there’s nothing particularly clever to the basic approach aside from finding the most arcane communications channels you can (like X window properties) to use. They’re lacking a unified overarching vision for why things are done the way they are. In Ecumenicalculator, aside from the “let’s not use any normal numbers or arithmetic” concept, all the other apparent strangeness has solid technical justifications for it.

If I had it to do over again, would I chance anything? Absolutely! I didn’t win with Ecumenicalculator, did I?

In hindsight, if I wanted a conceptual WTF approach (instead of Ecumenicalculator’s purely internal WTFery), I would do one based on Digital Rights ‘Rithmetic Management. In DRMCalc, the central premise would consist of two parts:

  1. Arithmetic operations are the precious intellectual property of DRMCalcCorp, and no one must be allowed to have it unless they pay for access.
  2. The user is a dirty rotten thief out to deprive DRMCalcCorp of its livelihood.

In other words, DRMCalc would answer the question “what would happen if the RIAA wrote a calculator?” DRMCalc would have some combination of the following features:

  • Each arithmetic operation (or “advanced” functions like trig) would be a separately installable module, in order to monetize potential revenue streams for increased functionality. (Hey user, if you like addition, you’ll love subtraction, only $49.95 per month!)
  • Each module will require a valid license key to operate. License keys would be based on a public key infrastructure; without the proper encryption and decryption keys, you can’t sign the inputs to the operation or decrypt the output.
  • Each module would phone home to a central server to verify that a license key hasn’t been revoked before accepting it. This would also allow detection of multiple users sharing a license key, which could lead to the key’s revocation.
  • Each module would also phone home each time a calculation is performed for, um, market research purposes. Also, DRMCalcCorp retains the rights to use all calculations you perform. (It’s in paragraph 175 of the EULA.)
  • Since arithmetic is the exclusive intellectual property of DRMCalcCorp, any other calculators on the system are violating DRMCalcCorp’s IP rights. On startup, DRMCalc would launch a stealthy, persistent set of processes to monitor system activity and sabotage any programs that look like they might be a calculator. (For example, running “killall -s SIGFPE gcalctool” will cause any running instance of GNOME’s calculator to think it crashed.) Covert channels are used to report such activity to the central server, since obviously use of an unlicensed calculator violates the EULA.
  • Advanced feature: DRMCalc would launch multiple instances of each module, which would use Byzantine consensus algorithms to prevent malicious user software from degrading DRMCalc’s accuracy. (I hear there’s programs out there that try to sabotage calculators!)
  • Really advanced feature: DRMCalc’s modules would periodically polymorph themselves to stymie reverse engineering efforts.

In other words, massive paranoia. Note that none of this has anything to do with the calculations itself, but rather comes out of a completely warped notion of what the calculator’s operational environment is going to be.

DRMCalc would actually probably be as much fun to write as Ecumenicalculator was, but given that there’d be no point in doing so aside from proving that it could be done, it’s not going to happen.

What Master Shake can teach us about graphic design

Me: OK, so I know it’s a lot later than what I promised, and I know it’s awfully dorky, but I do have some images, so can you post it anyway?
Editor (also me): That depends. Do the images reinforce the dorkiness?
Me: … Yes? But some of them have captions.
Editor: Not good enough.
Me: Funny captions?
Editor: *sigh* That’s debatable, but fine. I’ll post it.
Me: This counts as your disclaimer, folks.

Aqua Teen Hunger Force - “Super Hero”

Remember that episode of Aqua Teen Hunger Force where Master Shake tries to become a superhero? He steals some radioactive waste from the “storage facility” (a.k.a. the river), dunks some worms in it, tries to get the worms to bite him, fails, and dumps the waste on himself, thus supposedly giving him superpowers. Over rain. For some reason.

Of course, in the end it works about as well as it did in that one Family Guy episode, but that’s not the point.

Between dousing himself in radioactive waste and his eventual (literal) meltdown, Shake focuses on marketing his new superhero identity rather than doing any actual superheroing. Most of these efforts are naturally inept, such as his The Drizzle cell phone giveaway or his black-ink-on-black-paper stationery.

However, there is one moment in the episode (possible the only moment in the entire series, in fact) where Shake demonstrates actual competence. It’s when he calls the T-shirt printers to complain about the The Drizzle T-shirt they designed. The design shows lots of villains running amok, and Shake points out how it’s too busy and no one will understand it. His observation is borne out when Shake goes on an angry rampage through the city, which is caught on film by the local news, but the best they can make out of the design on the shirt Shake is wearing is “ants marching at a picnic.”

So, even Master Shake, someone who at best enjoys a fleeting and tenuous grip on reality, understands that making a graphic too complex can ruin it.

So why can’t a certain set of professional animators understand that?

I am talking, of course, about the logo redesigns in the forthcoming new Neon Genesis Evangelion movies.

[Editor’s note: Hey, it’s not my fault you ignored the disclaimer.]

SEELE Logo (original)

Let’s take the original logo used by SEELE. Now this is a logo befitting a shadowy, secretive organization that’s pulling the strings and orchestrating events for its own mysterious goals. The logo tells you nothing about who they are or what they’re doing, but it’s clear they’re powerful and probably evil. They’ve got the Illuminati outclassed: their logo’s got seven eyes, and their pyramid’s upside-down. What does that mean? They certainly aren’t going to tell you!

And as for the rainbow coloration, um, that’s a good question actually. Maybe it’s there to annoy Jerry Falwell or something.

We’re talking about an organization that’s so shadowy, their meetings look like this:

SEELE Meeting

SEELE 01: Good call on the monoliths, Jenkins. Think of all the money the animators will save with slow pans over a static image!
SEELE 06: Not to mention not needing to come up with character designs for all of us!
SEELE 07: Or names…
SEELE 03: But Chairman, what if the audience starts to lose interest during these scenes?
SEELE 11: We could use the money we saved from the animation budget to, I don’t know, interrogate a naked chick at our next meeting?
SEELE 01: Brilliant! Let’s pencil Ritsuko in for our meeting in Episode 23.

SEELE Logo (new)

Now take a look at this redesigned abomination. That is, if your eyes can even decide what part of it they’re supposed to focus on first. There is way too much going on here.

Sure, the classic bits are there, but they get crowded out by all unnecessary new pieces. I mean, what kind of secret organization puts their name right on the logo? That’s a rookie mistake. You might as well go ahead and put your street address and URL on there while you’re at it. (Sorry guys, seele.de is already taken.)

Bringing out a slogan in German isn’t helping the cause either, guys. Sure, if you want something that sounds evil, German has pretty much been the go-to language since the 1930s. But when you’re quoting Ode to Joy, the whole thing kind of loses its impact. (And if there’s one thing SEELE doesn’t want, it’s to lose its impact.)

And OK, the snake coiled around an apple makes sense if you understand just what SEELE’s trying to do, but is it really necessary? It’s not like there weren’t already plenty of references to that part of Genesis in the series already, what with the whole Adam and Eve thing being warped into an important part of the plot and all.

Although I suppose Evangelion has hardly been subtle about its use of Judeo-Christian imagery to begin with.


Misato: Um, yeah, wow. I’ve just got one question about this.
Kaji: Just one? I can think of a dozen.
Misato: Good point. But I mean, is this whole crucifixion thing actually symbolic, like the Sephirot in Gendo‘s office, or is it just there to look cool and meaningful like all those inexplicably cross-shaped explosions?
Kaji: Except for it being named Lilith, I’m guessing the latter.
Misato: Well, at least the imagery can’t get any more over-the-top than this.
Kaji: Are you kidding? Have you seen the movie?

NERV Logo (old)

But the unnecessary redesigns don’t end there, oh no. They even tamper with the classic, if not iconic, NERV logo. Being a publicly known paramilitary organization ostensibly working for the UN, NERV’s logo isn’t quite as sinister looking as SEELE’s.

Nevertheless, the logo still makes it clear that they’re hiding something, even though in the public eye they’re The Good Guys. Note especially how their name is partially obscured by the half fig leaf. A fig leaf’s at least a little more subtle than a snake-and-apple.

But don’t try telling me my criticism of the added SEELE slogan should also apply to the Browning quote that arcs along the bottom here, because it doesn’t. First, NERV’s slogan is at least scrutable. Besides, NERV is publicly recognized, remember? Of course they’re going to have a slogan that sounds reassuring, even though later on you learn just how ironic it is.

NERV Logo (new)

Besides, the old logo is far better than this new abomination they’re trying to foist on us. To quote Master Shake in a cameo on Sealab 2021, did an elephant paint this?

Who thought superimposing an upside-down apple (again with the apple!) over the half fig leaf with some swoopy highlights was a good idea? It looks like someone went crazy go nuts with the filled polygon tool in MS Paint. It’s almost indecipherable. I mean, what’s going on with the part to the immediate right of the V?

And as for the design of the slogan, it gets a resounding meh. It’s just sort of… there.

But lest you think Evangelion’s only about using religious iconography in weird ways, don’t worry. There’s also plenty of superficial allusions to genetics and molecular biology — the series could probably justify putting an “In Popular Culture” section under the Wikipedia article for Pribnow box, which would be quite an accomplishment.

And of course, there’s a healthy dose of Freud to be found too.

Entry Plug

A cigar may just be a cigar, but a long cylindrical tube you sit in to be inserted into the body of something that contains the soul of your dead mother? I’m pretty sure we all know what that represents, Oedipus Shinji. At least it only goes into the back of the neck, though I can imagine what might come out of Rule 34. Stupid Internet.

(Doubt me about the Oedipus crack? Shinji, Gendo, and Rei. Q.E.D.)

So, given how the two logo changes seem to beat the viewer over the head with the existing symbolism , I can only assume the remake movies are going to be cranking things up to eleven. So, in other words, I predict it’ll be The End of Evangelion all over again, but for the entire series instead of the last two episodes. Which is simultaneously exciting and frightening.

In conclusion, that is how you judge a series of four movies based solely on two small images taken from them. Next time: judging books by their covers.

[Editor's note: Not really.]

Comments Off

Music Applet 2.2.0 Released

The latest version of Music Applet is finally out, and hopefully you’ll find it well worth the wait. The biggest change is that there’s now support for MPD, Quod Libet, and the original XMMS. There’s also now support for a notification popup whenever the current song changes, which can be disabled if you so choose. Of course, there’s also bug fixes and updated translations; take a look at the release notes and the changelog for all the details.

Greatest congressional interview ever

If you don’t watch The Colbert Report, take a gander at what you’re missing out on:

Helpful tip: If you’re a congressman being interviewed by Stephen Colbert, you might want to know more about yourself and your district than he does, or that can be found on your own website.