MS in Ecommerce Mini-Course 20-853: Electronic Negotiation

Spring 2004

 

The course covers state-of-the-art negotiation technology for 1-to-many, and many-to-many negotiation.  Both game-theoretic and computational issues are discussed.  Multi-item, multi-unit, and multi-parameter negotiation are addressed.   Expressive bidding languages are analyzed and their implications on market clearing technology are discussed.  Software agents for automated negotiation are studied.

 

Overall, the goal is to cover classic basics as well as high-end new technology that has just emerged – both at a very understandable level.

 

Level: This is a Master’s level minicourse in the MS Ecommerce program.

 

Instructor: Prof. Tuomas Sandholm. Email: sandholm@cs.cmu.edu .  URL: www.cs.cmu.edu/~sandholm

 

This page: http://www.cs.cmu.edu/~sandholm/ec20-853/ec20-853.htm

 

Class times: TuTh 1:30-3:00, Wean Hall 4601.  First class: March 16th.  Last class: April 29th.

 

Instructor’s office hour: Tu 3-3:30, Wean Hall 4606.

 

Book:  There is no book that adequately covers these topics yet.  Professor Sandholm is writing a book on this topic for MIT Press.  In the class, we will use material prepared by the instructor – mainly on slides.  Much of this material, together with additional material, will eventually be published in the book.

 

Format:

  1. Lectures by Prof. Sandholm.  In addition, guest lectures by industry experts.
  2. In advance of each lecture, each student is expected to download the slides for that lecture from the course web page, and to print them.  

 

Evaluation: Evaluation is based on class participation and written homeworks.  There will be no significant programming project.

 

Prerequisites:  Applied Data Analysis (46-735), Electronic Payment Systems (99-763).  Others who would like to take the course need the instructor’s special permission.

Course schedule (subject to change)

 

  1. March 16: Motivation through an all-pay auction.  Course organization.  Introduction.  Automated negotiation in different stages of an ecommerce transaction. Utility functions for modeling preferences.  Measures of how good a negotiation mechanism is.   Slides  
  2. March 18: Game-theoretic analysis tools.  Extensive form and matrix form representations of games.  Notion of strategy and mixed strategy.  Prisoner’s dilemma and dominant strategy equilibrium.  Battle of the Sexes and Nash equilibrium.  Ultimatum bargaining.  Threats.  When is a threat credible?  Subgame perfect equilibrium.  Software as a commitment device.  Slides  
  3. March 23: Mechanism design.  Revelation principle.  Dominant strategy implementation.  Gibbard-Satterthwaite impossibility.  Clarke tax mechanism.  Budget imbalance.  Collusion.  Slides 
  4. March 25: -.
  5. March 30: Auctioning a single item.  Private vs. correlated vs. common value auction settings.  English, Japanese, Dutch, first-price sealed-bid, and second-price sealed bid (Vickrey) auction mechanisms.  Revenue equivalence.   Optional reading: Review article [Wolfstetter 94]   Slides
  6. April 1:  More on auctioning a single item.  Maximizing welfare vs. maximizing expected revenue.   Revenue non-equivalence.  Winner’s curse.  Theory of proxy bidding.  Collusion.  Strategic reserve price and revenue-maximizing auction. Slides
  7. April 6: Rest of auctioning a single item.  Auctions where bidders can invest effort/computation to determine their own valuations.   Dynamically vs. statically determined closing time.  Sniping.  Mobile proxy bidder agents.    Paper on late bidding.    Slides
  8. April 8: Exchanges (many-to-many markets): Myerson-Satterthwaite impossibility.  Multi-unit auctions.  Uniform-price auction.  Demand reduction lie.  Multi-unit Vickrey auction.  Bidding languages (price bids; PQ bids; PQ bids with XORs; price-quantity graph bids).  Computational complexity of clearing auctions, reverse auctions, and exchanges under the different bidding languages - with nondiscriminatory and discriminatory pricing.  Slides.  Homework 1 posted.
  9. April 13: Multi-item auctions. Sequential auction mechanisms.  Budget-constrained bidders in sequential auctions.  Parallel auction mechanisms.  Combinatorial auctions.  Approaches to winner determination in combinatorial auctions.  Slides.
  10. April 15: Bidding languages.  Generalized Vickrey auction.  Multi-unit combinatorial auctions.  Combinatorial reverse auctions.  Combinatorial exchanges.  Free disposal vs. no free disposal.  Complexity of clearing these markets.  Experiments on clearing generalized combinatorial markets.  Slides.
  11. April 20: Ascending combinatorial auctions. iBundle.  AkBA.  Automated bid elicitation in combinatorial auctions. Slides.   Side constraints and non-price attributes in markets.  Complexity of clearing these markets.  Slides.  Homework 1 due.  Homework 2 posted.
  12. April 22: Guest lecture:  Kirk Logan, Vice President of Client Services, CombineNet, Inc.  The talk includes a demo of a procurement optimization system with expressive competition.
  13. April 27: Guest lecture:  Reputation systems.  By Prof. Paul Resnick, University of Michigan.  Slides.
  14. April 29: Q & A regarding any topics covered in the course, and any related topics that students are interested in.  Career Q &A.  Homework 2 due.

 

Advanced optional reading

These topics and a host of related topics are covered in more detail in Professor Sandholm’s PhD-level computer science course “Foundations of Electronic Marketplaces”.  Curious students will find further readings on these topics on the web page of that course:

 

http://www.cs.cmu.edu/~sandholm/cs15-892/cs15-892.htm 

 

The slides at that site also contain proofs of most of the theorems mentioned in the “Electronic Negotiation” course.