Market-Based Allocation with Indivisible Bids

We study multi-unit double auctions accepting bids with indivisibility constraints. Modeling the auction problem as a Multiple Choice Knapsack Problem and using dynamic programming, we show that incremental computations during bid processing can speed the handling of key auction operations such as clearing and quoting. We propose different price-quote policies and study their influence on the efficiency of market-based allocation. Using a reconfigurable manufacturing scenario where agents trade large quantities of multiple goods, we demonstrate potential benefits of supporting indivisibility constraints in bidding. These benefits are highly sensitive to the form of price quote provided, indicating interesting tradeoffs in communication and allocation efficiency.

Learning Payoff Functions in Infinite Games

We consider a class of games with real-valued strategies and payoff information available only in the form of data from a given sample of strategy profiles. Solving such games with respect to the underlying strategy space requires generalizing from the data to a complete payoff-function representation. We address payoff-function learning as a standard regression problem, with provision for capturing known structure (e.g., symmetry) in the multiagent environment. To measure learning performance, we consider the relative utility of prescribed strategies, rather than the accuracy of payoff functions per se. We demonstrate our approach and evaluate its effectiveness on two examples: a two-player version of the first-price sealed-bid auction (with known analytical form), and a five-player market-based scheduling game (with no known solution). Additionally, we explore the efficacy of using relative utility of strategies as a target of supervised learning and as a learning model selector. Our experiments demonstrate its effectiveness in the former case, though not in the latter.

Iterated Weaker-than-Weak Dominance

We introduce a weakening of standard game-theoretic dominance conditions, called delta-dominance, which enables more aggressive pruning of candidate strategies at the cost of solution accuracy. Equilibria of a game obtained by eliminating a delta-dominated strategy are guaranteed to be approximate equilibria of the original game, with degree of approximation bounded by the dominance parameter, delta. We can apply elimination of delta-dominated strategies iteratively, but the delta for which a strategy may be eliminated depends on prior eliminations. We discuss implications of this order independence, and propose greedy heuristics for determining a sequence of eliminations to reduce the game as far as possible while keeping down costs. A case study analysis of an empirical 2-player game serves to illustrate the technique, and demonstrate the utility of weaker-than-weak dominance pruning.

Generalized Value Decomposition and Structured Multiattribute Auctions

Multiattribute auction mechanisms generally either remain agnostic about traders’ preferences, or presume highly restrictive forms, such as full additivity. Real preferences often exhibit dependencies among attributes, yet may possess some structure that can be usefully exploited to streamline communication and simplify operation of a multiattribute auction. We develop such a structure using the theory of measurable value functions, a cardinal utility representation based on an underlying order over preference differences. A set of local conditional independence relations over such differences supports a generalized additive preference representation, which decomposes utility across overlapping clusters of related attributes. We introduce an iterative auction mechanism that maintains prices on local clusters of attributes rather than the full space of joint configurations. When traders’ preferences are consistent with the auction’s generalized additive structure, the mechanism produces approximately optimal allocations, at approximate VCG prices.

Empirical Game-Theoretic Analysis of the TAC Supply Chain Game

The TAC Supply Chain Management (TAC/SCM) game presents a challenging dynamic environment for autonomous decision-making in a salient application domain. Strategic interactions complicate the analysis of games such as TAC/SCM, since the effectiveness of a given strategy depends on the strategies played by other agents on the supply chain. The TAC tournament generates results from one particular path of combinations, and success in the tournament is rightly regarded as evidence for agent quality. Such results along with post-competition controlled experiments provide useful evaluations of novel techniques employed in the game. We argue that a broader game-theoretic analysis framework can provide a firmer foundation for choice of experimental contexts. Exploiting a repository of agents from the 2005 and 2006 TAC/SCM tournaments, we demonstrate an empirical game-theoretic methodology based on extensive simulation and careful measurement. Our analysis of agents from TAC-05 reveals interesting interactions not seen in the tournament. Extending the analysis to TAC-06 enables us to measure progress from year-to-year, and generates a candidate empirical equilibrium among the best known strategies. We use this equilibrium as a stable background population for comparing relative performance of the 2006 agents, yielding insights complementing the tournament results.

Constraint satisfaction algorithms for graphical games

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.

Constrained automated mechanism design for infinite games of incomplete information

In general, identifying a solution concept only incompletely specifies a mechanism design problem. The designer must consider which among a multiplicity of solutions is likely to be played, as well as the possibility that actual play will not correspond to any solution. Given that actual play is the ultimate determiner of a mechanism's success, we advocate that designers embrace the corresponding forecasting problem and evaluate candidate mechanisms with respect to belief distributions over players' response. Solution concepts can play a useful role in delimiting and structuring belief distributions. We propose that membership of prospective strategy profiles in various solution classes be treated as evidence bearing on their likelihood of play. Flexible solution classes, for example based on approximate equilibrium, degree of dominance, or safety level, provide natural measures (e.g., distance from equilibrium) that can be employed in defining belief distributions.

Autonomous Bidding Agents: Strategies and Lessons from the Trading Agent Competition

E-commerce increasingly provides opportunities for autonomous bidding agents: computer programs that bid in electronic markets without direct human intervention. Automated bidding strategies for an auction of a single good with a known valuation are fairly straightforward; designing strategies for simultaneous auctions with interdependent valuations is a more complex undertaking. This book presents algorithmic advances and strategy ideas within an integrated bidding agent architecture that have emerged from recent work in this fast-growing area of research in academia and industry. The authors analyze several novel bidding approaches that developed from the Trading Agent Competition (TAC), held annually since 2000. The benchmark challenge for competing agents—to buy and sell multiple goods with interdependent valuations in simultaneous auctions of different types—encourages competitors to apply innovative techniques to a common task. The book traces the evolution of TAC and follows selected agents from conception through several competitions, presenting and analyzing detailed algorithms developed for autonomous bidding. Autonomous Bidding Agents provides the first integrated treatment of methods in this rapidly developing domain of AI. The authors—who introduced TAC and created some of its most successful agents—offer both an overview of current research and new results.

Stochastic Search Methods for Nash Equilibrium Approximation in Simulation-Based Games

We define the class of games called simulation-based games, in which the payoffs are available as an output of an oracle (simulator), rather than specified analytically or using a payoff matrix. We then describe a convergent algorithm based on a hierarchical application of simulated annealing for estimating Nash equilibria in simulation-based games with finite-dimensional strategy sets. Additionally, we present alternative algorithms for best response and Nash equilibrium estimation, with a particular focus on one-shot infinite games of incomplete information. Our experimental results demonstrate that all the approaches we introduce are efficacious, albeit some more so than others. We show, for example, that while iterative best response dynamics has relatively weak convergence guarantees, it outperforms our convergent method experimentally. Additionally, we provide considerable evidence that a method based on random search outperforms gradient descent in our setting.

Selecting Strategies using Empirical Game Models: An Experimental Analysis of Meta-Strategies

In many complex multi-agent domains it is impractical to compute exact analytic solutions. An alternate means of analysis applies computational tools to derive and analyze empirical game models. These models are noisy approximations, which raises questions about how to account for uncertainty when analyzing the model. We develop a novel experimental framework and apply it to benchmark meta-strategies – general algorithms for selecting strategies based on empirical game models. We demonstrate that modeling noise is important; a naïve approach that disregards noise and plays according to Nash equilibrium yields poor choices. We introduce three parameterized algorithms that factor noise into the analysis by predicting distributions of opponent play. As observation noise increases, rational players generally make less specific outcome predictions. Our comparison of the algorithms identifies logit equilibrium as the best method for making these predictions. Logit equilibrium incorporates a form of noisy decision-making by players. Our evidence shows that this is a robust method for approximating the effects of uncertainty in many contexts. This result has practical relevance for guiding analysis of empirical game models. It also offers an intriguing rationale for behavioral findings that logit equilibrium is a better predictor of human behavior than Nash equilibrium.