Archive for November, 2013

Today some 46 million turkeys will be devoured in the US. Any turkey is fair game, except for Popcorn (the duly elected Nationala_560x375 Thanksgiving Turkey) and Caramel, which were solemnly given a “full reprieve from cranberry sauce” by President Obama. Tomorrow, when they’re done with the turkeys, Americans (who are typically extremely nice on every other day of the year) will turn on each other, trampling anyone who stands in their way to get the best Black Friday deals.

For me, thanksgiving is a yearly reminder of how peculiar the American way can be even after 4+ years in the US. Therefore, as an alternative Thanksgiving celebration, I am happy to present the top five things that never cease to amaze me about the US (in no particular order):

  1. Credit history: Any long-term contract (renting an apartment, electricity or Internet connection, cellphone, etc.) requires a credit check, which determines whether you qualify as a good person (good credit history), a bad person (bad history), or a turkey (no history). The underlying logic is that you are a reliable person if you get into debt and then repay it. In contrast, if you never got into debt in your life and have lots of money in your savings account then you’re obviously a drug dealer. But here’s the catch 22-esque irony: To build your credit history you need a credit card, but to get a (usable) credit card you need credit history.
  2. Taxes: A crazy tax system is one where nobody has any idea what the rules are. A crazier tax system is one where the rules are nondeterministic. One of my favorite examples is this line from US tax form W-4: “Enter “1” for your spouse. But, you may choose to enter “-0-” if you are married and have either a working spouse or more than one job.”
  3. American Football: An average professional football game lasts 3 hours and 12 minutes. Average minutes of play: 11. Average time spent on replays: 17 minutes. Average number of commercials: more than 100. I’m not making this stuff up.
  4. US Congress: Enough said.
  5. Healthcare: The American healthcare system has turned inefficiency into an art form. Here’s what a typical visit to the hospital looks like. Upon arrival, you are quickly ushered into a private room. Now, let there be n nurses denoted 1,…,n such that for all i, nurse i+1 is more senior than nurse i (they have different titles like unlicensed assistive personnel, licensed vocational nurse, registered nurse, physician’s assistant, etc.); usually n is 4 or 5, but I’ve also witnessed n=6 at Children’s Hospital Boston. For i=1,…,n, nurse i enters the room and asks you the same questions asked by nurses 1,…,i-1 (nurse 1 usually also measures blood pressure or something). Nurse n is a nurse practitioner, and is essentially equivalent to a doctor; after asking the same questions asked by nurses 1,…,n-1, she writes a prescription, say for 10 pills. Incidentally, the pharmaceutical company distributes the pills in packs of 10. A naive person would think he can go to the pharmacy and procure a pack of 10 pills. But that would be too efficient; instead, a pharmacist must take the pills out of the box and carefully place 10 pills into a bag. It is widely understood that this medically indispensable process takes around an hour.

Ils sont fous ces Américains!

Read Full Post »

SigEcom Awards

The ACM Special Interest Group on Electronic Commerce has announced two new awards: the Test of Time Award and the SIGecom Doctoral Dissertation Award.

To be eligible (for the test of time award), a paper or series of papers must be on a topic related to the fields of electronic commerce or economics and computation and must have been published, in preliminary or final form, in a journal or conference proceedings at least ten years before the year of the award presentation.  The inaugural SIGecom Test of Time Award will be given in 2014


To be eligible (for the doctoral dissertation award), a dissertation must be on a topic related to the fields of electronic commerce or economics and computation and must have been defended successfully during the calendar year preceding the year of the award presentation.  The inaugural SIGecom Doctoral Dissertation Award will be given for dissertations defended in 2013.

The deadline for nominations for both awards is the end of February 2014.

Now, some researchers dislike the idea of awards in science.  I have to admit that I like them.  On my cynical days, I view them as an extremely cost-effective way of motivating us.  On my less cynical days I adopt Nati’s view of awards as “a pat on the back” that says “well done.  keep up the good work”.  One should give (deserved) pats on the back, and SigEcom is doing so now.

Read Full Post »

AGT course, weeks 5-7

Lecture videos from weeks 5-7 of my AGT course have been posted. Week 5 covers mechanism design with budgets and without money, with a case study on kidney exchange. Week 6 is all about selfish routing and the price of anarchy, with a case study on network overprovisioning. Week 7 goes beyond Nash equilibria and covers some aspects of the theory of smooth games. I fell behind on lecture notes, which are currently available through week 5, but am now catching up.

Looking ahead, in weeks 8-10 we’ll conclude this quarter’s course by talking about learning dynamics (best-response and no-regret) and the complexity of equilibria.

Read Full Post »

Author ordering

Guest post by Felix Brandt

We recently had an internal discussion about author ordering within our group and agreed to retain alphabetical ordering (sort of renewing a decision we made some years earlier when the group was composed differently). Author ordering is a surprisingly tricky issue and I think it’s particularly difficult in algorithmic economics where the cultures of many different disciplines clash.

The problem usually starts with the fact that nobody makes a conscious decision at the beginning of one’s career which author ordering policy to use. In most cases, PhD students just publish their first papers using whatever convention is used in their group. Once they have published papers, they are reluctant to change the convention for the sake of consistency and, perhaps more importantly, because changing the convention can have negative effects on previous coauthors (by making their contribution appear less). Whenever authors with different authorship conventions write a joint paper, they need to decide which convention to use (and if it’s not the alphabetical convention, they also need to agree on a particular ordering for the paper).

The two predominant conventions are alphabetical ordering and ordering by contribution. (Another interesting convention I heard about, but that I have rarely seen, is to list authors by age from youngest to oldest.) Alphabetical ordering is the standard in mathematics, economics, and theoretical computer science. In most other disciplines, including AI, it is not. Sometimes, the head of a group is listed as an author even though he did not contribute anything and, in some areas, there is a special meaning to being the first, the last, or even the second-to-last author (like here). Let’s assume for simplicity that in theoretical areas such as algorithmic economics, only people who significantly contributed to a paper are actually listed as authors (even though that might not always be the case).

At first glance, ordering by contribution seems to be the fairest solution. Measuring relative contribution, however, is a source of great dispute that can hamper productivity. Studies have shown that authors almost always disagree with respect to their relative contributions. Another problem arises when using a default ordering in case the contribution of all or some authors is roughly equivalent (which is mostly the case in our group). Even if one uses non-alphabetical ordering only if the contribution of one author was significantly larger than those of the others, the asymmetry remains: If the authors are listed alphabetically, the first author may have contributed more. If the authors are listed non-alphabetically, the first must have contributed more.

About two years ago, I had the privilege to write a joint paper with Paul Seymour and asked him to move my name further back because I had contributed less. His reply was that “it’s quite standard to be alphabetical and no-one reads anything else into it (and that is a treasure worth preserving)”. I think that’s a very good point because once non-alphabetical ordering is used, it indicates that some information can be deduced from the author orderings in general. The fact that authors have to be ordered in some way can be seen as an unwanted by-product of the sequential nature of language. Whenever I read papers myself, I never put any meaning into the ordering of authors. This is, however, not the case in general and sometimes researchers are denied awards, fellowships, or tenure because the committee in charge expects them to be “first authors”. In order to avoid this problem, some authors put a disclaimer on their webpage or on their papers, explaining which ordering convention is used and sometimes even listing the contribution of individual authors. An alternative, perhaps more elegant, solution to neutralize the author ordering in CVs or on personal homepages (places where it may actually matter) is to list publications as “<paper title> (with coauthor x and coauthor y)”. Despite all these efforts, author ordering remains a controversial issue simply because the cultures of fields, the principles of authors, and the expectations of readers differ so much.

Other articles on author ordering:

  • A statement by the AMS about author ordering. In mathematics, alphabetical author ordering is also known as the Hardy-Littlewood rule.
  • A paper in the Journal of Politicial Economy by Engers, Gans, Grant, and King (First-Author Conditions) finds that “it is an equilibrium for papers to use alphabetical ordering whereas it is never an equilibrium for authors always to be listed in order of relative contribution”.
  • A recent arxiv paper by Ackerman and Brânzei (Research Quality, Fairness, and Authorship Order) analyzes the “phenomenon that alphabetical ordering is correlated with higher research quality”. They cite several studies providing empirical evidence for this claim.
  • Blog posts by Michael Trick and Michael Mitzenmacher.

Read Full Post »