Hopelessly Out of Date List of Projects:

Constraint Satisfaction Algorithms for Graphical Games by Soni, Singh & Wellman: We formulate the problem of computing equilibria in multiplayer games represented by arbitrary undirected graphs as a constraint satisfaction problem and present two algorithms. The first is PureProp: an algorithm for computing approximate Nash equilibria in complete information one-shot games and approximate Bayes-Nash equilibria in one-shot games of incomplete information. PureProp unifies existing message-passing based algorithms for solving these classes of games. We also address repeated graphical games, and present a second algorithm, PureProp-R, for computing approximate Nash equilibria in these games.

Computing Approximate Bayes Nash Equilibria in Tree-Games of Incomplete Information by Singh, Soni & Wellman: We provide efficient algorithms for finding approximate BayesNash equilibria (BNE) in graphical, specifically tree, games of incomplete information. In such games an agentŐs payoff depends on its private type as well as on the actions of the agents in its local neighborhood in the graph. We consider two classes of such games: 1) arbitrary tree-games with discrete types, and 2) tree-games with continuous types but with constraints on the effect of type on payoffs. For each class we present a message passing on the game-tree algorithm that computes an epsilon-BNE in time polynomial in the number of agents and the approximation parameter 1/epsilon

Distributed Feedback Control for Decision Making on Supply Chains Decision makers on supply chains face an uncertain, dynamic, and strategic multiagent environment. We report on Deep Maize, an agent we designed to participate in the 2003 Trading Agent Competition Supply Chain Management (TAC/SCM) game. Our design employs an idealized equilibrium analysis of the SCM game to factor out the strategic aspects of the environment and to define an expected profitable zone of operation. Deep Maize applies distributed feedback control to coordinate its separate functional modules and maintain its environment in the desired zone, despite the uncertainty and dynamism. We evaluate our design with results from the TAC/SCM tournament as well as from controlled experiments conducted after the competition.

Gradient Dynamics in General-Sum Games by Singh, Kearns & Mansour: Multi-agent games are becoming an increasingly prevalent formalism for the study of electronic commerce and auctions. The speed at which transactions can take place and the growing complexity of electronic marketplaces makes the study of computationally simple agents an appealing direction. In this work, we analyze the behavior of agents that incrementally adapt their strategy through gradient ascent on expected payoff, in the simple setting of two-player, two-action, iterated general-sum games, and present a surprising result. We show that either the agents will converge to a Nash equilibrium, or if the strategies themselves do not converge, then their average payoffs will nevertheless converge to the payoffs of a Nash equilibrium.

Fast Planning in Stochastic Games by Kearns, Mansour & Singh: We consider the problem of computing Nash equilibria in stochastic games. We provide a generalization of finite-horizon value iteration that computes a Nash strategy for each player in general-sum stochastic games. The algorithm takes an arbitrary Nash selection function as input, which allows the translation of local choices between multiple Nash equilibria into the selection of a single global Nash equilibrium. Our main technical result is an algorithm for computing near-Nash equilibria in large or infinite state spaces. This algorithm builds on our finite-horizon value iteration algorithm, and adapts the sparse sampling methods of Kearns, Mansour and Ng (1999) to stochastic games. We conclude by describing a counterexample showing that infinite-horizon discounted value iteration, which was shown by Shapley to converge in the zero-sum case (a result we extend slightly here), does not converge in the general-sum case.

ATTac-2000: An Adaptive Autonomous Bidding Agent by Stone, Littman, Singh & Kearns: While at AT&T, I helped build an adaptive autonomous bidding agent, named ATTac-2000, that participated and won the first Trading Agent Competition (TAC). TAC-2000 was a travel agent game in which a our agent had to bid in auctions for airline tickets, hotel rooms and entertainment tickets. The attached paper describes our agent.

FAucS: An FCC Spectrum Auction Simulator for Autonomous Bidding Agents Crisik, Littman, Singh & Stone: We introduce FAucS, a software testbed for studying automated agent bidding strategies in simulated auctions, specifically the United States FCC wireless frequency spectrum auctions. In addition to the complexity of these auctions, which provides ample opportunities for intelligent approaches to bidding, this type of auction has huge commercial importance, each bringing in billions of dollars to governments around the world. We implement straightforward sample agents in FAucS and use them to replicate known beneficial bidding strategies in this type of auction. We then discuss potential in-depth studies of autonomous bidding agent behaviors using FAucS. The main contribution of this work is the implementation, description, and empirical validation of the FAucS testbed. We present it as a challenging and promising AI research domain.