Harvard Theory of Computation Seminar
Flow Allocation Games: Pricing, Equilibria
and Fast
Convergence
John Byers, Boston University
Place and Time: Monday 4/24, Refreshments at 2:30, talk at 2:45. Maxwell Dworkin 319.
ABSTRACT
In this talk, I will begin with a quick tour of the theory and
networking practice of distributed flow allocation problems:
given a fixed capacitated network in which a set of long-lived
flows is given and the routes these flows use are pre-ordained
and fixed throughout, assign rates to the flows to achieve a
global objective using a distributed algorithm.
I will then focus on a game-theoretic version of flow allocation
in which flows play an iterative game running in a set of
distributed rounds. In each round, each flow bids for network
resources by distributing a fixed set of tokens across links in
its path, and link bandwidth is then apportioned in proportion
to the number of tokens a flow has placed on the link. In
subsequent rounds, the flows may then reallocate their set of
tokens across links to improve their allocation. We characterize
the Nash equilibria of this game, relate them to the equilibria in
the TCP Vegas analysis, and describe strategies which converge to
the equilibria.
Joint work with Danny Raz (Technion).