Nash Bargaining Solution Allocation is Not Suitable for Datacenter Jobs

Ilya Nikolaevskiy, Andrey Lukyanenko, Andrei Gurtov

Research output: Contribution to journalArticleScientificpeer-review

1 Citation (Scopus)


The Nash Bargaining Solution (NBS) has been broadly suggested as an effective solution for the problem of fair allocation of multiple resources, namely bandwidth allocation in datacenters. In spite of being thoroughly studied, and provably strategy-proof for most scenarios, NBS-based allocation methods lack research on the strategic behavior of tenants in the case of proportionality of resource demands, which is common in datacenter workloads. We found that misbehavior is beneficial: by lying about bandwidth demands tenants can improve their allocations. We show that a sequence of selfish improvements leads to trivial demand vectors for all tenants. It essentially removes sharing incentives which are very important for datacenter networks. In this paper, we analytically prove that tenants can misbehave in 2- and 3- tenants cases. We show that misbehavior is possible in one recently proposed NBS-based allocation system if proportionality of demands is taken into account. Monte Carlo simulations were done for 2-15 tenants to show a misbehavior possibility and its impact on aggregated bandwidth. We propose to use another game-theoretic approach, namely Dominant Resource Fairness (DRF) to allocate bandwidth in the case of proportional demands. We show that this method performs significantly better than NBS after misbehavior.

Original languageEnglish
Article number1750001
Number of pages22
JournalInternational Game Theory Review
Issue number1
Publication statusPublished - 1 Mar 2017
MoE publication typeA1 Journal article-refereed


  • Dominant Resource Fairness
  • Game theory
  • Nash Bargaining Solution
  • resource allocation


Dive into the research topics of 'Nash Bargaining Solution Allocation is Not Suitable for Datacenter Jobs'. Together they form a unique fingerprint.

Cite this