Price of Anarchy in Capacitated Selfish Replication Game
Date Issued
2015
Date
2015
Author(s)
Wu, You-Guan
Abstract
The peer-to-peer (P2P) model is one of the most popular a decentralized architecture to share resources among others without use the centralized administrative server. Each node is an end-user who has the ability to determine which object to provide to other end-users. To cache object or not, that is the question. The assignment on whether each node should cache object or not can impact the performance of the network. All end-users tries to optimize their own benefit, that is, we can''t control end-user''s strategy (cache or not cache), so, it''s hard to optimize the performance of the P2P file-sharing overlay network due to the selfish strategy. We consider that the limit storage to servers and propose the 2-CSR game and the 2-CSRP game. We propose a FPNE algorithm to find a stable solution and prove that the stable solution (Nash equilibrium) always exists in the 2-CSR game. We use the Price of Anarchy (PoA) and the Optimistic Price of Anarchy (OPoA) to measure the system performance which is impacted by the strategy of selfish players. We observe that both the PoA and the OPoA may be inefficient in the 2-CSR game, so we use the payment mechanism to improve the OPoA (we call it the 2-CSRP game).
Subjects
Game Theory
Algorithm
Mechanism Design
Large-Scale Systems
Computer Architecture
Computer Network
Type
thesis