Search results for " Computer Science"
showing 10 items of 3983 documents
An efficient distributed algorithm for generating and updating multicast trees
2006
As group applications are becoming widespread, efficient network utilization becomes a growing concern. Multicast transmission represents a necessary lower network service for the wide diffusion of new multimedia network applications. Multicast transmission may use network resources more efficiently than multiple point-to-point messages; however, creating optimal multicast trees (Steiner Tree Problem in networks) is prohibitively expensive. This paper proposes a distributed algorithm for the heuristic solution of the Steiner Tree Problem, allowing the construction of effective distribution trees using a coordination protocol among the network nodes. Furthermore, we propose a novel distribut…
A new Media Access Control layer Quality of Service multicast scheme for IEEE 802.11s based wireless mesh networks
2014
Inderscience Publishers; International audience; We propose a new Media Access Control (MAC) layer enabling Quality of Service (QoS) multicast scheme for IEEE 802.11s networks, where a unicast routing protocol called HWMP (Hybrid Wireless Mesh Protocol) is defined. The HWMP protocol is more adapted for best effort traffic, that's why its usage is not suitable for real time multimedia applications. The goal of our proposed mechanism is to take into account multicast communication under QoS constraints for the IEEE 802.11s mesh networks where no QoS multicasting has been defined. Our multicasting scheme handles QoS guarantee for real time applications. Indeed, our scheme is based on finding t…
Introduction to the GiNaC Framework for Symbolic Computation within the C++ Programming Language
2002
AbstractThe traditional split into a low level language and a high level language in the design of computer algebra systems may become obsolete with the advent of more versatile computer languages. We describe GiNaC, a special-purpose system that deliberately denies the need for such a distinction. It is entirely written in C++and the user can interact with it directly in that language. It was designed to provide efficient handling of multivariate polynomials, algebras and special functions that are needed for loop calculations in theoretical quantum field theory. It also bears some potential to become a more general purpose symbolic package.
Crowd-Averse Cyber-Physical Systems: The Paradigm of Robust Mean-Field Games
2016
For a networked controlled system, we illustrate the paradigm of robust mean-field games. This is a modeling framework at the interface of differential game theory, mathematical physics, and $H_{\infty}$ - optimal control that tries to capture the mutual influence between a crowd and its individuals. First, we establish a mean-field system for such games including the effects of adversarial disturbances. Second, we identify the optimal response of the individuals for a given population behavior. Third, we provide an analysis of equilibria and their stability.
On coincidence of feedback and global Stackelberg equilibria in a class of differential games
2021
This paper shows for a class of differential games that the global Stackelberg equilibrium (GSE) coincides with the feedback Stackelberg equilibrium (FSE), although the GSE assumes that the leader/regulator an- nounces at the initial time the regulatory instrument rule she will follow for the rest of the game, while in the FSE, the regulator at any time chooses the optimal level of the regulatory instrument rate. This coincidence is based on the fact that the FSE is calculated using dynamic programming what implies that although the regulator chooses the regulatory instrument rate level that maximizes social welfare, the first-order condition for the maximization of the right-hand side of t…
Computational Complexity and Communication: Coordination in Two-Player Games
2002
The main contribution of this paper is the development and application of cryptographic techniques to the design of strategic communication mechanisms. One of the main assumptions in cryptography is the limitation of the computational power available to agents. We introduce the concept of limited computational complexity, and by borrowing results from cryptography, we construct a communication protocol to establish that every correlated equilibrium of a two-person game with rational payoffs can be achieved by means of computationally restricted unmediated communication. This result provides an example in game theory where limitations of computational abilities of players are helpful in solv…
Pragmatic languages with universal grammars
2012
Abstract This paper constructs the equilibrium for a specific code that can be seen as a “universal grammar” in a class of common interest Sender–Receiver games where players communicate through a noisy channel. We propose a Senderʼs signaling strategy which does not depend on either the game payoffs or the initial probability distribution. The Receiverʼs strategy partitions the set of possible sequences into subsets, with a single action assignment to each of them. The Senderʼs signaling strategy is a Nash equilibrium, i.e. when the Receiver responds best to the Senderʼs strategy, the Sender has no incentive to deviate. An example shows that a tie-breaking decoding is crucial for the block…
Provable Advantage for Quantum Strategies in Random Symmetric XOR Games
2013
Non-local games are widely studied as a model to investigate the properties of quantum mechanics as opposed to classical mechanics. In this paper, we consider a subset of non-local games: symmetric XOR games of $n$ players with 0-1 valued questions. For this class of games, each player receives an input bit and responds with an output bit without communicating to the other players. The winning condition only depends on XOR of output bits and is constant w.r.t. permutation of players. We prove that for almost any $n$-player symmetric XOR game the entangled value of the game is $\Theta (\frac{\sqrt{\ln{n}}}{n^{1/4}})$ adapting an old result by Salem and Zygmund on the asymptotics of random tr…
Quantum-over-Classical Advantage in Solving Multiplayer Games
2020
We study the applicability of quantum algorithms in computational game theory and generalize some results related to Subtraction games, which are sometimes referred to as one-heap Nim games.
Modular Strategies for Recursive Game Graphs
2006
AbstractMany problems in formal verification and program analysis can be formalized as computing winning strategies for two-player games on graphs. In this paper, we focus on solving games in recursive game graphs which can model the control flow in sequential programs with recursive procedure calls. While such games can be viewed as the pushdown games studied in the literature, the natural notion of winning in our framework requires the strategies to be modular with only local memory; that is, resolution of choices within a module does not depend on the context in which the module is invoked, but only on the history within the current invocation of the module. While reachability in (global…