Archive for September, 2013

AGT lecture videos and notes

I’m teaching my algorithmic game theory course at Stanford this quarter, and this time around I’m posting lecture videos and notes.  The videos are a static shot of my blackboard lectures, not MOOC-style videos.

The course home page is here.  Week 1 videos and notes, covering several motivating examples and some mechanism design basics, are already available.  This week (Week 2) we’ll prove the correspondence between monotone and implementable allocation rules in single-parameter environments, and introduce algorithmic mechanism design via Knapsack auctions.

The ten-week course has roughly four weeks of lectures on mechanism design, three weeks on the inefficiency of equilibria (e.g., the price of anarchy), and three weeks on algorithms for and the complexity of learning and computing equilibria. Periodically, I’ll post updates on the course content in this space.  I would be very happy to receive comments, corrections, and criticisms on the course organization and content.

Read Full Post »

My father is a professor (of physics), my only brother is (approximately) a professor (of math), my uncle and my cousin are professors (of law), and my grandfather was the index case. So it never occurred to me to do anything other than be a professor — it’s just the family trade. But this choice is not obvious at all, and students and postdocs sometimes ask me what it’s like to be a young faculty member; these questions are fueled by discussions on the blogosphere about academia vs. industry, and the success industry labs like Microsoft Research have had in recruiting researchers away from seemingly desirable faculty positions. So I thought it would be interesting to write down some thoughts from my incredibly specific early-career-faculty viewpoint.

Professors sometimes use words like “crazy” and “all-consuming” to describe their first few years as faculty members. I don’t think it has to be that way. I guess I work 50-55 hours a week, which is definitely more intense than the average job, but hardly qualifies for “all-consuming”. So how do I spend my time? Here is a rough breakdown.


The 25% time I devote to teaching is interesting: On the one hand it’s quite low, because I co-taught all of my courses so far; on the other hand it stays constant, because so far I have taught a different course each semester. Spending a lot of time on getting funding was one of the things I was worried about when I was on the job market, but so far it hasn’t been a big deal (probably because I haven’t done enough to get funding).

“Other” includes many things. For example: organizing the summer school on algorithmic economics, COMSOC’14, and a local seminar; co-editing an upcoming book; editing SIGecom Exchanges; a couple of journal editorial positions; program committees and internal committees such as PhD admissions; reviews, outreach, and, well, blogging. What I discovered about this “other” category is that most of the time is spent on getting people to do stuff: give talks, serve on program committees, write book chapters, write letters for Exchanges, do reviews, etc. In return, people ask you to do even more stuff! In any case, many of these things are actually quite fun (so far) so the fact that “other” is on the rise is not bad in and of itself, but it does come at the expense of research time, which went down from 60% to 40%. The more worrying trend, though, is how the time I devote to research is divided between thinking about research and talking about research:


Research is arguably the most fun part of the job; it’s almost always fun to think about research, and it’s often fun to talk about research. Yet Matt Welsh complains that “only about 10% of [academic meetings] have any tangible outcomes”, and (assuming most meetings professors have are research meetings), I think this graph may be the reason why. For a research meeting to have tangible outcomes, I feel I need to spend at least one hour thinking about the problem offline for every hour I spend talking about it. Otherwise, typically one of two things happens: Either my collaborators have made progress and then I struggle to keep up, or they haven’t made progress and then I have little to contribute — leading to a scarcity of tangible outcomes in both cases. My research meetings are still mostly productive and fun, but to keep them that way I really need to reverse this trend of increasing talking/thinking ratio. And I also just realized that, if I believe my graphs — a big “if” — I’m currently spending only a measly 12% of my time thinking about research.

Now for the good news: What do I love about the job? Many things, but let me single out the top two. First, I love being able to spend time at work writing this blog post. But it’s more than just “academic freedom”: I love that I can spend time at work writing this blog post and feel that I’m actually working. What’s amazing about being a professor is that there are so many ways to make an impact, and you can choose whichever ones fit your talents and mood.

Second, I love advising. Matt Welsh writes:

In an academic research group, the professor defines the technical scope of the group as well as mentors and guides the graduate students. The big difference here [in Google] is that I don’t consider the folks on my team to be my “apprentices” as a professor would with graduate students. Indeed, most people on my team are much better software engineers than I am, and I lean on them heavily to do the really hard work of building solid, reliable software. My job is to shield the engineers on my team from distractions, and support them so they can be successful.

The word “apprentices” sounds medieval, and there’s nothing wrong with that — it’s actually spot on (although I prefer to leave my sword at home). The 4-6 year apprenticeship called “grad school”, at its best, builds a unique relationship between the student and advisor, which can inspire the advisor and the student alike. When my students’ papers are accepted, I am as happy as I was when my first papers were accepted. And long after I stopped feeling excited or anxious about my own talks, I find that I am tense (in a good way) before theirs. Some of the nicest unexpected moments are when I identify something of myself in my students (for example, in their writing or speaking).

In conclusion: Yes, it’s really fun to be a professor. In fact, almost as fun as being a grad student.

Read Full Post »

WINE’13 updates

The following WINE’13 information is now available on the conference website:

Read Full Post »

New York Computer Science and Economics Day (NYCE) will be held on November 1st at the Simons Foundation in New York City. The goal of NYCE Day is to bring together researchers in New York and surrounding areas who are interested in problems at the intersection of economics and computation.  Our invited speakers this year are Nicole Immorlica, Panos Ipeirotis, Christos Papadimitriou, and Rakesh Vohra. We will have several shorter talks and posters as well. More details about the program can be found on the website: https://sites.google.com/site/nycsecon2013/home

If you plan to attend the workshop please register online before October 15th at https://sites.google.com/site/nycsecon2013/registration. Please note that the venue for NYCE 2013 has a limited space, and on-site registration may only be available on a (limited) first-come first-served basis.

The deadline for submissions for short talks and posters is October 8th. Topics of interest to the NYCE community include (but are not limited to) the economics of Internet activity such as search, user-generated content, or social networks; the economics of Internet advertising and marketing; the design and analysis of electronic markets; algorithmic game theory; mechanism design; and other subfields of algorithmic economics.  We welcome posters and short talks on theoretical, modeling, algorithmic, and empirical work. You can submit your abstract via our submission form at: https://sites.google.com/site/nycsecon2013/posters-and-short-presentations

Read Full Post »

The 2014 WWW conference will take place in Seoul on April 7-11, 2014.  As usual, one of the tracks is devoted to “Internet Economics and Monetization” and the submission deadline is October 8th (Abstract due by October 1st).

Read Full Post »

Usually I like to pontificate about mundane things like journals and the job market, but for once I’d like to soar above these trivialities and write about welfare and justice. Computer scientists like to talk about social welfare, but usually we mean it in an extremely restricted sense: the sum of players’ utilities. I think we like this interpretation because we love to optimize stuff.

But economists take a much broader view of social welfare. Most recently, one of the reviews (likely by an economist) of my CACM article on cake cutting included the following comment:

The author seems to believe that there are only two ways of evaluating social welfare, either utilitarian or egalitarian. Although both of these criteria are certainly interesting, it is far from being true that there are no other ways of making such evaluations. It is also not true, contrarily to what author asserts, that “the very thought of social welfare” requires an “interpersonal comparisons of value”. The Pareto criterion certainly is free of such comparisons and it says something about social welfare. Its conjunction with the no envy criterion, which is also free of such comparisons, provides another example, which is satisfactory from the fairness viewpoint as well.

My response amounted to an argumentum ad auctoritatem: Many CS papers use “welfare” or “social welfare” in the same way, including a recent CACM review article. I was actually trying to be extra careful by using the term utilitarian social welfare. An EC’12 reviewer raised similar objections to this paper, which is why the introduction of the camera-ready version includes a long (for a conference paper) historical discussion.

These reviewers are right, of course, in asking for a broader perspective. But perhaps part of the objection to (utilitarian) social welfare is also philosophical. Check out, for example, the article on distributive justice in the Stanford Encyclopedia of Philosophy. It turns out that from a philosopher’s point of view, even economists are narrow-minded:

Economists defending some form of welfarism normally state the explicit functional form, while philosophers often avoid this formality, concentrating on developing their theories in answer to two questions: 1) the question of what has intrinsic value, and 2) the question of what actions or policies would maximize the intrinsic value.

Strangely enough, though, “most philosophical activity has concentrated on a variant known as utilitarianism”, which is exactly the notion mentioned above. The Stanford article’s section that deals with welfare-based principles is essentially a critique (more like an indictment) of this approach:

For instance, some people may have a preference that the members of some minority racial group have less material benefits. Under utilitarian theories, in their classical form, this preference or interest counts like any other in determining the best distribution. Hence, if racial preferences are widespread and are not outweighed by the minority’s contrary preferences (perhaps because the minority is relatively few in number compared to the majority), utilitarianism will recommend an inegalitarian distribution based on race if there is not some other utility-maximizing alternative on offer. […] Utilitarians may believe that even more welfare in the long run can be achieved by re-educating the majority so that racist preferences weaken or disappear over time, leading to a more harmonious and happier world. However, the utilitarian must supply an account of why racist or sexist preferences should be discouraged if the same level of total long term utility could be achieved by encouraging the less powerful to be content with a lower position.

But similar questions get even murkier under alternative principles of distributive justice. A seemingly popular principle, equality of opportunities, is advocated by “those who believe that we can show equal concern, respect, or treatment of people without them having the same material goods and services, so long as they have equal economic opportunities.” From this viewpoint, it has been argued that discrimination based on gender or race is bad because people have no control over these parameters, and it is immoral to structure society in a way that one’s draw in this “natural lottery” can profoundly affect one’s opportunities in life. Going one step further, people also cannot control which families they are born into; should we let such factors affect a person’s chances in life? And taking this reasoning to the limit, we can observe that people cannot control the talents with which they are born. Where does one draw the line?

Putting my two cents (worth maybe two Israeli liras in this case) in, it seems to me that in simple domains, undesirable mechanisms like random serial dictatorship (see, e.g., Eric Budish’s position paper in Exchanges) satisfy the principle of equality of opportunities; going back to the review snippet above, RSD is also ex-post Pareto efficient. Perhaps maximizing the sum of utilities, when possible, is not that bad after all?

I’ll conclude with an ambitious thought. It seems (from ongoing work with Nicolas Christin and Anupam Datta at CMU) that research on distributive justice says little about how to implement and verify those lofty ideals. Is this a challenge for algorithmic philosophy?

Read Full Post »