Price Prediction Strategies for Market-Based Scheduling
In a market-based scheduling mechanism, the allocation of time-specific resources to tasks is governed by a competitive bidding process. Agents bidding for multiple, separately allocated time slots face the risk that they will succeed in obtaining only part of their requirement, incurring expenses for potentially worthless slots. We investigate the use of price prediction strategies to manage such risk. Given an uncertain price forecast, agents follow simple rules for choosing whether and on which time slots to bid. We find that employing price predictions can indeed improve performance over a straightforward baseline in some settings. Using an empirical game-theoretic methodology, we establish Nash equilibrium profiles for restricted strategy sets. This allows us to confirm the stability of price-predicting strategies, and measure overall efficiency. We further experiment with variant strategies to analyze the source of prediction's power, demonstrate the existence of self-confirming predictions, and compare the performance of alternative prediction methods.
Price Prediction in a Trading Agent Competition
The 2002 Trading Agent Competition (TAC) presented agents with a challenging market game in the domain of travel shopping. One of the pivotal issues in this domain is uncertainty about hotel prices, which have a significant influence on the relative cost of alternative trip schedules. Thus, virtually all participating agents employ some method for predicting hotel prices. We survey approaches employed in the tournament, finding that agents apply an interesting diversity of techniques, taking into account differing sources of evidence bearing on prices. Based on data provided by entrants on their agents' actual predictions in the TAC-02 finals and semifinals, we analyze the relative efficacy of these approaches. Employing a new measure of prediction quality, we relate absolute accuracy to bottom-line performance in the game.
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.
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.
