## General information

This seminar takes place weekly during SS08. Participants are expected to give a talk (in English or German) about current topics from mechanism design and pricing. Complexity and game theory knowledge is recommended.

## Important Dates

Preliminary discussion: 14. February, 16:00, Ahornstr. 55, room 4017.

Talks (during SS08): Thursdays, 10:00-12:00, Ahornstr. 55, room 4017.

## Requirements

- A final version of the term paper ("Ausarbeitung") has to be recevied by one of us (Martin or Alexander)
at least two weeks before the date of the talk.
**This term paper is expected to give an overview in own words about the presented work, not to be a shortened version of the paper(s).** - Talk slides must be presented to us at least one week before the date of the talk.

## Topics

Suppose you are a seller and have a set of goods. There is a set of customers
and you know the maximum price a customer is willing to pay for each good. How
should you set the prices in order to sell your products and end up with
maximum revenue? Algorithmic pricing problems like these are the topic of this
seminar and play an important role in e-commerce.

Suppose you do not know the valuations of customers. How should you design a
"mechanism", i.e. a selling process (e.g. an auction), to learn the true
valuations and sell with maximum possible revenue? This represents an extended
problem that is originated in algorithmic mechanism design, a
unique field on the intersection of Economics and Computer Science. Mechanism
Design studies whether and how selfish agents can be motivated to cooperate
and agree upon a joint outcome. How can we design a set of public rules to make sure that
each participant is motivated to reveal their true incentives? How can we
solve the associated algorithmic problems, e.g. compute an allocation of
goods, such that players have no incentive to manipulate? These are typical
questions that will be subject of this seminar.

## Additional Information

For basic concepts and notation of mechanism design we refer to this book chapter or this Google TechTalk.## Talk Topics and Dates

**"Algorithmic mechanism design"**

N. Nisan and A. Ronen

*Proc. 31st ACM Symp. on Theory of Computing, 1999.*

Fu Wenwei, 10.04.2008**"Truthful mechanisms for one-parameter agents"**

A. Archer and E. Tardos

*Proc. 42nd Annual Symp. on Foundations of Computer Science, 2001.*

Leonidas Lazos, 10.04.2008**"Competitive Auctions for Multiple Digital Goods"**

A. Goldberg and J. Hartline

*Proc. 9th Annual European Symposium on Algorithms, 2001.*

Mario Fraikin, 17.04.2008**"Algorithms for Multi-product Pricing"**

G. Aggarwal, T. Feder, R. Motwani, A. Zhu

*Proc. 31st International Colloquium on Automata, Languages and Programming, 2004.*

Yan Geng, 24.04.2008**"On profit-maximizing envy-free pricing"**

V. Guruswami, J. D. Hartline, A. R. Karlin, D. Kempe, C. Kenyon, F. McSherry

*Proc. 16th Annual ACM-SIAM Symposium on Discrete Algorithms, 2005.*

Johannes Laudenberg, 24.04.2008**"The Stackelberg Minimum Spanning Tree Game"**

J. Cardinal, E. D. Demaine, S. Fiorini, G. Joret, S. Langerman, I. Newman, O. Weimann

*Proc. 10th International Workshop on Algorithms and Data Structures, 2007.*

Jenny Gursch, 08.05.2008**"Stackelberg Network Pricing Games"**

P. Briest, M. Hoefer, P. Krysta

*Proc. 25th Symp. on Theoretical Aspects of Computer Science, 2008.*

Ingmar Gebhardt, 29.05.2008**"Competitive Analysis of Incentive Compatible On-Line Auctions"**

R. Lavi and N. Nisan

*Proc. 2nd ACM Conference on Electronic Commerce, 2000.*

__and__

**"Pricing WiFi at Starbucks"**

E. Friedman and D. Parkes

*Proc. 4th ACM Conference on Electronic Commerce, 2003.*

Gunter Spöcker, 29.05.2008**"Sharing the Cost of Multicast Transmissions"**

J. Feigenbaum, C. Papadimitriou, S. Shenker

*Journal of Computer and System Sciences, Vol. 63, 2001.*

Stefan Hafeneger, 05.06.2008**"Online Auctions with Re-usable Goods"**

M. Hajiaghayi, R. Kleinberg, M. Mahdian, D. Parkes

*Proc. 6th ACM Conference on Electronic Commerce, 2005.*

Stefan Böhmer, 12.06.2008**"Adaptive Limited-Supply Online Auctions"**

M. T. Hajiaghayi, R. Kleinberg, D. Parkes

*Proc. 5th ACM Conference on Electronic Commerce, 2004.*

Pascal Steingrube, Tuesday 17.06.2008, 13:00**"A BGP-based Mechanism for Lowest-Cost Routing"**

J. Feigenbaum, C. Papadimitriou, R. Sami, S. Shenker

*Proc. 21st ACM Symposium on Principles of Distributed Computing, 2002.*

Ilhan Ucar, 19.06.2008

## Helpful links

- How to present a paper in theoretical computer science: a speaker's guide for students from Ian Parberry
- Wie halte ich einen erfolgreichen Vortrag?
- "Hilfe, ich muss einen mathematischen Vortrag halten!"

## Contact

Alexander Fanghänel: fanghaenel (ät) cs.rwth-aachen.de

Martin Hoefer: mhoefer (ät) cs.rwth-aachen.de