Artwalk 09

Details here.

Price Negotiations for Ads

In Applied Algorithms Research, you look at a system up close, a problem pops out that baffles standard formulations, and you need to turn it around in your head a few times.

In an example, two sets of parties negotiate in a two-sided market over multiple rounds; a market runner observes, and wishes to make negotiations more efficient without significantly modifying the system. How should the market runner propose prices, ie., provide pricing guidance, to help the negotiations along? Google's PrintAds system is a marketplace for ads that appear in print in newspapers and magazines where the market runner faces this question, and there are some game-theoretic nuances. Here is a paper (joint work with Adam Juda and Ashish Rastogi) that describes the issues and solutions, an attempt at summarizing our insights from 1.5 years of running the system.

In Applied Research, you have a mission. We had one, we wanted to help save the newspaper ad business. Well, the mission remains.

NY Area Theory Day 09

NY area theory day was held at Columbia Univ on May 22, 09. I gave a talk on 3 problems in internet ads, here is the pdf of my talk. The talk describes a recent result with Jon Feldman, Aranyak Mehta, and Vahab Mirrokni that I am excited about in which we improve upon the 1-1/e bound for online stochastic bipartite matching. The 1-1/e bound is a monster in online algorithms, and anytime you are able and break past it, there is a story. Baruch Schieber who introduced me, dug up an old bio of mine, and pointed out how I "resented" my work. I dont know if he realized that the mike he used to introduce me was connected to the unit I held in my hand and I could have pulled the plug anytime. :)

The day was great. There were three talks before me. Dana Moshkovitz and Mark Braverman gave incredibly cogent talks on difficult material. Craig Gentry gave a talk on fully homomorphic encryption scheme with a lot of applications. During drinks later, people were still talking about it, wondering if it can all be implemented.

ps: As many pointed out, I really need some pictures in my talk. That will happen soon.

We'll see the Big Bang again

Here is an evening. You hear Mort talk. He is a pioneer of electronic music from 60's, an early contributor to CalArts, and an incessant musical experimenter. You hear him say that if he'd do it all again, he would be an Economics major. Not because as an artist (or a scientist even) you need to know how to manage your image and make money, but because, in order to understand the world as it is, the people as they are, you have to understand Commerce. This has been true through the times, commerce has moulded Arts. Now with barrier to Arts low (many can shoot films and upload, far too many can write and publish, and far, far too many can mix music and dj) and attention splintered into niches, commerce seems everywhere in Arts. This is not a bad thing. As one of the artists remarked, we are in a primordial state, waiting for the moment a new notion of currency is invented that will have as much impact on the world as the original invention of coins had. Someone said we will see the Big Bang again and the conversation turned to Marshall McLuhan (medium is the message), Angela Davis, and the state of Iceland. Some time during the evening, Sun had set, lights had come on, and when I reached for my wine glass, it was cold. Some evenings are like that.

Hal

Hal Varian has the ability to start a discussion off with simple calculations and before you know it, they start yielding important implications and you are discovering deep things. His writeup on Online Ad Auctions (based on the WINE08 talk) to appear in Am. Economic Review is an example. There are simple upper and lower bounds and before you know, they give a way to estimate the value advertisers get from sponsored search, which is nifty. One has to distil the discussion to its simplest and no harder, and still communicate a technical nugget the readers/audience can take away. To do that, one needs to really understand the math and the mechanisms. It is fun to watch!

ps: In a different vein, here is a video in which Hal does community service and explains basics of ad auctions.

pps: Some time ago, Hal was the speaker over a dinner I attended. It is difficult to give these talks to people distracted after a long day by the food and the drinks. You have to abstract a novel concept and still be technical so the audience can walk away with enough to reason about a nugget later. He spoke about his idea of the "combinatorial innovation" in detail.

NY Notes

Notes from a few NY weekends:

• A car pulls over and the guy asks me how to get to Desbrosses St. I tell him 1 block west and 2 down. He thanks me and then says, "I notice you are wearing glasses, I sell glasses, call me if you need any", and gives me his card.
  
• A van pulls over in the village and this guy asks me in Italian accent, "I have to catch a flight to Naples, how do I get to FDR?". I tell him. He thanks me and just as he is about to drive away, says "Hey, you dress sharp, I got 3 Armani suits in the back, brand new, I will give them to you, try them on. See, here is my Italian passport and flight ticket, I need to leave now. Dont have time to return or sell them. You want them? 3 for price of 1."
  
• I went on a cruise on the Hudson river in the historic John J. Harvey fireboat. Like several people did, this boat too rushed to the site on Sept 11, and did what it could, in its case, pump gallons of water. Far too aged, it is still plying the Hudson.
  
• Manolo Celi, a film maker friend, had his short film in the Tribeca Film Festival. His work was shown with some fantastic pieces (Pg 31 of this program, under Mixed Feelings), a mixture of techniques and budgets. Oil Change shook me up, Shimasani was a camerawork heaven and Manolo's Nueva York, was truly engaging in its inherent humanness. Kate Hudson got heavyweights to show up in this charming tale of desiring things badly.
  
• Real estate market in NY is inventive. Prices are now called either Pre-Lehmann or post. :)
• Weekends without food, Nah. New pizza on the block is Kesté (in Neopolitan slang, it means, "this is it"). You can see an interesting review in Village Voice (Fork on the Road column) or read the encyclopedic pizza blog.
  

WAA09: Wkshp on Ad Auctions

The Fifth Workshop on Ad Auctions will be held at Stanford Univ with the EC conference (deadline May 22). I liked the 2008 edition, it felt like a true workshop with discussions of raw results, not like a conf with presentations on polished publications. The organizers say:

Accepted papers will be made available through the workshop site. However, we emphasize that the workshop does not have a formal proceedings. We do not wish to preclude later publication in a conference and/or journal of papers in this workshop.

Crypto Honors

We need more crypto blogs. No, I haven't found a new cult, but I have been shown a sliver of crypto in a recent project, and am slightly more aware.

Moti Yung will be the IACR distinguished lecturer for 2010 (IACR Distinguished Lectures have been awarded by IACR since 1994 to people who have made important contributions to cryptology research.), and joins a superb list. Also, Michael Rabin becomes an IACR Fellow in a program that has been around since 2004.

Playing Teams

In football on the left (watch in mute!), one guy --- James Harrison --- runs with the ball and the Steelers throw their bodies to protect him and clear his path. Similarly, when an aircraft carrier moves, several destroyers and cruisers run safety and provide cover by being smaller targets. In research, do we play the team game, without involving self destruction?

Suffering

Yoram Singer visited NY and asked, why Indian culture accepts suffering as a given, in movies and beyond, sometimes even aspiring for it. Dont know, but to understand anything in life, you need to watch John Lee Hooker on the left, start slow, strum, suffer in a silky voice, and simmer your Saturday down.

Stanford White

Stanford White, an American architect who built Washington Square Arch and other structures says:

Two men set off to build a dream; ....
For the one the dream was finished when
the drawings were done. He laid down his pen.
The other made the dream complete; with bricks and mortar and concrete

That is the sign of last 1800's in NY when there was excitement of a new city bursting out, and you could not tell Architects and Engineers apart. Now the city feels like a zone of renovations, and Architects and Engineers make appointments to see each other. That is where my thoughts are on a Saturday morning even as the day is trying to make up its mind, to rain or not to rain.

Network Economics Mtg in NY

NYU Stern Business School is running a meeting on network economics on May 8th. There are two psts on sponsored search that, among other things, look interesting. (Notice, there is a discussant for each talk!)

Stimulants in Academia and Research

Baseball manages to keep steroids steadily in the news. Analogists will ask, is there a steroids problem in academia? An article in NYer digs deeper into use of neuroenhancing drugs in schools. And further, like pro sports, is there steroids use (sans coffee) in the highest echelons of research? Away from sensationalism, here is a research question: should we not be prepared for Erdos-like prediction of aliens demanding Ramsey numbers, and for sake of humanity, invest in research on steriods for brains? The point is steroids for sports produces one record, some good moments for the fans, and large $s for TVs, but humans move on to anticipate the next record. Steroids for science on the other hand may have more lasting impact. No, I am not advocating steroids, or proposing we produce monster brains that would read the NYer without savoring it. Just wondering if there is a utility function here.