Summer School on Matching Problems, Markets, and Mechanisms

A summer school on Matching Problems, Markets, and Mechanisms will be held in Budapest on June 24-28, 2013; see the website for more details. Incidentally, the summer school will be followed by the Erdos Centennial conference.

Read Full Post »

The rise and fall of my Erdos number

I turns out that Paul Erdos was born 100 years ago today. Nowadays his name most often comes up in the context of people’s Erdos numbers, so this happy occasion seems like a good opportunity for two anecdotes.

Anecdote 1. The Bacon number is the distance from Kevin Bacon in the graph where vertices are actors and there is an edge between two actors if they played in the same film. There is also an Erdos-Bacon number, which is the sum of one’s Erdos and Bacon numbers. I once read that Erdos had a Bacon number of 3, which would give him an astounding Erdos-Bacon number of 3; but this is false. Wikipedia tells the story:

He [Erdos] appears in N Is a Number: A Portrait of Paul Erdos (1993) with a Gene Patterson, and a Gene Patterson was in Box of Moon Light (1996) with Sam Rockwell who was in Frost/Nixon (2008) with Kevin Bacon. However, this is incorrect, as the Gene Patterson in N Is a Number: A Portrait of Paul Erdos is not the same person as the one in Box of Moon Light (1996).

According to the Wikipedia article Natalie Portman, Carl Sagan, and Richard Feynman have Erdos-Bacon numbers of 6.

Anecdote 2. My PhD advisor Jeff Rosenschein has an Erdos number of 3, so when I published my first paper with him my number decreased from infinity to 4. A year or two later, I wrote a paper with Bezalel Peleg, who has an Erdos number of 2, and we submitted it as a technical report. At this point I started bragging that my Erdos number is now 3. My office mate Shahar Dobzinski (whose own number is 3, I think) was quick to point out though that a technical report doesn’t count for the purposes of computing one’s Erdos number. Of course we turned to Wikipedia to adjudicate this important dispute. Wikipedia (still) says that the Erdos number is “measured by authorship of mathematical papers”. My paper with Bezalel is clearly a mathematical paper, right? Shahar wouldn’t give up, and looked up the definition of a “mathematical paper”. I couldn’t find the relevant entry now (this was six years ago), but if I remember correctly the (somewhat circular) definition that Shahar was able to find was that a mathematical paper is published in a “mathematical journal”. I was defeated.

Eventually I published a few papers with Noga Alon — whose Erdos number is 1 — including one in the journal Mathematics of Operations Research and one in the journal Discrete Mathematics. Journals with the word “mathematics” in their names are clearly mathematical journals, right?

Advertisement

Read Full Post »

Cambridge Area Economics and Computation Day — April 26

The Second Cambridge Area Economics and Computation Day (CAEC’13) will take place in Cambridge (the one near Boston) on Friday April 26th.  It will include long talks by  Daron Acemoglu, Yiling Chen, Matthew Jackson, and (recent Turing Award winner) Silvio Micali, as well as short talks and posters (for which you may send an email to caec13@seas.harvard.edu by Thursday April 11, 2013.)

Read Full Post »

The economic Turing test

Over a recent lunch, Boris Bukh suggested the following variant of the Turing test: a human and a computer play a game (in the game-theoretic sense). A judge who is observing only their moves must decide with confidence who is the human and who is the computer. The premise is that the human would play irrationally (he’s just a random person off the street), and the computer’s goal is to also play irrationally to avoid detection.

An interesting aspect of the economic Turing test is that it’s not clear whether it’s harder to be the judge or the computer (programmer). On the one hand, how do you program a computer to act irrationally? On the other hand, if a judge has a set of rules that identify humanly irrational behavior (e.g., he read the papers of Kahneman and Tversky), couldn’t the programmer implement the same set of rules?

I found this idea especially appealing because I sometimes think of rationality as a possible key to artificial intelligence. Indeed, one can argue that rationality is perceived as (a sufficient condition for) intelligence, and therefore a multiagent system that is based on game-theoretic principles will be perceived as intelligent, so in that sense game theory can enable classic artificial intelligence (albeit on the multiagent level). The economic Turing test turns this argument on its head: to be indistinguishable from a human the computer must strive to be irrational.

The field of AI has so far failed to deliver human-level intelligence; is this the dawn of the age of artificial stupidity?

Read Full Post »