Graduate Thesis Or Dissertation


Minimizing Price of Anarchy in Resource Allocation Games Public Deposited

Downloadable Content

Download PDF
  • Resource allocation refers to problems where there is a set of resources to be allocated efficiently among a group of agents. The distributed nature of resource allocation motivates modeling it as a distributed control problem. One of the strong modeling frameworks for distributed control problems is the game theoretic framework. Game theory provides mathematical models that aid in studying the aggregate behavior of a group of decision makers. The main challenge in modeling a distributed optimization problem as a game is the design of agents' utility functions. A utility function is designed as a distribution rule of some welfare; and the goal is to distribute the welfare in a way that incentivizes players to land in a "good" equilibrium point. The ratio between the performance of the worst possible equilibrium point and the optimal outcome of a game is called the price of anarchy. A distribution rule that distributes the welfare exactly is called budget-balanced, and one that distributes the welfare with excess is said to satisfy a relaxed budget-balance condition. On the other hand, if it causes a deficit we say that it violates the budget-balance condition. In this thesis, we study the design of utility functions in resource allocation games that minimize the price of anarchy. We compare two families of utility functions that guarantee equilibrium existence, namely the Shapley value and the marginal contribution. The Shapley value is a budget-balanced distribution rule, while the marginal contribution satisfies the relaxed budget-balance condition given that the welfare being distributed is submodular. We derive price of anarchy bounds for the marginal contribution utility in resource allocation games and compare them to those for the Shapley value, derived in the literature. We also perform a small-scale study for a wider range of utility functions. Lastly, we examine the connection between the price of anarchy and the satisfiability of the budget-balance conditions of the utility designs. We show that violating the budget-balance condition worsens the price of anarchy.
Date Issued
  • 2014
Academic Affiliation
Committee Member
Degree Grantor
Commencement Year
Last Modified
  • 2019-11-18
Resource Type
Rights Statement