A Semi Distributed Approach for Feasible Min-Max Fair Agent-assignment Problem with Privacy Guarantees

Abstract

In cyberphysical systems, a relevant problem is assigning agents to slots by distributed decisions capable of preserving an agent's privacy. For example, in future intelligent transportation systems, city-level coordinators may optimally assign cars (the agents) to parking slots depending on the cars' distance to final destinations in order to ensure social fairness and without disclosing or even using the car's destination information. Unfortunately, these assignment problems are combinatorial, whereas traditional solvers are exponentially complex, are not scalable, and do not ensure privacy of the agents' intended destinations. Moreover, no emphasis is placed to optimize the agents' social benefit. In this paper, the aggregate social benefit of the agents is considered by an agent-slot assignment optimization problem whose objective function is the fairness among the agents. Due to the problem's complexity, the problem is solved by an approximate approach based on Lagrange duality theory that enables the development of an iterative semidistributed algorithm. It is shown that the proposed algorithm is gracefully scalable compared to centralized methods, and that it preserves privacy in the sense that an eavesdropper will not be able to discover the destination of any agent during the algorithm iterations. Numerical results illustrate the performance and tradeoff of the proposed algorithm compared to the ideal optimal assignment and a greedy method.