Thursday, January 29, 2009

New Research Group: Economics and Computation

Concepts from economics (markets, incentives, social welfare, etc.) have gained increasing currency within computer science. We now have quite a well-developed research community at this interface, with meetings like ACM-EC, WINE and SAGT having arisen to cater to it.

Here at Liverpool we're starting up a new research group in the Computer Science dept: Economics and Computation (EcCo). Initially, Piotr Krysta and myself are members, and we are now looking to recruit two further faculty members --- see below! And of course, later we hope to attract students and RAs, and later on, grow by another 2-3 further faculty members.

The new group builds on existing expertise and research activity here, and thus there are excellent opportunities for collaborations with other current research groups here, notably the Complexity Theory and Algorithms Group and the Agent Applications, Research and Technology group. I can promise a great research environment, and am happy to answer questions from potential candidates about any aspect of these posts.

Here is a copy of an ad that has been emailed out to various mailing lists:



SALARY IN RANGE GBP 30,594 - GBP 35,469 pa

The Department of Computer Science 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. The successful candidates will join Professor Paul Goldberg and Dr Piotr Krysta in establishing a new research group in this area.

The group will carry out research in the computational foundations of economics/game theory and economic theory in computer science. The group will enjoy close collaborative links with the existing Complexity, Theory and Algorithms research group and the Agent Applications, Research, and Technology research group. Relevant topics of interest include (but are not restricted to):

** algorithmic game theory;

** mechanism design and auction theory;

** complexity and computation of solution concepts;

** optimization problems in economics; and

** computational social choice.

You should have an excellent track record of research at the intersection of computer science and economics/game theory, and will join a world-class Department.

The post attracts a special HEFCE-funded `Golden Hello' to the value of GBP 9K, subject to individuals satisfying the eligibility criteria.

Job Ref: A-569104 ** Closing Date: 27 February 2009 **

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

For full details, or to request an application pack, visit


tel 0151 794 2210 (24 hr answerphone).

Please quote Job Ref A-569104 in all enquiries.

Tuesday, January 27, 2009

Is green the new black?

Compared with other vices, envy gets a bad press. For years, the phrase "politics of envy" has been a trusty weapon of political discourse, wheeled out again and again whenever someone rails against excessive boardroom pay rises, or suggests raising the top level of income tax. Recently, things have changed - articles like this one are becoming fashionable, as we find out about the pay received by top bankers whose organizations are now being bailed out by the taxpayer.

It is a fair counter-argument that the excessive bonuses are a small percentage of the overall losses that banks are passing on to the public, and that to curb them would not cut the taxpayer's bill very much. But, there is a growing understanding that curbing other people's excessive bonuses simply feels good for its own sake -- it requires no financial justification. We don't penalise the bankers in order to save money -- we do so because it makes us happy.

In psychology and economics, envy requires one to be prepared to pay a small amount of money in order to see someone else lose a larger amount of money. The above attitude appears to qualify therefore, since if you get your kicks out of seeing some overpaid banker have to give up his 100 foot yacht, then there exists some sufficiently small amount of money that you would be prepared to pay for the spectacle.

Maybe this will provide a boost for envy-related research? There's an interesting line of research that has attracted some computer scientists, on the problem of envy-free cake cutting. The general topic is: how do you generalize the I-cut-you-choose idea, when there are more than 2 people who want to share a divisible good (such as a cake)? I just read a very nice paper: Thou Shalt Covet Thy Neighbor's Cake, by Ariel Procaccia. It shows that envy-freeness is harder to achieve than proportionality, in the sense that it requires more cuts, as a function of number of players. (Envy-freeness means that everyone can guarantee that they value their own share at least as much as anyone else's; proportionality means that everyone can guarantee a "fair share", but with the risk they end up thinking certain other players did better. So, proportionality is a weaker requirement.) The paper uses the Robertson-Webb model of cake-cutting procedure in which a centralized algorithm is allowed to submit certain queries to the players about what value they would assign to various parts of the cake. For me, a very interesting aspect of this model is the parallels with the query protocols that have been studied in computational learning theory.

Thursday, January 22, 2009

Exams, migration

My exam on Decision, Computation and Language took place yesterday, co-located with another one on Animal Parasitology. I could hopefully have scraped together a few marks had I taken the rival paper; could probably make a few constructive comments on the distinction between parasites, parasitoids and predators, not to mention lice and ticks. Not sure how those biologists would have gotten on with regular expressions for words that contain "aaa" as a substring, and the like. After that, listened to a talk by former Liverpool postdoc Edith Elkind on "beyond weighted voting games". She convinced me (not during the talk) that Singapore is, for climate, a nice place at this time of year, or failing that, Southampton. One good thing about heading south for the winter is, your reduced domestic heating probably offsets the carbon you burn in order to travel.

The latest CACM merits inspection. (Added a day later: that is, the Feb 09 issue, which became available online a day before my paper copy of the Jan 09 issue arrived! The Jan issue has an article on "Computational Challenges in E-Commerce" that I really should read.)

Friday, January 09, 2009

RAE Sector Overview report

Here is where one can download the "subject overview reports" from the RAE panels. Panel F is the one that includes Computer Science. It is a brief 4-page summary of their general findings about the state of CS research in the UK. One paragraph notes:

There was a significant increase in research in algorithms and complexity, including the establishment of several new centres of excellence. This increased activity was not, however, limited to the research groups specialising in this area, but permeated research in many other areas, such as data-mining, vision, evolutionary computing, agents, etc.

This was noted as a result of the 2001 International Review of UK Research in Computer Science, which (rightly) pointed out that algorithms and complexity, at the time, was under-represented here. But, the most encouraging aspect of the above observation is the bit about algorithmic analysis gaining recognition for its importance, outside of its own community.

Another paragraph noted what might be regarded as a more general trend, namely that the research being assessed was generally more rigorous than the previous RAE (2001), i.e. more mathematical analysis, and more careful and detailed experiments.