Description: Description: Description: Description: Description: Description: Description: Description: Description: http://www.epsrc.ac.uk/SiteCollectionImages/epsrc-logos/master-hires.jpg

Description: Description: Description: Description: Description: Description: Description: Description: Description: media_32250_en

UNIVERSITY of GLASGOW

COLLEGE OF SCIENCE AND ENGINEERING

SCHOOL OF COMPUTING SCIENCE

 

POSTDOCTORAL RESEARCH ASSOCIATE IN ALGORITHMIC MECHANISM DESIGN

Start date: 1 February 2013 or shortly thereafter

Post duration: 36 months

Salary: £31,948 - £35,938 per annum

 

REF: 002834

 

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 will involve theoretical research, to include the design and analysis of new algorithms, and also practical implementation and experimental evaluation of these algorithms.

 

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 Glasgow Principal Investigator, Dr David Manlove, and will also collaborate with the University of Liverpool project team, including Dr Piotr Krysta, Prof Paul Goldberg and Dr Giorgos Christodoulou, and with identified overseas researchers.

 

Applicants should have a good first degree in Computing Science or a related discipline, a PhD in the area of Algorithms and Complexity, and typically two years of postdoctoral experience in this area, or equivalent research / industrial experience.  Research experience in the areas of algorithmic mechanism design and/or matching problems with preferences is desirable.

 

Informal enquiries may be made to Dr David Manlove (email david.manlove@glasgow.ac.uk).

 

Apply online at www.glasgow.ac.uk/jobs.

 

Closing date: 12 November 2012.

 

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.

 

New software will arise from this work and we have existing routes for exploiting it through University of Glasgow collaborations with the NHS (concerning the assignment of junior doctors to hospitals as part of the Scottish Foundation Allocation Scheme, and the assignment of kidney donors to patients via the National Living Donor Kidney Sharing Schemes).

 

The research methodology is primarily the mathematical analysis of the systems outlined above, proving results about the performance of algorithmic mechanisms. To meet the goals of the project, the requested resources include two Research Associates (one based at each institution), and funding to support travel between the two sites and to support the travel of three visiting researchers.