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.
Preliminary discussion: 14. February, 16:00, Ahornstr. 55, room 4017.
Talks (during SS08): Thursdays, 10:00-12:00, Ahornstr. 55, room 4017.
- 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.
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 InformationFor 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.
"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
- 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!"
Alexander Fanghänel: fanghaenel (ät) cs.rwth-aachen.de
Martin Hoefer: mhoefer (ät) cs.rwth-aachen.de