NYCE Day 2008 went very well, with over 100 attendees, great talks, and valuable discussion. Many thanks to the four plenary speakers — Costis, Asim, Susan, and Tuomas — and ten rump session speakers who came in from various NYC suburbs like Boston, Pittsburgh, and Palo Alto.

At dinner the night before,¹ the organizers agreed that we were nervous because we weren’t at all nervous. Karin and Renee from the New York Academy of Sciences had taken care of almost everything, leaving little for us to fret about. It turned out we were right to not worry and wrong to worry about not worrying: indeed Karin, Renee, and NYAS were absolutely fantastic, orchestrating every detail of the event flawlessly, from technology to catered breaks. The venue itself is gorgeous — a well laid-out space in a modern building in the World Trade Center complex with stunning views² and a number of nice touches, from an alcove with a computer station to check email to a subtle gradient in the wallpaper that slowly pixilates as your gaze moves from the center toward the side of the room. I came away incredibly impressed with NYAS and delighted to become a member.

Muthu provides an excellent summary of the event, divided into before and after lunch. Read that first and then come back here for my additional thoughts/notes:

1. Costis gave us mostly bad news. He summarized some of his award winning work with Christos Papadimitriou and Paul Goldberg proving that computing equilibrium behavior in almost any moderately complex game may be beyond the reach of our computers,³ let alone our brains. As a saying goes, “if your laptop can’t find it, then neither can the market” [attribution: Kamal Jain?]. Still, all may not be lost. These results, as is the nature of computational complexity results, say only that some games are extremely hard to solve, not all games or even most games. Since nature is not adversarial (Murphy’s Law aside), it may be the case that among games that arise in the real world that we care about, a number of them can be solved for equilibrium. The problem is defining what “realistic” means in this context: an almost impossibly fuzzy task. Costis did end with some positive results, showing that anonymous games can be solved efficiently. Anonymous games crop up in realistic situations, for example in analyzing traffic, where only the quantity of cars near you matters and not the identity of the drivers inside.




2. Asim described a sophisticated Bayesian model well suited for social network data that handles non-existant links — meaning the lack of connection between two people, by far the most common situation — much better than previous approaches. The approach is good for digging deeply into a small data set but at least for now has difficulty with moderately large amounts of data. (To get results in a reasonable amount of time, Asim had to down sample his already fairly modest sized corpus.) The talk didn’t help me overcome my bias that Bayesian methods ala UAI often don’t work well at Internet scales without modification.




3. Susan gave a fantastic and energetic talk. She advocates economic models of online advertising that include more sophisticated users, as opposed to typical models that assume users scan from the top of the page down in a precise sequence. She went further to claim that users may actually choose their search engine based on the quality of the ads. Personally, I’m a bit skeptical about that, though I do agree that there is an indirect effect: search engines with better paying ads can afford to buy more traffic and improve their algorithmic search more. Susan highlighted the enormous shift in mindset required between economic theory and practice when just computing the mean of a data stream can take weeks (though this is changing with tools like Hadoop that can bring such computations down to hours or minutes as Sebastien confirms).




4. Someone asked Tuomas why his expressive commerce company CombineNet uses first-price auctions instead of VCG pricing. He listed four of what he said were dozens of reasons on top of Rothkopf’s thirteen and Ausubel and Milgrom’s list. In fact he went further to say that as far as he knew no real auction anywhere in the world has ever used true VCG pricing for anything more complicated than selling a single good at a time.




5. For those not familiar, a rump session is open to anyone to speak briefly on any relevant topic. As it turns out, in part because brevity forces clarity, and in part because editorial filtering overweights mediocrity, the rump session is often the most interesting part of a conference. The “NYCE rump” session was no exception, with topics spanning ad auctions, reputation, Internet routing, and user generated content. Ivy Li proposed a clever scheme whereby eBay sellers are motivated to reward buyers for honest feedback. Sebastien presented work with Sihem and I on an expressive bidding language for online advertising with fast allocation and pricing algorithms, with the goal of moving the industry toward an open standard. Sampath Kannan on leave at NSF had encouraging news on the funding front, laying out his vision for CS theory funding with an explicit call for proposals at the boundary of CS and economics.




6. I think we did a good job of attracting a diversity of speakers and participants, with talks ranging from computational complexity to Bayesian models of social networks, with academia and industry represented, and with CS, economics, and business backgrounds represented.