Advanced

Fair Scheduling in Common-Pool Games by Aspiration Learning

Chasparis, Georgios LU ; Arapostathis, Ari and Shamma, Jeff S. (2012) 2012 10th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt) In 2012 10th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt) p.386-390
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... (More)
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. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
Aspiration learning, medium-access control, common-pool games, resource allocation
in
2012 10th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt)
editor
Alpcan, Tansu and Koutsopoulos, Iordanis
pages
386 - 390
publisher
IEEE--Institute of Electrical and Electronics Engineers Inc.
conference name
2012 10th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt)
external identifiers
  • Scopus:84866901588
ISBN
978-1-4673-2294-2
language
English
LU publication?
yes
id
2ffc4f13-5d2f-4f8e-9f33-f184f69b663b (old id 2435455)
date added to LUP
2012-04-11 08:51:52
date last changed
2016-10-13 04:39:22
@misc{2ffc4f13-5d2f-4f8e-9f33-f184f69b663b,
  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.},
  author       = {Chasparis, Georgios and Arapostathis, Ari and Shamma, Jeff S.},
  editor       = {Alpcan, Tansu and Koutsopoulos, Iordanis},
  isbn         = {978-1-4673-2294-2},
  keyword      = {Aspiration learning,medium-access control,common-pool games,resource allocation},
  language     = {eng},
  pages        = {386--390},
  publisher    = {ARRAY(0x936f038)},
  series       = {2012 10th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt)},
  title        = {Fair Scheduling in Common-Pool Games by Aspiration Learning},
  year         = {2012},
}