Date of Award

Spring 1-1-2014

Document Type

Thesis

Degree Name

Master of Science (MS)

Department

Electrical, Computer & Energy Engineering

First Advisor

Jason Marden

Second Advisor

Eric Frew

Third Advisor

Lijun Chen

Abstract

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.

Share

COinS