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.
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.
