UNIVERSITY OF LIVERPOOL

DEPARTMENT OF COMPUTER SCIENCE

POSTDOCTORAL RESEARCH ASSOCIATE IN ALGORITHMIC MECHANISM DESIGN

Start date: 1 June 2013 (flexible)

Post duration: 36 months

Salary: £31,331 - £36,298 per annum

Ref.: R-580873

We are seeking a Grade 7 Research Associate to be employed for 3 years on an EPSRC-funded research project entitled "Efficient Algorithms for Mechanism Design without Monetary Transfer".

The aim of this project is to find new approximate and optimal, truthful mechanisms for combinatorial auctions, matching problems with preferences and facility location problems, in each case in the absence of monetary transfer.

This is a multi-site research project which involves the Universities of Glasgow and Liverpool (EPSRC grant refs EP/K010042/1 and EP/K01000X/1). Further details about the project are available below.

The successful applicant will be supervised by the University of Liverpool Principal Investigator, Dr Piotr Krysta, will collaborate with project co-Investigators, Prof Paul Goldberg and Dr Giorgos Christodoulou, and will also collaborate with the University of Glasgow project team, including, Dr David Manlove, and with identified overseas researchers.

Applicants should have a PhD in the area of algorithms and complexity, and substantial research experience in this area. Research experience in the areas of algorithmic mechanism design and/or combinatorial optimisation and/or approximation algorithms is desirable.

Informal enquiries may be made to Dr Piotr Krysta (email: pkrysta@liverpool.ac.uk).

For an application pack, please visit this link.

Closing date: 11 March 2013.

Project summary

Matching problems involve assigning agents to commodities, such as junior doctors to hospitals, or kidney patients to donors, based on preference lists expressed by the agents. They have important large-scale practical applications in centralised matching schemes that perform allocations of these types in a number of countries.

When designing mechanisms for these matching problems, two issues present research challenges going forward: (i) optimality (based on the social welfare of the agents involved), and (ii) truthfulness.

These two desirable properties may be conflicting. This led Procaccia and Tennenholtz to introduce the idea of approximate mechanism design without money - this involves the design of truthful mechanisms which may lead to a loss of optimality in the constructed solutions, but such loss can be theoretically bounded.

In the above practical applications, monetary transfer is not appropriate. Two further applications that motivate optimal truthful mechanisms, where monetary transfer is not allowed, involve combinatorial auctions and facility location problems.

This proposal lies in the area of Algorithmic Mechanism Design (AMD), part of the wider field of Computational Social Choice Theory. We are interested in particular in mechanism design without money.

The famous Gibbard-Satterthwaite Theorem roughly states that, in environments without money, the only truthful mechanism is (the trivial) dictatorship. However, it does not apply whenever the domain of preferences of the individuals over the possible outcomes is restricted. That is the case in most real-world applications, where indeed more interesting mechanisms occur.

We plan to advance the area of AMD without payments by tackling combinatorial auctions, junior doctor placement and reviewer assignment, kidney exchange and facility location problems. We will develop new truthful mechanisms whilst measuring their degradation in performance as compared to previous (non-truthful mechanisms). In particular, we will investigate the trade-off between truthfulness and optimality when considering approximate mechanism design.