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

 

Lecture

Date

Topic

Scribes

1

24.2

Introduction

 

2

3.3

Games and Nash Equilibrium

 

 

 

 

 

 

Exercises