This past week, a large part of our group attended ACM EC up in Palo Alto. EC is the top Algorithmic Game Theory conference, and has been getting stronger and stronger each year. I was on the PC this year, and I definitely saw very strong papers not making the cut (to my dismay)… In fact, one of the big discussions at the business meeting of the conference was how to handle the growth of the community.
Finding about about the increasingly difficult acceptance standards, I was even happier that our group was so well-represented. We had four papers on a variety of topics, from privacy to scheduling to equilibrium computation. I’ll give them a little plug here before talking about some of my highlights from the conference…
- Routing and staffing when servers are strategic. Ragavendran Gopalakrishnan, Sherwin Doroudi, Amy Ward and Adam Wierman
- Simple Approximate Equilibria in Large Games. Yakov Babichenko, Siddharth Barman and Ron Peretz
- Buying Private Data without Verification. Arpita Ghosh, Katrina Ligett, Aaron Roth and Grant Schoenebeck
- The Empirical Implications of Privacy‐Aware Choice. Rachel Cummings, Federico Echenique and Adam Wierman
Happily for me, these were all scheduled on the same day. Given my newborn at home, I was quite happy I could manage to make the trip < 24 hours!
But, that means that I only got a limited view of the papers at the conference, unfortunately. I was still really impressed, and found almost every talk I attended extremely interesting.
Two papers that really struck me as intriguing, and which I’ll definitely be spending a lot more time looking at in detail, were the following.
- Cournot Competition in Networked Markets. Kostas Bimpikis, Ehsani Shayan and Rahmi Ilkilic.
Kostas apologized at the beginning of his talk that he was a last-minute stand-in for presenting, but he really didn’t need to. The talk was excellent — and I think the topic is something that is likely to be one of the next “big things” in the community.
We increasingly understand efficiency and computational issues in single, isolated markets very well, but such situations are few and far between in the real world. Almost always, markets are interconnected, and firms can strategically interact across markets for a variety of strategic reasons.
The CS community has been looking at this recently in the context of Bertrand competition, but I think that Cournot competition is often the more natural model. For example, it is certainly the more natural model in the context of electricity markets — and we have begun to study them with that motivation.
In any case, over the last few months, I’ve heard of at least five different CS groups start to think about these issues, so I’m excited to see the work that will come out in the coming years!
- Differentially Private and Incentive Compatible Recommendation System for Adoption of Network Goods. Kevin He and Xiaosheng Mu.
This talk was about an issue that I hadn’t thought about before, but that I immediately got intrigued by. The motivating example they started with was a “social” netflix. While it’s not so popular now, Netflix does have its own social network and if you use it, you get recommendations based partly on your friends ratings. This can lead to more successful recommendations, but it can also be a privacy concern. Maybe the recommendations you receive reveal something sensitive about your friends…
You may not worry about this in the context of movies. But, instead think of the case where you are building an academic reputation system (like citeUlike) where we all rate each others’ papers, and then we receive recommendations about which papers we should read and which we should avoid. Here, there may definitely be sensitive information revealed by the ratings that people may not want to reveal.
So, in such systems there is a natural, fundamental tradeoff between the efficiency of the recommendations and the privacy of the individuals. This begs the question of what are the fundamental limits of such systems, and how one should go about designing them… This paper is a nice first step towards these questions!
Apart from these two papers, I also really enjoyed Kevin Leyton-Brown‘s keynote. It had a vague title, “Pragmatic Algorithmic Game Theory,” so I didn’t know what to expect going in, but it turned out to be pushing nearly the same perspective that we follow in our research in RSRG.
Basically, he argued that while the theoretical side of AGT is certainly important, fundamental, and all that, the field is at a point now where it is possible to start connecting with more practical challenges. More specifically, his message was that this goal can be accomplished by being much more conscious of the data and empirical side of the applications, and I completely agree. It’s not that we should move away from the theoretical questions, but instead we pushed the idea that we now have the tools to move away from worst-case type questions and instead approach questions where the instances are parametrized in more empirical ways.
Of course, I was particularly happy to hear that given our push toward connecting revealed preference theory, a very empirical part of economics theory, to core AGT questions related to computational complexity and privacy.