.png){kind=icon}
.png){kind=icon}
Return
The Bodyguard Allocation Problem
.png){kind=icon}
PRE
AI
DOI：10.1109/TPDS.2012.165.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
In this paper, we introduce the Bodyguard Allocation Problem (BAP) game, that illustrates the behavior of processes with contradictory individual goals in distributed systems. In particular, the game deals with the conflict of interest between two classes of processes that maximize/ minimize their distance to a special process called the root. A solution of the BAP game represents a rooted spanning tree in which there exists a condition of equilibrium with maximum social welfare. We analyze the inefficiency of equilibria of the game based on both a completely cooperative and noncooperative approach. Additionally, we design two algorithms, CBAP and DBAP, that provide approximated solutions for the BAP game. We prove that both algorithms always terminate in a configuration with equilibrium and we analyze their running time based on the approach of cooperation used. We perform experimental simulations to compare the overall quality of equilibria obtained by the proposed algorithms.
Keywords:
Distributed applications
game theory
distributed algorithms
bodyguard allocation problem
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
6
Papers:
5.2K
Citations:
1.1W
View more organizations