Name
Abstract | ||
|---|---|---|
A stochastic algorithm is presented for a class of optimisation problems that arise when a group of agents compete to share a single constrained resource in an optimal manner. The approach uses intermittent single-bit feedback, which indicates a constraint violation and does not require inter-agent communication. The algorithm is based on a positive matrix model of AIMD, which is extended to the nonhomogeneous Markovian case. The key feature is the assignment of back-off probabilities to the individual agents as a function of the past average access to the resource. This leads to a nonhomogeneous Markov chain in an extended state space, and we show almost sure convergence of the average access to the social optimum.
|
Year | DOI | Venue |
|---|---|---|
2019 | 10.1145/3312741 | Journal of the ACM |
Keywords | Field | DocType |
AIMD,Nonhomogeneous Markov chains,almost sure convergence,invariant measure,iterated function systems,optimisation | Applied mathematics,Iterated function system,Discrete mathematics,Convergence of random variables,Markov process,Nonnegative matrix,Computer science,Markov chain,Constraint violation,State space,Invariant measure | Journal |
Volume | Issue | ISSN |
66 | 4 | 0004-5411 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Fabian Wirth | 1 | 900 | 77.70 |
| S. Studli | 2 | 51 | 5.81 |
| Jia Yuan Yu | 3 | 168 | 25.35 |
| M. Corless | 4 | 267 | 49.21 |
| Robert Shorten | 5 | 293 | 60.79 |