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.
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.
16541041
Helping based on future expectations
Autonomous agents interacting in an open world can be considered to be primarily driven by self interests. Previous work in this area has prescribed a strategy of reciprocal behavior, based on past interactions, for promoting and sustaining cooperation among such self-interested agents. Here we present a new mechanism where agents base their decisions both on historical data as well as on future interaction expectations. A decision mechanism is presented that compares current helping cost with expected future savings from interaction with the agent requesting help. We experiment with heterogeneous agents that have varying expertise for different job types. We evaluate the effect of both change of agent expertise and distribution of task types on subsequent agent relationships. The reciprocity mechanism based on future expectations is found to be robust and flexible in adjusting to the environmental dynamics.
10373451
Reciprocal resource sharing in P2P environments
Peer-to-peer (P2P) systems enable users to share resources in a networked environment without worrying about issues such as scalability and load balancing. Unlike exchange of goods in a traditional market, resource exchange in P2P networks does not involve monetary transactions. This makes P2P systems vulnerable to problems including the free-rider problem that enables users to acquire resources without contributing anything, collusion between groups of users to incorrectly promote or malign other users, and zero-cost identity that enables nodes to obliterate unfavorable history without incurring any expenditure. Previous research addresses these issues using user-reputation, referrals, and shared history based techniques. Here, we describe a multi-agent based reciprocity mechanism where each user's agent makes the decision to share a resource with a requesting user based on the amount of resources previously provided by the requesting user to the providing user and globally in the system. A robust reputation mechanism is proposed to avoid the differential exploitations by the free-riders and to prevent collusion. Experimental results on a simulated P2P network addresses the problems identified above and shows that users adopting the reciprocative mechanism outperform users that do not share resources in the P2P network. Hence, our proposed reciprocative mechanism effectively suppresses free-riding.
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.
7067374
Profit Sharing Auction
Auctions are a class of multi-party negotiation protocols. Classical auctions try to maximize social welfare by selecting the highest bidder as the winner. If bidders are rational, this ensures that the sum of profits for all bidders and the seller is maximized. In all such auctions, however, only the winner and the seller make any profit. We believe that "social welfare distribution" is a desired goal of any multiparty protocol. In the context of auctions, this goal translates into a rather radical proposal of profit sharing between all bidders and the seller. We propose a Profit Sharing Auction (PSA) where a part of the selling price paid by the winner is paid back to the bidders. The obvious criticism of this mechanism is the incentive for the seller to share its profit with nonwinning bidders. We claim that this loss can be compensated by attracting more bidders to such an auction, resulting in an associated increase in selling price. We run several sets of experiments where equivalent items are concurrently sold at a First Price Sealed Bid, a Vickrey, and a PSA auction. A population of learning bidders repeatedly choose to go to one of these auctions based on their valuation for the good being auctioned and their learned estimates of profits from these auctions. Results show that sellers make more or equivalent profits by using PSA as compared to the classical auctions. Additionally, PSA always attracts more bidders, which might create auxiliary revenue streams, and a desirable lower variability in selling prices. Interestingly then, a rational seller has the incentive to share profits and offer an auction like PSA which maximizes and distributes social welfare.
11397521
Nearest neighbors search using point location in balls with applications to approximate Voronoi decompositions
We present alternate reductions of the nearest neighbor searching problem to Point Location in Balls that reduces the space bound of Sariel Har-Peled's [S. Har-Peled, A replacement for Voronoi diagrams of near linear size, in: Proc. of IEEE FOCS, 2001, pp. 94-103, full version available from http://www.uiuc.edu/~sariel/papers] recent result on Approximate Voronoi Diagrams to linear while maintaining the logarithmic search time. We do this by simplifying the construction of [S. Har-Peled, A replacement for Voronoi diagrams of near linear size, in: Proc. of IEEE FOCS, 2001, pp. 94-103, full version available from http://www.uiuc. edu/~sariel/papers] that reduces the number of balls generated by algorithm by a logarithmic factor to O(n log n). We further reduce the number of balls by a new hierarchical decomposition scheme and a generalization of PLEBs to achieve linear space decomposition for nearest neighbor searching. The construction of our data structures takes O(n log n) time.
9417710
Using real-valued genetic algorithms to evolve rule sets for classification
In this paper, we use a genetic algorithm to evolve a set of classification rules with real-valued attributes. We show how real-valued attribute ranges could be encoded with real-valued genes and present a new uniform method for representing don't cares in the rules. We view supervised classification as an optimization problem, and evolve rule sets that maximize the number of correct classifications of input instances. We use a variant of the Pitt approach to genetic-based machine learning system with a novel conflict resolution mechanism between competing rules within the same rule set. Experimental results demonstrate the effectiveness of our proposed approach on a benchmark wine classifier system.<<ETX>>
13878075
Optimal sequencing of individually rational contracts
Multiagent researchers have worked on the problem of determining optimal contracts between self-interested agents. In particular, Sandholm et al. [1,8] have both theoretically and experimentally studied the necessity and usefulness of different contract types under the assumption of individually myopically rational contracting. We study a variant of sequential contracting where the goal is to maximize social welfare through a fixed-length sequence of individually rational contracts. The space of possible contract sequences is exponential. We compare a greedy deterministic heuristic with a stochastic genetic algorithm based approach for this optimal sequential contract selection problem. We focus on sub-additive domains where individually rational contracts are feasible with side payments. We show that the GA-based approach consistently outperforms the deterministic heuristic by generating larger social welfare.
8938271
Kernel-Based Reinforcement Learning
We present a kernel-based approach to reinforcement learning that overcomes the stability problems of temporal-difference learning in continuous state-spaces. First, our algorithm converges to a unique solution of an approximate Bellman's equation regardless of its initialization values. Second, the method is consistent in the sense that the resulting policy converges asymptotically to the optimal policy. Parametric value function estimates such as neural networks do not possess this property. Our kernel-based approach also allows us to show that the limiting distribution of the value function estimate is a Gaussian process. This information is useful in studying the bias-variance tradeoff in reinforcement learning. We find that all reinforcement learning approaches to estimating the value function, parametric or non-parametric, are subject to a bias. This bias is typically larger in reinforcement learning than in a comparable regression problem.
13425332
A generalization of the 0-1 principle for sorting
The traditional zero-one principle for sorting networks states that "if a network with n input lines sorts all 2n binary sequences into nondecreasing order, then it will sort any arbitrary sequence of n numbers into nondecreasing order". We generalize this to the situation when a network sorts almost all binary sequences and relate it to the behavior of the sorting network on arbitrary inputs. We also present an application to mesh sorting.