New Book : Algorithmic Game Theory

I recently received my "desk copy" of the new book Algorithmic Game Theory, edited by Nisan, Roughgarden, Tardos, and Vazirani.

While I haven't read it cover-to-cover yet, I'm very impressed by the book. It's taken a large area with a fairly short history, and broken it up into reasonable-sized chunks each written by an expert, with most chunks covering a new and active research area. For example, Michael Kearns writes about Graphical Games, Christos Papadimitriou explains the complexity of finding Nash equilibria, Jon Kleinberg discusses cascading behavior in networks and the corresponding economic issues, Ramesh Johari and David Parkes and Joan Feigenbaum and so many others have chapters on their specialties, and so on. Overall I count 45 contributors! The result is a solid tome that really combines breadth and depth to create a resource that I assume works well for people working in the area and is certainly useful for an outsider trying to look in and see what's going on. There are also exercises in some chapters; it could certainly be used as a textbook.

I'd like to see other books of this form, built up by a coalition of experts to cover emerging areas. You do lose something with this approach -- for example, many concepts are defined multiple times in various chapters, and while the authors have made an effort pointing out relations among chapters, you don't really have the sense of coherence you get from most textbooks or books about research written by a single author. On the other hand, you do get a much broader coverage of topics than you'd probably see from a single-author textbook, and I assume that it was easier to spread the workload among authors. It's not clear to me any single author (or group of 3-4) could have put something like this together in any reasonable amount of time. Kudos to the editors (and authors).

What other topics could benefit from a treatment like this?

Consulting

I enjoy consulting, for several reasons:

1. It fulfills a need to be more directly relevant to the real world.
2. It gives me a chance to work with different sets of people.
3. It allows me to learn new things and exercise skills that I don't necessarily use as a professor.
4. It pays well.

I’ve consulted for research labs, startups, and larger companies, doing research, development, and expert witness work. I’ve been consulting since graduate school, and it’s an activity I’d recommend for most graduate students, once they’re comfortable in their research. I view the flexibility of being able to do research while still being able to take on consulting projects as one of the major benefits of being a professor.

Although I do know several algorithmists that consult at times, my impression is that the consulting culture is surprisingly small in computer science theory, even among algorithmists, and that it is much more prevalent in networking and EE theory. (The exceptional case I can recall is around the time of Akamai, where once it seemed like a sure bet, a lot of theorists hopped on the bandwagon for at least a short stint.) I generally hear people talk about consulting much more at networking and EE conferences than I do at theory conferences. Maybe it's just impolite to talk about it. Or maybe theorists don't consult much because most don’t have the skills people are looking for in consultants. Or maybe most theorists just aren’t that interested in consulting, and that's part of why they ended up being theorists.

Do you consult? (I'm particularly curious -- do complexity theorists consult?) If not, why not? Are my impressions about theory+consulting just way off base?

Academic jobs this season?

I’ve already mentioned Harvard is doing a junior faculty search – although not specifically for a theorist. Any other faculty hiring announcements, either broad-based or theory specific? Or any new postdoc announcements worth repeating here?

Service to the Academic Community: Goals?

Except for the rare award (like the ACM-SIGACT Distingushed Service Award or Aaron D. Wyner Distinguished Service Award), our academic community does not appear to especially value service to the community. Research dominates our mindset. At the same time, on the whole, pleasantly the community seems quite conscientious about giving back. Somehow, conferences get run, workshops get organized, journal papers get reviewed, the NSF panels meet and make their bizarre decisions, and so on.

Strangely, I can't think of any time where a "philosophy of service" has been explained to me -- in graduate school or as a new faculty member, from the theory CS community or from my institution that employs me. Thinking about this, I find it rather odd. Surely, someone should be suggesting what's an appropriate level of time and effort to put into service, and where these efforts might best be applied.

(There is some advice I've seen in books for new faculty members. For example, Robert Boice's book Advice for New Faculty Memberssuggests that new faculty essentially spend as little time as possible on service activities, and make early service opportunities as self-serving as self-benefitting as possible. I roughly agree, but we should make this part of a well-reasoned philosophy of service -- the community should protect it's youngest members and help them flourish.)

I think this topic is ripe for community discussion, and some resulting general guidelines. People should have some guidelines as to what's expected -- what's usual and what's exceptional community service. (And to be clear, here I mean service to the scientific community at large; university service, for example, is separate.)

I'll start with two basic, over-arching questions. (I have more specific ones in mind, but I'll save that for the next post.)

1. How much time should be spent on academic service activities? [My take -- 1/8 time, or at least one hour a day on average, for senior faculty. Less for junior faculty starting out, but increasing steadily toward that. Ostensibly, people in research labs should also be at 1/8 service time -- anyone know of any policies on that?]
2. Should we be better rewarding service, and if so, how?

Brief FOCS Update

I went to FOCS for the day of tutorials. Great talks by all of the speakers (Terence Tao, Dan Boneh, and Dan Spielman) -- and it seemed to me like a very large attendance for the tutorials. I understand slides and such will be put on the appropriate FOCS page soon, so rather than give detailed comments, I'll provide a pointer when they're up.

Also, I wanted to give a big thanks to the local arrangements team of Philip Klein, Anna Lysyanskaya, and Claire Mathieu, as well as everyone assisting them, since I know from experience that local arrangements is a thankless job. I found today's setup wonderful. The room at Brown was great -- perfect size, fine acoustics. Lots of food and refreshments were put out, and to save the conference money, it wasn't catered, but the local arrangements team brought stuff in themselves. (I arrived early and saw Anna driving up with a car full of goodies!) That's the kind of extra dedication that helps keep conferences affordable for everyone, at the expense of the personal time of the people who have to make it all run. So thanks again!

The FOCS setup has reminded me that I wanted to do a series of posts on the theme of service, something I'll try to get to this week.

Harvard Computer Science Hiring

We're eagerly looking for candidates in CS in all areas at the junior level (i.e., assistant profs). (Be sure to tell your non-theory friends as well.) Here's the ad for the search.

Harry Lewis's book, Excellence Without a Soul

Since my colleague Harry Lewis is kind enough to stop by and post comments from time to time, I would be remiss not to encourage everyone with an interest in the education of college students -- in the broad sense of whether universities are and how universities should be teaching students to become adults -- to pick up his book Excellence Without a Soul: How a Great University Forgot Education (also now available in paperback as well). I highly recommend the book, and plan to give it to my daughters to read when they're teenagers so they're better prepared for the college experience.

The book takes a stark look at the directions of modern college education, painting a picture of increasing directionlessness at the leading research universities, using Harvard and Harry's experience as Dean of Harvard college as a backdrop. Whether you agree with it or not -- and I have to admit I found a strong resonance with most of the issues in the book -- it is definite food for thought, well-reasoned and well-argued through and through.

There are two very small points of criticism I can make with the book. The first is that while the book sheds light on a number of challenging problems, it frustratingly offers little advice in the way of solutions. However, I think this was quite intentional. Indeed, one of the points in the book is that for many of these problems, what is needed isn't a "solution", but leadership, discussion, and the building of a consensus within the university.

The second nitpick is that one issue raised repeatedly in the book is the invasion of the consumer culture in education. Students pay a great deal for an education, particularly at private institutions, and they expect to get what they pay for; Harry argues forcefully that this trend is not good for the education of students. It would seem to me that this should be another compelling reason why Harvard shouldn't charge for tuition, as it might lessen the "I paid for this" attitude of many students (and parents), but perhaps Harry believes that even if there was no tuition, the consumer attitude would remain.

Broadening the Teaching of Theory

Offhand, I can think the following primary "types" of computer science classes:

1. Classes specialized for graduate students in a subfield (e.g., theory, or usually the next level down, e.g. cryptography, pseudorandomness).
2. Classes for graduate students in CS.
3. Classes specialized for undergraduate CS majors.
4. Classes for undergraduates primarily in other sciences.
5. Classes for general, non-science undergraduates.

I think most CS professors naturally gravitate to teaches types 1 and 3 -- classes in their area of specialization. I think, as a community, there is generally at least some effort by theorists to broaden the scope of some at least classes to types 2 and 4. Certainly I try to encourage non-CS majors into my undergraduate algorithms class -- what scientist shouldn't be learning to think algorithmically? -- and to get non-theory graduate students to take my randomized algorithms and algorithms at the end of the wire courses. I suspect, though, as a community, we could be doing more. While personally theory seems less isolated within CS today to me than it did say a decade ago, there still seems to be plenty of bridges left to be built.

Perhaps more challenging is classes of type 5 -- classes for non-scientists. The question of how to design a science distribution requirement course for non-scientists is not specific to computer science, but in CS it perhaps especially challenging. Programming is often taken to be off-limits, since how much worthwhile programming can be taught to people who have never seen a computer program before? And theory seems to require too much math. Plus there is the age-old question of how to make it all relevant to non-scientists.

Harry Lewis co-designed a course, Bits, which I think is a great example of what's possible, and is the course I wish I could have designed, if I wasn't so busy teaching my regular classes. I enjoy this first paragraph from the course description:

This is a course about information for students who are not technically or mathematically oriented. It aims to explain the dramatic increase in the amount of information that is being communicated and stored, and the consequences for society of that increase in capacity.We are on the cusp of a revolution, potentially as consequential as the invention of printing or the replacement of animals by steam engines as the vehicles of transportation.The course aims to equip those who will determining policies, whether as legislators, corporate leaders, or ordinary citizens in their multiple roles, with an awareness of the choices that lie only a short time ahead of us.

I am also strongly biased in that Harry followed my advice, with much of the technical meat in the beginning of the course covering basic information theory, specifically compression and coding. (Note: I emphasize that Harry followed my advice, not that he took my advice. As far as I know, he always planned to structure the course this way, and it's just happenstance that his take on what was worthwhile matched mine. I'm pleased nonetheless.)

The course is an interesting mix of science, technology, and policy. The lectures are now apparently freely available online now that the course is over for those who want to see it. Someday, perhaps I'll get to design a course like this. I'd be curious to hear from others what other examples there are for CS-based courses with non-trivial technical content meant for non-science majors. (Jon Kleinberg's course new course comes to mind, but it really seems to be type 4, built for scientists, including mathematically oriented economists and sociologists.)

The simplest insertion/deletion channel

The simplest binary insertion/deletion channel that I can think of is the following: with probability p, each bit independently results in two copies of itself. This is a special case of a subclass of channels that I have dubbed sticky channels, which are like sticky keyboards: each symbol can result in a random number of copies of that symbol.

Sticky channels have the nice property that contiguous blocks of (resp 1s) at the input correspond to contiguous blocks of 0s (resp 1s) at the output. This property makes sticky channels easier than more general insertion/deletion channels.

I've just had a paper on sticky channels accepted to Transactions on Information Theory; here's a link to a preprint. The main result is that for that simplest channel above, I can numerically obtain very tight bounds on the channel capacity. But of course I'd still like to know -- is there a simple formula that gives the capacity as a function of p? And is there are simple and efficient coding scheme that nearly reaches the capacity?

The Importance of Recommendation Letters

If there is one piece of career-gamesmanship advice I would give to anyone, especially undergraduates eventually looking to get into graduate school or beginning PhDs who will be eventually looking for jobs, it would be to think carefully well in advance about where you plan to get letters of recommendation from.

For graduate school, your letters are probably the most important deciding factor for whether you'll get accepted or not. For job searches, good letters won't really get you the job, but you'll need great letters to even get your foot in the door for an interview.

Yes, great work will trump everything (if you do really great work, you'll get the great letters). But I've seen numerous students do less well than they should have because they didn't think well enough in advance about this part of the game.

For undergraduates thinking about graduate school, have you formed a close working relationship with one or more faculty members? (This can be done by doing research with them, writing a thesis with them as an advisor, being a teaching assistant for them, etc.) Lots of students will have exceptional grades and test scores; we want to know about you as an individual, and your capacity for research. Letters are the best way for us to get this information. Particularly if you go to a smaller school or a school with a smaller CS department, you may want to try to find a way to do a summer internship with a "bigger name" person -- a letter from such a person will likely make the difference between getting in and not for many places.

For graduate students thinking about jobs, who besides your advisor is going to write you a letter? We expect your advisor to say that you're wonderful; we want to hear from less biased sources. (Many students fall into the trap of working almost exclusively with their advisor -- good in the short-term, not in the long-term.) What other faculty have you worked at your institution? Have you worked with anyone from another institution? Have you thought about doing a summer internship -- which can be worthwhile just to get a good letter! It's important to work with multiple people, not just your advisor, so we can see multiple letters explaining and confirming why you and your work are so outstanding.

I thought about this after a discussion on the complexity blog about graduate school detoured slightly into the subject of letters for jobs (in particular, check Paul Beame's insightful comment #41).

By the time you get to tenure, letters are still important, but ostensibly you have less control about where the letters come from. The same general advice seems to apply, though -- great work trumps all, but working with or having some shared experience with many colleagues, including more senior ones, can be key to career advancement.

Set Your Own Price for Music

Tangentially related to my previous post on why Harvard should be free (but you pay later through donations), via the Machinist I've learned that Radiohead (some "music group" -- I'm old and out of touch...) is putting their new album online and letting people choose what to pay to download the album here. (More information for actual music fans is available from the Machinist in a follow-up.) This sounds like an interesting experiment, and I'm very curious to see how it works out for them.

Somehow it made me think, will the pick and play model of iTunes ever make it to universities? Imagine selecting your own collection of courses for your undergraduate or graduate degree, without being limited to your actual physical university; you could take say Kleinberg's Structure of Information Networks, Roughgarden's Introduction to Algorithmic Game Theory, Demaine's Geometric Folding Algorithms, and so on... of course, an appropriate payment mechanism would have to be designed, but the possibilities are exciting and frightening at the same time...

Cyber-Enabled Discovery and Innovation Call

The CDI call was finally published last Friday at http://www.nsf.gov/pubs/2007/nsf07603/nsf07603.htm. There is related information here. The time scale for moving on CDI is rather short; letters of intent are required, with a first due date of November 30. But CDI looks to be the ITR of next few years, so lets get lots of theory-related proposals in...