PhD Studentship: Practical Analysis of Computational Mechanism Design

Location
United Kingdom
Posted
Mar 29, 2017
Closes
Mar 29, 2018
Organization Type
University and College
Hours
Full Time
PhD Studentship: Practical Analysis of Computational Mechanism Design

Engineering & the Environment

Location: Highfield Campus

Closing Date:  Thursday 29 March 2018

Reference: 857417F2

Project Reference: NGCM-0113

This project sits within a field called computational mechanism design. Computational mechanism design involves the design of algorithms for effectively and efficiently allocating limited resources (from every-day resources such as electricity, parking spaces and taxi rides, to virtual resources such as CPU power and advertising space), as well as determining payments, in order to meet desirable objectives such as fairness, profit maximisation and to incentivise “good” behaviour (which avoids manipulation and the need for speculation). Typical examples of such mechanisms are auctions, such as those used in financial exchanges and online advertising.

Since many algorithms are computationally intractable, an important research problem in this domain is to find approximate solutions with certain performance guarantees. Specifically, in this project, you will design novel mechanisms and determine performance bounds for important real-life problems such as kidney exchange, stable matchings, auctions, and scheduling.

The project has both a theoretical and computational component. In terms the theoretical component, you will conduct a theoretical evaluation of the performance of the mechanisms in terms of their worst-case, average-case and using smoothed analysis. The worst-case is the canonical measure used to analyse algorithms, but it is often too pessimistic and does not always reflect the performance in many practical settings (since the worst-case outcomes might never occur in practice). Instead, the average-case performance overcomes this problem but requires that the data follows a certain probability distribution. Smoothed analysis is in-between these two and measures the performance when there are slight random perturbations of the worst-case instances. This leads to more practical guarantees on the mechanisms.

In terms of the computational component, you will implement the mechanisms and apply them to several real-world domains. This requires large-scale simulations using real data, which will be executed on the Southampton computational cluster. The results of these simulations will then be compared to the theoretical performance guarantees.

We are looking for applicants with a background in mathematics, economics or computer science, and an interest in computational game theory, algorithmic mechanism design, and/or multi-agent systems, as well as good programming skills.

The stipend is at the standard EPSRC levels. More details on facilities and computing equipment are available http://ngcm.soton.ac.uk/facilities.html

1 http://assets.cambridge.org/97805218/72829/toc/9780521872829_toc.pdf

2 http://www.masfoundations.org/mas.pdf

If you wish to discuss any details of the project informally, please contact Jie Zhang, Email: jie.zhang@soton.ac.uk, Tel: +44 (0) 2380 598415

This project is run through participation in the EPSRC Centre for Doctoral Training in Next Generation Computational Modelling (http://ngcm.soton.ac.uk). For details of our 4 Year PhD programme, please see http://www.findaphd.com/search/PhDDetails.aspx?CAID=331&LID;=2652

For a details of available projects click here http://www.ngcm.soton.ac.uk/projects/index.html

To apply, please use the following website: http://www.southampton.ac.uk/engineering/postgraduate/research_degrees/apply.page

Further details:

  • Job Description and Person Specification