Walverine: A Walrasian Trading Agent

TAC-02 was the third in a series of Trading Agent Competition events fostering research in automating trading strategies by showcasing alternate approaches in an open-invitation market game. TAC presents a challenging travel-shopping scenario where agents must satisfy client preferences for complementary and substitutable goods by interacting through a variety of market types. Michigan's entry, Walverine, attempts to bid optimally based on a competitive analysis of the TAC travel economy. Walverine's approach embodies several techniques not previously employed in TAC: (1) price prediction based on competitive equilibrium analysis, (2) hedged optimization with respect to a model of outlier prices, (3) optimal bidding based on a decision-theoretic calculation of bid actions, and (4) reinforcement learning for CDA trading strategies. Each of these is potentially applicable in a broad class of trading environments.

Strategic Interactions in a Supply Chain Game

The TAC supply-chain game presented automated trading agents with a challenging strategic problem. Embedded within a high-dimensional stochastic environment was a pivotal strategic decision about initial procurement of components. Early evidence suggested that the entrant field was headed toward a self-destructive, mutually unprofitable equilibrium. Our agent, Deep Maize, introduced a preemptive strategy designed to neutralize aggressive procurement, perturbing the field to a more profitable equilibrium. It worked. Not only did preemption improve Deep Maize's profitability, it improved profitability for the whole field. Whereas it is perhaps counterintuitive that actions designed to prevent others from achieving their goals actually helps them, strategic analysis employing an empirical game-theoretic methodology verifies and provides insight about this outcome.

Self-Confirming Price Prediction for Bidding in Simultaneous Ascending Auctions

Simultaneous ascending auctions present agents with the exposure problem: bidding to acquire a bundle risks the possibility of obtaining an undesired subset of the goods. Auction theory provides little guidance for dealing with this problem. We present a new family of decision-theoretic bidding strategies that use probabilistic predictions of final prices. We focus on self-confirming price distribution predictions, which by definition turn out to be correct when all agents bid decision-theoretically based on them. Bidding based on these is provably not optimal in general, but our experimental evidence indicates the strategy can be quite effective compared to other known methods.

Graphical models for groups: Belief aggregation and risk sharing

We investigate the practical value of using graphical models to aid in two fundamental problems of group coordination: (1) belief aggregation and (2) risk sharing. We identify restrictive conditions under which graphical models can be useful in both settings. We show that the output of the logarithmic opinion pool (LogOP) can be represented as a Markov network (MN) or a decomposable Bayesian network (BN), and give an algorithm for doing so. We show that a securities market structured like a decomposable BN can support optimal risk sharing, if all agents have exponential utility and all of their Markov independencies coincide with the market structure. On the other hand, most of our results are negative, taking the form of impossibility theorems. We show that no belief aggregation function can maintain all independencies representable in a BN. Neither can an aggregation computation be decomposed into local computations on graph subsets. We show that computing query outputs of LogOP or the linear opinion pool (LinOP) is NP-hard. Except in fairly restrictive settings, structuring securities markets according to unanimously agreed upon independencies may be of no help in supporting optimal risk sharing because agents’ behavioral independencies change as they engage in securities trade.

Exploring bidding strategies for market-based scheduling

A market-based scheduling mechanism allocates resources indexed by time to alternative uses based on the bids of participating agents. Agents are typically interested in multiple time slots of the schedulable resource, with value determined by the earliest deadline by which they can complete their corresponding tasks. Despite the strong complementarities among slots induced by such preferences, it is often infeasible to deploy a mechanism that coordinates allocation across all time slots. We explore the case of separate, simultaneous markets for individual time slots, and the strategic problem it poses for bidding agents. Investigation of the straightforward bidding policy and its variants indicates that the efficacy of particular strategies depends critically on preferences and strategies of other agents, and that the strategy space is far too complex to yield to general game-theoretic analysis. For particular environments, however, it is often possible to derive constrained equilibria through evolutionary search methods.

Betting Boolean Style: A Framework for Trading in Securities based on Logical Formulas

We develop a framework for trading in compound securities: financial instruments that pay off contingent on the outcomes of arbitrary statements in propositional logic. Buying or selling securities—which can be thought of as betting on or against a particular future outcome—allows agents both to hedge risk and to profit (in expectation) on subjective predictions. A compound securities market allows agents to place bets on arbitrary boolean combinations of events, enabling them to more closely achieve their optimal risk exposure, and enabling the market as a whole to more closely achieve the social optimum. The tradeoff for allowing such expressivity is in the complexity of the agents' and auctioneer's optimization problems. We develop and motivate the concept of a compound securities market, presenting the framework through a series of formal definitions and examples. We then analyze in detail the auctioneer's matching problem. We show that, with n events, the matching problem is co-NP-complete in the divisible case and sigma-2-complete in the indivisible case. We show that the latter hardness result holds even under severe language restrictions on bids. With log n events, the problem is polynomial in the divisible case and NP-complete in the indivisible case. We briefly discuss matching algorithms and tractable special cases.

Approximate Strategic Reasoning through Hierarchical Reduction of Large Symmetric Games

To deal with exponential growth in the size of a game with the number of agents, we propose an approximation based on a hierarchy of reduced games. The reduced game achieves savings by restricting the number of agents playing any strategy to fixed multiples. We validate the idea through experiments on randomly generated local-effect games. An extended application to strategic reasoning about a complex trading scenario motivates the approach, and demonstrates methods for game-theoretic reasoning over incompletely-specified games at multiple levels of granularity.