Foundations of Electronic Commerce


Instructor: Noam Nisan




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 notions from game-theory and economics.
  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 mathematical in nature and makes no attempt at discussing current practices.


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 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 some papers here.


Lecture Notes


Each pair of students is expected to prepare scribe notes for one lecture.  Here is a basic LaTeX template to use.    Here are various LaTeX tutorials.  


Here is the table of scribe notes.












Games and Nash Equilibrium