A Two-Player Coalition Cooperative Scheme for the Bodyguard Allocation Problem

We address the bodyguard allocation problem (BAP), an optimization problem that illustrates the conflict of interest between two classes of processes with contradictory preferences within a distributed system. While a class of processes prefers to minimize its distance to a particular process called...

Full description

Saved in:
Bibliographic Details
Published in:Journal of computer science and technology 2018-07, Vol.33 (4), p.823-837
Main Authors: Fernández-Zepeda, José Alberto, Brubeck-Salcedo, Daniel, Fajardo-Delgado, Daniel, Zatarain-Aceves, Héctor
Format: Article
Language:English
Subjects:
Algorithms
Analysis
Artificial Intelligence
Computer networks
Computer Science
Data Structures and Information Theory
Economic models
Empirical analysis
Game theory
Graph theory
Information Systems Applications (incl.Internet)
Regular Paper
Software Engineering
Theory of Computation
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We address the bodyguard allocation problem (BAP), an optimization problem that illustrates the conflict of interest between two classes of processes with contradictory preferences within a distributed system. While a class of processes prefers to minimize its distance to a particular process called the root, the other class prefers to maximize it; at the same time, all the processes seek to build a communication spanning tree with the maximum social welfare. The two state-of-the-art algorithms for this problem always guarantee the generation of a spanning tree that satisfies a condition of Nash equilibrium in the system; however, such a tree does not necessarily produce the maximum social welfare. In this paper, we propose a two-player coalition cooperative scheme for BAP, which allows some processes to perturb or break a Nash equilibrium to find another one with a better social welfare. By using this cooperative scheme, we propose a new algorithm called FFC-BAP S for BAP. We present both theoretical and empirical analyses which show that this algorithm produces better quality approximate solutions than former algorithms for BAP.
ISSN:1000-9000
1860-4749
DOI:10.1007/s11390-018-1858-8