Fair Scheduling in Common-Pool Games by Aspiration Learning

Abstract : We propose a distributed learning algorithm for fair scheduling in common-pool games. Common-pool games are strategic-form games where multiple agents compete over utilizing a limited common resource. A characteristic example is the medium access control problem in wireless communications, where multiple users need to decide how to share a single communication channel so that there are no collisions (situations where two or more users use the medium at the same time slot). We introduce a (payoff-based) learning algorithm, namely aspiration learning, according to which agents learn how to play the game based only on their own prior experience, i.e., their previous actions and received rewards. Decisions are also subject to a small probability of mistakes (or mutations). We show that when all agents apply aspiration learning, then as time increases and the probability of mutations goes to zero, the expected percentage of time that agents utilize the common resource is equally divided among agents, i.e., fairness is established. When the step size of the aspiration learning recursion is also approaching zero, then the expected frequency of collisions approaches zero as time increases.
Type de document :
Communication dans un congrès
WiOpt'12: Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks, May 2012, Paderborn, Germany. pp.386-390, 2012
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00764167
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mercredi 12 décembre 2012 - 14:58:52
Dernière modification le : mercredi 19 décembre 2012 - 15:15:31
Document(s) archivé(s) le : mercredi 13 mars 2013 - 03:54:11

Fichier

p386-chasparis.pdf
Accord explicite pour ce dépôt

Identifiants

  • HAL Id : hal-00764167, version 1

Collections

Citation

Georgios Chasparis, Ari Arapostathis, Jeff Shamma. Fair Scheduling in Common-Pool Games by Aspiration Learning. WiOpt'12: Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks, May 2012, Paderborn, Germany. pp.386-390, 2012. 〈hal-00764167〉

Partager

Métriques

Consultations de la notice

75

Téléchargements de fichiers

56