Summer School on Market Design

XIII Summer School organized by the Department of Economics of the University of Trento (Italy) will be during 25 June - 06 July 2012, on “Market Design: Theory and Pragmatics”. Students, post-docs and visitors who are interested will get more information about the application process here; the deadline is March 17.

On Sadness and Other Topics

I am reminded of The Prophet who prepares to leave and people gather around him, ask him to address the issues of human condition. Anyway, here is something on human condition.

• What of sadness? In Congo, they have delestage (literally power cut, in french): Older children eat today, young one tomorrow, some days all children eat and no adults, some days only adults. "If today we eat, tomorrow we'll drink tea".
• What of struggle? Children in the picture cross the Ciberang River clinging to the remaining side of a collapsed bridge to get to their school.
• What of love? I am reminded of an old quote, "Love is the moment when a man who needs shave becomes the man with a beard." Let me add, "And Love is also the moment when a man with a beard becomes the man who needs a shave".

Google Updates

Google announced on Thursday in their earnings call that: "In addition to the $5 billion run rate for display, Google reported that its DoubleClick ad exchange had 130% growth in spending year-over-year. One driver of display growth was marketer interest in buying for specific audience categories -- such as hybrid-car buyers or adventure travelers -- which the technology now can target, according to SVP-Advertising Susan Wojcicki." So AdX is growing.

I have been playing with interactive graphing built into Google search. I enjoy typing in functions like sin(1/x)+x^2 = in the box and playing with the graph, zooming, reading off values, etc. (sometimes you see a little message at the bottom, if the function is not plotted correctly and an explanation why).

EPFL visit

I managed to make it to EPFL, Lausanne, a few months ago. EPFL has a great collection of researchers in communication/information theory, and it is always a pleasure to visit:

• I discussed with Jean-Pierre Hubaux and Nevena Vratonjic about privacy and security in online advertising. They have a paper that studies the following question. ISPs can (a) cooperate with ad networks with direct traffic as usual, or (b) modify the traffic on the fly such that can divert part of the online advertising revenue for themselves. If this diversion becomes material, ad networks can secure the connection so ISPs can not divert the traffic. The paper studies the game theory between ISPs and ad networks and figures out the various equilibria.
• I discussed the problem of identifying the same people/nodes/personas in two social networks, this is a popular problem to data mining community with no principled approach I know. Mathias (Matt) Grossglauser and Pedram Pedarsani take an interesting approach to this problem. Say there is an underlying network is an instance of G(n,p), the standard random graph. Consider G1 and G2, driving from the this instance by sampling each edge with prob s. Then, given only G1 and G2, can one retrieve the mapping of identical nodes? This is a coding theoretic way to approach the problem. The authors show that under certain conditions dependent on n,p and s, one can retrieve the entire mapping!

Matt, who has returned to EPFL after several years heading Nokia Research, was a great host and we were two geeks in the sauna, sweating, but still discussing puzzles. Over one dinner, I talked with Patrick Thiran and Martin Vetterli about compressed sensing and other problems. Over the other dinner, I discussed with the highly energetic Christoph Koch (who has meandered through research in logic to XML and databases) about theory and databases, and eventually debated the issue: does a research community like theory or databases tend to largely agree each year on how to rank the star candidates on the job market? And what does it mean, when the rank orders differ. I also had a great discussion with Katerina Argyraki about some streaming network measurement questions I should really think about. Some of the discussions veered to good natured debate whether international conferences had a strong US vs EU bias.

Lausanne has Art. One of my favorite ``museums'' in the world is collection de l'Art Brut at Lausanne, but I didnt get a chance to visit. Matt and I had a magic moment at Fondation de l'Hermitage when we stumbled onto a room full of crates marked Van Gogh, Bonnard, Vallotton etc. (obviously crates destined to deliver the masterpieces!). Finally, since the last time I was at Lausanne, the campus has a new building, the incredible, innovative Rolex Learning Center: a great fluid, undulating space that naturally finds sectional uses without explicit interior walls.

India: Good, Bad, and Beyond

There is the good in India: wireless access is a great success story, despite the general inefficiency, nearly everyone has cellphones, they work, and they are affordable (even for data, I pay $10 for 4GB).

Then, there is the bad: the various forms that need to be filled out drive people and clerks to panic, and ultimately to a statis: what goes in these ambiguous fields, do the signatures match precisely, is the form/check/currency torn/creased somewhere, and so on.

Finally, there is the beyond bad: people wall their houses, office buildings, and keep things clean within their ``personal'' space, but discard trash just over the walls on to the ``public'' space. Often neighbors swap trash onto each others' public spaces! Forget microloans, I would love to see an economically viable model to collect and process trash in India.

In pictures: food with many dishes; "how to calculate your mortgage payment" by a local newspaper; two trees help announce the theory day.

India Theory Day

Satya Lokam, Ravi Kannan and others at MSR hosted the India Theory Day at Bangalore. It is a little spooky to fly several hours, drive to some office, see Kunal Talwar, George Varghese, Deeparnab Chakrabarty, Amit Deshpande, and others from a more immediate context in my working mind.

Eva Tardos spoke about the Generalized Second Price (GSP) auction. She reviewed by now well-known analyses of GSP that PoS=1 and PoA is like 1.6 or 1.2 depending. Her talk focused on the role of uncertainty. In particular, assuming separability, bidder i in position j will get expected value \alpha_i \beta_j v_i where \alpha_i depends on bidder, \beta_j on the position. While bidder i knows value v_i, they dont know the other parameters, and even if they know the distribution of these parameters, they dont know the instantiation of the click probability in any particular auction. In presence of this uncertainty, GSP does not have efficient Nash equilibrium, and the result was that PoA is bounded by like 2.93. The O(1) PoA result is easy to motivate by considering the shading strategy of letting bid of i be v_i/2 (the best bound needs a more detailed strategy). Likewise, this strategy also has direct no-regret learning interpretation, and similar results follow for revenue as well under MHR assumption like Myerson. This research is much-needed, GSP is widely used and it is remarkable how little we know about it.

Other speakers: Mike Saks spoke about his very nice results on finding LIS in sampling and streaming models; Amit Kumar gave a near encyclopedic discussion of approximate clustering; Alas, I missed Nikhil Bansal's talk on randomized rounding; Nisheeth Vishnoi gave a short, rapid talk on closest vector problems with preprocessing, his brain seemingly whirring even as he stated complicated results.

On the earlier day, I gave a general introductory talk on ad auctions and met several researchers from other areas (Venkat: talked about difficulties of localizing even with compass and accelerometer, Kumaran: translating Indian languages; Sriram: language verification). Over dinner, we debated what was the great intellectutal work of 20th century: Einstein's, Turing's or Watson-Crick's? Deeparnab stretched with the observation that Einstein's work will be relevant even if there were non-carbon lifeforms!

NII Shonan Meeting: Social

Socially, Japan is awesome. I took an evening off to look for Yasuda's new sushi place in Tokyo with my friend Luigi. Alas, I failed (btw Jun Tarui may have found the true one), but an arbitrary couple we stopped to ask about good restaurants in the neighborhood, walked us around to show us several restaurants for us to pick (we protested we didn't want to interrupt their evening plans, they said, "We ate a large meal, we need to walk it off anyway!").

What is International travel without movies on the airplane? I watched Egyptian movie, Al Kebar: this was reminiscent of 70's bollywood, men and women, friends and love, caught across the lines of law. The consensus in US is that Egypt has the potential to be a top 10 Economy within the next 10 years, this movie is just the past.

Finally, sundries: a superb calligraphic exhibition at the National Art Center in Tokyo; fruits, individually sweatered; and, a symmetric gallery of chopsticks.

NII Shonan Meeting: Work

Suresh has blogged extensively about the workshop on large scale distributed computing, so I have only \eps to add. Btw, talk abstracts and slides can be found here.

At high level, there were three models discussed: streaming (S); mapreduce/DHTs based computing (M); distributed, continuous monitoring (DCM). New variations of these models continue to be identified, and while probably algorithmic techniques for S are probably the most developed, increasingly more results are appearing in M and DCM. Eventually, it will be nice to see some general reductions and relationships between these models. There were several database researchers at the meeting.

About specific problems: Qin Zhang talked about tight bounds for various frequency moments in DCM closing out several open problems; Amr Abbadi rose to the occasion to engage the theoretician by posing a simple social network based variants of heavy hitters that is challenging; Suresh spoke about a nice formulation of distributed learning. Minos Garofalakis talked about some nifty prediction schemes so that individual, distributed sensors need to hardly send any bits to the center, and yet the center can track sophisticated functions on the sensor readings. I liked Amr's comment how DCM is related to view maintenance in databases.