
Practical Analysis of Computational Mechanism Design Project Ref: NGCM0113 Available: Yes Supervisor: Jie Zhang, Enrico Gerding Research Group: Agents, Interaction, and Complexity Cosupervisor: 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 everyday 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 reallife 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 worstcase, averagecase and using smoothed analysis. The worstcase 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 worstcase outcomes might never occur in practice). Instead, the averagecase performance overcomes this problem but requires that the data follows a certain probability distribution. Smoothed analysis is inbetween these two and measures the performance when there are slight random perturbations of the worstcase 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 realworld domains. This requires largescale 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 multiagent 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 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 . Project Images

