International Journal of Foundations of Computer Science

The aim of this paper is to compute Shapley's and Banzhaf's values of cooperative games restricted by a combinatorial structure. There have been previous models developed to study the problem of games with partial cooperation. Games restricted by a communication graph were introduced by Myerson and Owen. Another type of combinatorial structure introduced by Gilles, Owen and van den Brink is equivalent to a subclass of antimatroids. Cooperative games in which the set of players is a partially ordered set, that is, games on distributive lattices was investigated by Faigle and Kern. We introduce a new combinatorial structure called augmenting system which is a generaligation of the antimatroid structure and the system of connected subgraphs of graph. We present new algorithmic procedures for computing values of games under augmenting systems restrictions and we show that there exist problems with polynomial algorithm complexity.

Let Γ = (N, v) be a cooperative game with the player set N and value function v : 2^N → R. A solution of the game is in the core if no subset of players could gain advantage by breaking away from the grand coalition of all players. This paper surveys theoretical results on the cores for some cooperative game models. These results proved that the linear program duality characterization of the core is a very powerful tool. We will focus on linear and integer programming techniques applied in this area.

In this work, the computational complexity of a hierarchic optimization problem involving in several players is studied. Each player is assigned with a linear objective function. The set of variables is partitioned such that each subset corresponds to one player as its decision variables. All the players jointly make a decision on the values of these variables such that a set of linear constraints should be satisfied. One special player, called the leader, makes decision on its decision variables before of all the other players. The rest, after learnt of the decision of the leader, make their choices so that their decisions form a Nash Equilibrium for them, breaking tie by maximizing the objective function of player. We show that the exact complexity of the problem is FP^NP-complete.

In this paper we discuss the VaR-related portfolio optimization problems. We give a scenario-based formulation of the portfolio optimization problem with VaR objective and show that the problem is NP-hard.

We are interested in computation of arbitrage condition in financial market with friction. We consider a deterministic model with a finite number of financial assets and a finite number of possible states of nature. The future return of each asset under each possible state of nature is given in the model. We derive a negative result on computational complexity of arbitrage in the case when assets are traded in integer numbers of shares and with a maximum amount of shares that can be bought for a fixed price.

It is well acknowledged that the European options can be valued by an analytic formula, but situation is quite different for the American options. Mathematically, the Black-Scholes model for the American option pricing is a free boundary problem of partial differential equation. This model is a non-linear problem; it has no closed form solution. Although approximate solutions may be obtained by some numerical methods, but the precision and stability are hard to control since they are largely affected by the singularity at the exercise boundary near expiration date. In this paper, we propose a new numerical method, namely SDA, to solve the pricing problem of the American options. Our new method combines the advantages of the Semi-analytical Method and the Sliced-fixed Boundary Finite Difference Method while overcomes demerits of the two. Using the SDA method, we can resolve the problems resulted from the singularity near the optimal exercise boundary. Numerical experiments show that the SDA method is more accurate and more stable than other numerical methods. In this paper, we focus on the American put options, but the proposed method is also applicable to other types of options.

Chandra and Toueg proposed in 1993 a new approach to overcome the impossibility of reaching deterministically Consensus — and by corollary Atomic Broadcast — in asynchronous systems subject to crash failures. They augment the asynchronous system with a possibly Unreliable Failure Detector which provides some information about the operational state of processes. In this paper, we present an extension of the Consensus problem that we call Uniform Prefix Agreement. This extension enables all the processes to propose a flow of messages during an execution — instead of one as in the Consensus problem — and uses all these proposed messages to compose the decision value. Prefix Agreement is based on an Unreliable Failure Detector. We use repeated executions of Prefix Agreement to build an efficient Uniform Atomic Broadcast algorithm. This paper describes the Uniform Prefix Agreement and Uniform Atomic Broadcast algorithms, and provides proofs of their correctness.

A common characteristic of the new distributed systems is the increasing complexity. Useful paradigms to cope with the complexity of systems are modularity and compositionality. In this paper we define a compositional method to attack the state explosion problem in model checking. The method, given a formula to be checked on a system composed of a set of parallel processes, allows syntactically reducing in a modular way the processes, in order to reduce the state space of their composition. The reduction is formula driven and is based on a notion of equivalence between processes, which is a congruence w.r.t. the parallel composition operator.

An accepting device based on the communication between finite automata working in parallel is introduced. It consists of several finite automata working independently but communicating states to each other by request. Several variants of parallel communicating finite automata systems are investigated from their computational power point of view. We prove that all of them are at most as powerful as multi-head finite automata. Homomorphical characterizations of recursively enumerable languages are obtained starting from languages recognized by all variants of parallel communicating finite automata systems having at most three components. We present a brief comparison with the parallel communicating grammar systems. Some remarks suggesting that these devices might be mildly context-sensitive ones as well as a few open problems and directions for further research are also discussed.

The local sequence alignment problem is the detection of similar subsequences in two given sequences of lengths n ≥ m. Unfortunately the common notion of local alignment suffers from some well-known anomalies which result from not taking into account the lengths of the aligned subsequences. We introduce the length restricted local alignment problem which includes as a constraint an upper limit T on the length of one of the subsequences to be aligned. Obvious extensions of dynamic programming formulations for the solution of the length restricted local alignment problem result in expensive computations: O(Tnm) time and O(Tm) space. We propose an efficient approximation algorithm using which we can find a solution satisfying the length bound, and whose score is within difference Δ of the optimum score for any given positive integer Δ in time O(nmT/Δ) using O(mT/Δ) space. We also introduce the cyclic local alignment problem and show how our idea can be applied to this case as well. This is a dual approach to the well-known cyclic edit distance problem. These results generalize directly to the case of affine gap penalties.

Culik II and Harju have shown that the ω-equivalence problem is decidable fot D0L systems. We give a partially new proof of this result by using elementary morphisms.