Auction theory

elective monographs

Computational complexity 1000-218bZO
Introduction to Game Theory 1000-135WTG

Auctions are a widely used mechanisms for resource exchange and allocation, that finds application in real world (e.g. internet auctions) as well as computational applications (e.g. resource allocation in multi-agent systems and eCommerce). Which auctions are best for the seller and which for the buyers? What is the impact of knowledge of others' valuations? How bad is collusion? Is it hard to determine the winner when bundles of several interdependent objects are being sold? Does it depend on the bidding language?

The aim of this course is to introduce and present the basic issues and problems of arising in auctions and to deepen their understanding via game theory and computational complexity theory.

1.Single unit auctions

a.Auctions with private valuations: first and second price auctions, revenue equivalence principle, effects of risk aversion, budget restrictions and asymmetry of valuations

b.Mechanism design: revelation principle, optimal mechanisms, Vickerey-Clark-Groves mechanism

c.Interdependent valuations: English auction, ranking auctions wrt revenue, effects of asymmetric information, minimal prices and entry fees

d.Efficient allocations

e.Collusion

f.All-pay auctions

2.Multi-unit auctions

a.Discriminatory auctions, Uniform-price auctions and Vickrey auction vs open bid auctions (English, Dutch and Ausubel)

b.Efficiency and equilibria for different action formats

c.Revenue equivalence for multi-unit auctions

d.Sequential auctions

e.Nonidentical objects, interdependent valuations

3.Combinatorial auctions: winner determination problem, bidding language and communication complexity, iterative auctions

Basic literature

V. Krishna, Auction theory

N. Nisan, T. Roughgarden, É. Tardos, V. Vazirani, Algorithmic game theory

Supplementary literature

P. Klemperer, Auctions: Theory and practice (http://www.paulklemperer.org/)

L. Ausubel, Auction Theory for the New Economy (http://www.bsos.umd.edu/econ/ausubel/auction-theory-new-economy.pdf)

M. Osborne, A. Rubinstein, A course in game theory (http://books.osborne.economics.utoronto.ca/)

Knowledge:

Knows basic auction formats

Understands impact of incomplete information, risk aversion, budget restrictions, valuations asymmetry, ,minimal prices and entry fees on different auction formats

Knows and understands revelation principle

Knows the notion of optimal mechanism and VCG mechanism

Knows and understands revenue equivalence principle

Knows and understands the notion of allocation efficiency

Knows the winner determination problem and the problem of communication complexity for combinatorial auctions

Skills:

Is capable of finding Nash equilibria for different auction formats and under different assumptions about the participants

Is capable of evaluating different auction formats from buyers' and seller's perspectives

Is capable for evaluating different auction formats in face of collusion

Is capable of evaluating succinctness of different bidding languages and the associated interpretation complexity

Competences:

Knows basic problems associated with auctions and is capable of analysing auctions against these problems

Knows limits of own knowledge and understands the need for further study, including interdisciplinary knowledge (K_K01)

Is capable for posing precise questions that help to deepen own understanding of the given topic (in particular when facing non-computer-scientists) or finding missing parts of the reasoning (K_K02)

Final grade based on the score from written exam. Same criteria in retake session.