15974834
Learning Pareto-optimal Solutions in 2x2 Conflict Games
Multiagent learning literature has investigated iterated two-player games to develop mechanisms that allow agents to learn to converge on Nash Equilibrium strategy profiles. Such equilibrium configurations imply that no player has the motivation to unilaterally change its strategy. Often, in general sum games, a higher payoff can be obtained by both players if one chooses not to respond myopically to the other player. By developing mutual trust, agents can avoid immediate best responses that will lead to a Nash Equilibrium with lesser payoff. In this paper we experiment with agents who select actions based on expected utility calculations that incorporate the observed frequencies of the actions of the opponent(s). We augment these stochastically greedy agents with an interesting action revelation strategy that involves strategic declaration of one's commitment to an action to avoid worst-case, pessimistic moves. We argue that in certain situations, such apparently risky action revelation can indeed produce better payoffs than a non-revealing approach. In particular, it is possible to obtain Pareto-optimal Nash Equilibrium outcomes. We improve on the outcome efficiency of a previous algorithm and present results over the set of structurally distinct two-person two-action conflict games where the players' preferences form a total order over the possible outcomes. We also present results on a large number of randomly generated payoff matrices of varying sizes and compare the payoffs of strategically revealing learners to payoffs at Nash equilibrium.
1281859
Unsupervised Surrogate Agents and Search Bias Change in Flexible Distributed Scheduling
Computational infrastructures for cooperative work should contain embedded agents for handling many routine tasks (Galegher, Kraut, Egldo 1990), but as the number of agents increases and the agents become geographically and/or conceptually dispersed, supervision of the agents will become increasingly problematic. We argue that agents should be provided with deep domain knowledge that allows them to make justifiable decisions, rather than shallow models of users to mimic. In this paper, we use the application domain of distributed meeting scheduling to investigate how agents embodying deeper domain knowledge can choose among alternative strategies for searching their calendars in order to create flexible schedules within reasonable cost.
13052705
Learning to Coordinate without Sharing Information
Researchers in the field of Distributed Artificial Intelligence (DAI) have been developing efficient mechanisms to coordinate the activities of multiple autonomous agents. The need for coordination arises because agents have to share resources and expertise required to achieve their goals. Previous work in the area includes using sophisticated information exchange protocols, investigating heuristics for negotiation, and developing formal models of possibilities of conflict and cooperation among agent interests. In order to handle the changing requirements of continuous and dynamic environments, we propose learning as a means to provide additional possibilities for effective coordination. We use reinforcement learning techniques on a block pushing problem to show that agents can learn complimentary policies to follow a desired path without any knowledge about each other. We theoretically analyze and experimentally verify the effects of learning rate on system convergence, and demonstrate benefits of using learned coordination knowledge on similar problems. Reinforcement learning based coordination can be achieved in both cooperative and non-cooperative domains, and in domains with noisy communication channels and other stochastic characteristics that present a formidable challenge to using other coordination schemes.
2727968
A bayes net approach to argumentation
Argumentation-based negotiation approaches have been proposed to capture realistic negotiation contexts where all issues being negotiated are not fixed a priori and the negotiatorýs beliefs may be influenced during the negotiation process. We have proposed a novel Bayesian network based argumentation and decision making framework that allows agents to utilize models of other agents. We discuss a decision mechanism for generating the most effective argument to convince the opponent to accept favorable contracts.
10902519
Effects of Local Information on Group Behavior
Researchers in the field of Distributed Artificial Intelligence have studied the effects of local decisionmaking on overall system performance in both cooperative and self-interested agent groups (Bond & Gasser, 1988) . The performance of individual agents depends critically on the quality of information available to it about local and global goals and resources. Whereas in general it is assumed that the more accurate and up-to-date the available information, the better is the expected performance of the individual and the group, this conclusion can be challenged in a number of scenarios. The populace in human societies tend to look for opportunities and search for better opportunities in their environment (Bartos, 1967) . The theory of migration in social behavior and occupational mobility suggests that the stability of the population depends on how an individual chooses its action based on the prevailing circumst antes. As agent designers, we are faced with the problem of developing decision mechanisms that allow agent societies to stabilize in states where system resources are effectively utilized. In this research, we focus on a particular aspect of distributed decision-making: the effect of limited global knowledge on group behavior. The research question that we are asking is the following: Can limited local knowledge be a boon rather than a bane in a multiagent system ? To investigate this issue we use a resource utilization problem where a number of agents are distributed between several identical resources. We assume that the cost of using any resource is directly proportional to its usage. This cost can be due to a delay in processing of the task in hand, or a reduction in the quality of the resource due to congestion. Hence, there is a justified urge in agents to seek out and move to resource with lesser usage. Other researchers have shown that such systems can exhibit oscillatory or chaotic behavior where agents move back and forth between resources (Hogg & Huberman 1991; Kephart, Hogg & Huberman 1989) resulting in ineffective uti1406 AAAI-96 lization of system resources. Whereas asynchrony, heterogeneous agent decision mechanisms, etc. has been suggested as possible means for solving the instability problem, our proposed solution of using locally differing global views is a novel mechanism to introduce asymmetry in group decisions that expedites group stability.
975549
Agent teaching agent framework
We address the problem of knowledge transfer between a trainer and a trainee agent. The knowledge being transferred is a concept description, a boolean-valued function that classifies input examples as members or non-members of the target concept. We assume that the trainer agent does not have access to the internal knowledge representation of the trainee agent, but can evaluate its concept recognition abilities by asking it to categorize selected exemplars and non-exemplars of the target concept. The trainer agent also do not have access to the original training set from which it learned its concept description, and hence has to rely only on that learned knowledge to train the trainee agent. We present an Agent Teaching Agent (ATA) framework which focuses on incremental selection of training examples by the trainer to expedite the learning of the trainee agent. We envisage an iterative training procedure in which alternatively the trainer selects a set of training and testing exemplars, the trainee trains using the training set and then classifies the testing set, the trainer observes errors made by the trainee in classifying the instances in the last testing set and accordingly generates the next training and testing sets. This iterative process converges when error of the trainee falls below a given threshold. We now present these iterative training steps in an algorithmic form:
7862990
Output-Sensitive Algorithms for Uniform Partitions of Points
We consider the following one- and two-dimensional bucketing problems: Given a set S of n points in R1 or R2 and a positive integer b, distribute the points of S into b equal-size buckets so that the maximum number of points in a bucket is minimized. Suppose at most (n/b) + Δ points lies in each bucket in an optimal solution. We present algorithms whose time complexities depend on b and Δ. No prior knowledge of Δ is necessary for our algorithms. 
 
For the one-dimensional problem, we give a deterministic algorithm that achieves a running time of O(b4Δ2 log n + n). For the two-dimensional problem, we present a Monte-Carlo algorithm that runs in sub-quadratic time for certain values of b and Δ. The previous algorithms, by Asano and Tokuyama [1], searched the entire parameterized space and required Ω(n2) time in the worst case even for constant values of b and Δ.
7431315
Optimal, Output-sensitive Algorithms for Constructing Planar Hulls in Parallel
Abstract In this paper we focus on the problem of designing very fast parallel algorithms for the planar convex hull problem that achieve the optimal O(nlogH) work-bound for input size n and output size H. Our algorithms are designed for the arbitrary CRCW PRAM model. We first describe a very simple O(lognlogH) time optimal deterministic algorithm for the planar hulls which is an improvement over the previously known Ω( log 2 n) time algorithm for small outputs. For larger values of H, we can achieve a running time of O(lognloglogn) steps with optimal work. We also present a fast randomized algorithm that runs in expected time O(logH·loglogn) and does optimal O(nlogH) work. For log H = Ω( loglog n) , we can achieve the optimal running time of O(logH) while simultaneously keeping the work optimal. When logH is o(logn), our results improve upon the previously best known Θ(logn) expected time randomized algorithm of Ghouse and Goodrich. The randomized algorithms do not assume any input distribution and the running times hold with high probability.
16079000
Searching for optimal coalition structures
Coalition formation has been a very active area of research in multiagent systems. Most of this research has concentrated on decentralized procedures that allow self-interested agents to negotiate the formation of coalitions and division of coalition payoffs. A different line of research has addressed the problem of finding the optimal division of agents into coalitions such that the sum total of the the payoffs to all the coalitions is maximized (Larson and Sandholm, 1999). This is the optimal coalition structure identification problem. Deterministic search algorithms have been proposed and evaluated under the assumption that the performance of a coalition is independent of other coalitions. We use an order-based genetic algorithm (OBGA) as a stochastic search process to identify the optimal coalition structure. We compare the performance of the OBGA with a representative deterministic algorithm presented in the literature. Though the OBGA has no performance guarantees, it is found to dominate the deterministic algorithm in a significant number of problem settings. An additional advantage of the OBGA is its scalability to larger problem sizes and to problems where performance of a coalition depends on other coalitions in the environment.
2420350
Smooth workload adaptive broadcast
The high-bandwidth requirements and long-lived characteristics of digital video make transmission bandwidth usage a key limiting factor in the widespread streaming of such content over the Internet. A challenging problem is to develop bandwidth-efficient techniques for delivering popular videos to a large, asynchronous client population with time-varying demand characteristics. In this paper, we propose smooth workload adaptive broadcast to address the above issues. A key component of our scheme is Flexible Periodic Broadcast (FPB). By introducing a feedback control loop into FPB, and enhancing FPB using techniques such as parsimonious transmission, smooth workload adaptive broadcast provides instantaneous or near-instantaneous playback services and can smoothly adapt to workload changes. Furthermore, FPB, as proposed in this paper, is bandwidth efficient and exhibits the periodic smooth channel transition property.
16723670
PLEASE: A Prototype Learning System Using Genetic Algorithms
Prototypes have been proposed as representation of concepts that are used eeec-tively by humans. Developing computational schemes for generating prototypes from examples , however, has proved to be a dii-cult problem. We present a novel genetic algorithm based prototype learning system, PLEASE, for constructing appropriate prototypes from classiied training instances. After constructing a set of prototypes for each of the possible classes, the class of a new input instance is determined by the nearest prototype to this instance. Attributes are assumed to be ordinal in nature and prototypes are represented as sets of feature-value pairs. A genetic algorithm is used to evolve the number of prototypes per class and their positions on the input space. We present experimental results on a series of artiicial problems of varying complexity. PLEASE performs competitively with several nearest neighbor clas-siication algorithms on the problem set. An analysis of the strengths and weaknesses of the initial version of our system motivates the need for additional operators. The inclusion of these operators substantially improves the performance of the system on particularly diicult problems.