MAGIKS: Fair Multi-Resource Allocation Game Induced by Kalai-Smorodinsky Bargaining Solution

Erfan Meskar, Ben Liang

Abstract

We study the problem of fair and efficient mechanism design for allocating multiple resources in multiple servers among a set of users with Leontief utilities. This problem is motivated by a mobile edge computing environment where each mobile user cannot establish a wireless connection simultaneously to multiple edge servers. Each user is a selfish utility maximizing agent that chooses a single server for its job execution. When a server is shared by multiple users, a resource allocation rule decides the utility that each user must receive. Our goal is to design a mechanism that always admits a Nash Equilibrium (NE), i.e., a state where no user has incentive to change its server, that (1) can be reached in polynomial time and (2) provides fair and efficient resource allocation. We propose the Multi-resource Allocation Game Induced by Kalai-Smorodinsky bargaining solution (MAGIKS) and prove that under discrete resource demands it finds an NE in $\mathcal {O}({\textrm {poly}(n)})$ moves for any fixed server configuration, where $n$ is the number of users. Furthermore, MAGIKS satisfies envy-freeness, sharing incentive, and Pareto optimality on each server. Regarding fairness among users in different servers, we prove that MAGIKS satisfies 2-approximate envy-freeness and maximin share guarantee. Moreover, we show that 2-approximate envy-freeness is the best that any mechanism that satisfies local Pareto optimality can achieve at its NEs.
BibTeX
@article{meskar2022magiks,
  author = {Erfan Meskar and Ben Liang},
  title = {{MAGIKS: Fair Multi-Resource Allocation Game Induced by Kalai-Smorodinsky Bargaining Solution}},
  journal = {IEEE Open J. Commun. soc},
  year = {2022},
  doi = {10.1109/ojcoms.2022.3169969},
}

Loading related content...

Figure