EPSRC logo

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 DatePanel NameOutcome
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


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


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
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