Friday, March 21, 2003
On Basketball and Politics
Some follow-up on earlier posts of this week.
The University of Connecticut
BYU in men's basketball yesterday, keeping the integrity of
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
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
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
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.
Sunday, March 16, 2003
Check out America's Favorite Binary Tree.