Fast convergence to satisfying distributions
Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence. Pages 1657-1657.
© 2005 International Joint Conferences on Artificial Intelligence
Abstract
We investigate an environment where selfinterested agents have to find high-quality service resources. Agents have common knowledge about resources which are able to provide these services. The performance of resources is measured by the satisfaction obtained by agents using them. The performance of a resource depends on its intrinsic capability and its current load. We use a satisfying rather than an optimizing framework, where agents are content to receive service quality above a threshold. We introduce a formal framework to characterize the convergence of agents to a state where each agent is satisfied with the performance of the service it is currently using. We analyzed the convergence behavior of such a system and identified a mechanism to speed up convergence.
- Sudhir K. Rustogi and Munindar P. Singh. Be Patient and Tolerate Imprecision: How Autonomous Agents can Coordinate Effectively. In Proceedings of the Six- teenth International Joint Conference on Artificial Intel- ligence, pages 512-519, Morgan Kaufmann Publishers Inc. 1999 ISBN: 1-55860-613-0 IJCAI
- Sandip Sen and Neeraj Arora and Shounak Roychowd- hury. Using limited information to enhance group sta- bility. In the journal Int. J. Hum.-Comput. Stud., Vol- ume 48, Number 1, Year 1998, Pages 69-82 ISSN 1071- 5819, Academic Press, Inc.,
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1 Introduction
Agents searching for high-quality services can use either their own interaction experience or referrals from peer agents. We assume that agents are interested in finding a quality of service which exceeds an acceptable performance threshold. The performance of a resource depends on its intrinsic characteristics and is inversely correlated to the current workload it is handling. Individual agent satisfaction depends both on the resource selected and choices made by the other agents. Two agents may have different satisfactions for the same performance level of a resource. Efficient decentralized protocols for finding satisfying resources are necessary. Reaching a suitable global state where all agents are satisfied with the resources they are using can be viewed as a coordination problem. Resource choice decisions that appear to be most appropriate for an individual may prove to be damaging for a part or the whole agent group. Selecting the locally optimal action can then increase the number of conflicts of interests where resources are shared. Besides, knowledge about the global state is likely to be inaccurate in dynamic, partially known, open environments.
Coordination in such environments is a challenging problem which, however, needs reasonably good solutions. There are two primary motivations for the current work: (a) characterize the properties of agent satisfaction functions and resource selection strategies that guarantees convergence to stable system states, and (b) providing guidelines for designing such systems with fast convergence to stable states. Our proposed, distributed coordination scheme ensures convergence to a satisfactory system state. We experimentally highlight the effect of different protocol and system parameters that influence the coordination process and expedites convergence to equilibrium states
2 Framework
Let E =< A, R, perf , L, S, Γ > where: (i) A = {ak}k=1..K is the set of agents, (ii) R = {rn}n=1..N is the set of resources, (iii) f : R × R → [0, 1], intrinsic performance function of a provider, (iv) L = A → R+, daily load assigned to agents, (v) S : A × [0, 1] → [0, 1], satisfaction function for agents, (vi) Γ = {γ1, . . . , γK}, set of satisfaction thresholds of agents. If a set Adn of agents use the resource rn on day d then the feedback received by every agent in Adn at the end of the day d is perf = f (rn, ∑a∈Adn L(a)). An agent ak ∈ Adn evaluates the performance of rn by the the satisfaction it obtained and is given by s = S(ak, perf ). An agent is satisfied if this performance s is above a threshold γk. Consequently, two agents may have different satisfactions for the same resource performance.
Agents are interested in obtaining satisfactions above a threshold. Our aim is to design an environment where every agent will have the opportunity to find satisfying resources. The following definitions formalize this idea.
Definition 1 (Distribution of agents over providers)
We call distribution of agents over resources the set D = {An}n=1..N where An is the set of agents using resource rn. The set of distributions is denoted by D.
Definition 2 (Γ-acceptable distribution) A distribution D is said to be Γ-acceptable if each agent is satisfied by the resource they use in D. The set of Γ-acceptable distributions is denoted by DΓ.
A Γ-acceptable distribution is an equilibrium concept and our goal is to develop mechanisms that enable a group of agents to converge to such a distribution. We now present two properties needed by any resource-selection algorithm to ensure convergence to satisfying distributions. In the following, Alg = {Algk}k=1..K is the set of algorithms used by agents to choose a resource and Hd denotes the set of possible histories after d days and H = ⋃+∞ d=1 Hd the set of all possible histories.
Definition 3 (Weighted directed distribution graph) : A directed graph G = (V, E, ω) is called a weighted directed distribution graph associated with Alg if and only if (i) V ⊂ D, (ii) E ∈ V × V , (iii) (D1, D2) ∈ E =⇒ ∃d ∈ N, ∃Hd ∈ Hd s.t (ω(D1, D2, Hd) ̸= 0) where ω : Hd → [01]. ω(Hd) is the probability to reach the distribution D2 given agents are in distribution D1 and they use algorithms in Alg.
In weighted directed distribution graphs, an arrow from D1 to D2 is present if it is possible to reach D2 from D1 with a non-zero probability using algorithm Alg.
Property 1 A distributed algorithm Alg stops when a Γacceptable distribution is reached.
Property 2 Let G = (V,E, ω) be the graph associated to Alg. G is such that at least one node of G is a Γ-acceptable distribution. A Γ-acceptable distribution is reachable from any distribution with a non-zero probability.
Theorem 1 Every algorithm Alg which respect Properties 1 and 2 converge to a Γ-acceptable distribution.
Theorem 2 Let ∀k = 1..K, αk : H → [0, 1]. Alg converges to a Γ-acceptable distributionif the following conditions are satisfied: (i) Alg respects Property 1, (ii) a Γacceptable distribution exists, (iii) agents are identical, (iv) agents explore with probability αk(H) if they are unsatisfied, (v) ∀k = 1..K, ∃δk > 0 s.t ∀H ∈ H αk(H) ≥ δk.
We omit the proof of the above theorems due to space limitations. Theorem 2 concludes that exploration ensures convergence. The nature of the agents, e.g., self-interested, cooperative, deceptive does not influence the existence of convergence as long as minimum exploration is guaranteed. Another strength of the theorem is that it does not require the probability of exploration to be constant. An agent may adapt this probability based on whether it believes it should explore more or less.
3 Speed of convergence
In this paper, we will reason using two axes: a measurement of goodness of a state that we will call entropy, the number of agents who can move at the same time.
Definition 4 (Entropy) Given an environment where agents are identical and resource rn has capacity Cn, we call entropy of a distribution D: E(D) = ∑Nn=1 max (0, |An| -Cn).
Each Γ-acceptable distribution has zero entropy. The lower the entropy the better the distribution since less agents are unsatisfied.
We claim that when agents choose their actions based on local perspective only, the system is likely to move from a distribution with a low entropy to one with a higher entropy and vice and versa.Such oscillations can be controlled by limiting the number of agents moving simultaneously, Kmove. We experimentally show Kmove has a critical influence on the convergence speed. A high value for Kmove leads to system oscillations and hence is undesirable. A low value for Kmove guides the system toward a Γ-acceptable distribution but the convergence process slows down progressively when approaching a perfectly coordinated distribution. The decrease in entropy is almost monotonic. With an intermediate value of Kmove, entropy decreases at a faster rate, but has more fluctuations.
4 Related work
Coordinated search of resources is a challenging problem in multiagent systems. Sen et al [2] show that information can negatively impact agent coordination to find balanced distribution among resources. Rustogi & Singh [1] prove that high inertia hasten convergence when knowledge increases but low inertia performs better with little knowledge.
We believe that a more comprehensive understanding of system behavior can be obtained by studying system entropy and controlling the number of simultaneously moving agents, Kmove. Our approach provides a more detailed characterization of such systems while confirming the general conclusions from Rustogi & Singh [1].
5 Conclusion
We studied the properties of agent decision functions and their interaction with the distribution of agents over resources so that stable distributions, with no incentive for any agent to move, are produced. We characterized the behavior of such a system of agents in terms of the entropy of the system. We showed that that the entropy of a system can be steadily reduced, and hence convergence accelerated, by increasing the inertia or reducing the number of agents that can move simultaneously. A distributed implementation of controlling inertia is proposed in the form of an exploration parameter. We are evaluating the scale-up property of such a system. Our work provides guidance to selection of system protocols and parameters, including satisfaction functions, exploration attitude, etc.
@inproceedings{ijcai2005p338,
title = {Fast convergence to satisfying distributions},
author = {Candale, Teddy and Sen, Sandip},
booktitle = {Proceedings of the Nineteenth International Joint Conference on
Artificial Intelligence, {IJCAI-05}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Leslie Pack Kaelbling and Alessandro Saffiotti},
pages = {1657--1657},
year = {2005},
url = {https://ijcai.org/proceedings/2005/338},
}
TY - CPAPER TI - Fast convergence to satisfying distributions AU - Candale, Teddy AU - Sen, Sandip T2 - Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, IJCAI-05 PB - International Joint Conferences on Artificial Intelligence PY - 2005 SP - 1657 EP - 1657 UR - https://ijcai.org/proceedings/2005/338 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: