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

Mini V 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

TA: Andrew Gilpin. Email: gilpin@cs.cmu.edu .  URL: www.cs.cmu.edu/~gilpin

 

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

 

Class times: May 17th to Jun 28th

 

Web conference office hour: Tuesday 5:30-6:30 PM (starts May 25th)

 

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. 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. 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. Mechanism design.  Revelation principle.  Dominant strategy implementation.  Gibbard-Satterthwaite impossibility.  Clarke tax mechanism.  Budget imbalance.  Collusion.  Slides 
  4. 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
  5.   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
  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
  7. 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
  8. 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.
  9. 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.
  10. 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 2
  11. Guest lecture:  Kirk Logan, Vice President of Client Services, CombineNet, Inc.  The talk includes a demo of a procurement optimization system with expressive competition.
  12. Guest lecture:  Reputation systems.  By Prof. Paul Resnick, University of Michigan.  Slides.
  13. Q & A regarding any topics covered in the course, and any related topics that students are interested in.  Career Q &A.

Homework

Please send your homework in either Word or PDF to Andrew Gilpin.

  1. Homework 1 Due on Jun 20th (Ignore the due date given in the homework)
  2. Homework 2 Due on Jun 27th (Ignore the due date given in the homework)

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.