Wednesday, March 31, 2010

2 new faculty posts at Liverpool, UK

Having just send the ad to various mailing lists, it should also appear at the blog...


The Department was ranked in the top 10 UK Computer Science departments in RAE2008, and building on this success, we seek to significantly expand current research around existing strengths at the intersection of economics/game theory and computer science. You will join Professor Paul Goldberg, Dr Piotr Krysta, Dr Martin Gairing and Dr Rahul Savani in our research group on Economics and Computation. The group carries out research in the computational foundations of economics and game theory and enjoys close collaborative links with other strong research groups in the Department. You will be expected to contribute to our MSc in Computation and Game Theory.

You should have a PhD in Computer Science or related discipline and an excellent track record of research at the intersection of computer science and economics/e-commerce/game theory.

Relevant topics of interest include (but are not restricted to):

  • algorithmic game theory;
  • e-commerce;
  • mechanism design and auction theory;
  • complexity and computation of solution concepts;
  • optimisation problems in economics;
  • computational social choice.

salary in range GBP 36,715 - GBP 41,323 pa; Job Ref: A-570581; Closing Date: 30 April 2010

Further details

online applications/job description

For informal discussions please contact Prof Paul Goldberg, Head of Group (

For full details, or to request an application pack, visit here
tel +44 151 794 2210 (24 hr answerphone).

Thursday, March 11, 2010

Dagstuhl 10101

I am at Dagstuhl seminar 10101 (schedule) on computational social choice; it ends tomorrow. Much of the chatter in the evenings has been about the AAAI conference, due to author feedback to reviews being made available a couple of days ago; to a lesser extent ACM-EC accepted papers, also announced a couple of days ago. I will not try to do a complete overview; let me try a more vignette-like approach.

A nice talk by Jérome Lang was in the context of conducting a collection of yes/no votes where there is preferential dependencies between attributes, meaning that a voter's support for one issue may depend on the outcome of the vote on one or more of the other issues. The example used was voting to build a swimming pool and voting to build a tennis court, where some voters would like one or the other, but not both (too expensive). Each voter is represented by a preference relation on the 4 possible outcomes (for n yes/no issues, he uses a more concise representation, "CB-nets"). The question is, how hard is it for the "chair" (who chooses which order the issues are voted on) to control the outcome. Commonly NP-hard, which is taken to be good news, although it is noted that it raises the question of easier manipulation in typical or average cases. That issue is analogous to the hardness of a voter choosing a strategic vote (a ranking of the candidates that is not his true ranking) so as to get a better outcome. While that is NP-hard for some voting schemes, it may often be easy in practical settings. Indeed, Edith Hemaspaandra's talk was about polynomial-time manipulability when there is single-peaked preferences over the candidates.

The rump session (not covered in the above schedule) was 11 talks each of 5 minutes, really aimed at stating problems where no results have been obtained. I gave an introduction to the "chairman's paradox" (to ask about related computational issues) -- it was identified by Farquharson in 1969 and goes as follows. Say you have a committee of 3 voters {1,2,3} who have to choose one of 3 outcomes {A,B,C}. Let voter 1 be the "chair" and voters 2 and 3 be the ordinary members. The special role of the chair is that if all 3 outcomes get one vote each, then the one supported by the chair is the winner. The paradox is that if the voters' preference lists are generated at random, and your solution concept is pure Nash equilibrium, then the chair gets what he wants less often than the other members. For example, consider the (Condorcet cycle) preferences where 1 has preferences ABC (in descending order), 2 has preferences BCA and 3 has preferences CAB. Then, voter 2 will vote for C since that results in C rather than A winning (2 and 3 supporting C). Voters 1 and 3 continue to support A and C respectively, having no incentive to switch. That is the only pure Nash equilibrium that results from iterative removal of weakly dominated strategies, and notice that 1 (the chair) gets his worst outcome C. I will note that the last time I had to chair a committee of this nature, I felt disadvantaged, although not quite for this reason. The session contained an interesting talk by Kóczy on a method for ranking economics journals (someone has to do it I suppose; see this article on the ranking obsession factor). Finally I should surely mention Felix Brandt's entertaining talk on the "kicker theorem".

Edith Elkind's talk on plurality voting with abstentions was related to the above in using pure Nash equilibrium as the solution concept with a bunch of voters and alternatives (not just 3). An interesting open problem she raised is: Suppose you have sets of voters and alternatives, and for each voter/alternative pair there's a numerical utility of that outcome to that voter. Assume that in the event of a tie, the voter's utility is the average (furthermore, let's assume that all numbers and averages are distinct). Suppose voters cast their votes in some prescribed order, and consider the solution concept of subgame perfect equilibrium. What is the complexity of computing their votes? (On a less formal note, Aviv Zohar told me about a "taxicab game" he had played rather poorly, in which a sequence of (say) 10 people board a minibus with 11 seats, and you aim to end up next to the vacant seat, or failing that, maybe some seats/neighbours are better than others. OK, it needs to be specified more precisely.)

Here is another recent blog post on computational social choice, just to prove I have been paying attention.

Friday, March 05, 2010

inaugural lecture

The illustration is from one of my slides - it is intended to give an idea of how to make a hard instance of 2D-SPERNER. I must thank my colleagues in the EcCo research group for the talks they gave in the morning, also Troels Bjerre Sorensen, David Manlove, Kousha Etessami and Bernhard von Stengel for visiting and giving very nice talks in the afternoon, as well as other visitors and everyone who attended the talks.