Efficient Algorithms for Mechanism Design Without Monetary Transfer

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