# Computational Complexity

### Friday, March 21, 2003

Some follow-up on earlier posts of this week.

The University of Connecticut defeated BYU in men's basketball yesterday, keeping the integrity of the tree.

If you are a male American, you are likely participating in a pool predicting the outcomes of the games of the NCAA basketball tournament. How are you doing? Have you been eliminated yet? Not such an easy question to answer as it turns out. Six MIT grad students have recently shown it is NP-complete to decide if you can still win the pool.

Dave Pennock pointed out that there have been many articles in the popular press about information markets including a piece in the New Yorker.

Pennock also mentioned the Iowa Electronic Markets, which allows limited legal trading in certain political markets.

### Thursday, March 20, 2003

ICALP Papers Announced

The accepted papers for ICALP have been posted. As I mentioned last week, ICALP has two submission tracks that match the Theory A and Theory B split. The list of accepted papers though has both tracks intermingled. See if you can guess which papers are from track A and which papers are from track B.

### Wednesday, March 19, 2003

Information Markets

Suppose you want to make a prediction on say who will win the Best Actress Award at Sunday's Oscars. You can visit various web sites, look at the predictions of so-called experts, look at polls, etc. Aggregating all of this information to make a single prediction seems quite difficult.

Information Markets do information aggregation by creating financial securities based on the outcome of some event. You can then make predictions based on the prices of these securities. For example, look at the Best Actress page of the Hollywood Stock Exchange. There are five securities listed for each of the nominees. Each security will pay out \$25 if that nominee wins and \$0 otherwise. At the time I am writing this, the price of the Nicole Kidman security is \$13.45. If you take the ratio of the price to the final payoff this gives a probability of winning. For Kidman that would be a \$13.45/\$25 or 53.8% chance of winning the award.

There are two problems with the Hollywood Stock Exchange. First they don't use real money since that would be illegal in the US. Also the best actress winner has already been chosen so if real money were being used there is the potential for corruption. Nevertheless studies have shown that even such artificial markets still do far better than the experts in predicting the winners.

You can eliminate the problems by considering sporting events on real off-shore betting sites. Sites like Tradesports or the World Sports Exchange have securities (futures) on outcomes based on sporting events that you can look at without registering. In Tradesports consider the security NCAA.BK.KENTUCKY that pays off \$100 if the University of Kentucky wins the men's basketball championship and \$0 otherwise. The price as I am writing has a bid of \$25 and an ask of \$26 meaning that Kentucky has between a 25% and 26% chance of winning the NCAA tournament. It will be interesting to see the price and thus the odds change as the tournament progresses. For example if Arizona would be upset in an early round, this should cause Kentucky's price to go up.

Tradesports also has securities in entertainment and political events. On Tradesports Kidman has a bid/ask of \$54/\$57 not too far off of the Hollywood Stock Exchange.

### Tuesday, March 18, 2003

It's Not a Tree After All

On Sunday, I posted a link to the 2003 NCAA Division 1 Men's Basketball Championship Brackets which I called "America's Favorite Binary Tree". But in a strange twist the championship is not quite a tree this year.

In a usual year the rules are simple. Each team plays its sibling. The winner advances to the parent node and the process repeats. The team that reaches the root is the champion.

The tree structure gives a nice uniqueness factor. If Notre Dame plays Duke this year, they would have to meet in the fourth round. There is no scenario of plays in the other games that would cause Notre Dame to play Duke in any other round.

So why isn't it a tree this year? The problem is Brigham Young University. If BYU wins their first three games, they would have played their fourth game on Sunday, March 30. BYU is a Mormon school and school policy forbids games on Sundays. The NCAA solution is the following: If BYU wins their first two games they would swap with one of the teams from the Midwest subtree which plays its fourth round on Saturday the 29th. In the more likely event that BYU does not win its first two games the original schedule will hold.

It's not hard to show that the uniqueness property above no longer holds and thus the tournament this year no longer can be represented as a tree.

### Monday, March 17, 2003

War and This Weblog

I was teaching my class right after the first Gulf war started in 1991 and wondering what to say. Sometimes I wish I were a history or government professor and could bring in current events into my lectures. But I taught computer science so I mumbled a few words acknowledging the conflict and went on to talk about NP-completeness or whatever I was teaching back then.

Now with the second war about to start I am not teaching but am in a similar position with respect to this weblog. I will not discuss much about the war in this weblog, there are plenty of other weblogs for that purpose. I will instead keep this weblog going as usual to keep a sense of normalcy and because science, in its pure form, does not depend on the political events of the world.