Algorithms for Game-Theoretic Environments

Sgouritsa, A (2017) Algorithms for Game-Theoretic Environments. PhD thesis, University of Liverpool.

Text 200832199_May2017.pdf - Unspecified Download (1MB)

Abstract

Game Theory constitutes an appropriate way for approaching the Internet and modelling situations where participants interact with each other, such as networking, online auctions and search engine’s page ranking. Mechanism Design deals with the design of private-information games and attempts implementing desired social choices in a strategic setting. This thesis studies how the efficiency of a system degrades due to the selfish behaviour of its agents, expressed in terms of the Price of Anarchy (PoA). Our objective is to design mechanisms with improved PoA, or to determine the exact value of the PoA for existing mechanisms for two well-known problems, Auctions and Network Cost-Sharing Design. We study three different settings of auctions, combinatorial auction, multi- unit auction and bandwidth allocation. The combinatorial auction constitutes a fundamental resource allocation problem that involves the interaction of selfish agents in competition for indivisible goods. Although it is well-known that by using the VCG mechanism the selfishness of the agents does not affect the efficiency of the system, i.e. the social welfare is maximised, this mechanism cannot generally be applied in computationally tractable time. In practice, several simple auctions (lacking some nice properties of the VCG) are used, such as the generalised second price auction on AdWords, the simultaneous ascending price auction for spectrum allocation, and the independent second-price auction on eBay. The latter auction is of particular interest in this thesis. Precisely, we give tight bounds on the PoA when the goods are sold in independent and simultaneous first-price auctions, where the highest bidder gets the item and pays her own bid. Then, we generalise our results to a class of auctions that we call bid-dependent auctions, where the goods are also sold in independent and simultaneous auctions and further the payment of each bidder is a function of her bid, even if she doesn’t get the item. Overall, we show that the first-price auction is optimal among all bid-dependent auctions. The multi-unit auction is a special case of combinatorial auction where all items are identical. There are many variations: the discriminatory auction, the uniform price auction and the Vickrey multi-unit auction. In all those auctions, the goods are allocated to the highest marginal bids, and their difference lies on the pricing scheme. Our focus is on the discriminatory auction, which can be seen as the variant of the first-price auction adjusted to multi-unit auctions. The bandwidth allocation is equivalent to auctioning divisible resources. Allocating network resources, like bandwidth, among agents is a canonical problem in the network optimisation literature. A traditional model for this problem was proposed by Kelly [1997], where each agent receives a fraction of the resource proportional to her bid and pays her own bid. We complement the PoA bounds known in the literature and give tight bounds for a more general case. We further show that this mechanism is optimal among a wider class of mechanisms. We further study design issues for network games: given a rooted undirected graph with nonnegative edge costs, a set of players with terminal vertices need to establish connectivity with the root. Each player selects a path and the global objective is to minimise the cost of the used edges. The cost of an edge may represent infrastructure cost for establishing connectivity or renting expense, and needs to be covered by the users. There are several ways to split the edge cost among its users and this is dictated by a cost-sharing protocol. Naturally, it is in the players best interest to choose paths that charge them with small cost. The seminal work of Chen et al. [2010] was the first to address design questions for this game. They thoroughly studied the PoA for the following informational assumptions. i) The designer has full knowledge of the instance, that is, she knows both the network topology and the players’ terminals. ii) The designer has no knowledge of the underlying graph. Arguably, there are situations where the former assumption is too optimistic while the latter is too pessimistic. We propose a model that lies in the middle-ground; the designer has prior knowledge of the underlying metric, but knows nothing about the positions of the terminals. Her goal is to process the graph and choose a universal cost-sharing protocol that has low PoA against all possible requested subsets. The main question is to what extent prior knowledge of the underlying metric can help in the design. We first demonstrate that there exist graph metrics where knowledge of the underlying metric can dramatically improve the performance of good network cost-sharing design. However, in our main technical result, we show that there exist graph metrics for which knowing the underlying metric does not help and any universal protocol matches the bound of Chen et al. [2010] which ignores the graph metric. We further study the stochastic and Bayesian games where the players choose their terminals according to a probability distribution. We showed that in the stochastic setting there exists a priority protocol that achieves constant PoA, whereas the PoA under the the Bayesian setting can be very high for any cost- sharing protocol satisfying some natural properties.

Item Type:	Thesis (PhD)
Uncontrolled Keywords:	Price of Anarchy, Auctions, Network Cost-Sharing Design
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	19 Dec 2017 09:57
Last Modified:	19 Jan 2023 06:59
DOI:	10.17638/03008454
Supervisors:	Christodoulou, G
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3008454