FOCS Q's

Some questions that came up during discussions at FOCS.

• Increasingly, the graduating theory PhDs have longer list of publications than in the past. Why? Perhaps more accepted papers, more venues, more competition, increase in the avg number of authors per paper, more junior faculty, increased quality of students, ...
  
• Is there a robust future for algorithmic mechanism design research in FOCS/STOC? The answer seems to be YES, in EC, INFORMS, SODA, Economics/OR/Game Theory, ...

FOCS Trot

Here are some notes from FOCS 08.

Gagan Aggarwal and I gave a tutorial on the theory of sponsored search auctions. Gagan went first and did a fantastic job with the theory of single auctions. Usually people just describe the generalized second price mechanism. Instead, Gagan chose to start off with the Meyerson's pricing scheme and derived various mechanisms naturally. Her talk showed the triumph of Ecom+CS theory: a lot of understanding of single auctions. I went later and spoke about running many auctions (not repeated ones) and the role of budgets. Here, nice theory is far off. We mostly have partial and demi-partial results. I described some of these: 1,2,3,4. Time worked against me, and I skipped parts, in particular, discussing the case of multiple, related slots, beyond this. A feedback I particularly liked (paraphrasing), "I did not know there was so much to do in sponsored search auction theory."

About the conference: Nikhil has nice results with R. Kannan on computing market equilibria using some algebraic geometry (he asked, "Are prices irrational?" :) and showed that they were roots of polynomials with signs, and yes they were.) Mihai P. loomed large, and I felt an odd excitement about data structures during his talk on dynamic connectivity (graph connectivity when nodes are inserted/deleted with connections to geometric connectivity) and (data) structures (where he showed this picture of lower bounds). Milan Ruzic spoke about his results with Piotr Indyk on sparse recovery problems: his paper showed why work on this problem has become a battle of tables (mea definitely culpa)! Finally, Assaf appeared with transparencies and enacted a talk, like in the past, I gathered. Many talks ended with the last slide asking "What happens in the general case?". The audience in most cases did not ask questions, perhaps mentally resolving to go read the proceedings.

It was great to see Sudipto Guha in a position of great responsibility, feeling it and living up to it. Sincere thanks to all the organizers and the volunteers. The conf hotel is one of many escalators, Escher-esuqe stairs and few signs, but had great views from 33rd floor, the scene of the reception and the tutorials.

Billion dollar baby

I would love to see algorithms researchers attack problems (not only longstanding ones but also ones) that are urgent and timely. Beyond the million dollar problems, we may now care about how the US govt (and may be other govts around the world in slow motion) will (may be) buy troubled assets from financial companies for $$$ Billions. The question is to design a suitable auction. Lawrence Ausubel and Peter Cramton are two Economists who have a working paper addressing this problem: check out the pages 1 and 2, and this paper. There are issues here a Computer Scientist can address.

Election, Economics and The Homeless

Winter is setting in, the Homeless will try to find nooks and subway vents or simply submerge to the tunnels and may not be visible before the elections. For now, they have cardboard messages.

• Sen. Obama wants change. I want change too.
• I am Joe, Need $'s for the Six Pack.

Wall Street Journal sometimes shines. Their recent review referred to this hefty tome of a biography of Warren Buffett titled The Snowball by Alice Schroder as "Warren Peace".

In a meeting where US and Europe advertising folks came to brainstorm, I watched someone riff and accuse US of being directed by Economists, and Hal Varian retort, "What an enlightened country!". Plus one for me.

Banksy's Pets in NY

NY is a town of pets and Banksy, the British graffiti artist, tests NY's sense and sensibility with his pets store.

CS + Ecom + Nobel Prize

Alfred Nobel, "being of sound mind, has of his own free will...," set aside money for the prize we all know (click on the image for the nytimes article from 06). The Nobel prize for Economics went to Paul Krugman for his work on trade patterns and location of economic activity (in a modern version, Economicists study location of activity in ad auctions). His blog is an interesting read.

Of course the prize for Economics was not on Nobel's mind in 1890's when he wrote the will. It was later endowed by the Bank of Sweden. Should we do something similar for CS, that is, get a patron to endow a prize that can be selected and blessed by the Nobel process? I spoke with Kurt Mehlhorn about it a few months ago since the Max Planck Society may be a (unlikely) patron.

Roman Streets

My friend sends me this street view from Rome. It was his response to my Ode to Surprises. That is the thing about surprises, some are not even real in situ or not. My favorite of surprises is the T-shirt:

Ad Experiments

Playing with a system is a great way to get some insight and ultimately find the important problems to solve. In internet ad auctions, it is easy to experiment as an advertiser. For example, if you search for FOCS 2008 (or Piotr Indyk or Muthukrishnan or ..) in Google, you find variations of the following ad (run by one you can also find by searching for Ronitt):

FOCS 2008 Read an accepted paper, visit Krzysztof's website! csail.mit.edu

You can get valuable experience then looking at the clicks and impressions. The more difficult issue to get experience in being a publisher who shows ads from different sources. OpenX now gives an open source platform to play the publisher, wonder if it will be useful to the academic community for experimenting.

Doing Research when Ground Shifts Underneath

It is hard enough to do research when you are competing with other smart people or against the unyielding truth of the universe, but it is harder to do research when the ground underneath shifts even as one preps a research question. I was reminded of this when I heard a pst on how people purchase HDTVs: by a sequence of steps that includes searching the web, seeing and being influenced by display ads, going to product review and comparison sites, before finally buying it at a physical store. Being a curious person, I typed in "hdtv" into Google and I got the following (left), complete with product names, prices and no. of stores; if you click one of those links, you see the comparison (right). There goes that sequence. We researchers have to keep in mind when trying to formulate problems to model, study, and optimize that in some cases, the technology might change faster than we can write down the problem.

Working and Death

Working (or being a Salesman) can lead to death. I recalled this oldie (2005): Workingman's Death. Every once in a while I get frustrated with my sedentary job and want a job of physically challenging subsistence labor, and am continually obsessed with working in coal mines. Enjoy the videos.

NYCE++

David Pennock has a blog entry with some terrific technical insights and recollections of the NY area Computer Science and Economics (NYCE) mtg. Btw, it is time to acknowledge that the nice acronym was David's idea, to his credit.

In a related note, I was in Boston yesterday for brainstorming about internet ad business in a broad but closed forum. I tend to see more algorithmic problems than the ones of mechanism design or revenue/budget optimization problems that the theory CS community has attacked in Internet Ad Auctions, and it was reaffirmed at this meeting when I heard about the challenges that many companies face that are remarkably common. I will update the outline in my open problems writeup and the set of open problems some time.

Ode to Surprises

Cities --- jobs, relationships --- should be able to surprise you, and keep you thinking, but not guessing. I biked along the Hudson River park (Frying Pan on Pier 66 continues the horrible tradition of converting gritty industrial stuff into common place, but at least it is public and serves alcohol) and discovered in left to right order:First I thought it was cute what some child had done, the white chalk outlines of shadow that had long moved on, and then after the second, thought it was a pattern and looked for the artist, and when I found the chalk around the cart of the homeless man, guessed he was the artist. But something was not kosher, I mean the cart was from Bed, Bath and Beyond. Then the "homeless" with the expensive bike on the right brought it all together. The whole thing was an art show, with artists in situ.

Clothes

Some days clothes cling to you, you defy them and you are busting out with energy, ideas and things done. Other days, you cling to your clothes, and need them to define, defend and just carry you across. I felt like I was clinging to my clothes the last week when I taught, and somehow managed to do a three-hour lecture on randomized algorithms (closest pairs, polynomial identity testing, karp-rabin fingerprints, bloom filters, and part-way to primality testing).

NYCE: After Lunch

We selected a set of about 10 submissions for 5 min "rump session" presentations. This worked out phenomenally. There were

• Announcements: David, Chair of SIGecom, promoted the organization; Anindya announced CeDER, a center at NYU Stern; and Sampath discussed NSF program for funding the CS+Economics area (commenting on how CS was cool, Sampath, the effortless cross-bearer, said, "Being cool is a terrible cross to bear.")

• CS Style Theorems: Gagan Goel described results on using two additional bidders to get improved efficiency and revenue. Sebastien Lahaie described their results on using a tree to represent bids for display ads more expressively. Jacomo Corbo and Aaron Jaggard presented results related to network connectivity games.

• Ecom+Marketing Style Psts: Nikolay Archak, Christina Aperjis, Ivy Li, and Zhengzheng Pan presented large amount of work via broad stroke of ideas related to designing reputation scores , economics of user generated content and feedback-related mechanisms.

The final pst after a coffee break (in which we rectified the mistake from AM that Esther pointed out and this time provided the much-needed cookies to go with the coffee) was by Tuomas Sandholm. I have heard a lot about Tuomas's energy and he exceeded my estimates. He hit on all fronts: impact in practice (he described his company's work with expressive auctions for 40B worth of sourcing), in theory (mixing learning and complexity aspects with equal ease), in principle (addressing some questions of expressivity needed some angst in formulating the problem), and in philosophy (why VCG auctions are not practical, how expressive should auctions get). He showed he can do academic beauty and face reality, too. Very inspiring.

ps: Our sincere thanks to NYAS for helping us organize this event. Karin Pavese, my contact, is a scientist who has gone from corporate research to legistation (working with Sen. Lieberman), and is now leading the physical sciences effort at NYAS, with a heart for spreading the message and programs worldwide. Renee orchestrated the organization of the event, and was the reason why all 4 organizers were less tense than usual!

NY Area CS and E (NYCE) Day: Before Lunch

We brought some excitement to the Wall Street neighborhood on Friday, as researchers from CS, Economics, Business, and other areas stormed the offices of the NY Academy of Sciences --- not far from Wall Street --- for the NYCE day.



Costis went first and spoke about the complexity of finding (approx) equilibria. He started off our lethargic minds with a cute proof of Sperner's lemma about multicolored triangles on colored grids, and via Brouwer, established hardness of finding exact equilibria. I wonder what non-theoreticians thought of it when he constructed gadgets such that their equilibrium will perform arithmetic operations, like multiplication and addition, but for a theory CS person it is exciting when the structure clicks in to place.

Asim Ansari from Columbia U. was the next speaker. As you know, computer scientists go ahead and build things -- search engines, social networks etc., and modelers have to understand and explain their impact later. Asim, a Marketing professor who is an expert on Bayesian modeling, described in detail not only the basics of statistical modeling and the complexities of huge number of covariates even in static cases, but also its empirical application to a data set of artists sharing music.

Susan Athey went next. She is an Economist, and gave a really insightful overview of the complex games behind internet ads. Her talk was a hit with the audience. Some CS engineers built a platform for showing ads with search queries via an auction some 4+ years ago, and Economists now study the system, indeed find some resonance with principles they know, but discover nuances and novelties, and ultimately are excited to work on the system and change pieces! I asked Susan if she felt fundamentally new Economic theory would emerge, and she said yes, in particular since she is trying to model the search user's utilities as well. This has been the one line summary I give people for sometime now on why we in CS have been developing new methods for search ads for the past several years when Economists have studied auctions for 50+ years, so it is reassuring.

ps: Btw, there is a 4-party game (Problem 3) we CS people in ad auction systems have been working on for a few years now, perhaps now it will get more attention of the Economists. Also, Joan asked why a boutique shoe store and a mega shoe outlet will both compete for the same search query. As Susan said it is because users don't specify exactly what they are looking for, and just provide one or two search terms. I did not get to discuss with Joan that what this means is that the offline and online notions of competitors are very different.