5997994
Evolving Cooperation Strategies
We propose an approach to developing cooperation strategies for multiagent problem solving situations which is different from existing techniques in two ways: strategies are incrementally constructed by repeatedly solving problems in the domain, i.e., on-line; and, we utilize an automated method of strategy formulation and modification, that relies little on domain details and human expertise, and more on performance on randomly generated problems in the domain. The genetic programming (GP) (Koza 1992) paradigm used to develop, through repeated problem solving, increasingly efficient strategies. Populations of structures are represented as Lisp symbolic expressions (Sexpressions). These are manipulated to evolve better structures by propagating and combining parts of structures that perform well compared to others in the population. To use this approach, we have to develop an encoding of strategies as S-expressions and choose an evaluation criterion for a strategy corresponding to an arbitrary S-expression. Strategies are evaluated by allowing the agents to execute them in the application domain and by measuring their efficiency and effectiveness by a set of criteria relevant to the domain.
43158386
Evolution and learning in multiagent systems
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.
1062630
The Role of Commitment in Cooperative Negotiation
Cooperative information agents need mechanisms that enable them to work together effectively while solving common problems. We investigate the use of commitment by agents to proposed actions as a mechanism that allow agents to work concurrently on interdependent problems. Judicious use of commitment can not only increase the throughput of cooperative information systems, but also allow them to deal flexibly with dynamically changing environments. We use the domain of distributed scheduling to demonstrate that static commitment strategies are ineffective. Results from simulated experiments are used to identify the environmental features on which an adaptive commitment strategy should be predicated.
12119095
Correlating Internal Parameters and External Performance: Learning Soccer Agents
We have developed a Soccer simulator in Java, which allows us to evaluate agent behavioral strategies for effectively collaborating with other team members while countering threats posed by the opposing team. Whereas action selection mechanisms to decide when to shoot, pass, dribble, guard opponent, tackle, etc. are important from a player's viewpoint, learning the capabilities of individual opponents from repeated encounters can provide critical information for the success of a team. Each agent is described by a set of skill levels for different soccer skills. A soccer agent uses its incomplete perceptions, model of the changing environment, knowledge of the skill levels of its own team players, and estimated skill levels of the opponent team players to select the most prudent action. In this paper, we identify learning opportunities for soccer agents, and investigate some of these possibilities in detail. Initial experimental results demonstrate the advantage of learning agents.
3526092
Selecting partners
1. I N T R O D U C T I O N In an open environment the goal of a self-interested agent would be to interact with or enter into partnership with those agents that will produce maximal local utility for this agent [5]. We assume that an agent can get one of several payoffs (utilities) for joining a particular coalition which is determined by a static probability distribution over the payoffs for each coalition. We consider choosing a single coalition to interact with repeatedly when the total number of interactions is known ahead of time.
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.
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 Δ.
15940614
Lower Bounds for Parallel Algebraic Decision Trees, Parallel Complexity of Convex Hulls and Related Problems
We show that any parallel algorithm in the fixed degree algebraic decision tree model that answers membership queries in W ⊑ R n using p processors, requires Ω(¦W¦/n log(p/n)) rounds where ¦W¦ is the number of connected components of W. We further prove a similar result for the average case complexity. We give applications of this result to various fundamental problems in computational geometry like convex-hull construction and trapezoidal decomposition and also present algorithms with matching upper bounds.
32334601
Finding an Approximate Median with High Probability in Constant Parallel Time
Given n elements from a totally ordered set we outline a method for choosing an element whose rank is γn for some 0 0.
14600509
A Genetic Prototype Learner
Supervised classification problems have received considerable attention from the machine learning community. We propose a novel genetic algorithm based prototype learning system, PLEASE, for this class of problems. Given a set of prototypes for each of the possible classes, the class of an input instance is determined by the prototype nearest to this instance. We assume ordinal attributes 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 as determined by corresponding feature-value pairs. Comparisons with C4.5 on a set of artificial problems of controlled complexity demonstrate the effectiveness of the proposed system.