Worst-Case Guarantees in Auction Design

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.

Auctions is arguably the most efficient method to allocate national
resources, so any regulator agency that conducts allocation of such
resources is a potential beneficiary of this project.

The main advantage of an auction is that, because of the competition
it creates among participants, it tends to assign the resources to
those best able to use it. Another advantage of auctions is that this
competition leads to auction revenues, which can be used to
counterbalance taxation. Finally, it is a transparent way of assigning
licenses, as those who did not win can see who won the auction and
why. Two such examples that are heavily used both at an international
and at UK level, with huge impact in our quality of life. As an other
example of impact of our research is Sponsored Search Auctions used by
the giants of Web Search (Google, Microsoft and Yahoo).

We outline one public-sector area and one private
sector-area where organizations and individuals stand to benefit from
the impact of the research described in this proposal.

* Spectrum Allocation

Since the great success of FCC spectrum auctions in the US, auctions
have been the predominant method to allocate spectrum. In 2000, the
Radiocommunications Agency of the United Kingdom completed its first
spectrum auction, raising £22.5 billion for five third-generation (3G)
mobile wireless licenses. The recent auction conducted by the Office
of Communications (Ofcom) for 4G mobile broadband services in 2013,
has achieved Ofcom's purpose of promoting strong competition in the
market, and as a result it is anticipated that this will lead to
faster broadband speeds, lower prices, new investment and better
coverage. The value of the benefits from 4G services to UK consumers
over the next 10 years is estimated to be above £20 billion. As Ofcom
suggest, by 2030, demand for mobile data could be 80 times higher than
today. To help meet this demand more mobile spectrum is needed over
the long term, together with new technologies to make mobile broadband
more efficient. Ofcom is planning to support the release of further
spectrum for possible future '5G' mobile services.

Our research methodology and in particular our proposed analysis for
Multi-Unit auctions, can lead to the better understanding on the
currently used auction format, as well as to the development of new
auction formats with improved efficiency for spectrum allocation.

* Sponsored Search Auctions

Web search engines gain profit by selling advertising space next to
the search results. The way this space is allocated is via an auction
(sponsored search auction). Each advertiser can bid for a specific
keyword of interest and for a specific advertisement place that is
usually displayed next to the search result. As an example, a pizza
restaurant can 'bid' a price and get advertised whenever users
search for 'pizza'.

Sponsored search auctions is the dominant way of internet advertising,
and is the main investment in advertising campaigns of all modern
industrial companies. It is also the major source of revenue for web
search providers. As an example, in 2011 96% of Google's revenue was
due to its advertising programs.

All parties involved are potential mid and long-term beneficiaries of
our research, that is Web Search providers (Google, Microsoft and
Yahoo), all merchants that advertise their products via sponsored
search, as well as the end users that get more targeted advertisement.
The long-term impact of our research will be both economical and
societal. The final recipient and beneficiary of the project is any
individual that uses the above services. In the case of national
resources, it is the general public that enjoy the services of faster
and cheaper broadband and better quality of service for
gas and electricity. Better web search quality of service to the end-user is also expected,
by more targeted advertisement.