Resource Allocation Polytope Games: Uniqueness of Equilibrium, Price of Stability, and Price of Anarchy

Abstract : We consider a two-player resource allocation polytope game, in which the strategy of a player is restricted by the strategy of the other player, with common coupled constraints. With respect to such a game, we formally introduce the notions of independent optimal strategy profile, which is the profile when players play optimally in the absence of the other player; and common contiguous set, which is the set of top nodes in the preference orderings of both the players that are exhaustively invested on in the independent optimal strategy profile. We show that for the game to have a unique PSNE, it is a necessary and sufficient condition that the independent optimal strategies of the players do not conflict, and either the common contiguous set consists of at most one node or all the nodes in the common contiguous set are invested on by only one player in the independent optimal strategy profile. We further derive a socially optimal strategy profile, and show that the price of anarchy cannot be bound by a common universal constant. We hence present an efficient algorithm to compute the price of anarchy and the price of stability, given an instance of the game. Under reasonable conditions, we show that the price of stability is 1. We encounter a paradox in this game that higher budgets may lead to worse outcomes
Type de document :
Communication dans un congrès
AAAI 2018 - 32nd Conference on Artificial Intelligence, Feb 2018, New Orleans, United States. pp.997-1006, 2018, 〈https://aaai.org/Conferences/AAAI-18/〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01712284
Contributeur : Swapnil Dhamal <>
Soumis le : mardi 20 novembre 2018 - 10:41:00
Dernière modification le : jeudi 22 novembre 2018 - 01:14:00

Fichier

ODSN_nash_HAL.pdf
Accord explicite pour ce dépôt

Identifiants

  • HAL Id : hal-01712284, version 2

Citation

Swapnil Dhamal, Walid Ben-Ameur, Tijani Chahed, Eitan Altman. Resource Allocation Polytope Games: Uniqueness of Equilibrium, Price of Stability, and Price of Anarchy. AAAI 2018 - 32nd Conference on Artificial Intelligence, Feb 2018, New Orleans, United States. pp.997-1006, 2018, 〈https://aaai.org/Conferences/AAAI-18/〉. 〈hal-01712284v2〉

Partager

Métriques

Consultations de la notice

13

Téléchargements de fichiers

14