Fair scheduling in common-pool games by aspiration learning

Georgios C. Chasparis*, Ari Arapostathis, Jeff S. Shamma

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

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.

Original languageEnglish (US)
Title of host publication2012 10th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, WiOpt 2012
Pages386-390
Number of pages5
StatePublished - 2012
Externally publishedYes
Event2012 10th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, WiOpt 2012 - Paderborn, Germany
Duration: May 14 2012May 18 2012

Other

Other2012 10th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, WiOpt 2012
CountryGermany
CityPaderborn
Period05/14/1205/18/12

Keywords

  • Aspiration learning
  • Common-pool games
  • Medium-access control
  • Resource allocation

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Control and Optimization
  • Modeling and Simulation

Fingerprint

Dive into the research topics of 'Fair scheduling in common-pool games by aspiration learning'. Together they form a unique fingerprint.

Cite this