CaltechTHESIS
  A Caltech Library Service

Characterizing Distribution Rules for Cost Sharing Games

Citation

Gopalakrishnan, Ragavendran (2013) Characterizing Distribution Rules for Cost Sharing Games. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/AWE2-H976. https://resolver.caltech.edu/CaltechTHESIS:06032013-104204451

Abstract

In noncooperative cost sharing games, individually strategic agents choose resources based on how the welfare (cost or revenue) generated at each resource (which depends on the set of agents that choose the resource) is distributed. The focus is on finding distribution rules that lead to stable allocations, which is formalized by the concept of Nash equilibrium, e.g., Shapley value (budget-balanced) and marginal contribution (not budget-balanced) rules.

Recent work that seeks to characterize the space of all such rules shows that the only budget-balanced distribution rules that guarantee equilibrium existence in all welfare sharing games are generalized weighted Shapley values (GWSVs), by exhibiting a specific 'worst-case' welfare function which requires that GWSV rules be used. Our work provides an exact characterization of the space of distribution rules (not necessarily budget-balanced) for any specific local welfare functions remains, for a general class of scalable and separable games with well-known applications, e.g., facility location, routing, network formation, and coverage games.

We show that all games conditioned on any fixed local welfare functions possess an equilibrium if and only if the distribution rules are equivalent to GWSV rules on some 'ground' welfare functions. Therefore, it is neither the existence of some worst-case welfare function, nor the restriction of budget-balance, which limits the design to GWSVs. Also, in order to guarantee equilibrium existence, it is necessary to work within the class of potential games, since GWSVs result in (weighted) potential games.

We also provide an alternative characterization—all games conditioned on any fixed local welfare functions possess an equilibrium if and only if the distribution rules are equivalent to generalized weighted marginal contribution (GWMC) rules on some 'ground' welfare functions. This result is due to a deeper fundamental connection between Shapley values and marginal contributions that our proofs expose—they are equivalent given a transformation connecting their ground welfare functions. (This connection leads to novel closed-form expressions for the GWSV potential function.) Since GWMCs are more tractable than GWSVs, a designer can tradeoff budget-balance with computational tractability in deciding which rule to implement.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:Cost sharing; Game theory; Marginal contribution; Nash equilibrium; Potential game; Shapley value
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Computer Science
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Wierman, Adam C.
Thesis Committee:
  • Wierman, Adam C. (chair)
  • Chandy, K. Mani
  • Ledyard, John O.
  • Ligett, Katrina A.
  • Marden, Jason R.
Defense Date:28 May 2013
Funders:
Funding AgencyGrant Number
AFOSRFA9550-09-1-0538
AFOSRFA9550-12-1-0359
ONRN00014-12-1-0643
NSFCNS-0846025
NSFCCF-1101470
Record Number:CaltechTHESIS:06032013-104204451
Persistent URL:https://resolver.caltech.edu/CaltechTHESIS:06032013-104204451
DOI:10.7907/AWE2-H976
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:7822
Collection:CaltechTHESIS
Deposited By: Ragavendran Gopalakrishnan
Deposited On:06 Jun 2013 23:09
Last Modified:04 Oct 2019 00:01

Thesis Files

[img]
Preview
PDF - Final Version
See Usage Policy.

1MB

Repository Staff Only: item control page