EPSRC logo

Details of Grant 

EPSRC Reference: EP/F069502/1
Title: Algorithmic Mechanism Design and Optimization Problems with Economic Applications
Principal Investigator: Krysta, Professor P
Other Investigators:
Researcher Co-Investigators:
Project Partners:
Department: Computer Science
Organisation: University of Liverpool
Scheme: First Grant Scheme
Starts: 01 April 2009 Ends: 30 September 2012 Value (£): 287,199
EPSRC Research Topic Classifications:
Fundamentals of Computing
EPSRC Industrial Sector Classifications:
No relevance to Underpinning Sectors
Related Grants:
Panel History:
Panel DatePanel NameOutcome
05 Jun 2008 ICT Prioritisation Panel (June 2008) Announced
Summary on Grant Application Form
Our day-to-day life activities are influenced by various communication networking facilities, like electronic mail, electronic trade and banking systems. Their common underlying infrastructure is the Internet, probably one of the mostinfluential human creations of the last century. The Internet is decentralized, i.e.,created and operated by independent entities (humans, servers, companies)which mostly realize their own, usually selfish, goals. In classic optimization problems which are mostly NP-hard, the complete input data is available to the algorithm. The selfish setting raises new, challenging optimization problems withthe added difficulty that part of the input data is private data of these entities to be elicited. The very successful theory of approximation algorithms is usually used to treat NP-hard problems. On the other hand, the standard tool to cope with selfish behavior is economic non-cooperative game theory and mechanism design, with the prominent notion of Nash equilibria. The synergy between these two areas,algorithmic game theory (AGT), has been a major research area in computer science recently. This vibrant research area is establishing the mathematical platform for problems arising in context of the Internet. Despite efforts, many problems still await their solutions, and many applications call for newmathematical models. We propose to contribute to this fascinating and important research endeavor from many different perspectives, by attacking both fundamental, basic problems and opening new lines of thinking.Our main high level goal is to develop new techniques for mathematical analysis of algorithmic models, and to develop new models, motivated by economic and network design applications, using as basis approximation algorithms and linear programming (duality) techniques. The main classes of problems which we plan to study include basic auction settings (like combinatorial auctions, adwords auctions), revenue maximizing product pricing problems, and network mechanism design problems.
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
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
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