Misbehavior in Nash Bargaining Solution Allocation

Abstract

Nash Bargaining Solution (NBS) has been broadlysuggested as an efficient solution for problem of fair allocation ofmultiple resources, namely bandwidth allocation in datacenters.In spite of being thoroughly studied, and provably strategyprooffor most scenarios, NBS-based allocation methods lack researchon strategic behavior of tenants in case of proportionalityof resource demands, which is common in datacenter workloads.We found that misbehavior is beneficial: by lying aboutbandwidth demands tenants can improve their allocations. Weshow that the sequence of selfish improvements leads to trivialdemand vectors for all tenants. It essentially breaks sharingincentives which are very important for datacenter networks.We analytically prove that tenants can misbehave for 2 and 3tenants cases.We show that misbehavior is possible in one recently proposedNBS-based allocation system if demands proportionality is takeninto account. Monte-Carlo simulations were done for 2 --- 15tenants to show a misbehavior possibility and its impact onaggregated bandwidth.We propose to use another game-theoretic approach to allocatebandwidth in case of proportional demands. That method performssignificantly better on average than NBS after misbehavior.