SIGecom

Like other SIGs, SIGecom has its notices: SIGecom exchanges, the recent edition is here. The back issues have an interesting collection of articles, mainly short summaries with pointers to longer articles. Also, Vince Conitzer does an interesting column on puzzles (for me, puzzles are the beats of a research area).

Rome: Digging Past the Past

In Switzerland, if you stand in a street corner, you see at least 3 clocks; in Rome, it is 3 obelisks, or may be fountains, or churches, or all of the above.

I have my favorite observations of Rome, ancient and modern. They may be wrong, but they are plausible and therefore good. The first is that Romans could scale buildings as much as they did because they used bricks, stone-based constructions would not have scaled, much as without steel-based constructions, modern cities will not be. The other is their modern metro, DC-like, plunges deep into the ground because they had to operate below the antique sites and their treasures. Even in the CS dept of La Sapienza, where WINE was held, a little digging hit ancient Rome and you can see the remains where the stairs end.

The US coffee market that has scaled coffee from regular (8 oz), to tall, grande, venti (20 oz) and beyond, may want to scale the other way with their espresso. How about a regular (US) and micro (Italy, as someone at WINE said, call them "espre")? Luigi Laura said of Espresso in Monaco: "they have Italian machines, Italian people, almost Italian water, but still can't make an Espresso".

ps: Not Rome, but Parma: Must read nytimes note of travel guide to Parma, or is it book review of The Charterhouse of Parma from 1839?

WINE 2009

The WINE conf as usual slipped into the fading days of 2009. For me, it started with Andrei Broder's tutorial on Sunday. (Alas, I missed Nikhil's and Tim's tutorials on Saturday). At the basic level, there is a "mapping":
(user queries, context, content of web pages) \rightarrow (suitable ads or creatives),that is a challenge in Internet Ads, and Andrei's tutorial was a flourishing, flowing view of this mapping, mainly as a Information Retrieval (IR) task. Some specific topics beyond the tf-idf like measures and precision-recall curves included (a) looking at ads -- creatives/URLs/bid phrases -- as documents for IR, (b) using taxonomy to capture context for content match, (c) graphical ad selection by looking at this mapping as a recommendation function, (d) bandit variations with taxonomy for new ads, and (e) classification, in particular for rare queries, across multiple languages. These ideas are published in a slew of papers in WWW, KDD, SIGIR confs. Andrei's audience showed an yearning for novelty, and he indulged them with describing challenges in mobile ads, ads over IPTV, VDP newspapers etc. He mentioned the Webscope program to share data with academia, including some data on mapped (query, ad) pairs.

On Monday, I gave a talk on my AdX model for Ad exchanges. It is difficult to communicate how the many decisions you make every week ultimately determines the overall system that audience get to see, and users get to play. I chose to talk about 3 technical results, one each on auction, online optimization and crypto, so people get a little bit of new things in their area of expertise, and a little peek into new things in other areas. I had a bunch of questions over the following two days.

• Why not sell bulk impressions? AdX trades on individual impressions. More sophisticated instruments -- like bulk impressions, futures, derivatives, whatever -- may get traded on top of this primitive.
  
• Why do we need AdX, and why will traders come to AdX? Publishers come for liquidity and better prices. Peyton Young, ever sharp, asked one question over dinner: what is the information that goes from AdX to ad networks. Advertisers come to AdX to potentially influence ad experience across multiple websites easily.
  
• Aren't there complex pathways from advertisers to AdX via multiple interacting ad networks? Yes. In some exchanges like RightMedia, these relationships are endogenized and leads to sophisticated graph problems to determine suitable bids for each impression. In the AdX model, these are exogenized so we can focus on the game theory between AdX and ad networks, or between AdXs.
• How to deal with currency changes? This is not a question of $s vs Euros, but as marketplaces get sophisticated, parties have many different payment schemes (pay per impressions, clicks, conversions, or pay flat fee or for bulk etc), these have to compiled down to per-impression bid in AdX, and this involves taking some statistical risk; it is a nice open problem how to manage this risk. Finally,
  
• Why do you work on AdX and why not work on exchanges in general instead of ad exchanges? It sounds silly, but I want to change the display ads business, and I think AdX will change the display ads business to make it more transparent, robust. In Applied Algorithms research, you have to believe in a goal beyond the theorems.
  

On Tuesday, Peyton Young gave a very interesting talk on adaptive learning rules in complex systems of agents. As an aside, he like many Economists is a swingman, being able to talk macro, micro, math, policy and everything else with insight. His talk was a series of "experiments" in which agents have a state comprising a benchmark of what they did and an aspiration function, and based on choosing to experiment, can change their benchmark. In one version, agents experiment based on mood in an interactive trial and error way. In yet another version, agents have logit response to neighbors' actions (a la some of Larry Blume's work). He showed the connection between these rules and well-known games from weakly acyclic games to interdependent games and spatial potential games. In each case, under some mild conditions, the Nash equilibrium is in some amount of experimentation. I really liked the spirit of this talk, and would have liked to see more, perhaps connection to the bandit literature.

Games or Fun

I heard this boy (5 yrs old perhaps, running around the waiting room) tell his mom with candor: "I can't be quiet". There is sometime stunning about playfulness laid out straight. In that spirit, the FUN conference has submissions due Jan 15. This is the conference that makes research out of fun ("game theory" has so much gravitas than "fun theory"). So, go ahead, make your day, indulge and submit a paper. FUN 2010 will take place at Ischia Island (Naples, Italy), from June 2 to June 4, 2010.

Other upcoming deadlines: EC (Jan 11) held June 7--11 in Boston and ICALP (Feb 10) held July 5--12 in Bordeaux.

Discovering Arad

Ron Arad is a great industrial designer (I know, I know, his name sounds like a PODC researcher). His work appeared in MoMA two months ago as Ron Arad: No Discipline. Check out the site for his wild structures and creativity. He also did the VIP lounge design at Art Basel last week in Miami. Truth in Blogging: I own one of his pieces.

Nearest Neighbors

We have a dictionary D of vectors to be preprocessed, and a query vector q. We need to find nearest neighbor of q in D. Distance d(u,v) is the Hamming distance but any position i in which u and v differ can not differ by more than k (|u[i]-v[i]| \leq k). We can think of this as L_{\leq k,1} distance where L_{a,b} means you apply "a" operator to each dimension and "b" operator over the ensuing results. Hamming distance is L_{\infty,1}, standard L_1 is L_{1,1}. Any pointers welcome. Btw, for those who care, the string matching problem with this distance can be solved in O(nk polylog (m)) time.

Compressing Many

We now know how to compress individual strings, down to the various notions of optimal entropy inherent in Lempel-Ziv to Burrows-Wheeler methods. But what is the theory of compressing a set S of strings, ie, what are optimal compression methods and suitable notions of entropy? I can imagine approaches based on (i) models for the set of strings, (ii) grammar based compression, (iii) converting S into a tree, or (iv) concatenating the individual strings in some order to reduce to the single string problem, etc., but I am curious about the optimal entropy.

(Quasi) Proportional Mechanisms

Say you have a slot and multiple bids b_i's. We can assign it proportional to the bids, b_i/sum_i b_i. In a nice paper, Johari and Tsitsiklis showed that even in presence of strategic bidders, the total utility to the bidders is no worse than 3/4 of the maximum possible utility for proportional allocation. Interestingly, not much is known about analyses of revenue from such mechanisms. Uri Nadav visited for summer and studied quasi-proportional allocations where the slot is assigned proportional to f(b_i)/sum_i f(b_i), for some f. These allocations turn out to have interesting revenue properties (even without resorting to reserve prices like optimal revenue auctions do, and without prior knowledge of value distributions). Based on prior work of Uri, we could also prove the existence of unique Nash equilibria of such allocations. The paper is here. I was sorta surprised these mechanisms have not been characterized totally by now because they seem so basic, but our paper also leaves open a few analyses.

Italian Travel Fun

Travel to Italy should really be about food, friends and Fabriano on the left (making paper since 1264 AD). But it was all about flying.

I don't mean just the angst of Alitalia (the security announcements were muffled, the remote for the entertainment system on the Airbus craft was a challenge. I watched movies: Star Trek (playing the trick of projecting back in time with the characters), a documentary about Apollo flights (a great quote: "a small step for Neil, but a giant step for ..."), and when I returned, I did what I do every week, grab the New Yorker, flip to the end and read movie reviews, this time about "Up in the air".

ps: I referred to Facebook as the Masters of New Universe in a conversation.

ps: What will be a iPhone/Android application that many researchers will download and use that will network them socially for their research (CS, Sciences, Engg, etc)?