{'fraction_non_alphanumeric': 0.039503560738982355, 'fraction_numerical': 0.01104345133656724, 'mean_word_length': 4.219797979797979, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Convergence Analysis of Iterated Best Response for a Trusted Computation Game

We introduce a game of trusted computation in which a sensor equipped with limited computing power leverages a central node to evaluate a specified function over a large dataset, collected over time. We assume that the central computer can be under attack and we propose a strategy where the sensor retains a limited amount of the data to counteract the effect of attack. We formulate the problem as a two player game in which the sensor (defender) chooses an optimal fusion strategy using both the non-trusted output from the central computer and locally stored trusted data. The attacker seeks to compromise the computation by influencing the fused value through malicious manipulation of the data stored on the central node. We first characterize all Nash equilibria of this game, which turn out to be dependent on parameters known to both players. Next we adopt an Iterated Best Response (IBR) scheme in which, at each iteration, the central computer reveals its output to the sensor, who then computes its best response based on a linear combination of its private local estimate and the untrusted third-party output. We characterize necessary and sufficient conditions for convergence of the IBR along with numerical results which show that the convergence conditions are relatively tight.


Introduction
The Internet of Things (IoT) [1] is the next generation internet where many embedded devices (sensors, actuators, controllers, etc.) are interconnected and can exchange data. Although such devices are becoming increasingly more advanced and capable, the amount of data they can process is still a small fraction of what they can collect. As a consequence, IoT devices may need to leverage intermediate but more capable devices that can store and compute over larger data streams.
We study the problem where a sensor (short for IoT device) exchanges data with a larger and more powerful computer to carry out a specific computation on the data the sensor has collects over a certain period of time. Ideally, the sensor would be able to send/stream the data to the computer, which would then compute the function and send back the result. However, we assume here that the data stored in the central computer can be manipulated maliciously by an attacker. In this case, the sensor has three options: 1) to retain a small amount of the data and compute the function of interest on such trustworthy data knowing that the computation will not be as accurate or, 2) take the risk that the attack is only mildly compromising the data on the central computer so that the result of the computation is close to the true value; or, 3) try to exchange partial results iteratively with the central computer and fuse locally trusted computation on small sample with tampered computation on the full dataset. This paper formalizes the third scenario, which has the other two as limiting cases. In particular, we model this problem of trusted computation as a game between the sensor/central computer and the attacker. We design and analyze a simple protocol in which each player plays its best response and we study its convergence properties. Additionally, this paper makes a "worst case" assumption, namely that the attacker knows exactly the fusion strategy adopted by the sensor.
The approach we consider in this paper is related to an emerging field called adversarial machine learning, wherein two parties, a learner and an attacker, are involved, see [10,3,14]. The learner uses data to train, for example, a classifier or a regressor, and the attacker is modifying the data so that the learner ends up training the algorithm incorrectly. In this context, the problem is posed as a Bayesian game [14], where the learner minimizes the effect of the attack on the learning algorithm, whereas the attacker maximizes the deviation of such learning algorithm from the correct result and towards a strategically chosen outcome, under the assumption that only a subset of the data can be modified. In [14], for example, the e-mail spam problem is considered, where the learner is set to train a classifier to discriminate between spam and non-spam, while the attacker tries to maximize the chances that a spam is classified as non-spam.
The approach considered in this paper also relates to the procedure of fictitious play (FP). In this procedure, each player tries to learn the probability distribution from which the opponent is drawing its actions [5,13]. A recent body of work in the control literature analyzes convergence of fictitious play for several scenarios [15,16,11]. In particular, [15] presents unified energy-based convergence proofs that work for several special classes of games under FP. In [16], convergence to Nash equilibria is analyzed under the assumption that each player can access the derivatives of the update mechanisms, leading to dynamic FP. A variant of FP, known as Joint Strategy FP, is proposed and the convergence analyzed for several classes of games, especially in high-dimensional spaces, see [11]. More recently, Gaussian cheap talk games, such as [8], have been considered. In this context, a sender (adversary) sends corrupted information to a receiver (sensor) under the assumption that the adversary has full knowledge of the receiver's private information.

Main Contributions
The contributions of this paper are four-fold. First, we formulate a new problem on trusted computation within a game-theoretic framework and adopt an Iterated Best Response (IBR) [12,9] algorithm to compute final strategies for the sensor and the attacker. More specifically, we consider a protocol such that at each iteration, the attacker reveals its output to the sensor that then computes its best response as a linear combination of its private local estimate and of the untrusted output. The attacker can then, based on the announced policy of the sensor, decide its best response. There is a clear mismatch in the information pattern between attacker and sensor and, in particular, the fact that the attacker cannot access the realization of the private local estimate of the sensor distinguishes this work from the information pattern considered in cheap talk games [8].
Second, we characterize conditions on the existence of equilibria of the game. These conditions and the equilibria themselves turn out to be functions of all of the problem parameters, viz., the private information belonging to both players. Therefore, to obtain results from a single player's perspective, a third contribution of this paper is to define two notions of convergence for the IBR algorithm, depending upon whether the algorithm converges for some initial value picked by the attacker (weak convergence), or for every initial value (strong convergence). We derive necessary conditions for weak convergence and sufficient conditions for strong convergence. If the algorithm converges, then it also tells the sensor how to optimally fuse its private estimate with the output. We identify regimes in which some sufficient conditions are also necessary. Numerical simulations indicate that the conditions are relatively tight.
Fourth and finally, the analysis in this paper allows for a certain level of mismatch in the distributions used by the players in computing their respective cost functions. This generalizes the analysis presented in the preliminary conference version [4], which assumed that the attacker knows precisely the mean of the distribution used by the sensor to compute its private estimate. Additionally, in the special scenario considered in [4], the analysis in this paper recovers the results from [4], and in one of the cases, also improves the result.
Given that the proposed framework requires an iterative process between sensor and the central computer, the algorithm presented in this paper could be suitable for computation algorithms that are iterative in nature so that partial results can be exchanged between sensor and the central computer. Examples are eigenvalue/eigenvector computation, matrix factorization, iterative optimization methods, etc. The connection of this work to control theory lies in the fact that convergence analysis of the IBR essentially leads to a closed loop dynamical system. This aspect is similar in flavor to the set-ups analyzed in [15,16,11]. Using geometric relationships to bound the evolution, we determine necessary and sufficient conditions on the parameters involved which will lead to stability from any/some initial conditions.

Paper Organization
The paper is organized as follows. The problem formulation and the proposed approach is described in Section 2. Conditions for the existence of equilibria together with an insightful geometric interpretation are presented in Section 3. Convergence results for the IBR algorithm are derived in Section 4 along with supporting numerical results. A special case of equal means of the random variables used by the two players is discussed in Section 5. Finally, conclusions and directions for future research are discussed in Section 6.

Problem Formulation
The problem scenario is depicted in Figure 1. This work assumes that the data and the computation to be carried out are such that it is possible for the sensor to compute an estimate of the true output locally using some random subset of the data, and that the statistics (up to the mean with a finite second moment) about how the actual value is distributed given a value of estimate is known to the sensor. For example, suppose that the data d ∈ R N ×M , consisting of N data points each represented by an M -dimensional feature vector, is uploaded through a trusted sensor to the third-party computer. During the upload process, the sensor could retain a randomly sparsified sampled ∈ R N ×M of the original data d. The data, once stored on the central computer, can be compromised by the attacker leading to a different valued ∈ R N ×M . The sensor seeks to compute the true value of the function y = g(d) ∈ R k of the data d where g : R N ×M → R k is an algorithm of interest. For example, g(d) ∈ R could be the maximum singular value of a matrix withd being a sparsified sample of d. The sensor has only an approximate knowledge,ŷ = g(d) ∈ R k , of y, obtained from the sparsified datad. The third-party computer computes the valueȳ = g(d) ∈ R k based on the corrupted datad. This paper does not address the problem of how to construct a sparsified sampled, but rather makes an implicit assumption that for a given number of non-zero The computer returns some valueȳ as the output of the computation, while the sensor computes a valueŷ based on the sampled. The goal is to fuse, using a function φ(.), the two quantitiesŷ andȳ in an optimal manner. elements ind and a corresponding sparsification procedure, the distribution of y givenŷ can be characterized a priori. The actual construction of a specific sampling procedure for a computation such as the maximum eigenvalue would be a topic of future investigation and we direct an interested reader to [2] and [7] for related existing results.
The sensor needs to design a fusion function φ : R k × R k → R k that provides y fused so that the effect of the attack is minimized, i.e., the sensor seeks to minimize the squared error between y fused and y in an expected sense. On the other hand, the attacker seeks to drive the fused value to a different value y A instead of the true y, and therefore, seeks to minimize the squared error between y fused and y A in an expected sense. The attacker returns a valueȳ ∈ R k , which will be chosen in order to minimize the mean squared error between y fused and y A .
Given a value ofŷ, one can view the true value y as a random variable, and we assume that the conditional distribution of y givenŷ (y|ŷ) is known to the sensor. From the sensor's perspective, this work only requires it to know the mean of y givenŷ and the fact that y givenŷ has bounded variance. This paper proposes a new protocol between the sensor and the computer that will enable the sensor to compute an optimal fusion strategy y fused = φ(ŷ,ȳ) ∈ R k , in the space of convex combinations of the approximate valueŷ and the computer's outputȳ, to minimize the mean square error, i.e., where the norm · is the 2-norm. The goal of the attacker is to pick aȳ to minimize the mean square error where y A is a value that the attacker chooses to corrupt the sensor. We will assume that y A is a fixed and non-random value known only to the attacker. In other words, the goal of the attacker is to choose a valueȳ to be given to the sensor as the output of the computation so that when the sensor fuses this value with its private estimateŷ, the fused value y fused becomes close to a certain value y A which is selected by the attacker. The value y A is the value that the attacker wants the sensor to believe is the true output. The mismatch in the information structure available to both players is reflected in their respective cost functions in that the random variable relative to which the expectation is computed is the one whose realization is not known to that player.
In the space of allowed strategies, we choose φ(.) = φ α (.) to be a convex combination ofŷ andȳ, namely In other words, the sensor needs to compute an α ∈ [0, 1], thus deciding the weight to attach to its own valueŷ and the attacker's outputȳ. Therefore, both cost functions, J D and J A are functions of the action α ∈ [0, 1] of the sensor and the actionȳ ∈ R k of the attacker. To be specific, let µ denote the expected value of y givenŷ using a density function chosen by the sensor, modeling the sensor's knowledge about the data, and let ζ denote the expected value ofŷ using the density function chosen by the attacker, modeling the knowledge the attacker has about the data. In the space of linear strategies (3), the cost functions (1) simplifies to: where µ := R k wf y|ŷ (w)dw, and f x|y (·) denotes the probability density function of a random variable x given y. The cost function (2) simplifies to: where the quantity ζ := R k wfŷ(w)dw. This is a non zero-sum game for which we will consider the following notion of equilibrium.
Further, if α * ∈ (0, 1), then the resulting Nash equilibrium pair is said to be mixed.
In other words, a pair of strategies is in equilibrium if no other strategy can give a strictly better cost against the opponent's strategy, from each player's perspective. Further, when the best response of the sensor is mixed, it means that the sensor selects a non-trivial weighted combination ofŷ andȳ. However, it will be clear from the next section that an explicit one-shot computation of the equilibrium strategies requires the players to have full knowledge of all the problem parameters, i.e.,ŷ, y, y A , and the expected values µ and ζ of y givenŷ and y, respectively. Clearly, from one player's point of view, this information is not available. Indeed, y A is a private information that the attacker has and is not shared with the sensor and theŷ is private information of the sensor which is not shared with the attacker. Therefore, we will consider the following iterative scheme in which each player will announce its best response to a strategy announced by the opponent, with the attacker playing first. This protocol is summarized in Algorithm 1.

Algorithm 1 Iterated Best Response
Assumes: Attacker plays first, i.e., select a value forȳ 0 . i = 0 α i = 0 # Exit when α reaches steady-state or becomes 1 while α i sequence has not converged do . # Exit and trust the sensor output only if α i == 1 then return α i end if end while return α i andȳ i To apply Algorithm 1, we will first need to compute the best responses of each player against an action of the opponent. Setting ∂J D /∂α = 0 in (4), we obtain the unconstrained minimizer Due to the constraint α * ∈ [0, 1], the best response for the sensor is: A similar calculation for the attacker yields, Observe thatȳ * is a linear combination of y A and ζ. Since we have a total of four parameterŝ y, ζ, y A and µ, it is convenient considering the plane containing the three pointsŷ, ζ, y A and let µ be the orthogonal projection of µ on to this plane. Therefore, we can write µ :=μ + µ ⊥ . Since Interestingly, we can give a geometric interpretation to (8) and (7), as shown in Figure 2. In particular, the figure illustrates the locations ofȳ that lead to different values of α * , given the values of y A ,ŷ andμ. In the plane defined by y A ,ŷ and ζ, a given subspace containing y A can be divided into at most three distinct regions corresponding to the three regimes in (8). The green regime corresponds to the set of pointsȳ for which α * (ȳ) = 0 and when it exists, it lies between two blue regimes corresponding to the set of pointsȳ for which α * (ȳ) ∈ (0, 1). The red regime corresponds to the set of pointsȳ for which α * (ȳ) = 1. Note that the boundary points between the green and blue regimes satisfy the property that the lines joining them toμ andŷ are orthogonal to each other, as highlighted in Figure 2.
The termination condition within the if loop of Algorithm 1 is due to the fact that when α = 1, it implies that the output of the central computer is not to be trusted, and thereafter, the computer is not providing any further useful information than the sensor's private value ofŷ. In order to discard trivial initial conditions for which Algorithm 1 would exit at the first iteration, we will restrict our discussion to non-trivial initial values ofȳ 0 defined next.
Definition 2 (Non-trivial initial condition) An initial conditionȳ 0 is said to be non-trivial if Algorithm 1 does not exit at the first iteration.
We will consider the following two notions of convergence for Algorithm 1.
Definition 3 (Weak Convergence) Algorithm 1 is said to possess weak convergence property if, for some non-trivial initial conditionȳ 0 and for some values of the means µ and ζ, Algorithm 1 outputs α * ∈ [0, 1).
Definition 4 (Strong Convergence) Algorithm 1 is said to possess strong convergence property if, for every non-trivial choice ofȳ 0 , and for every value of the means µ and ζ, Algorithm 1 outputs α * ∈ [0, 1).
In the sequel, we will see that the weak convergence concept will be useful from the sensor's perspective, whereas strong convergence will be useful from the attacker's perspective. The main contributions in the rest of this paper are to present conditions on the problem parameters, viz.ŷ ,y, y A , µ and ζ, under which: 1) equilibrium strategies exist for Algorithm 1 and 2) Algorithm 1 demonstrates weak or strong convergence properties. Whenever Algorithm 1 converges, then the steady-state strategies correspond to a Nash equilibrium (cf. Definition 1).

Equilibrium Strategies
In this section, we will derive conditions on the parametersŷ, y A , µ and ζ under which equilibria exist for the system of equations (6) and (7).
The following is the main result on the equilibria of the above system.  (6) and (7), we have the following: i. The pair of strategies (α * ,ȳ * ) = (0, y A ) is an equilibrium if and only if ii. An equilibrium in mixed strategies exists if and only if This result provides conditions on the game parameters under which one of the two types of equilibria considered in this paper would exist. The first type is the one when α * = 0, i.e., the sensor completely trusts the output from the central computer. The condition in (i) essentially describes the set of values for the attacker's intent y A for which it will be beneficial for the sensor to use the outputȳ from the central computer than its own valueŷ. The second type is the one which will require the sensor to fuse its private valueŷ with the valueȳ in a non-trivial way (α * ∈ (0, 1)). Proof: i. The claim follows from the best response of the players for the case when α * = 0. In this case,ȳ * = y A . Conversely, ifȳ * = y A , then α * = 0 if and only if which establishes the first claim.
ii. Since we are searching for mixed policies α * , we substitute the expression for α * (ȳ) into the fixed point equation forȳ to obtain Subtracting ζ from both sides, we havē By denotingz :=ȳ − ζ, we obtain where r is a scalar that must satisfy On simplifying, we obtain the following quadratic equation in r: The condition now follows from the existence of real roots to the above quadratic equation.
Clearly, the computation of equilibria requires complete information of the problem parameters. Therefore, in the next sub-section, we will characterize conditions on the parameters under which Algorithm 1 will converge.

Convergence Analysis
In this section, we will derive conditions under which Algorithm 1 possesses weak and strong convergence.
From the point of view of the sensor, the goal is to characterize conditions on the attack parameter y A for which Algorithm 1 will converge in the weak and in the strong sense. However, there is an additional uncertainty on where the attacker's mean ζ will lie. We will commence the convergence analysis for a given value of ζ and then extend it to the case when there is a bound on the amount of mismatch, such as one in the following assumption. This assumption is reasonable to expect because the deviation ŷ − µ will be relatively large when only a small subset of the data being sampled. The convergence analysis will require two intermediate results using geometry which we present in the next sub-section.

Preliminary Geometric Results
Given any y A , we will first show that Assumption 4.1 leads to the following upper bound on ζ −μ , whereμ is the orthogonal projection of µ on to the plane containing ζ, y A andŷ. Proof: Consider a realization of the parameters ζ,ŷ, y A and µ as shown in Figure 3. Sinceμ is the orthogonal projection of µ on to the plane containing ζ,ŷ and y A , Applying the triangle inequality, we obtain where the second inequality follows sinceμ is the orthogonal projection of µ on to the plane containing ζ, y A andŷ, the third inequality follows from Assumption 4.1 and the final inequality follows from (10). We will also require another geometric result which will aid the proof of the necessary condition. We introduce the following notation: given two vectors x 1 , x 2 ∈ R k , the vector Proj(x 1 , x 2 ) ∈ R k denotes the orthogonal projection of x 1 onto x 2 . Then, Proj(ŷ −μ, y A −ŷ) ≥ Proj(ŷ −μ,ȳ −ŷ) .
Proof: We refer the reader to Figure 4 for an illustration. Let the smaller angle between y A −ŷ andȳ −ŷ be α and the angle betweenμ −ŷ and y A −ŷ be β. Given the second assumption in the lemma, we have: and Proj(ŷ −μ,ȳ −ŷ) = ŷ −μ cos(β) .

Weak Convergence
We now begin our analysis of a necessary condition assuming that y A and ζ are known, which therefore implies thatμ is known. i. For Algorithm 1 to converge to (α * = 0,ȳ * = y A ), y A must satisfy: ii. Under Assumption 4.1, for Algorithm 1 to weakly converge, y A must satisfy iii. Let Ψμ be defined as the closure of the half-plane defined by the line joiningŷ and y A and which contains the pointμ. For Algorithm 1 to yield a converging sequence of mixed α * ∈ (0, 1), y A must satisfy either one of the following: Proof: i. Algorithm 1 results into a steady-state value (α * = 0,ȳ * = y A ) only if (cf. (6) and (7)), sinceμ is the orthogonal projection of µ on to the plane containing ζ, y A andŷ. This proves the first case.
ii. Suppose that Algorithm 1 converges to an α * ∈ [0, 1) from some arbitrary, non-trivial initial conditionȳ 0 . Ifȳ 0 is in the green region (α 0 = 0), then after one iteration of Algorithm 1, we obtainȳ 1 = y A . If y A is also in the green region (i.e., corresponding to α 1 = 0), then the algorithm converges to an equilibrium with α * = 0 and case i) applies. On the other hand, if y A is in the blue region (α ∈ (0, 1)), then it follows thatȳ 1 = y A , and thusȳ 1 lies in the blue region (α ∈ (0, 1)). Therefore, we can assume that without any loss of generality,ȳ 0 is in the blue region. From (8), it needs to hold that Now, substituting (7) into (8) and on following the same steps that led to (9), we have that after one iteration of Algorithm 1,ȳ 1 is such that the vectorȳ 0 − ζ is a positive scalar multiple of the vector y A − ζ. More precisely, we havē which implies that for any non-trivialȳ 0 ,ȳ 1 − ζ is a positive scalar multiple greater than unity of y A − ζ.
Let us assume, for the sake of arriving at a contradiction, that 0 ≤ (ŷ −μ) T (y A −ŷ), namely that the condition of case ii) does not hold. Therefore, we can write where ψ is the smaller angle between the vectorsŷ −μ and ζ −μ. Since Assumption 4.1 holds, Lemma 4.2 holds. Therefore, the left hand side of the above inequality is non-negative, and thus, Now, from (11), we can write where the second inequality follows from (12) and from the fact that r = ŷ −ȳ 0 2 /((ŷ − µ) T (ŷ −ȳ 0 )) ≥ 1. This however implies, from (8), thatȳ 1 is in the red region (α 1 = 1). But this is not possible as we already showed thatȳ 1 is in the blue region (α = (0, 1)). This proves the second case.
iii. From the previous case, without loss of generality, we can assume that (ȳ 0 − ζ) is a positive scalar multiple of y A − ζ, and thatȳ 0 is in the blue region (i.e., corresponding to α ∈ (0, 1)).
Suppose that for every i ≥ 0,ȳ i is in the blue region, i.e., every α i ∈ (0, 1). Then consider the recursion, Note that (13) may be viewed as a discrete-time dynamical system inȳ. Replacingȳ 0 byȳ i−1 in (11), we have that for every i ≥ 1, and for anyȳ 0 , such thatȳ 0 − ζ is a positive scalar multiple of y A − ζ, We need now to distinguish two cases.
iii.a If ζ ∈ Ψμ, then (14) implies that for every i ≥ 1, the pointȳ i−1 ∈ Ψ ĉ µ , namely the complement of Ψμ. We refer to Figure 5 for a geometric interpretation of the proof. Additionally, we have that α * (ȳ i−1 ) ∈ (0, 1). Thus, applying Lemma 4.3, we conclude that for every i ≥ 1, Further, from applying the triangle inequality to the three pointsȳ i−1 ,ŷ and ζ, we have Combining this together with (15) and (13) yields which is a linear system in the quantity ȳ i − ζ . This implies that Algorithm 1 will output a converging sequence of mixed α * 's only if iii.b If ζ ∈ Ψ ĉ µ , then we can apply the following upper bound which follows from the fact that the length of the projection of a vector x onto any another vector can never exceed the length of x itself. Following the same steps as in the previous case, we conclude that the sequence ȳ i − ζ will converge only if This proves the iii) case.
We numerically verify this result by studying the region of divergence for Algorithm 1 in two dimensions. In the planar case, the value of the mean µ =μ = (0, 0), and the sensor's valueŷ = (0.8, 0). The attacker's mean, ζ = (0.3, −0.2). For every value of y A on a grid in the neighborhood of µ, we ran Algorithm 1 for a set of different initial valuesȳ 0 . The results are summarized in Figure 6. If the algorithm converged 1 to an α * ∈ [0, 1) for some choice ofȳ 0 , then the corresponding point y A is shown as a (green) dot. Otherwise, it is shown as a (red) cross. The analytically derived necessary conditions from Theorem 4.4 is shown as a black dashed contour.  (2)] on a grid in the neighborhood of µ, we run Algorithm 1 for a set of different initial valuesȳ 0 . If the algorithm converges to an α * ∈ [0, 1) for some choice ofȳ 0 , then the corresponding point y A is shown as a (green) dot. Otherwise, it is shown as a (red) cross. The analytically derived necessary conditions from Theorem 4.4 is shown as a black dashed contour.
We now revisit the fact that the parameter ζ is not known to the sensor. Suppose that ζ ∈ C, where C is a set known to the sensor and which satisfies Assumption 4.1. Define the set N ζ as the set of all points x ∈ R k which satisfy the necessary conditions from Theorem 4.4. Then, the following result holds.

Corollary 4.5 (Necessary Condition)
Suppose that C is a set of all ζ ∈ R k that satisfies Assumption 4.1. Then, a necessary condition for weak convergence of Algorithm 1 is that Proof: Suppose that Algorithm 1 weakly converges, i.e., for someζ ∈ C and some non-trivial initial conditionȳ 0 , α * ∈ [0, 1). Then, y A must satisfy the conditions in Theorem 4.4. Therefore, y A ∈ Nζ, and hence, y A ∈ ζ∈C N ζ .
In Figure 7 we plot the analytic condition from Corollary 4.5 for different sets C in R 2 . Since this example is planar,μ = µ. In particular, let the value of the mean µ = (0, 0), the sensor's valuê y = (1, 0), and the set C be different circles of increasing radii around µ. Figure 7 shows how the set ζ∈C N ζ evolves with increasing radius, δ, of C. As is expected, the set computed for a higher values of the radius contains the set computed for a lower one. In other words, for a higher level of uncertainty about the attacker's mean ζ, the necessary condition becomes more conservative.

Strong Convergence
The next result establishes a sufficient condition for strong convergence. ii.
Additionally, condition (17) is also necessary for strong convergence.
Proof: Following the same steps that lead to (14) in the proof of Theorem 4.4, we can assume without any loss of generality thatȳ 0 − ζ is a positive scalar multiple (greater than unity) of y A − ζ.
Recall (13): Observe that in the regime given by (17), the angle between the vectors y A − ζ andŷ −μ lies in the interval [π/2, π]. In this regime, for every i ≥ 1, one out of the following two possibilities occurs. i.
which holds whenever ζ is contained in Ψμ 2 . This can be seen in Figure 8. Equality is achieved whenȳ i−1 has a magnitude equal to infinity.  ii.
which holds whenever ζ is not contained in the closure of the half plane defined by the line joiningŷ and y A and which contains the pointμ. This can be seen in Figure 9. Equality is achieved whenȳ i−1 has a magnitude equal to infinity.
Therefore, we conclude that Further, applying the triangle inequality to the set of points ζ,ŷ, andȳ i−1 , we obtain Combining (19), (22) and (23), we obtain which converges if condition (18) is satisfied. We show the necessity of (17) through the following construction. Suppose that condition (17) is violated. Equivalently, suppose that the angle between the vectors y A − ζ andŷ −μ is in the interval [0, π/2) (we refer the reader to Figure 5 for an illustration). Now, we can choose aȳ 0 to be arbitrarily close to the red region (α = 1). The coefficient in front of y A − ζ in (19) can be made arbitrarily large. Therefore, in one iteration of the algorithm, α 1 = 1. This establishes the necessity of (17).
This result is numerically verified in Figure 10. In this figure, condition (17) is the vertical line passing through the point ζ (the black diamond). We can see that there are no green points that lie strictly to the right of this vertical line, thereby numerically verifying the necessity of (17).
Akin to the necessary condition, we seek a result which does not depend upon the knowledge of ζ. Suppose that ζ ∈C, whereC is a set known to the sensor. Define the set S ζ as the set of all points which satisfy the sufficient conditions from Theorem 4.6. Then, the following result holds. Proof: Suppose that y A ∈ ζ∈C S ζ . From Theorem 4.6, this means that for everyζ ∈C and for every non-trivial initial conditionȳ 0 , α * ∈ (0, 1). Hence, Algorithm 1 strongly converges. We now plot the analytic condition from Corollary 4.7 for different setsC. In particular, let the value of the meanμ = µ = (0, 0) (since this is a planar case), the sensor's valueŷ = (0.8, 0), and the setC be different circles of increasing radii around µ. Then, Figure 11 shows how the set ζ∈C S ζ evolves with increasing radius ofC. As is expected, the set computed for a smaller radius contains the set computed for one with higher radius. Since the sufficient condition is of interest to the attacker, we can see that with higher uncertainty in the mismatch between the means, the set of values of y A that guarantee convergence of Algorithm 1 shrinks in size, making it increasingly difficult for an attacker to always guarantee convergence of Algorithm 1.

A Special Case: Equal Means
This section addresses the case when the random variables y|ŷ andŷ have equal means, i.e., µ = ζ. This scenario may arise in the following situation: the entire multi-sample d is viewed as multiple independent measurements of a random vector and the trusted sampled drawn by the sensor is not sent to the central computer for computation. This will mean that the random variablesŷ and y are independent with possibly equal expected values (depending on the algorithm g(.) and the sampling distribution for the measurements). However, since y is computed using many more samples thanŷ, y is likely to have a lower variance if computed in a non-adversarial setting.
Through a simple substitution of the mismatch parameter δ = 0, it follows that the results from Section 3 apply directly to this case of equal means. However, the conditions from Theorem 3.1 as well as the computation of equilibria still requires complete information of the problem parameters, i.e.,ŷ, µ and y A . So we can study the convergence conditions for Algorithm 1 in this limiting regime, which we now formally present. i. For Algorithm 1 to converge to α * = 0,ȳ * = y A and y A must satisfy ii. For Algorithm 1 to weakly converge, y A must satisfy iii. For Algorithm 1 to yield a converging sequence of mixed α * ∈ (0, 1), y A must satisfy Proof: When ζ = µ, Assumption 4.1 is trivially satisfied. Also, we have thatμ = µ. Additionally, the requirement in the third case of Theorem 4.4 is also trivially satisfied. Therefore, applying Theorem 4.4, we obtain the claim.
This result provides an improvement over the conditions presented in our previous work [4]. We numerically verify this claim by studying the region of divergence for Algorithm 1 in two dimensions. In this simulation, the value of the mean µ = (0, 0), and the sensor's valueŷ = (1, 0). For every value of y A on a grid in the neighborhood of µ, we ran Algorithm 1 for a set of different initial values y 0 . The results are summarized in Figure 12. If the algorithm converged to an α * = 1 for some choice ofȳ 0 , then the corresponding point y A is colored green. Otherwise, it is colored red. The analytically derived necessary conditions from Corollary 5.1 are shown as a black dashed contour. We can see that the result is fairly tight especially in the regions where y A makes an angle that is either very close to zero or to π. We should expect this to be the case since one can show that the results are exact in the scalar case [4].
Next, we address the sufficient condition for strong convergence of Algorithm 1 in this case of equal means.
Corollary 5.2 (Sufficient Conditions with ζ = µ) Suppose that ζ = µ. Algorithm 1 will converge in the strong sense if the following two conditions are satisfied. i. ( ii. Additionally, as long as the points µ, y A andŷ are non-collinear, condition (24) is also necessary for strong convergence.
Proof: Since ζ = µ, condition (17) reduces to (24), while (18) reduces to We now refer the reader to Figure 13 for an illustration of this scenario in which the angle γ between the vectors y A − µ andŷ − µ is in the interval [π/2, π] (i.e., condition (24) holds). From the exterior angle property applied to triangle formed byŷ, µ and y A , we conclude that π − γ > θ, where θ is the angle between the vectors µ −ŷ and y A −ŷ. Therefore, Therefore, (26) reduces to (25). Applying Theorem 4.6, we obtain the desired claim. The necessity of (24) follows using the same construction as in the proof of Theorem 4.6.

Remark 5.3
In case the points µ, y A andŷ become collinear, the problem reduces to the scalar case described in [4].
This result is numerically verified in Figure 14. We can see that the theoretical conditions have a fairly low gap, especially in the scalar case, i.e., for choices of y A that lie on the x-axis, in which case the result is known to be tight [4]. Figure 14: Numerically generated plot to study the region of convergence for Algorithm 1 in two dimensions. The value of the mean µ = (0, 0) (shown as a (magenta) star), and the sensor's valueŷ = (1, 0), shown as a (black) square. For every value of y A = [y A (1), y A (2)] on a grid in the neighborhood of µ, we run Algorithm 1 for a set of different initial valuesȳ 0 . If the algorithm converges to an α * = 1 for every choice ofȳ 0 , then the corresponding point y A is shown as a (green) dot. Otherwise, it is shown with a (red) cross. The analytically derived sufficient conditions from Corollary 5.2 is shown as a solid (blue) contour. The analytically derived necessary conditions from Corollary 5.1 are shown as a dashed (black) contour.

Conclusion and Future Directions
This work introduced a novel approach to trusted computation when a central node is leveraged to carry out a complex computation, but is likely to be compromised by an adversary. In our approach, we considered a sensor that may perform approximate but trusted computation on partial data, which is then fused with the output of the central computer in an optimal manner. We proposed a game-theoretic formulation and formalized an iterated best response algorithm. Formal statements were derived that characterize parameter regimes under which the iterative algorithm converges. The derived necessary and sufficient conditions become relatively tight in the case when the distributions of the unknown random variables used by the defender and the attacker to compute their respective cost functions have identical means. Numerical simulations validate our theoretical results.
This work spawns several future directions in this general theme of trusted computation. One promising direction is to apply these concepts to a specific computation, such as maximum eigenvalue, to explore tradeoffs between the size of the subset of the original data that needs to be retained by the sensor and the sizes of the regions of convergence. Further, this paper posed trusted computation as a static problem. It would be of interest to explore dynamic variants of this problem. For example, in this paper, the parameter y A is simply chosen by the attacker and is kept fixed in the duration of the game. What if y A were to also depend upon the defender's strategy α? It would also be of interest to explore more specific models of attacks in which the attacker can only attack at the computational level or at the data level. Another interesting research direction would be to formulate scenarios in which the data owner may also use similar iterative schemes as a honeypot [6] to decide whether a particular third-party computation service is trustworthy.