Saturday, December 24, 2011

Rain Talk: Security Games

Vincent Conitzer --- who, as Ashish pointed out, is a PolyCS person of AI, Theory and Economics --- talked at the RAIN seminar a few weeks ago. I am familiar with Milind Tambe's work at USC on game theory + physical security. What is remarkable about that work is that it breaks beyond academia and they have been phenomenally successful in getting their solutions deployed in airports for screening, flights for scheduling air marshals, coast guard inspections and so on. I have always been keen on hearing the research issues involved behind theses achievements and Vincent precisely addressed that and did a great job.

In particular, he focused on security games and asked: what equilibrium should one select? How does one model temporal/information structure? What are suitable structures for utility functions? And, do algorithms scale? Security strategies can be observed by intruders and thus this setting can be formalized as a commitment game where one party goes first and commits to a strategy and the other picks a strategy after observing the commitment. Commitment can be to pure or mixed (stackelberg games) strategies and can be viewed as extensive-form games (finite or infinite resp). Vincent described how the optimal mixed strategy can be determined via a set of LPs, and this has nice properties (agrees with Nash in zero-sum, leader has at least as good a payoff as Nash, no equilibrium selection problems, etc). Then Vincent reviewed concepts of correlated equilibria and the associated LP. After that the talk focused on LP for optimal correlated strategy to commit. He also went through several examples of security and resource allocation games, discussed compact LP issues, and so on.

For finale, Vincent had a great slide, pointing out where CS was pushing the boundaries of game theory. It is an amoeba with many protusions. I say, invite Vincent to give a talk, ask him to show you.


Friday, December 23, 2011

Music in Two Parts

I can't make music, and have little if any music taste. Still, there is music I like. My fave is Woody Guthrie (who should simply be known as The Source). On the left is one of his children's songs. For grownup me, workin hard blues.

Likewise I have no ballet sense. Still, I decided to see The Nutcracker. Seeking something different, I went to the Oakland version, not SF or NY. The show may be light on Fouetté en tournant or tombé, but the production was tight, the Paramount theater was magnificient, costumes deserve a real review from a real local newspaper.

Monday, December 05, 2011

Research Sickness

In Zen and the Art of Motorcycle Maintenance: An Inquiry into Values, Phaedrus discusses several metaphors about the challenges to doing quality work, be it hiking mountains or maintaining motorcycle repair shops. I was out on the Ocean -- when I am in a self-analysis mode more than usual --- and noticed the following apt metphaor, for doing research: It is difficult to keep ones eyes focused on the horizon, with so many shifting waves that are close.

MassDAL 2.0

People ask me about my lab (MassDAL for Massive Data Analysis Lab) at Rutgers.

Here is the page as I set up 8+ years ago, so totally web 1.0. During that 1.0 phase, we worked on data streams and blog data analysis; Graham Cormode, a postdoc visitor, went on to greatness; 6 students finished their PhDs and 4 their MS, and you can see at that page where they are now; we collaborated with Narus, AT&T, Telcordia, Sprint, and of course the Govt.

Now, it is 2.0 time. I really should update the page to be more say html 5, and may be call it "BigDAL" in keeping with the fashion. :) Seriously though, we have new batch of students: Alex (Differential Privacy, Discrepancy theory), Brian (Communication graphs analysis), Darja (Ad auctions), Jinyun (Recommendations), Priya (Graph learning), and Qiang (Stochastic streams). We have a Fulbright Scholar visiting: Magdalena Punceva (p2p social networks). We have a spirited team of 7 students analyzing display ads (Aparna, Lavanya, Edan, Shyamsundar, Vinay and Vasisht). Students collaborate with Narus, Technicolor, Google, and of course the Govt. We work on social network analysis, internet ads, data streams, and theory.

Saturday, December 03, 2011

Data Challenges

Here are two recent ones:
  • Heritage data challenge, the goal is to "identify patients who will be admitted to a hospital within the next year, using historical claims data".
  • Nokia data challenge, the opportunity is to analyze mobile data. Registration deadline is Dec 7.

Back with Big Data Streams

I am slowly getting back to thinking about streams. In the past few years, new systems seem to have emerged that process streams.
  • See the upcoming meeting in NY on Twitter's Cassandra and open source platform Storm (for continuous queries, distributed query processing, fault tolerance)
  • Yahoo's S4 distributed stream platform which is a "general-purpose, distributed, scalable, partially fault-tolerant, pluggable platform that allows programmers to easily develop applications for processing continuous unbounded streams of data."