Nonhomogeneous Place-dependent Markov Chains, Unsynchronised AIMD, and Optimisation | Zendy

Fabian Wirth | Zendy; Sonja Stüdli | Zendy; Jia Yuan Yu | Zendy; M. Corless | Zendy; Robert Shorten | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Nonhomogeneous Place-dependent Markov Chains, Unsynchronised AIMD, and Optimisation

Author(s) -

Fabian Wirth,

Sonja Stüdli,

Jia Yuan Yu,

M. Corless,

Robert Shorten

Publication year - 2019

Publication title -

journal of the acm

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.672

H-Index - 134

eISSN - 1557-735X

pISSN - 0004-5411

DOI - 10.1145/3312741

Subject(s) - markov chain , constraint (computer aided design) , mathematical optimization , convergence (economics) , computer science , markov process , resource (disambiguation) , key (lock) , class (philosophy) , mathematics , artificial intelligence , machine learning , computer network , statistics , geometry , economics , economic growth , computer security

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research