The IPCO X Summer School
3rd Summer School on Integer Programming and Combinatorial Optimization
will be held at
idea of a
summer school immediately preceding the IPCO meeting was introduced at
the occasion of IPCO
Please visit the IPCO X program page for a schedule and other details.
Incentives and Internet Computation
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.
The Price of Anarchy
"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
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.
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.
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)