English English

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

  1. "Algorithmic mechanism design"
    N. Nisan and A. Ronen
    Proc. 31st ACM Symp. on Theory of Computing, 1999.

    Fu Wenwei, 10.04.2008


  2. "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


  3. "Competitive Auctions for Multiple Digital Goods"
    A. Goldberg and J. Hartline
    Proc. 9th Annual European Symposium on Algorithms, 2001.

    Mario Fraikin, 17.04.2008


  4. "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


  5. "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


  6. "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


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


  8. "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


  9. "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


  10. "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


  11. "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


  12. "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

We are thanking i7 for those useful links!

Contact

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