1. Foundations of Electronic Marketplaces Organizer:

Dr. Tuomas Sandholm
Department of Computer Science
Washington University
St. Louis, MO, 63130

Description of tutorial for the brochure/site:

In multiagent systems - e.g. for agent-mediated electronic commerce - computational agents find contracts on behalf of the real world parties that they represent. This automation saves human negotiation time, and computational agents are often better at finding beneficial deals in combinatorially and strategically complex settings. Applications include electronic trading, manufacturing planning and scheduling among companies, electricity markets, allocating and pricing bandwidth in multi-provider multi-consumer computer networks, digital libraries, vehicle routing among dispatch centers, and resource allocation in distributed operating systems, to name just a few.

A key research goal is to design open distributed systems in a principled way that leads to globally desirable outcomes even though every participating agent only considers its own good and may act insincerely. The tutorial covers relevant topics in AI, game theory, market mechanisms, voting, auctions (also multi-unit and multi-item auctions), coalition formation, and contract nets. Emphasis is given to rigorous results and algorithms - both classic ones from microeconomics and recent ones from the distributed AI community - that have direct applications to computational multiagent systems. Effects of computational limitations (agents' bounded rationality) are discussed as a key feature that has not received adequate attention. Implementation experiences will be shared, and real world applications presented.

About the instructor:

Tuomas Sandholm is Assistant Professor of computer science at Washington University. He received the Ph.D. and M.S. degrees in computer science from the University of Massachusetts at Amherst in 1996 and 1994. He earned an M.S. (B.S. included) with distinction in Industrial Engineering and Management Science from the Helsinki University of Technology, Finland, in 1991. He has nine years of experience building multiagent systems. He has also co-developed two fielded AI systems, and is Chief Scientist of an electronic commerce startup company. He has published over 110 technical papers, and received over twenty academic awards including the NSF CAREER award.

Intended audience:

The tutorial is targeted to the builder of (open) ecommerce systems that consist of multiple self-interested parties. It also serves to make newcomers and executive level participants familiar with the issues. The tutorial reviews work from microeconomics that has been found most relevant to computational agents. It also presents recent results from the multiagent systems (DAI) research community. Emphasis is given to results that have direct applications to computational multiagent systems. Applications themselves will be discussed. No specific background is required in economics or multiagent systems. A general familiarity with computer science is helpful, but even a layperson will be able to appreciate the basic issues raised and answered in this tutorial. The target audience includes:

- Builders of electronic market places (auction and exchange servers, bots, automated negotiation software, electronic stock trading protocols and monitoring daemons, etc.).

- Builders of open multiagent systems.

- Researchers in ecommerce who know some microeconomic theory, but do not know the big picture of it well.

- Researchers in ecommerce that do not know game theory, but would like to get a thorough and broad overview of how it can be used in ecommerce.

- Executive/management level participants that want to know what the key issues are, and what technologies they can use in their applications.

- Electronic commerce people who are interested in how agents can beneficially mediate electronic commerce.

- Press who want to cover the topic.

Handouts: 160 pages can be reduced 2/1 to 80 pages

Detailed description of tutorial:

A. Introduction to multiagent systems consisting of self-interested agents
      1. What are multiagent systems and automated negotiation systems?
      2. Why do we need/want them?
      3. Autonomous, distributed agents
      4. Open systems, no centralized designer
      5. Self-interested vs. cooperative agents
      6. Normative vs. non-normative methods in MAS
      7. Designing interaction protocols
      8. Growing importance
              - Technology push:
                    x Internet, WWW, EDI, KQML, Java, Telescript, Concordia, Odyssey,                     Voyager, Aglets, ...
                    x Collaboration technology
              - Application pull:
                    x Electronic commerce of goods, info, bandwidth, processing, and storage
                    x Virtual enterprises and agile manufacturing
                    x Coordination of distributed operations
                    x Other trends contributing to application pull
      9. Relationships to other disciplines
    10. Example applications
             - Multienterprise agile manufacturing planning & scheduling
             - Internet commerce, e.g. auctionbots
             - Electricity markets (Cases: California, New England, Finland, Sweden)
             - Heating markets for building environments
             - Multiagent information gathering on the web
             - Collective article rating on the web
             - Computer networks
                    x Bandwidth allocation
                    x Video on demand
                    x Mirror site allocation
                    x Dynamic pricing
                    x Provider (and/or user) collusion
             - OS & mobile agents: allocation of storage & computation
             - Vehicle routing among independent dispatch centers
             - Treatment scheduling across hospitals
             - Electronic trading (Case: NASDAQ)
             - Multicontractor software engineering
             - Multirobot systems...
11. Agenthood
             - Utility theory
             - Full vs. bounded rationality
12. Distributed vs. centralized
             - Naturality
             - Reliability
             - Adaptability
             - Development & management
             - Efficiency (a critical inquiry)
             - Bandwidth bottleneck (a critical inquiry)
13. Evaluation criteria for multiagent systems
       1. Computational efficiency
       2. Distribution of computation
       3. Communication efficiency
       4. Social welfare
       5. Pareto efficiency
       6. Individual rationality
       7. Stability
       8. Symmetry
       9. Others B.
Game theoretic analysis tools
       1. Terminology
       2. Solution concepts
            - Dominant strategy equilibrium (Case: Prisoner's Dilemma game)
            - Nash equilibrium (Case: Battle of the Sexes Game)
                    x Criticisms of Nash equilibrium (nonexistence, nonuniqueness, computability)
                    x Existence theorems
            - Refinements of Nash equilibrium
       3. The Revelation Principle and why it does not hold among computational agents
C. Voting
       1. Voting setting
       2. Truthful voting
            - Undesirable properties of common voting protocols
                    x Agenda paradox
                    x Pareto dominated winner paradox
                    x Inverted order paradox
                    x Majority winner paradox
           - Arrow's impossibility theorem
      3. Strategic voting
           - Gibbard-Satterthwaite impossibility theorem
           - Ways to get around the impossibility
                    x Restricted domains (Case: Clarke tax mechanism for truth extraction in                       quasilinear environments; Applications in multiagent planning)
                    x Randomization (Case1: Hat protocol Case2: Random pair protocol)
                    x Complexity
D. Auctions
      1. Auction settings
          - Private value auctions
          - Common value auctions
          - Hybrids
      2. Auction protocols and their properties
          - All-pay auctions - Ascending (English) auction
          - First-price sealed-bid auction
          - Descending (Dutch) auction
          - Second-price sealed-bid (Vickrey) auction
      3. Results for private value auctions
          - Optimal strategies
          - Allocation efficiency
          - Revenue Equivalence Theorem
          - Revenue nonequivalence with risk averse bidders/auctioneer
      4. Results for non-private value auctions
          - Optimal strategies
          - Allocation efficiency
          - Winner's curse
          - Revenue nonequivalence
          - Settings with asymmetric information among agents
      5. Collusion in auctions (Case: Self-enforcing collusive agreements)
      6. Vulnerability to shills
      7. Vulnerability to a lying auctioneer (Case: Third party auctionbots)
      8. Auctioneer's other possibilities - Bidding - Minimum prices - Refusing to sell
      9. Undesirable private information revelation
    10. Untruthful bidding with local uncertainty in the Vickrey auction
    11. Wasteful counterspeculation even in the Vickrey auction
          - Costly computation actions
          - Costly information gathering actions
    12. Sequential interrelated auctions
          - Complexity and local optima (Case 1: FCC bandwidth auctions; Case 2: Dynamic             pricing in computer networks)
         - Inefficient allocation under truthful myopic bidding
         - Lying in interrelated auctions
    13. Multi-unit auctions
         - Flat rate protocol
         - Discriminatory protocol
         - Demand reduction lie
    14. Combinatorial auctions
         - Computational complexities at the bidders' side
         - Computational complexity of winner determination x NP
         -completeness
                    x Exhaustive dynamic programming
                    x Efficiency of optimized constructive search
                    x Inapproximability results
                    x Approximate algorithms for the general case
                    x Approximate algorithms for special cases
                    x Polynomial winner determination via restricted bundles
    15. Continuous double auction protocol (Case: New York Stock Exchange)
    16. Existing auction-based CS applications
         - Network bandwidth allocation
         - Computation allocation
E. General equilibrium based market mechanisms
      1. Example CS applications
         - Power load management (Case: Swedish electricity market)
         - Distributed design
         - Mirror site allocation
         - Network flow routing
      2. General equilibrium market setting
         - Consumers and their choice sets
         - Producers and their choice sets
         - Commodities and assumptions regarding them
         - Prices
      3. Definition of a general equilibrium
      4. Properties of a general equilibrium
         - Pareto efficiency: First Fundamental Theorem of Welfare Economics
         - Second Fundamental Theorem of Welfare Economics
         - Existence conditions for a general equilibrium
         - Uniqueness conditions for a general equilibrium
      5. Limitations of the basic general equilibrium model
         - Price taking (competitive) assumption
                    x Sandholm&Ygge speculation scheme and its convergence
         - Divisible vs. discrete goods
         - Convex production possibilities sets
         - Externalities
         - Universal prices
         - No transfers before convergence
         - Single-shot
      6. Algorithms for reaching a general equilibrium
         - Price tatonnement
                   x Convergence conditions
                   x Conceptual problems
         - Variable step (Newtonian) price tatonnement
                   x Convergence conditions
         - WALRAS [Wellman et al]
                   x Convergence conditions
         - Quantity tatonnement
                   x Convergence conditions
                   x Anytime property
     7. Pros of general equilibrium methods
     8. Cons of general equilibrium methods
F. Coalition formation
     1. Coalition formation as
         - Desirable (Case: Vehicle routing among independent dispatch centers)
         - Undesirable (Case: Auctions)
     2. Activities of coalition formation
         - Coalition structure generation
         - Optimization
         - Payoff division
     3. Approach of classic game theory
     4. High-level classification of coalition games
         - Domain classification for rational agents
         - Domain classification for bounded rational agents
     5. Solution concepts
         - Core (Case: Coalition formation among ATM network providers)
         - Shapley value
         - Coalition-proof Nash equilibrium
         - Strong Nash equilibrium
      6. Core and Walrasian equilibrium
      7. Research on reducing complexity of coalition formation
         - In the coalition structure generation activity
              (Case 1: Shehory&Kraus algorithm;
               Case 2: Ketchpel algorithm)
         - In the optimization activity
             (Case: Sandholm&Lesser method)
         - In the payoff division activity
             (Case 1: Transfer schemes (example runs are presented));
              Case 2: Zlotkin&Rosenschein cryptographic algorithm)
G. Contract nets
     1. The contract net concept for task allocation
     2. Desirability among computationally limited agents
     3. Scaling up (Case: Vehicle routing among independent dispatch centers)
     4. Marginal costs in automated contracting
     5. Bidding and awarding while old bids are pending
     6. Modern combinatorial contract types
         - Cluster contracts
         - Swap contracts
         - Multiagent contracts
         - OCSM contracts
         - Results
                   x Necessity for optimal task allocation
                   x Sufficiency for optimal task allocation
                   x Anytime property
      7. Leveled commitment contracts
         - Definition
         - Motivation
         - Uses
         - Comparison to contingency contracts
         - Insincere decommitting
         - Example using noncooperative equilibrium analysis
                   x Contract enabling theorem
                   x Efficiency improvement theorem
         - Contract parameter optimization
         - Revenue analysis
         - Biased information
     8. Hybrid multiagent search algorithms
     9. Message congestion and agent saturation
                (Case: TRACONET experience of avoiding these problems in an asynchronous                  distributed implementation)
    10. Tradeoffs resulting from limited computation