Selfishness in strategic resource allocation problems

Ravindran Vijayalakshmi, Vipin; Peis, Britta (Thesis advisor); Woeginger, Gerhard (Thesis advisor); Skopalik, Alexander (Thesis advisor)

Aachen : RWTH Aachen University (2021, 2022)
Dissertation / PhD Thesis

Dissertation, RWTH Aachen University, 2021

Abstract

The advent of modern technology in the communication and the transportation industry encouraged the proliferation of its consumer base. Due to the rising demand on many of these modern applications and scenarios, centralization was no longer deemed a viable approach for managing their operations. These days, many modern infrastructures are designed to allow for multiple strategic users who make decisions that suit their individual utility. Consequently, non-cooperative game theory has emerged as an essential tool in analyzing and predicting the outcome of decentralized systems. We study various algorithmic aspects arising due to strategic behavior among multiple non-cooperative users in several classes of resource allocation problems using a game theoretic approach. The classes of strategic games we study, succinctly represent many of the socio-economic scenarios arising due to decentralization. At first, we consider congestion games which are often used to model various scenarios of resource allocation by non-cooperative users. In these games, the resources could possibly correspond to edges in a road or communication network, machines in distributed systems, etc., and have cost functions with a diseconomy of scale. The players in a congestion game then iteratively pick feasible subsets of resources that maximize their individual utility. The players continue to strategically deviate, if necessary, until the game converges to a widely studied solution concept known as the pure Nash equilibrium. The hardness of computing a pure Nash equilibrium in congestion games has been of significant interest in the scientific community over the past two decades. As computing an exact pure Nash equilibrium is known to be hard, we study a weaker notion of pure Nash equilibrium called an approximate pure Nash equilibrium and to that extend, analyze an efficient algorithm that computes approximate pure Nash equilibria in congestion games with an approximation guarantee that is by far the best known in the literature. The impact of non-coordination among the users on the self emerging solutions of a congestion game are provably bad. One of the many approaches used to alleviate the effects of non-cooperativeness is the introduction of taxes. Economic incentives have provably shown to influence the users to induce solutions that are significantly closer to the optimal solution. We present a mechanism to compute load dependent taxes for congestion games that are robust against the changes in the number of users and resources in the game.In spite of being the predominant class of games to model resource allocation problems involving different users, congestion games lack an element of time dependence, especially in certain application scenarios such as the road transportation network. It is quite unnatural to assume that all users of a road section experience the same congestion. A cost sharing mechanism must also take into account the order in which a resource processes the users assigned to it. We extend congestion games with resource dependent priority list to model the impact of fixed order scheduling on the strategic behavior of users. We then study the question of existence and inefficiency of pure Nash equilibria in the extended model. It is quite natural to then consider a scheduling game on parallel machines, in which jobs try to minimize their completion time by choosing a machine to be processed on. Each machine uses an individual priority list to decide on the order according to which the jobs on the machine are processed. Here, we study the existence of a pure Nash equilibrium and characterize classes of instances in which a pure Nash equilibrium is guaranteed to exist. For each of these classes, we settle algorithmic questions such as tractability and the inefficiency of pure Nash equilibria. Finally, we study the impact of non-cooperative users in a large scale distributed communication network such as the peer-to-peer overlay network, where the existence of non-cooperative and malicious users is considered as a rule rather than an exception. Due to its distributed architecture, users or peers are allowed to join and leave without admission control. A necessary condition to maintain the stability of a distributed overlay network that allows for efficient storage and retrieval of information is to have certain degree of commitment and coordination among the peers in the network. Moreover, the lack of a centralized mechanism entails that the peers in the network coordinate among themselves. However, peers joining and leaving the network in a non-coordinated manner leads to instability and loss of information. We model this scenario using an adversary and present an algorithm that is able to ensure stability in the network in the presence of large fraction of non-cooperative peers.

Institutions

• UnRAVeL Research Training Group [080060]
• Department of Computer Science [120000]
• Chair of Computer Science 1 (Algorithms and Complexity) [121110]
• Chair of Management Science [815110]