Borodin, Allan (University of Toronto)

Purpose

This proposal concerns a number of different research areas. However, my recent research interests are often motivated by the question as to what can and cannot be computed by ``conceptually simple algorithms''. In this regard, my primary interest concerns conceptually simple approximation algorithms for combinatorial optimization problems. More specifically, I am studying various forms and extensions of online and greedy algorithms, primal dual algorithms, dynamic programming algorithms, local algorithms, and local search. And most recently, I have been concerned with domains where rather naive randomization can often outperform more ``principled'' and sophisticated deterministic algorithms. As examples, we can ask, what is the simplest deterministic one pass algorithm that can match or surpass the 3/4 approximation ratio achieved by various algorithms for the Max-Sat problem and the same question as to exceeding the 1-1/e approximation for online bipartite matching. In particular, I am studying parallel and multi-pass online and greedy algorithms. It has recently been shown that such algorithms can be sometimes be derived from randomized algorithms. However, so far there are only a couple of examples where randomized algorithms have been successfully de-randomized to become parallel algorithms. Furthermore, when such a de-randomization is possible, we do not know how much parallelism is required. My interest in conceptually simple algorithms has led me to various problems in the field of algorithmic game theory/mechanism design (AGT). One fundamental problem is when can good approximations be turned into good mechanisms given that self-interested agents are providing the inputs. For example, in auctions the underlying allocation algorithms needs to be conceptually simple for the auction mechanism to be adopted in practice. Perhaps the simplest type of auction mechanism is a posted price mechanism where agents (in some order) are offered prices for various bundles of goods and then must make a ``take it or leave it'' choice as to what to purchase. How such a mechanism price items or when there is no mechanism what are the eqquilibrium prices and what are the dynamics that can lead to equilibria. In the related field of social choice theory, I am also considering algorithmic questions concerning the use of various voting rules. And in other somewhat related fields, I am also interested in how influence spreads in a social network and how one achieves stable matchings given only partial (e.g. probabilistic) information as to preferences.