Search

Sensor network localization (SNL) is a challenging problem due to its inherent non-convexity and the effects of noise in inter-node ranging measurements and anchor node position. We formulate a non-convex SNL problem as a multi-player non-convex potential game and investigate the existence and uniqueness of a Nash equilibrium (NE) in both the ideal setting without measurement noise and the practical setting with measurement noise. We first show that the NE exists and is unique in the noiseless case, and corresponds to the precise network localization. Then, we study the SNL for the case with errors affecting the anchor node position and the inter-node distance measurements. Specifically, we establish that in case these errors are sufficiently small, the NE exists and is unique. It is shown that the NE is an approximate solution to the SNL problem, and that the position errors can be quantified accordingly. Based on these findings, we apply the results to case studies involving only inter-node distance measurement errors and only anchor position information inaccuracies., Comment: arXiv admin note: text overlap with arXiv:2311.03326, arXiv:2401.02471

This work studies the parameter identification problem of a generalized non-cooperative game, where each player's cost function is influenced by an observable signal and some unknown parameters. We consider the scenario where equilibrium of the game at some observable signals can be observed with noises, whereas our goal is to identify the unknown parameters with the observed data. Assuming that the observable signals and the corresponding noise-corrupted equilibriums are acquired sequentially, we construct this parameter identification problem as online optimization and introduce a novel online parameter identification algorithm. To be specific, we construct a regularized loss function that balances conservativeness and correctiveness, where the conservativeness term ensures that the new estimates do not deviate significantly from the current estimates, while the correctiveness term is captured by the Karush-Kuhn-Tucker conditions. We then prove that when the players' cost functions are linear with respect to the unknown parameters and the learning rate of the online parameter identification algorithm satisfies \mu_k \propto 1/\sqrt{k}, along with other assumptions, the regret bound of the proposed algorithm is O(\sqrt{K}). Finally, we conduct numerical simulations on a Nash-Cournot problem to demonstrate that the performance of the online identification algorithm is comparable to that of the offline setting., Comment: 10 pages, 5 figures

There has been significant recent interest in leader-follower security games, where the leader dominates the decision process with the Stackelberg equilibrium (SE) strategy. However, such a leader-follower scheme may become invalid in practice due to subjective or objective factors, and then the Nash equilibrium (NE) strategy may be an alternative option. In this case, the leader may face a dilemma of choosing an SE strategy or an NE strategy. In this paper, we focus on a unified three-player leader-follower security game and study the coincidence between SE and NE. We first explore a necessary and sufficient condition for the case that each SE is an NE, which can be further presented concisely when the SE is unique. This condition not only provides access to seek a satisfactory SE strategy but also makes a criterion to verify an obtained SE strategy. Then we provide another appropriate condition for the case that at least one SE is an NE. Moreover, since the coincidence condition may not always be satisfied, we describe the closeness between SE and NE, and give an upper bound of their deviation. Finally, we show the applicability of the obtained theoretical results in several practical security cases, including the secure transmission problem and the cybersecurity defense.

Consider a $k$-valued network. Two kinds of (control) invariant subspaces, called state and dual invariant subspaces, are proposed, which are subspaces of state space and dual space respectively. Algorithms are presented to verify whether a dual subspace is a dual or dual control invariant subspace. The bearing space of $k$-valued (control) networks is introduced. Using the structure of bearing space, the universal invariant subspace is introduced, which is independent of the dynamics of particular networks. Finally, the relationship between state invariant subspace and dual invariant subspace of a network is investigated. A duality property shows that if a dual subspace is invariant then its perpendicular state subspace is also invariant and vice versa., Comment: 15 pages, 3 figures

The macroscopic fundamental diagram (MFD) is a powerful and popular tool that describes a network scale traffic operational state and serve as the plant model of perimeter control. As both the supply and the demand suffer from random disturbances, the traffic flow dynamics cannot be said to be deterministic. A stochastic MFD model can generate a stochastic evolution of the system state with desired distribution of aggregated variables is still lacking. A stochastic formulation of MFD, that considers the accumulation-dependent variations, is proposed to fill this gap. The model is based on the stochastic differential equation (SDE) theory. First, the exit flow variation is formulated as a Wiener-driven process, which admits the accumulation-of dependent variations. The stochastic MFD model is then constructed by combining the exit flow variations model. The solution of the system state is derived by the forward Fokker-Planck equation. The stability of the model is analyzed, and the parameters of a calibration method are provided. Several cases of the model are then tested. The results show that the model can be applied to different functional MFD forms, and the hysteresis and gridlock phenomenon is reproduced. The proposed MFD model can be used in the network analysis and control that considers the system's stochastic evolution.

We design a distributed algorithm to seek generalized Nash equilibria of a robust game with uncertain coupled constraints. Due to the uncertainty of parameters in set constraints, we aim to find a generalized Nash equilibrium in the worst case. However, it is challenging to obtain the exact equilibria directly because the parameters are from general convex sets, which may not have analytic expressions or are endowed with high-dimensional nonlinearities. To solve this problem, we first approximate parameter sets with inscribed polyhedrons, and transform the approximate problem in the worst case into an extended certain game with resource allocation constraints by robust optimization. Then we propose a distributed algorithm for this certain game and prove that an equilibrium obtained from the algorithm induces an $\epsilon$-generalized Nash equilibrium of the original game, followed by convergence analysis. Moreover, resorting to the metric spaces and the analysis on nonlinear perturbed systems, we estimate the approximation accuracy related to $\epsilon$ and point out the factors influencing the accuracy of $\epsilon$.

In this paper, we aim to design a distributed approximate algorithm for seeking Nash equilibria of an aggregative game. Due to the local set constraints of each player, projectionbased algorithms have been widely employed for solving such problems actually. Since it may be quite hard to get the exact projection in practice, we utilize inscribed polyhedrons to approximate local set constraints, which yields a related approximate game model. We first prove that the Nash equilibrium of the approximate game is the $\epsilon$-Nash equilibrium of the original game, and then propose a distributed algorithm to seek the $\epsilon$-Nash equilibrium, where the projection is then of a standard form in quadratic programming. With the help of the existing developed methods for solving quadratic programming, we show the convergence of the proposed algorithm, and also discuss the computational cost issue related to the approximation. Furthermore, based on the exponential convergence of the algorithm, we estimate the approximation accuracy related to $\epsilon$. Additionally, we investigate the computational cost saved by approximation on numerical examples.

Quantum computing enables quantum neural networks (QNNs) to have great potentials to surpass artificial neural networks (ANNs). The powerful generalization of neural networks is attributed to nonlinear activation functions. Although various models related to QNNs have been developed, they are facing the challenge of merging the nonlinear, dissipative dynamics of neural computing into the linear, unitary quantum system. In this paper, we establish different quantum circuits to approximate nonlinear functions and then propose a generalizable framework to realize any nonlinear quantum neuron. We present two quantum neuron examples based on the proposed framework. The quantum resources required to construct a single quantum neuron are the polynomial, in function of the input size. Finally, both IBM Quantum Experience results and numerical simulations illustrate the effectiveness of the proposed framework., Comment: 9 pages, 8 figures

In this paper, we propose distributed algorithms that solve a system of Boolean equations over a network, where each node in the network possesses only one Boolean equation from the system. The Boolean equation assigned at any particular node is a {\em private} equation known to this node only, and the nodes aim to compute the exact set of solutions to the system without exchanging their local equations. We show that each private Boolean equation can be locally lifted to a linear algebraic equation under a basis of Boolean vectors, leading to a network linear equation that is distributedly solvable using existing distributed linear equation algorithms as a subroutine. A number of exact or approximate solutions to the induced linear equation are then computed at each node from different initial values. The solutions to the original Boolean equations are eventually computed locally via a Boolean vector search algorithm. We prove that given solvable Boolean equations, when the initial values of the nodes for the distributed linear equation solving step are i.i.d selected according to a uniform distribution in a high-dimensional cube, our algorithms return the exact solution set of the Boolean equations at each node with high probability. Furthermore, we present an algorithm for distributed verification of the satisfiability of Boolean equations, and prove its correctness. Finally, we show that by utilizing linear equation solvers with differential privacy to replace the in-network computing routines, the overall distributed Boolean equation algorithms can be made differentially private. Under the standard Laplace mechanism, we prove an explicit level of noises that can be injected in the linear equation steps for ensuring a prescribed level of differential privacy., Comment: 34 pages, 5 figures

In this paper, we study the recursion of measurement outcomes for open quantum networks under sequential measurements. Open quantum networks are networked quantum subsystems (e.g., qubits) with the state evolutions described by a continuous Lindblad master equation. When measurements are performed sequentially along such continuous dynamics, the quantum network states undergo random jumps and the corresponding measurement outcomes can be described by a vector of probabilistic Boolean variables. The induced recursion of the Boolean vectors forms a probabilistic Boolean network. First of all, we show that the state transition of the induced Boolean networks can be explicitly represented through realification of the master equation. Next, when the open quantum dynamics is relaxing in the sense that it possesses a unique equilibrium as a global attractor, structural properties including absorbing states, reducibility, and periodicity for the induced Boolean network are direct consequences of the relaxing property. Particularly, we show that generically, relaxing quantum dynamics leads to irreducible and aperiodic chains for the measurement outcomes. Finally, we show that for quantum consensus networks as a type of non-relaxing open quantum network dynamics, the communication classes of the measurement-induced Boolean networks are encoded in the quantum Laplacian of the underlying interaction graph., Comment: 21 pages, 3 figures

In this paper, we study extended linear regression approaches for quantum state tomography based on regularization techniques. For unknown quantum states represented by density matrices, performing measurements under certain basis yields random outcomes, from which a classical linear regression model can be established. First of all, for complete or over-complete measurement bases, we show that the empirical data can be utilized for the construction of a weighted least squares estimate (LSE) for quantum tomography. Taking into consideration the trace-one condition, a constrained weighted LSE can be explicitly computed, being the optimal unbiased estimation among all linear estimators. Next, for general measurement bases, we show that $\ell_2$-regularization with proper regularization gain provides even lower mean-square error under a cost in bias. The regularization parameter is tuned by two estimators in terms of a risk characterization. Finally, a concise and unified formula is established for the regularization parameter with complete measurement basis under an equivalent regression model, which proves that the proposed tuning estimators are asymptotically optimal as the number of samples grows to infinity under the risk metric. Additionally, numerical examples are provided to validate the established results., Comment: 33 pages, 8 figures

In this paper, we study dynamical quantum networks which evolve according to Schr\"odinger equations but subject to sequential local or global quantum measurements. A network of qubits forms a composite quantum system whose state undergoes unitary evolution in between periodic measurements, leading to hybrid quantum dynamics with random jumps at discrete time instances along a continuous orbit. The measurements either act on the entire network of qubits, or only a subset of qubits. First of all, we reveal that this type of hybrid quantum dynamics induces probabilistic Boolean recursions representing the measurement outcomes. With global measurements, it is shown that such resulting Boolean recursions define Markov chains whose state-transitions are fully determined by the network Hamiltonian and the measurement observables. Particularly, we establish an explicit and algebraic representation of the underlying recursive random mapping driving such induced Markov chains. Next, with local measurements, the resulting probabilistic Boolean dynamics is shown to be no longer Markovian. The state transition probability at any given time becomes dependent on the entire history of the sample path, for which we establish a recursive way of computing such non-Markovian probability transitions. Finally, we adopt the classical bilinear control model for the continuous Schr\"odinger evolution, and show how the measurements affect the controllability of the quantum networks., Comment: 26 pages, 7 figures

Consider a multiplayer game, and assume a system level objective function, which the system wants to optimize, is given. This paper aims at accomplishing this goal via potential game theory when players can only get part of other players' information. The technique is designing a set of local information based utility functions, which guarantee that the designed game is potential, with the system level objective function its potential function. First, the existence of local information based utility functions can be verified by checking whether the corresponding linear equations have a solution. Then an algorithm is proposed to calculate the local information based utility functions when the utility design equations have solutions. Finally, consensus problem of multiagent system is considered to demonstrate the effectiveness of the proposed design procedure., Comment: 6 pages, 5 figures, 2018 IEEECDC

This paper aims to provide a systemic analysis to social opinion dynamics subject to individual biases. As a generalization of the classical DeGroot social interactions, defined by linearly coupled dynamics of peer opinions that evolve over time, biases add to state-dependent edge weights and therefore lead to highly nonlinear network dynamics. Previous studies have dealt with convergence and stability analysis of such systems for a few specific initial node opinions and network structures, and here we focus on how individual biases affect social equilibria and their stabilities. First of all, we prove that when the initial network opinions are polarized towards one side of the state space, node biases will drive the opinion evolution to the corresponding interval boundaries. Such polarization attraction effect continues to hold under even directed and switching network structures. Next, for a few fundamental network structures, some important interior network equilibria are presented explicitly for a wide range of system parameters, which are shown to be locally unstable in general. Particularly, the interval centroid is proven to be unstable regardless of the bias level and the network topologies.

This paper establishes a framework for the acceleration of quantum gossip algorithms by introducing local clique operations to networks of interconnected qubits. Cliques are local structures in complex networks being complete subgraphs. Based on cyclic permutations, clique gossiping leads to collective multi-party qubit interactions. This type of algorithm can be physically realized by a series of local environments using coherent methods. First of all, we show that at reduced states, these cliques have the same acceleration effects as their roles in accelerating classical gossip algorithms, which can even make possible finite-time convergence for suitable network structures. Next, for randomized selection of cliques where node updates enjoy a more self-organized and scalable sequencing, we show that the rate of convergence is precisely improved by $\mathcal{O}(k/n)$ at the reduced states, where $k$ is the size of the cliques and $n$ is the number of qubits in the network. The rate of convergence at the coherent states of the overall quantum network is proven to be decided by the spectrum of a mean-square error evolution matrix. Explicit calculation of such matrix is rather challenging, nonetheless, the effect of cliques on the coherent states' dynamics is illustrated via numerical examples. Interestingly, the use of larger quantum cliques does not necessarily increase the speed of the network density aggregation, suggesting quantum network dynamics is not entirely decided by its classical topology., Comment: 12 pages, 2 figures

Semi-tensor product(STP) or matrix (M-) product of matrices turns the set of matrices with arbitrary dimensions into a monoid $({\cal M},\ltimes)$. A matrix (M-) addition is defined over subsets of a partition of ${\cal M}$, and a matrix (M-) equivalence is proposed. Eventually, some quotient spaces are obtained as vector spaces of matrices. Furthermore, a set of formal polynomials is constructed, which makes the quotient space of $({\cal M},\ltimes)$, denoted by $(\Sigma, \ltimes)$, a vector space and a monoid. Similarly, a vector addition (V-addition) and a vector equivalence (V-equivalence) are defined on ${\cal V}$, the set of vectors of arbitrary dimensions. Then the quotient space of vectors, $\Omega$, is also obtained as a vector space. The action of monoid $({\cal M},\ltimes)$ on ${\cal V}$ (or $(\Sigma, \ltimes)$ on $\Omega$) is defined as a vector (V-) product, which becomes a pseudo-dynamic system, called the cross-dimensional linear system (CDLS). Both the discrete time and the continuous time CDLSs have been investigated. For certain time-invariant case, the solutions (trajectories) are presented. Furthermore, the corresponding cross-dimensional linear control systems are also proposed and the controllability and observability are discussed. Both M-product and V-product are generalizations of the conventional matrix product, that is, when the dimension matching condition required by the conventional matrix product is satisfied they coincide with the conventional matrix product. Both M-addition and V-addition are generalizations of conventional matrix addition. Hence, the dynamics discussed in this paper is a generalization of conventional linear system theory., Comment: 22 pages

This paper proposes and investigates a Boolean gossip model as a simplified but non-trivial probabilistic Boolean network. With positive node interactions, in view of standard theories from Markov chains, we prove that the node states asymptotically converge to an agreement at a binary random variable, whose distribution is characterized for large-scale networks by mean-field approximation. Using combinatorial analysis, we also successfully count the number of communication classes of the positive Boolean network explicitly in terms of the topology of the underlying interaction graph, where remarkably minor variation in local structures can drastically change the number of network communication classes. With general Boolean interaction rules, emergence of absorbing network Boolean dynamics is shown to be determined by the network structure with necessary and sufficient conditions established regarding when the Boolean gossip process defines absorbing Markov chains. Particularly, it is shown that for the majority of the Boolean interaction rules, except for nine out of the total $2^{16}-1$ possible nonempty sets of binary Boolean functions, whether the induced chain is absorbing has nothing to do with the topology of the underlying interaction graph, as long as connectivity is assumed. These results illustrate possibilities of {relating dynamical} properties of Boolean networks to graphical properties of the underlying interactions.