NYCE 2: CS and Econ

The Second Annual New York Computer Science and Economics Day (NYCE 2009) will be on November 9th at the NY Academy of Sciences, and organized by Robert Kleinberg and Eva Tardos. They are soliciting speakers for the rump session, deadline is Oct 12. Tentative agenda: Michael Kearns (9 AM), Shahar Dobzinski (10 AM), Jennifer Rexford (11:30 AM), Rump Session (2:30 PM) and Larry Blume (4 PM).

Cross Product Research

I remember Hal's talk about "combinatorial innovation", that is, once you have certain basic ingredients for innovation, people find ways to combine them and generate an explosion of ideas and products in a very short time. That is the good part. I want to talk about an annoyance that is similar in spirit that I often confront.

I refer to Cross Product Research, that is, research that is the result of mixing ingredients. The formula is (recent hot topic) X (known problem formulations) X (favorite math tools and methods) X (some data, experiments, and good writing) \rightarrow (Paper Submission). I may have left out certain adjectives and some dimensions may be superfluous, but this formula begets longer titles, more papers and destroys trees.

Algorithm Aware

If some researcher asks you, what is your area of research, and you say Algorithms, most times they look at you without comprehension. So, in a discussion, the crowd wondered, what is Algorithms Research? I mean, every researcher -- in CS and beyond -- thinks they design Algorithms, so poetically:

An Algorithm is an Algorithm,
Databasers do Algorithms, Networkers do Algorithms,
Visioners do Algorithms, So do Machine Learners I suppose.
But a SODA Algorithm is an Algorithm and was always an Algorithm.

So the crowd meandered with hypotheses of what is Algorithms Research and Sudipto Guha supplied, "You know you do Algorithms Research when you are aware." (paraphrased)

Travel to the Bay Area

Typically when I travel to the Bay Area, I feel like a horse with blinders, my sights focused on meetings and what needs to be accomplished. Last week, I looked around more than usual and had some interesting conversations:

• Moshe Babaioff: Structure of subdominant strategies and their usefulness.
  
• Aranyak Mehta: That is so paperware!
• Ashish Goel: What will be an open architecture for auction platforms? (like OpenFlow is for IP routing).
  
• Lars Backstrom: Say people vote only when their votes matter. Dynamics in small committees.
• Sivakumar: What is the rate of growth of information consumption?
• Ravi Kumar: PTAS for Jacard median. Interesting stuff. Ravi has been giving plenary talks, we need to see the slides, we need to see the slides....
• Jasson Schrock: new YouTube skins.
• Kunal Talwar: Is budget-limited auction design a foundational research problem of interest?

And many others. In some cases, I am still continuing the conversations in my head. :)

Friday Evening Play

It was a long week, with situations that force a definition upon you and you have to remember to bust out. For friday evening, I went to Brooklyn which is forgiving of tired researchers and veering artists. Far from the prying Manhattan, at the dilapidated but charming Harvey Theater on the left, I watched Actress Juliette Binoche and Choreographer Akram Khan from very close, as they tried out each others' trades some. Juliette is not a graceful dancer, but she has a great presence reminiscent of her film roles; Akram excels when he reaches back to his boyhood and acts out 2 roles, but the plot is from the left field. All this storytelling takes away from the joy of the dance, but like seasoned researchers who can do with 6 what others do in 10 filled camera-ready pages, the artists kept it short and did not grate. Dinner at Stonehome, crispy Chicken and warm Chocolate Cake, got me to the weekend.

Visit to NYU Stern

I visited NYU Stern to give a talk. Putting disparate people together pays off. I met with faculty from OR, Data Mining, Stats, Econ, and Social and behavior sciences working in a single division. So, during the day, I discussed many different topics and saw how much the faculty had learned from each other being colleagues who make hiring, teaching, mentoring and funding decisions together, with social lunches too.

• Vasant Dhar: Transparency and speed of exchanges auctions in ARCA, SEC's REG NMS spec for getting the best price across all the exchanges, 30 ms that each platform gives itself to fill an order before it accesses other exchanges and the resulting dynamics.
  
• Foster Provost: Identifying people with brand affinity using friends in social networks and using the user-target feature in ad exchanges to market to such users across web properties. Level of trust among ad networks, brand advertisers, exchanges etc.
  
• Anindya Ghose: Confs that bring marketing and CS folks together such as CIST09. Bidders in ad auctions seems to care about competitors: at what granularity should they care (aggregate or individual)?
  
• Arun: A practical economics puzzle: the medium coffee costs more per ounce than small or large coffee at the Stern Cafeteria, why? We also talked about teaching math to Business majors, and the cute Manga Guide to Calculus. He is a clever man: during my talk on sponsored search, I spoke about bananas, and he asked, "Organic or Sponsored"?
• Alex Tuzhilin: He was an expert witness on a click fraud analysis case, and his report is public. Click report audit and verification is sometimes outsourced to third party companies such as ClickForensics. ACM conf on Recommender Systems will be in NY. Exactly how much did NetFlix gain with a paltry $1M competition? :)
• Lunch at Lupa, Dinner at Tabla. oolala.
• Sonny. Understanding organizational and human capital in services. Scrapping resumes from LinkedIn. How to infer hierarchies from communications among people.
• Yannis Bakos. Classic Econ discussions. Tradeoff between finding better matches vs cost of search, eg in the "house around the lake" model (on a circle, rather than on a line as in Hot dog vendors model). Bundling and what happens when marginal cost tends to zero. During my talk, Yannis asked how to bundle ads, something in general worth thinking about.
• Sinan Aral: Information flow in organizations. He asked what is on my mind these days, and I answered: I would like to design a reservations/futures marketplace for ads.
• Students: I met Nikolay, Jing, Eyal, Xiaohan, Shawn, Bebe, Ning, and others. I dont see their homepages.
• Post-Talk: Over wine and cheese, Panos, a thoughtful blogger, quickly converged on the second part of a proof I left out in my talk. Btw, check out his citation tracker.
  
• Dinner: All dinner conversations should be so scintillating! Roy Radner asked two questions: Why should Economists care about Internet Ads? What is the total value of Internet Ads to the society? I can only answer these over dinner. :) Foster Provost, clearly very deep into thinking about Internet Ads, challenged me about the standard notion that Internet has made ads measurable: in particular, if you ignore direct marketing, there are more offline measures and measurements of brands ads than online.
  

Coda: It is amazing how much Hal Varian populates conversations even 3000+ miles away.

Labs vs Academia Contd

I enjoyed the discussion on labs vs academia at Boyd, Michael, Katz and Mihai, and comments therein. I more easily understand Mihai's take than say Boyd's, perhaps because I am closer to Mihai in research interests and geographic preference. An interesting mental exercise is to ask, have truly fundamental results come from Academia (more than Labs) and have truly great applied algorithmic results come from Corporate Labs (more than Academia)? I would reckon world does not divide nicely that way. It will also be great to get a balanced view on grants. Is it an all consuming monster of a process or is there a way to be selective and reap the benefits?

Timing

A friend asked what I seek. Such a question is usually an opportunity to make something of that moment in the conversation, with a few words you can spin it to wild place, veer towards an adventure when the bar closes and the music turns to the Blues or simply subdue the moment, get the check and take taxis home. My answer is this: I have always wanted to live in the moment, not bear the burden of the past or the future, just be. That is difficult.

I was reminded of us when I read this NY Times piece on a Tajik storeroom worker who finds fame singing Bollywood songs with uncanny precision. "Mr. Allaberiyev’s family understood that he had a gift; by the age of 7 or 8, he could commit songs to memory and repeat them with eerie accuracy, after watching a movie twice. But he was born at the wrong time, or in the wrong place. By his early teens, he was picking cotton for a pittance in pay." Having all your belongings in a satchel, asking the reporters for replacement teeth and carrying around the red backstage pass with the words "artist" like people who leave ski passes on their jackets long after their brush with the snow, reminded me of what I seek.

WWW2010

WWW2010 "is a premier conference on web research" and has an interesting mix of theory, systems, software and practice (yes, the last three are different!). Ashish Goel, Ramakrishnan Srikant and I are helping with the Internet Monetization area, but you will see other theory folks on the various committees. Deadline is Oct 26.

Here is a blog entry by Danah Boyd from Microsoft Research that discusses Corporate Research vs Academia, with a particular point of view. The comments are interesting as well, and surprisingly one-sided.

Back to Art

One of the conversations at the CS and Econ meeting at Cornell reminded me that I need to post this. Video of a fantastic Artist Kevork Mourad, a visual atist who paints to music. His Gilgamesh rendition is on Youtube and is a treat to watch in person.

CS and Econ at Cornell: PS

Well, I am back and what did I think of the entire meeting? I met many new thinkers, in particular the ones in Economics, and hope to be in touch with them more. And I became less self-conscious about using "endogenize" and "exogenize", ie., Economics-speak. Finally, game theory and economics may be in vogue in CS confs, and people have told me that it is NOT right to accept papers just because they are on a vogue topic. My notes will hopefully convince people that it is NOT right to reject papers just because they are on a vogue topic. Fads apart, there is a helluvalot we need to learn, understand, and exploit in Economics and CS.

ps: Someone asked, "What CS Systems should not be exposed to market mechanisms?"

pps: Many thanks to the organizing committee of Larry, David, Jon, Eva and Ehud. They found ways to ask right questions and stimulate CS vs Econ research debates during the sessions. Also, Cornell's facilities were excellent.

CS and Econ at Cornell: Day II

Continuing.....

• Avrim Blum spoke about potential games, and cost of uncertainty. His talk reminded you the CS art of problem formulation which I think of as one of our contributions to the world. Yoav Shahom argued against addiction to equilibrium. He seemed like one who can research or play or combine both and he did. He spoke about equilibrium of strategies in computational games and demo-ed his winning software for pool! Bill Sandholm spoke about population games where the number of players is large and evolutionary game theory kicks in. David Parkes spoke about cases like dynamic auctions where you can't go for strategyproof and optimality directly, but proposed starting with heuristic mechanisms and tweaking them. Dirk Bergemann spoke about modeling and tradeoff of targeting. Michael Schwarz spoke about finding stable matches in which people are matched to the median partners in utility. Fun stuff with the stable matching lattice.
  
• Lance Fortnow gave a quintessential theory talk, formulating computational time creatively as discounted utility in two party games and other similar problems. Costas Daskalakis gave a great talk, neatly laying out the hardness of general games against zero-sum games and sketched out some special cases which may be easier. His talk drew a lot of discussion from Economics, mainly wondering what the hardness of these models meant for real behavior of agents. PPAD met milk price at Walmart.

David Easley, Joan Feigenbaum, Joe Halpern and H. Peyton Young led a panel at the end. Joan formulated a cogent argument for studying game theory on graphs, that IP networks at infrastructure level comprise real economic agents that strategize. Joe Halpern did the much needed job of extended the scope of the discussion to include logic and languages, and to real systems issues like asynchrony, fault tolerance, verifying correctness, etc. Kindred spirit there. David Easley emphasized that we need to understand market design better, with the example of his experience with the Spanish Option Exchange design. It is hard to experiment with market design in some worlds like financial exchanges, seemingly less so in Internet ads world. Peyton Young too emphasized how we need to understand designing markets, in particular, with limited information.

CS and Econ at Cornell: Day I

At Cornell, I got to hear a constellation of Economists and Computer Scientists lay out their research.

• Larry Blume started it with, let's: Understand better (a) how markets work and should be designed, (b) limitations of Bayesian view, and (c) effects of underlying networks.
  
• Sampath Kannan while playing a funding person, still made a scientific argument. He succinctly argued that it was the most natural possible for CS and Econ to bond, both studying human-generated artefacts with Math tools. Historically there should have been more bandwidth in their intersection, and in the future, who knows, may be even a world not of CS or not of Econ in the future, but one of CSECON or ECONCS.
• Rakesh Vohra did a phenomenal job of representing half a century of interleaved CS and ECON developments, and this in a talk crackling with humor, wit and sharp mind. Later, talking to him, I realized that he can look at the messy world and with a few slices, get to the core and relate it to other worlds.When possible, get him to give a talk or even better, just talk with him.
  
• Stephen Morris talked about weakening common knowledge assumptions, and in classic Economics style, showed how revenue is affected when information about others decreases. Jason Hartline spoke exceedingly clearly and with conviction on approximations in mechanism design. He gave nice examples of replacing complex exact designs by simple approximate ones. John Ledyard spoke about Exchanges -- with a cute example of CO_2 exchange eg -- and about fairness, his was the talk I should have given had I been an Economist. Jeff Mackie-Mason spoke about mechanisms to induce online behavior, and how it is difficult to explain humans' altruistic behavior on the web. Michael Kearns spoke about his real-life game experiments. It is a lot of work what they do, and the community should thank them for running these detailed, well-thought out experiments. They should make the data available for the community to analyze. He briefly mentioned how players quickly developed signaling strategies, but not many seemed to have looked for others' signals! Gun Sirer and Jennifer Rexford spoke about CS systems and networking perspectives.
• Meetings or not, I still had to work, so I had to miss a talk or two.
  

Quick Life Notes

Coffee is indispensible, and the struggles we go through to get the right coffee is always a story. For me, addicted to American coffee in the morning, it took 2 weeks in Rome to converge to a suitable substitute and order "Due Cafe Americano, Lungo". Mallesh Pai points me to this article by Ariel Rubenstein on the price of coffee when you want a variant, and the associated socio-economic experiments.

Btw, I realized: when someone offers and asks, "Mint?", you should take it. :)

MFCS Retro

MFCS admirably clings to the notion that Mathematical Foundations of Computer Science means all theory, from algorithms and complexity to logic, computability and semantics. Here are some notes from the 34th MFCS:

• There were three plenary invited talks titled Stochastic Process Creation (Javier Esparaza) Stochastic Games (Chatterjee, Henzinger and Horn) and Stochastic Data Streams (me), resp. So, we know "stochastic" is in. One of the other plenary talks was by Peter Widmayer who spoke about sorting of train car, from simple Knuthian to far beyond, and ended with a beautiful picture of Lausanne trainyard triage. Combinatorial algorithmicists should grab his slides.
  
• People like Ratislav Královič of Cromenius Univ, Ivona Bezáková of Rochester Inst, and many others remind me there is a pipeline of talented TCS researchers from Slovakia and I got to see parts of the pipeline.
  
• Discussions with Wim Martens, Javier Esparaza and Sven Schewe centered on (a) Is FOCS and STOC representative of logic/automata/semantics community? (b) How to improve the quality of journal refereeing? and (c) Should we encourage publishing fewer papers. Of course in Europe, one discusses US vs Europe. Let me add a joke yesterday over lunch when I observed that a journal submission should be rejected with a note, "Please publish this first in a conf to get some feedback from the community."
  
• On a social note, I learned that there is a special insurance you need to buy if you go up mountains, lest you need helicopter and other extraordinary emergency services. Hm... Also, Pierre McKenzie told me about 24 speed folding mountain bikes, and how he bicycled to the conf from Poland. Sounded cool.