Project Ref: NGCM-0113
Supervisor: Jie Zhang, Enrico Gerding
Research Group: Agents, Interaction, and Complexity
Research Area: Computational Engineering
Project Description: 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 http://assets.cambridge.org/97805218/72829/toc/9780521872829_toc.pdf http://www.masfoundations.org/mas.pdf
If you wish to discuss any details of the project informally, please contact Jie Zhang, Email: firstname.lastname@example.org, Tel: +44 (0) 2380 598415
Keywords: Applied Mathematics, Applied Physics, Computer Science, Economics, Materials Science, Mechanical Engineering, Operational Research, Software Engineering
Support: All studentships provide access to our unique facilities and training and research support .