This paper discusses the infinite horizon static output feedback stochastic Nash games involving state-dependent noise in weakly coupled large-scale systems. In order to construct the strategy, the conditions for the existence of equilibria have been derived from the solutions of the sets of cross-coupled stochastic algebraic Riccati equations (CSAREs). After establishing the asymptotic structure along with the positive semidefiniteness for the solutions of CSAREs, recursive algorithm for solving CSAREs is derived. As a result, it is shown that the proposed algorithm attains the reduced-order computations and the reduction of the CPU time. As another important contribution, the uniqueness of the strategy set is proved for the sufficiently small parameter ε. Finally, in order to demonstrate the efficiency of the proposed algorithm, numerical example is given.

Quantifying user satisfaction is essential, because the results can help service providers deliver better services. In this work, we propose a generalizable methodology, based on survival analysis, to quantify user satisfaction in terms of session times, i.e., the length of time users stay with an application. Unlike subjective human surveys, our methodology is based solely on passive measurement, which is more cost-efficient and better able to capture subconscious reactions. Furthermore, by using session times, rather than a specific performance indicator, such as the level of distortion of voice signals, the effects of other factors like loudness and sidetone, can also be captured by the developed models. Like survival analysis, our methodology is characterized by low complexity and a simple model-developing process. The feasibility of our methodology is demonstrated through case studies of ShenZhou Online, a commercial MMORPG in Taiwan, and the most prevalent VoIP application in the world, namely Skype. Through the model development process, we can also identify the most significant performance factors and their impacts on user satisfaction and discuss how they can be exploited to improve user experience and optimize resource allocation.

Generalized Tsume-Shogi (GTS) is Tsume-Shogi on the board of size n n for arbitrary n. The problem to decide the existence of a winning sequence of moves (where the attacker must always check) on an instance of GTS was proved to be exptime-complete by Yokota et al. (2000). This paper considers the complexity of yozume problem of GTS, which is, roughly speaking, the problem whether a given position of GTS has a winning sequence other than given sequences (though the actual rule of yozume is more complicated). The detection of yozume is an important issue in designing Tsume-Shogi problems, since the modern designing rule strongly prohibits it. We define a function problem of GTS appropriately to formulate yozume problem as its Another Solution Problem (ASP; the problem to decide the existence of solutions other than given ones). Moreover, we extend the existing framework for investigating ASPs so that it can be applied to exptime-complete problems. In particular, since the decision of correctness of given winning sequences is not easy, we establish a framework to treat ASP of function problems with promises. On the basis of these results, we prove that the decision version of yozume problem of GTS is exptime-complete as a promise problem using the existing reduction which was constructed by Yokota et al. to prove the exptime-completeness of GTS.

We discuss a typical profile of the k-error linear complexity for balanced binary exponent periodic sequences and the number of periodic distinct sequences by their profiles. A numerical example with period 16 is also shown.

Most traditional board and card games, such as Chess, Chinese Chess, Go, Chinese Mahjong, Hearts, Bridge, etc., share the same playing model: Players play around tables using physical objects such as cards and may hold objects in their own private areas, e.g., players hold cards in their own hands in Bridge. In this paper, this model is called the play-on-table (POT) game model and these games following the model are called POT games. The research of this paper is summarized as follows. First, formalize the definition of the POT game model. Second, present some game systems to allow players to design and play new POT games. Third, prove that these game systems are general for all POT games. Finally, in order to demonstrate the theory, practically implement one of the general game systems that allows players to design and play new POT games in a what-you-see-is-what-you-get (WYSIWYG) manner.

Goldwasser and Sipser proved that every interactive proof system can be transformed into a public-coin one (a.k.a. an Arthur-Merlin game). Unfortunately, the applicability of their transformation to cryptography is limited because it does not preserve the computational complexity of the prover's strategy. Vadhan showed that this deficiency is inherent by constructing a promise problem Π with a private-coin interactive proof that cannot be transformed into an Arthur-Merlin game such that the new prover can be implemented in polynomial-time with oracle access to the original prover. However, the transformation formulated by Vadhan has a restriction, i.e., it does not allow the new prover and verifier to look at common input. This restriction is essential for the proof of Vadhan's negative result. This paper considers an unrestricted transformation where both the new prover and verifier are allowed to access and analyze common input. We show that an analogous negative result holds even in this unrestricted case under a non-standard computational assumption.

We propose the problem of how to transmit an information-theoretically secure bit using random deals of cards among players in hierarchical groups and a computationally unlimited eavesdropper. A player in the highest group wants to send players in lower groups a secret bit which is secure from the eavesdropper and some other players. We formalize this problem and design protocols for constructing secret key exchange spanning trees on hierarchical groups. For each protocol we give sufficient conditions to successfully construct a secret key exchange spanning tree for the hand sizes of the players and the eavesdropper.