| 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 Date | Panel Name | Outcome |
|
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
|
|
Impacts |
|
| Description |
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk |
| Summary |
|
| 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 |