Ph.D. Thesis

The emergence of large scale distributed computing networks has given increased prominence to a number of algorithmic concerns, including the need to handle dynamic membership, selfishness, and incomplete information. In this document, we outline our explorations into these algorithmic issues.

We first present our results on the analysis of a graph-based coupon collector process related to load balancing for networks with dynamic membership. In addition to extending the study of the coupon collector process, our results imply load balancing properties of certain distributed hash tables.

Second, we detail our results on worst case payoffs when playing buyer-supplier games, against many selfish, collaborating opponents. We study optimization over the set of core vectors. We show both positive and negative results on optimizing over the cores of such games. Furthermore, we introduce and study the concept of focus point price, which answers the question: If we are constrained to play in equilibrium, how much can we lose by playing the wrong equilibrium?

Finally, we present our analysis of a revenue management problem with incomplete information, the online weighted transversal matroid matching problem. In specific, we present an algorithm that delivers expected revenue within a constant of optimal in the online setting. Our results use a novel algorithm to generalize several results known for special cases of transversal matroids.


Comments and Questions

Add a comment

Add A Comment

Visual Captcha
Code in the picture:
Your Name(*):

© Copyright 2004-2019 - Ned Dimitrov