Details of Grant 

EPSRC Reference:	EP/M008118/1
Title:	Worst-Case Guarantees in Auction Design
Principal Investigator:	Christodoulou, Dr G
Other Investigators:
Researcher Co-Investigators:
Project Partners:
Department:	Computer Science
Organisation:	University of Liverpool
Scheme:	First Grant - Revised 2009
Starts:	01 November 2014	Ends:	31 January 2017	Value (£):	98,538
EPSRC Research Topic Classifications:	Fundamentals of Computing
EPSRC Industrial Sector Classifications:	Information Technologies
Related Grants:
Panel History:	Panel Date Panel Name Outcome 09 Sep 2014 EPSRC ICT Prioritisation Panel - Sept 2014 Announced
Summary on Grant Application Form
Mechanism design studies the design of algorithms, called mechanisms, in strategic environments, where part of the input is unknown and controlled by selfish entities. Algorithmic mechanism design studies the interplay between selfishness and computation in optimisation problems. We are interested in the design and study of mechanisms that allocate goods or resources to a group of selfish parties in competition. The preferences of each player for different bundles of the items are expressed via a valuation set function, that is typically private knowledge to each player. Hence, the mechanism designer asks the players to submit bids to express their preferences, and the players may strategically lie about their true values and select a bid that will maximize their utility. Fundamental paradigms of this general setting include combinatorial auctions, bandwidth allocation, and job scheduling. The main challenge is to design a (truthful) mechanism that allocates the items in an efficient way in the equilibrium. That is, to find a partition of the items that maximizes the social welfare, which is the sum of the values of the players. Although it is well-known that this can be achieved optimally by the celebrated VCG mechanism, unfortunately this might take exponential time in the number of players and goods. Consequently, practitioners typically resort to simple, non-truthful mechanisms. A notable example is the famous Generalized Second Price auction (GSP) for selling adwords. Other examples include simultaneous ascending price auctions for wireless spectrum allocation, or eBay independent second price auctions. Furthermore, in such auctions, the expressive power of the buyers is heavily restricted by the bidding language and they are not able to represent their complex preferences precisely. We are interested in settings where both the players and the mechanism designer have incomplete information. In light of the above, in our previous work, we proposed the study of simple, non-truthful mechanisms using the Price of Anarchy as a measure of inefficiency for simultaneous second price auctions. In this proposal we would like to extend this powerful research idea and study a general class of mechanisms in a unified way.
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