Abstract:
My thesis work concerns the generation of trading agent strategies -- automatically, semi-automatically, and manually. Automatic generation of an agent strategy means creating a system that can read the description of some mechanism and output a strategy for a participating agent. To make this more concrete, consider an extremely simple auction mechanism: a two-player first-price sealed-bid auction. My current system can take such a game description and output the optimal strategy, i.e., the Nash equilibrium. Existing game solvers (Gambit and Gala) can only solve games with an enumerated (finite) set of actions, and this limitation makes it impossible to even approximate the solution to games with a continuum of actions because the size of the game tree quickly explodes. Of course, the optimal strategy for the first-price sealed-bid auction was computed before game solvers existed; however, my algorithm can automatically solve any of a class of games (with certain caveats) that current solvers can’t. In addition to this algorithm for exact solutions, I have an approximation algorithm using Monte Carlo simulation that can handle a more general class of games albeit at high computational cost. Both of the above methods are only tractable for quite simple games. For example, almost any mechanism that involves iterated bidding and multiple auctions is likely not to be tractable for strictly game-theoretic analysis, regardless of whether exact or approximate solutions are sought. An example of such a mechanism that we are analyzing is a simultaneous ascending auction for scheduling resources among a group of agents. In this domain, every agent has certain preferences for acquiring time slots and simultaneous English auctions are held for every slot until bidding stops and the slots are allocated. Since this mechanism is too complicated for the fully automatic techniques described above, we are attempting to generate strategies semi-automatically. Finally, there are domains in which even the semi-automatic method for generating strategies is not yet feasible. These include many real-world market scenarios, but also a particular structured domain---the Trading Agent Competition (TAC). TWe believe this work in designing trading agent strategies for very rich domains will shed light on how to extend our results on the automatic generation of trading agent strategies.