Design and analysis of algorithms for non-cooperative environments
Design and analysis of algorithms for non-cooperative environments
Date
Authors
Βουδούρης, Αλέξανδρος Ανδρέας
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
This thesis studies issues related to problems that arise in large-scale distributed environments with non-cooperative users, who act strategically and compete with each other to maximize their personal payoffs.
For instance, imagine a scenario where a set of users compete over a resource, such as the bandwidth of a communication link or advertisement slots when keywords are queried in search engines on the Internet. A mechanism takes input from all participating users (which represents their preferences) and outputs an allocation of the resource to them (it distributes the bandwidth or assigns slots). Each user aims to select her input to the mechanism in order to satisfy her personal objectives (possibly by misreporting her true preferences), without caring about the social welfare which we would like to maximize as the designers of the mechanism. Therefore, this behavior induces a strategic game among the users who act as players and sequentially change their strategies until they reach an equilibrium state (if one exists) from which no one has any incentive to deviate. Due to the strategic behavior of the users, the equilibrium that is reached may be of low quality in terms of some objective function like the social welfare, compared to what could happen if a central authority dictated the strategies of the users. The price of anarchy and stability are two quantification measures of this kind of inefficiency at equilibrium.
Our main goal in this thesis is to understand the advantages and constraints of the strategic games that arise in non-cooperative environments as means of computation. What can they compute and how well can they compute it? Is it possible to alter the rules of the game and incentivize the players to truthfully report their preferences? We answer to such questions related to equilibrium computation, price of anarchy and stability estimation, and truthful mechanism design for many interesting and important classes of problems. In particular, we study resource allocation with budget constraints, opinion formation, ownership transfer with expert advice, and revenue maximization in randomized combinatorial sales.
Description
Keywords
Strategic games, Price of anarchy, Mechanism design, Approximation algorithms, Resource allocation, Opinion formation, Ownership transfer, Asymmetric information