Optimal Algorithms for <Emphasis Type="Italic">k</Emphasis>-Search with Application in Option Pricing

In the k-search problem, a player is searching for the k highest (respectively, lowest) prices in a sequence, which is revealed to her sequentially. At each quotation, the player has to decide immediately whether to accept the price or not. Using the competitive ratio as a performance measure, we give optimal deterministic and randomized algorithms for both the maximization and minimization problems, and discover that the problems behave substantially different in the worst-case. As an application of our results, we use these algorithms to price “lookback options”, a particular class of financial derivatives. We derive bounds for the price of these securities under a no-arbitrage assumption, and compare this to classical option pricing. J. Lorenz is partially supported by UBS AG. K. Panagiotou is partially supported by the SNF, grant number: 200021-107880/1.     

A genetic approach to the design of autonomous agents for futures trading

We propose a genetic algorithm-based method for designing an autonomous trader agent. The task of the proposed method is to find an optimal set of fuzzy if–then rules that best represents the behavior of a target trader agent. A highly profitable trader agent is used as the target in the proposed genetic algorithm. A trading history for the target agent is obtained from a series of futures trading. The antecedent part of fuzzy if–then rules considers time-series data of spot prices, while the consequent part indicates the order of trade (Buy, Sell, or No action) with its degree of certainty. The proposed method determines the antecedent part of fuzzy if–then rules. The consequent part of fuzzy if–then rules is automatically determined from the trading history of the target trader agent. The autonomous trader agent designed by the proposed genetic algorithm consists of a fixed number of fuzzy if–then rules. The decision of the autonomous trader agent is made by fuzzy inference from the time-series data of spot prices. This work was presented in part at the 11th International Symposium on Artificial Life and Robotics, Oita, Japan, January 23–25, 2006     

Optimal portfolio trading subject to stochastic dominance constraints under second‐order autoregressive price dynamics

This paper studies the optimal portfolio trading problem under the generalized second‐order autoregressive execution price model. The problem of minimizing expected execution cost under the proposed price model is formulated as a quadratic programming (QP) problem. For a risk‐averse trader, problem formulation under the second‐order stochastic dominance constraints results in a quadratically constrained QP problem. Under some conditions on the execution price model, it is proved that the portfolio trading problems for risk‐neutral and risk‐averse traders become convex programming problems, which have many theoretical and computational advantages over the general class of optimization problems. Extensive numerical illustrations are provided, which render the practical significance of the proposed execution price model and the portfolio trading problems.     

Avoiding game‐tree pathology in 2‐player adversarial search

Adversarial search, or game‐tree search, is a technique for analyzing an adversarial game to determine what moves a player should make in order to win a game. Until recently, lookahead pathology (in which deeper game‐tree search results in worse play) has been thought to be quite rare. We provide an analysis that shows that every game should have some sections that are locally pathological, assuming that both players can potentially win the game. We also modify the minimax algorithm to recognize local pathologies in arbitrary games and cut off search accordingly (shallower search is more effective than deeper search when local pathologies occur). We show experimentally that our modified search procedure avoids local pathologies and consequently provides improved performance, in terms of decision accuracy, when compared with the minimax algorithm. In addition, we provide an experimental evaluation on the African game of Kalah, which shows the improved performances of our suggested error‐minimizing minimax algorithm when there is a large degree of pathology.     

Graphical Congestion Games

We consider congestion games with linear latency functions in which each player is aware only of a subset of all the other players. This is modeled by means of a social knowledge graph G in which nodes represent players and there is an edge from i to j if i knows j. Under the assumption that the payoff of each player is affected only by the strategies of the adjacent ones, we first give a complete characterization of the games possessing pure Nash equilibria. Namely, if the social graph G is undirected, the game is an exact potential game and thus isomorphic to a classical congestion game. As a consequence, it always converges and possesses Nash equilibria. On the other hand, if G is directed an equilibrium is not guaranteed to exist, but the game is always convergent and an equilibrium can be found in polynomial time if G is acyclic, even if finding the best equilibrium remains an intractable problem.     

Secure peer-to-peer trading in small- and large-scale multiplayer games

A fundamental aspect of many multiplayer online games is the ability to trade items between players. Trading may occur with items that were found in the virtual environment, included as pieces of the game, or purchased by the player as assets. Regardless of the types of items, any multiplayer game that supports trading or exchanging items in the game must do so in a secure manner. We have developed a protocol to solve the problem of secure peer-to-peer trading in games in which the primary concern is that items are exchanged fairly, and additionally that items are not duplicated. Our protocol enables one-way and two-way trades and can be extended to multi-item trades in both small- and large-scale games where trades last only for the duration of a session or are persistent. We show that our protocol addresses the security threats which it might encounter, and then provide an analysis to demonstrate its scalability.     

Online algorithms for the general k-search problem

This paper investigates the general k-search problem, in which a player is to sell totally k units of some asset within n periods, aiming at maximizing the total revenue. At each period, the player observes a quoted price which expires before the next period, and decides irrecoverably the amount of the asset to be sold at the price. We present a deterministic online algorithm and prove it optimal for the case where k?n−1. For the other case where k?n, we show by numerical illustration that the gap between the upper and the lower bound of competitive ratio is quite small for many situations.     

The Impact of Payoff Function and Local Interaction on the N-Player Iterated Prisoner's Dilemma

The N-player iterated prisoner's dilemma (NIPD) game has been widely used to study the evolution of cooperation in social, economic and biological systems. This paper studies the impact of different payoff functions and local interactions on the NIPD game. The evolutionary approach is used to evolve game-playing strategies starting from a population of random strategies. The different payoff functions used in our study describe different behaviors of cooperation and defection among a group of players. Local interaction introduces neighborhoods into the NIPD game. A player does not play against every other player in a group any more. He only interacts with his neighbors. We investigate the impact of neighborhood size on the evolution of cooperation in the NIPD game and the generalization ability of evolved strategies. Received 18 August 1999 / Revised 27 February 2000 / Accepted 15 May 2000     

A Risk‐Reward Framework for the Competitive Analysis of Financial Games

Competitive analysis is concerned with minimizing a relative measure of performance. When applied to financial trading strategies, competitive analysis leads to the development of strategies with minimum relative performance risk. This approach is too inflexible. Many investors are interested in managing their risk: they may be willing to increase their risk for some form of reward. They may also have some forecast of the future. In this paper we extend competitive analysis to provide a framework in which investors can develop optimal trading strategies based on their risk tolerance and forecast. We first define notions of risk and reward that are natural extensions of classical competitive analysis and then illustrate our ideas using the ski-rental problem. Finally, we analyze a financial game using the risk—reward framework, and, in particular, derive an optimal risk-tolerant algorithm. Received October 8, 1997; revised March 9, 1998.     

Competitive Optimal On-Line Leasing

Consider an on-line player who needs some equipment (e.g., a computer) for an initially unknown number of periods. At the start of each period it is determined whether the player will need the equipment during the current period and the player has two options: to pay a leasing fee c and rent the equipment for the period, or to buy it for a larger amount P . The total cost incurred by the player is the sum of all leasing fees and perhaps one purchase. The above problem, called the leasing problem (in computer science folklore it is known as the ski-rental problem), has received considerable attention in the economic literature. Using the competitive ratio as a performance measure this paper is concerned with determining the optimal competitive on-line policy for the leasing problem. For the simplest version of the leasing problem (as described above) it is known and readily derived that the optimal deterministic competitive performance is achieved by leasing for the first k-1 times and then buying, where k = P/c . This strategy pays at most 2-1/k times the optimal off-line cost. When considering alternative financial transactions one must consider their net present value. Thus, accounting for the interest rate is an essential feature of any reasonable financial model. In this paper we determine both deterministic and randomized optimal on-line leasing strategies while accounting for the interest rate factor. It is shown here, for the leasing problem, that the interest rate factor reduces the uncertainty involved. We find that the optimal deterministic competitive ratio is 1 + (1+i)(1-1/k)(1 - k(i/1+i)) , a decreasing function of the interest i (for all reasonable values of i ). For some applications, realistic values of interest rates result in relatively low competitive ratios. By using randomization the on-line player can further boost up the performance. In particular, against an oblivious adversary the on-line player can attain a strictly smaller competitive ratio of 2 - ( (k/(k-1)) ^γ - 2 )/( (k/(k-1)) ^γ -1 ) where γ = ln ( 1 - k(1 - 1/(1+i)) ) / ln(1/(1+i)) . Here again, this competitive ratio strictly decreases with i . We also study the leasing problem against a distributional adversary called ``Nature.' This adversary chooses the probability distribution of the number of leasing periods and announces this distribution before the on-line player chooses a strategy. Although at the outset this adversary appears to be weaker than the oblivious adversary, it is shown that the optimal competitive ratio against Nature equals the optimal ratio against the oblivious adversary. Received October 8, 1997; revised February 8, 1998.