| EPSRC Reference: |
EP/K01000X/1 |
| Title: |
Efficient Algorithms for Mechanism Design Without Monetary Transfer |
| Principal Investigator: |
Krysta, Professor P |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Computer Science |
| Organisation: |
University of Liverpool |
| Scheme: |
Standard Research |
| Starts: |
01 June 2013 |
Ends: |
31 May 2016 |
Value (£): |
329,764
|
| EPSRC Research Topic Classifications: |
| Fundamentals of Computing |
|
|
| EPSRC Industrial Sector Classifications: |
| No relevance to Underpinning Sectors |
|
|
| Related Grants: |
|
| Panel History: |
| Panel Date | Panel Name | Outcome |
|
04 Sep 2012
|
EPSRC ICT Responsive Mode - Sep 2012
|
Announced
|
|
|
Summary on Grant Application Form |
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 routes for exploiting it through existing 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).
|
|
Key Findings |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
|
Potential use in non-academic contexts |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
|
Impacts |
|
| Description |
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk |
| Summary |
|
| Date Materialised |
|
|
|
|
Sectors submitted by the Researcher |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
| Project URL: |
|
| Further Information: |
|
| Organisation Website: |
http://www.liv.ac.uk |