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.
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.
|
