Selfishness and uncertainty: successful strategies in algorithmic game theory

The thesis consists of three parts, which come from somewhat different branches of algorithmic game theory and focus on aspects of selfishness and uncertainty to different degrees. We provide the following results: First, we present a simple and natural correlated-rounding technique to obtain truthful-in-expectation mechanisms for two-sided allocation problems with tree structure. From the domain of packing problems, we outline the technique for the generalized assignment problem, where it results in a 2-approximation for social welfare. In contrast to some previous work, we maintain exact truthfulness. From the covering domain, we apply the technique to the example of restricted-related scheduling, where it matches the best-known algorithm without truthfulness and again achieves a 2-approximation. Second, we consider the weighted bipartite matching problem, simply referred to as the assignment problem in the field of operations research. For its online version in the random order model, there exist strategies with small constant competitive ratios, including an optimal e-competitive algorithm. However, incentive-compatible mechanisms fall short of such near-optimal solutions, and the best-known guarantee here achieves a competitive ratio logarithmic in the number of vertices. We present a simple, truthful mechanism achieving optimal competitive ratio of e, and close this gap between online algorithms and mechanism design. Finally, we study a variation of the classic multi-armed bandits problem. In contrast to the common assumption that losses of actions are either stochasticor adversarial, we examine the case that they also show a trend structure. When this is true, we give a general framework combinable with various well-known bandit algorithms, like Exp3. We achieve a new, state-of-the-art regret guarantee with respect to a switching strategy for the classic problem, and a similar one for the problem variant where m actions are chosen per round. This guarantee is a significant improvement over the conventional benchmark