Abstract

A resource allocation game with identical preferences is considered where each player, as a node of an undirected unweighted network, tries to minimize his or her cost by caching an appropriate resource. Using a generalized ordinal potential function, a polynomial time algorithm is devised in order to obtain a pure-strategy Nash equilibrium (NE) when the number of resources is limited or the network has a high edge density with respect to the number of resources. Moreover, an algorithm to approximate any NE of the game over general networks is provided, and the results are extended to games with arbitrary cache sizes. Finally, a connection between graph coloring and the NE points has been established.

Original languageEnglish (US)
Pages (from-to)536-547
Number of pages12
JournalIEEE Transactions on Control of Network Systems
Volume5
Issue number1
DOIs
StatePublished - Mar 2018

Fingerprint

Nash Equilibrium
Resource Allocation
Resource allocation
Game
Resources
Coloring
Graph Coloring
Caching
Polynomials
Potential Function
Equilibrium Point
Cache
Polynomial-time Algorithm
Minimise
Costs
Arbitrary
Vertex of a graph
Strategy

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Signal Processing
  • Computer Networks and Communications
  • Control and Optimization

Cite this

@article{22af58ff5a42408dbd3bc2c01b73c480,
title = "Pure Nash Equilibrium in a Capacitated Selfish Resource Allocation Game",
abstract = "A resource allocation game with identical preferences is considered where each player, as a node of an undirected unweighted network, tries to minimize his or her cost by caching an appropriate resource. Using a generalized ordinal potential function, a polynomial time algorithm is devised in order to obtain a pure-strategy Nash equilibrium (NE) when the number of resources is limited or the network has a high edge density with respect to the number of resources. Moreover, an algorithm to approximate any NE of the game over general networks is provided, and the results are extended to games with arbitrary cache sizes. Finally, a connection between graph coloring and the NE points has been established.",
author = "Etesami, {Seyed Rasoul} and Basar, {M Tamer}",
year = "2018",
month = "3",
doi = "10.1109/TCNS.2016.2631440",
language = "English (US)",
volume = "5",
pages = "536--547",
journal = "IEEE Transactions on Control of Network Systems",
issn = "2325-5870",
publisher = "IEEE CONTROL SYSTEMS SOCIETY",
number = "1",

}

TY - JOUR

T1 - Pure Nash Equilibrium in a Capacitated Selfish Resource Allocation Game

AU - Etesami, Seyed Rasoul

AU - Basar, M Tamer

PY - 2018/3

Y1 - 2018/3

N2 - A resource allocation game with identical preferences is considered where each player, as a node of an undirected unweighted network, tries to minimize his or her cost by caching an appropriate resource. Using a generalized ordinal potential function, a polynomial time algorithm is devised in order to obtain a pure-strategy Nash equilibrium (NE) when the number of resources is limited or the network has a high edge density with respect to the number of resources. Moreover, an algorithm to approximate any NE of the game over general networks is provided, and the results are extended to games with arbitrary cache sizes. Finally, a connection between graph coloring and the NE points has been established.

AB - A resource allocation game with identical preferences is considered where each player, as a node of an undirected unweighted network, tries to minimize his or her cost by caching an appropriate resource. Using a generalized ordinal potential function, a polynomial time algorithm is devised in order to obtain a pure-strategy Nash equilibrium (NE) when the number of resources is limited or the network has a high edge density with respect to the number of resources. Moreover, an algorithm to approximate any NE of the game over general networks is provided, and the results are extended to games with arbitrary cache sizes. Finally, a connection between graph coloring and the NE points has been established.

UR - http://www.scopus.com/inward/record.url?scp=85044514428&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85044514428&partnerID=8YFLogxK

U2 - 10.1109/TCNS.2016.2631440

DO - 10.1109/TCNS.2016.2631440

M3 - Article

AN - SCOPUS:85044514428

VL - 5

SP - 536

EP - 547

JO - IEEE Transactions on Control of Network Systems

JF - IEEE Transactions on Control of Network Systems

SN - 2325-5870

IS - 1

ER -