The IPCO X Summer School

The 3rd Summer School on Integer Programming and Combinatorial Optimization will be held at Columbia University on June 7-8, 2004. The summer school will feature lectures from leading researchers in emerging areas at the intersection of computer science, economics, and operations research.

The idea of a summer school immediately preceding the IPCO meeting was introduced at the occasion of IPCO VIII in Utrecht. It intends to facilitate the participation of young researchers in the joint events, even if an IPCO submission is not made.

Please visit the IPCO X program page for a schedule and other details.

Lectures

Joan Feigenbaum

Computer Science Department, Yale University.

Incentives and Internet Computation

Traditional treatments of distributed computation typically assume nodes to be either cooperative (i.e., they execute the prescribed algorithm) or Byzantine (i.e., they can act in an arbitrary fashion).  However, to properly model the Internet, in which distributed computation and autonomous agents prevail, one must also consider selfish agents that maximize their own utility.  To cope with selfish agents, system designers must develop mechanisms in which cooperation is in each agent's self interest; we call such mechanisms "incentive-compatible." 

These lectures will first introduce the audience to the economic theory that forms the basis for the design and analysis of incentive-compatible Internet algorithms. It will then review previous results in this area, including those on interdomain routing and multicast cost sharing.  Finally, it will present several promising research directions and pose some specific open problems.

Tim Roughgarden

Computer Science Division, University of California at Berkeley.

The Price of Anarchy

The "price of anarchy"---the worst-case ratio between the social objective function value of an equilibrium and that of a social optimum---is an increasingly popular measure of the extent to which competition approximates cooperation.  It is a rendezvous of the idea of an equilibrium, an idea fundamental to game theory, and the concept of approximation, which is ubiquitous in optimization and theoretical computer science. 

In this tutorial, we will survey several mathematical techniques for bounding the price of anarchy, along with the applications to which they have been successfully applied.

Rakesh Vohra

MEDS Department, Kellogg School of Management, Northwestern University.

Linear Inequalities and Mechanism Design

A mechanism is a black box that takes as inputs the preferences of a set of agents and outputs an allocation of resources. The subject of mechanism design is concerned with the existence (or non-existence) of mechanisms that satisfy `desirable' properties. For example, do agents have the incentive to truthfully report their preferences? Is it non-discriminatory in the sense that the outcome does not depend on the names of agents?

The literature has two strands. The first, called Social Choice, beginning with Arrow's Impossibility Theorem, makes very few assumptions about preferences, but limits the choice of mechanisms. The second, associated with Auction Theory, places severe restrictions on preferences but enlarges the set of mechanisms considered. In both cases the class of desired mechanisms can be described by a system of linear inequalities or linear programs. Existence or non-existence can be deduced by an appeal to the Farkas lemma. In these two lectures I will give two examples of this: The first is an application to Social Choice and the second to Auction Theory.

References:

Sethuraman, Teo, and Vohra, `Integer Programming and Arrovian Social Welfare Functions', Math of OR, vol. 28, 2003

Muller and Vohra, `On Dominant Strategy Mechanisms', 2003

Lecture Notes (in preparation)