cd Foundations of Electronic Commerce

Foundations of Electronic Commerce

 

Instructor: Noam Nisan

 

Scope

 

This course attempts to provide a mathematical foundation for electronic commerce.  This is very problematic since the world hardly understands “electronic commerce”, and certainly lacks agreement regarding what its “foundations” are.  Never the less, a growing number of researchers are attempting to build such foundations, and a sampling of such work can be found in the series of ACM conferences on Electronic Commerce.  Much of this work addresses computational perspectives of basic notions from micro-economics and game-theory, and this will be the focus of this course. 

 

The course will be composed of three parts:

 

  1. Basics of classical game theory, auction theory, and mechanism design
  2. Computational markets and auctions
  3. Sampling of recent research papers

 

The course is intended for CS students but is also appropriate for economics students.  The course is very different from similarly named courses that are intended for business students.

 

Part I.  Basics

 

  1. Introduction to (non-cooperative) game-theory and the Nash equilibrium. 
  2. Games with imperfect information and Bayesian-Nash equilibrium.
  3. Auctions (private value): 1st price, 2nd price (Vickery), Ascending (English, Japanese), and Descending (Dutch).
  4. Introduction to Mechanism Design (and social choice theory): Vickery-Clarke-Groves mechanisms, The Gibbard-Satterthwaite theorem, and Arrow’s impossibility result.

 

The material for this part of the course can be found in graduate textbooks on game theory or micro-economics.  The recommended book is called “A Course in Game Theory” by Osborne and Rubinstein.  Much material can also be found in the web site gametheory.net. A CS-oriented introduction to mechanism design can be found in chapter 2 of Parkes’ thesis.  You can find on the web a book on auction theory and a survey of implementation theory.  Here is a nice paper with brief proofs of Arrow’s theorem.

 

Part II.  Computational Markets and Auctions

 

  1. Combinatorial Auctions
    1. Bidding
    2. Winner Determination Algorithms
    3. Iterative Auctions
    4. Communication and Preference elicitation
    5. Computational Hardness and Truthfulness (1, 2, 3)
  2. Online markets
  3. Digital Goods

 

Part III.  Recent Research Papers

 

I will put a list of papers here.  For now, you can look at the papers in the websites of the following courses:

 

  1. HUJI, “Issues on the border of economics and CS” 2001 (Nisan&Perry), 2002 (Nisan&Lehmann), 2003 (Lehmann).
  2. CMU, Sandholm, “Foundations of Electronic Marketplaces”.
  3. Harvard, Parkes, “Topics at the interface between CS and economics”.
  4. Yale, Feigenbaum, “Economics and Computation”
  5. Brown, Greenwald, “Internet Agent Economics”

 

Exercises

 

  1. Ex 1 solution: Ex1_sol
  2. Ex 2 solution: Ex2_sol
  3. Ex 3 solution: Ex3_sol