{'fraction_non_alphanumeric': 0.04105130538251557, 'fraction_numerical': 0.005844473997340239, 'mean_word_length': 4.254689223979404, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Playing Stackelberg Opinion Optimization with Randomized Algorithms for Combinatorial Strategies

From a perspective of designing or engineering for opinion formation games in social networks, the opinion maximization (or minimization) problem has been studied mainly for designing subset selecting algorithms. We furthermore define a twoplayer zero-sum Stackelberg game of competitive opinion optimization by letting the player under study as the first-mover minimize the sum of expressed opinions by doing so-called “internal opinion design”, knowing that the other adversarial player as the follower is to maximize the same objective by also conducting her own internal opinion design. We propose for the min player to play the follow-the-perturbed-leader algorithm in such Stackelberg game, obtaining losses depending on the other adversarial player’s play. Since our strategy of subset selection is combinatorial in nature, the probabilities in a distribution over all the strategies would be too many to be enumerated one by one. Thus, we design a randomized algorithm to produce a (randomized) pure strategy. We show that the strategy output by the randomized algorithm for the min player is essentially an approximate equilibrium strategy against the other adversarial player.


Introduction
The opinion forming process in a social network can be naturally thought as opinion influencing and updating dynamics. This already attracted researchers' interest a while ago in mathematical sociology, and recently in theoretical computer science. DeGroot [9] modeled the opinion formation process by associating each individual with a numeric-value opinion and letting the opinion be updated by weighted averaging the opinions of her friends and her own, where the weights represent how much she is influenced by her friends. This update dynamics will converge to a consensus where all individuals hold the same opinions. However, we can easily observe that in the real world, the consensus is difficult to be reached. Friedkin and Johnsen [11] differentiated an expressed opinion that each individual in the networks updates over time from an internal opinion that each individual is born with and stays unchanged. Thus, an individual would always be influenced by her inherent belief, and the dynamics converges to an unique equilibrium, which may not be a consensus.
Bindel et al. [5] viewed the updating rule mentioned above equivalently as each player updating her expressed opinion to minimize her quadratic individual cost function, which consists of the disagreement between her expressed opinion and those of her friends, and the difference between her expressed and internal opinions. They analyzed how socially good or bad the system can be at equilibrium compared to the optimum solution in terms of the price of anarchy [16]. The price of anarchy is at most 9/8 tight in undirected graphs and is unbounded in directed graphs. Nevertheless, a bounded price of anarchy can be obtained for weighted Eulerian graphs in [5], where the total incoming weights equal to the total outgoing weights at each node, while the price of anarchy is bounded for opinion formation games with directed graphs more general than weighted Eulerian graphs in [6].
From a perspective of designing or engineering, opinion maximization (or minimization) has been studied for seeding algorithms in [12,2]. We then define the game of Stackelberg opinion optimization that will be introduced and analyzed in this paper. With a linear objective of the sum of expressed opinions, opinion maximization seeks to find a k-subset (for a fixed size k) of nodes to have their expressed opinions fixed to 1 to maximize the objective. Opinion minimization can be similarly defined to minimize the objective. A seeding algorithm chooses what subset of nodes to fix their expressed opinions (to 1 if to maximize the objective), and it turns out that opinion optimization is NP-hard [12] so greedy algorithms [12,2] have been designed to approximate the optimum with the help of the submodularity of such social cost. It is obvious to see that controlling the expressed opinions is not the only way to optimize the objective. It is natural to consider changing the intrinsic (or equivalently, internal) opinions of some subset to optimize the objective. Notice that setting a chosen subset of nodes to have certain assigned intrinsic opinions does not prohibit later deciding their expressed opinions by the influence and update dynamics while controlling the expressed opinions of the chosen subset is definitive. In this sense, such "internal opinion designing" approach is relatively more relaxed, compared with the previously studied expression control [12]. Note that intrinsic opinion design enjoys its computational tractability.
One can think of a scenario of two players, one with the goal to minimize (or maximize) the objective and the other adversarial player trying to do the opposite thing. In such scenario of competitive opinion optimization, a zero-sum game is formed by these two players with all the subsets of nodes as the strategy set and each optimizing the same objective in the opposite direction. We can furthermore define a Stackelberg game by letting the player under study as the first-mover minimize the sum of expressed opinions by doing internal opinion design discussed above, knowing that the other adversarial player as the follower is to maximize the same objective by also her own internal opinion design. Even if a node is selected by the first-mover for intrinsic opinion design, its internal opinion would still be overwritten once later selected by the adversarial follower. Thus, a node's expressed opinion will be decided by its designed internal opinion (possibly first by the min player and then the max player) and the update dynamic.
We view our problem of coming up with the min player's strategy against the max player's as an online optimization problem, specifically an online linear optimization one. We propose for the min player to repeatedly play some "no-regret" learning algorithm in such two-player Stackelberg game of competitive opinion optimization, obtaining rewards or losses depending on the other adversarial player's play. Using generic or specific no-regret algorithms as strategies is a common approach to reach certain equilibria (on average) in repeated games [17,Chapter 4] [8]. However, the previous results are established when players only have finite strategies to play. Since our strategies are combinatorial in nature, i.e., any subset of size k, the probabilities in the distribution over all the strategies (all k-subsets) would be too many to be enumerated one by one in a vector, which is how they are treated in the previous works. Therefore, the general result of playing no-regret algorithms in two-player zero-sum matrix game such as in [8] is not directly applicable here. Also, due to the problem structure such as how the strategies of the two players are related to each other and something corresponding to the payoff matrix (which will be clear in Section 2.1), we do not have symmetry between the two players as those in the previous results. This justifies why we design algorithms for computing strategies for the min player facing the other adversarial play (which can be efficiently computed), and settle for, instead of characterizing equilibrium (which needs equilibrium strategies for both players), showing that it is indeed the best thing to do for the min player.
The probability distribution for a mixed strategy needs to be expressed implicitly instead of being expressed explicitly as a long vector. We resort to randomizing over such probability distributions (at different time steps), and follow this "average" distribution to produce a k-subset for the min player. Thus, we design a randomized algorithm for outputting a pure strategy of some uniformly chosen time step. Technically, such strategy computation has to be modeled as an online linear optimization problem, and the adversary's strategy has to be shown efficiently computable. Finally, we show that the strategy output by the randomized algorithm for the min player converges to an approximate min strategy against the other adversarial player (the max player) mainly using the no-regret property. In other words, in our particular setting (opinion optimization games) with large strategy sets, using the randomized algorithm to play such Stackelberg game with the max plater playing in adversary guarantees an approximate minmax equilibrium.

Related Work
Using the sum of expressed opinions as the objective, opinion maximization seeks to find a k-subset of nodes to have their expressed opinions fixed to 1 to maximize the objective. Greedy algorithms have been designed to approximate the optimum with the help of the submodularity of such social cost [12,2].
There are works on competitive versions of various (combinatorial) optimization problem other than competitive opinion optimization that we define in this paper. The most wellknown one is probably competitive influence maximization and its variation [3,13,14].
It has been studied for two players playing no-regret algorithms to reach mixed Nash equilibrium (minmax equilibrium) in general zero-sum matrix-form games where the strategy set is finite [8]. On the other hand, here we apply some specific no-regret algorithms in Stackelberg opinion optimization games and randomize the output strategy for a large strategy set to guarantee the convergence to equilibria on expectation.
Another work closely related to that of Bindel et al. for opinion formation games is by Bhawalkar et al. [4]. The individual cost functions are assumed to be "locally-smooth" in the sense of [18] and may be more general than quadratic functions, for example, convex ones. The price of anarchy for undirected graphs with convex cost functions is shown to be at most 2. They also allowed social networks to change by letting players choose the k-nearest neighbors throughout opinion updates and bounded the price of anarchy.
When graphs are directed, a bounded price of anarchy is only known for weighted Eulerian graphs [5], which may not be the most general class of directed graphs that give a bounded price of anarchy. Thus, we bounded the price of anarchy for games with directed graphs more general than weighted Eulerian graphs in [6]. We gave bounds on the the price of anarchy for a more general class of directed graphs with conditions intuitively meaning that each node does not influence the others more than she is influenced by herself and the others, where the bounds depend on such influence differences (in a ratio). This generalizes the previous results on directed graphs, and recovers and matches the previous bounds in some specific classes of (directed) Eulerian graphs. We also showed that there exists an example that just slightly violates the conditions with an unbounded price of anarchy so the conditions are indeed necessary for a bounded price of anarchy. Chierichetti et al. [7] considered the games with discrete preferences, where expressed and internal opinions are chosen from a discrete set and distances measuring "similarity" between opinions correspond to costs.

Preliminaries
We introduce fundamentals in opinion formation games first and proceed with preliminaries about our Stackelberg games of competitive opinion optimization in Section 2.1.
We describe a social network as a weighted graph (G, w) for directed graph G = (V, E) and weight matrix w = [w ij ] ij . The node set V of size n is the selfish players, and the edge set E is the relationships between any pair of nodes. The edge weight w ij ≥ 0 is a real number and represents how much player i is influenced by player j; note that weight w ii can be seen as a self-loop weight, i.e., how much player i influences (or is influenced by) herself. Each (node) player has an internal opinion s i , which is unchanged and not affected by opinion updates. An opinion formation game can be expressed as an instance (G, w, s) that combines weighted graph (G, w) and vector s = (s i ) i . Each player's strategy is an expressed opinion z i ∈ [−1, 1], which may be different from her s i ∈ [−1, 1] and gets updated. Both s i and z i are real numbers. The individual cost function of player i is where z is the strategy profile/vector and N (i) is the set of the neighbors of i, i.e., {j : j = i, w ij > 0}. Each node minimizes her cost C i by choosing her expressed opinion z i . We analyze the game when it stabilizes, i.e., at equilibrium. In a (pure) Nash equilibrium z, each player i's strategy is z i such that given z −i (i.e., the opinion vector of all players except i) for any other z ′ i , That is equivalently for each player to update her expressed opinion by the following rule [5,4]: This is obtained by taking the derivative of C i w.r.t. z i , setting it to 0 for each i, and solving the equality system since very player i minimizes C i . Note that C i is continuously differentiable. We consider an objective C(z) = i z i that is linear in z i 's in this paper.

Absorbing Random Walks
In an opinion formation game, computing Nash equilibrium can be done by using absorbing random walks [10]. In a random walk on a directed graph H = (Z, R) with its weight matrix W , a node in Z is an absorbing node if the random walk can only enters this node but not exit from it, and each entry W i,j is the weight on edge (i, j) in R. Let B ⊆ Z be the set of all absorbing nodes, and the set of the remaining nodes U = Z \ B is transient nodes.
Given the transition matrix P (from the weight matrix W ) whose entry P i,j represents the probability transiting from node i to node j in this random walk, a |U | × |B| matrix Q UB can be computed where each entry Q UB i,j is the probability that a random walk starting at transient state i ∈ U is absorbed at state j ∈ B (see Appendix A for details). If a random walk starting from transient node i gets absorbed at an absorbing node j, we assign to node i the value b j that is associated with absorbing node j. With Q UB , the expected value of i is then f i = j∈B Q UB i,j b j . Let f U be the vector of the expected values for all i ∈ U and f B the vector of values b j for all j ∈ B. We have that Thus, computing the expressed opinion vector at Nash equilibrium for an opinion formation game can be done by taking advantage of Equation (5) In the case of expressed opinion control for opinion maximization as in [12,Section 3.3], controlling the set S ⊆ V gives U = V \ S and B = V ′ ∪ S with all b j = 1 for j ∈ S, i.e., f B = (s, 1), where 1 is a all-1 vector of size |S|, since the nodes in S cannot change their expressed opinions but stick to value 1. The so-called internal opinion design will be explained in the following Section. There, when using absorbing random walks for arriving at stable states, U = V and B = V ′ along with the weighted edges remain as mentioned in the last paragraph yet with f B being the internal opinion after manipulation.

Stackelberg Opinion Optimization Games and Online Linear Optimization
A two-player Stackelberg opinion optimization game can be described as an instance ((G, w), s, X, Y, f ). We will elaborate each component one by one. Let the min player's strategy be a vector x = (x i ) i ∈ R n with x i ∈ {0, −s i − 1} and ||x|| 0 = k. Denote the modified internal opinion vector by s ′ = s + x with −1 ≤ s i + x i ≤ 1 for all i after the min player makes her decision first. So, for a node i, if it is selected by the min player, its internal opinion becomes −1 or stays as s i if not selected by the min player. Knowing s ′ , the adversarial player's strategy is a vector y = (y i ) i ∈ R n with y i ∈ {0, −s ′ i + 1} and ||y|| 0 = k. Denote the final internal opinion vector by s ′ + y with −1 ≤ s ′ i + y i ≤ 1 for all i after the adversarial player also makes her decision. If a node i is selected by the adversarial player, its final internal opinion immediately becomes 1 or stays as s ′ i if not selected by the adversarial player. Let X = {x ∈ R n : ||x|| 0 = k, x i = 0 ⇒ x i = −s i − 1} and Y = {y ∈ R n : ||y|| 0 = k, y i = 0 ⇒ y i = −s ′ i + 1} denote the strategy sets X and Y . Note that the expressed opinions are still influenced by s ′ + y and get updated to the value at stable state by the dynamic, using absorbing random walks (applying Equation (5)).
The min player minimizes her cost function over all x's, which the adversarial player maximizes, g(x, y) = C(Q UB (s ′ + y)) = ℓ T (s ′ + y) for U = V and B = V ′ and a vector ℓ = ( i Q UB i,j ) j .

No-Regret Algorithms for Online Linear Optimization
In the setting of online convex optimization, we describe an online game between a player and the environment. The player is given a convex set K ⊂ R d and has to make a sequence of decisions x (1) , x (2) , ... ∈ K. After deciding x (t) , the environment reveals a convex reward function f (t) and the player obtains f (t) (x (t) ). The performance of the player is measured by regret defined in the following. In this paper, what is closely related to our problem is a more specific problem of online linear optimization where the reward functions are linear, i.e., We define the player's adaptive strategy L as a function taking as input a subsequence of loss vectors f (1) , ..., f (t−1) and returns a point x t ← L(f (1) , ..., f (t−1) ) where x (t) ∈ K.
Definition 1 Given an online linear optimization algorithm L and a sequence of loss vectors f (1) , f (2) , ... ∈ R d , let the regret Regret(L; f 1:T ) be defined as A desirable property that one would want an online linear optimization algorithm to have is a regret which scales sublinearly in T . For example, the online gradient descent algorithm [19] guarantees a regret of O( √ T ). This property can be formally captured as the following. The no-regret property is useful in a variety of contexts. For example, it is known (e.g., [1, Section 3]) that two players playing o(T )-regret algorithms L X and L Y , respectively, in a zero-sum game with a cost function c : X × Y → R of the form c(x, y) = x T M y for some M ∈ R n×m give a version of minmax equilibrium.
We restate the argument here to provide a reference to the standard technique and result that have been existing for playing no-regret algorithms in a zero-sum n × m matrix game. One can view the argument in the following as something we would like to do in Section 3 yet with different technical details for coping with our more challenging games with combinatorial strategies. For every t, we have By applying the definition of regret twice, we have We obtain min x∈X max y∈Y x T M y ≤ max y∈Y min x∈X x T M y + o(T ) T by combining the inequalities above and setting T → ∞, and min x∈X max y∈Y x T M y ≥ max y∈Y min x∈X x T M y by weak duality.

Randomized Algorithms for Combinatorial Strategies
For our opinion optimization game, one can first notice that the strategies of the two players interact with each other and matrix Q UB , which corresponds to the cost matrix M , in a very different way from the standard result discussed in Section 2.1.1. For example, we have Q UB (s + x + y) here instead of x T M y. Because of the differences, we design algorithms for computing an approximate equilibrium strategy of the min player (against the adversarial player), and focus on efficient computation of the adversary's strategy and the equilibrium strategy analysis only for the min player, instead of characterizing equilibrium, i.e., equilibrium strategies for both players (since the adversarial player can overwrite the min player's selection and we do not have a symmetric structure such as x T M y in our problem).
Given the strategy sets X and Y defined in Section 2.1, our Stackelberg opinion optimization game takes a cost function g : X × Y → R defined in Section 2.1. Such game is played repeatedly, where at time t the min player chooses x (t) and the adversarial (max) player chooses y (t) . Here, the min player chooses her strategies according to a no-regret algorithm, and the adversarial player is assumed to maximize the value of the objective.

Follow-the-Perturbed-Leader Algorithms
If we want to use the follow-the-perturbed-leader algorithm [15] to compute a sequence of "mixed" strategies in our game, then since our strategies are combinatorial in nature, i.e., |X | = |Y| = C n k , the probabilities in a distribution over all the strategies would be too many to be enumerated one by one. The probability distribution needs to be expressed implicitly instead of being expressed explicitly as a long vector. Let X t denote this long vector of the probability distribution at time step t.
For every time step t, we have that .. , f (t−1) (·)) where now L X is the follow-the-perturbed-leader algorithm, and estimating will be explained in Section 3.2. 5 As in online linear optimization, we need to define the loss function for the min player's strategy first. Let be the k-subset that the adversarial player selects at time step τ . Fixing the adversarial player's strategy y (τ ) and thereby determining N (τ ) , we can write the loss function as an affine function of the min player's strategy x for τ from 1 to t − 1: We are now ready to specify the follow-the-perturbed-leader algorithm for "large strategy sets" to get a randomized pure strategy x (t) at each time step t. The min player's strategy at time step t is for a random vector R t ∈ [0, √ T ] n uniformly distributed in each dimension. L (t) (x) can be simplified to n i=1 α i x i + c with each where α i = ℓ i |{τ : i ∈ {1, ..., n} \ N (τ ) }|+ t R t (i) ≥ 0 for each i with realized random value R t (i) at t and c is a constant. Thus, x (t) can be efficiently computed by considering α i and x i 's range for all i and selecting the top k nodes that contribute to L (t) least. Note that x (t) does not represent a mixed strategy in our game, but a randomized (combinatorial) pure strategy following distribution X t . Actually, E x (t) ∼X (t) [x (t) ] can be estimated by sampling x (t) enough times. We explain this in Section 3.2. Thus, we conclude that our randomized algorithm outputs a (randomized) pure strategy in a uniformly random time step T min for the min player against the adversarial player who ideally is to play arg max y∈Y g(E x (t) ∼X (t) [x (t) ], y) at each time step t. We can estimate this strategy of the adversary as accurately as possible with high probability. That is, with high probability where ǫ > 0 is an error from estimation, which can be made as small as desired. We show that such strategy y (t) of the adversary can be found efficiently in Section 3.2. The randomized algorithm runs the follow-the-perturbed-leader update up to time step T min . Our main result is to show that the randomized pure strategy indeed approaches an approximate minmax equilibrium (see Section 3.3). The randomized algorithm is summarized in the following.
Algorithm 1 Randomized algorithm for combinatorial strategies 1: Choose T min uniformly at random from {1, ..., T } 2: for t = 1 to T min do 3: √ T ] n , where the adversary's y (τ ) that determines N (τ ) can be efficiently computed using the procedure described in Section 3.2. 4: end for

Computing the Adversary's Strategy
We now show that the adversarial player's strategy y (t) satisfies with high probability where ǫ > 0 is an error from estimation, can be efficiently computed (and thereby finding the loss function f (t) ) by estimating each probability that the min player selects node i.
Recall that the cost value can be computed as is the expected modified internal opinion by the min player. The randomized pure strategy produced by the follow-the-perturbed-leader algorithm at that time step provides a randomized way to modify entries of the vector s to the value −1. Let p (t) i denote the probability that it chooses to modify node i at time step t. Note that For each t, we can draw r samples (each of which is a k-subset of nodes) from distribution X (t) . We letp (t) i denote the ratio of the number that it chooses to modify node i to the number r. By applying the Hoeffding's inequality, we have That is, by choosing r = T , we can use the estimated probabilityp (t) i that is within an estimation error ǫ = ln T /T from the actual one with at least probability of 1 − 2/T 2 .
Then the expected cost of the min player (before the adversarial player's intervention) is Now the adversarial player would like to increase the min player's cost as much as possible. For the max player, by compromising node i, the expected cost can be increased by Thus, the adversarial (max) player simply chooses the k nodes with the k largest ∆ i 's. Note that usingp (t) i for each node i incurs an estimation error that jointly guarantees computing the adversary's y (t) efficiently such that with at least probability of 1 − 2/T 2

Equilibrium Strategy Analysis
Let the min player play the strategy output by the randomized algorithm and the adversarial player's strategy be the one maximizing the loss, given the min player's chosen strategy. First, it can be shown that the play output by the randomized algorithm is O( √ T )-regret. This is achieved naturally in the sense of expected losses of the min player since there is a random vector R t as a random source that produces the distribution X (t) .
Lemma 3 For the min player, follow-the-perturbed-leader algorithms are O( √ T )-regret w.r.t. her respective loss functions depending on the adversary's strategy y (t) 's, i.e., Proof 4 We apply Theorem 1.1(a) of [15] in our context with random vector R t ∈ [0, √ T ] n chosen uniformly at random in each dimension.
Since the randomized algorithm chooses time step T min uniformly at random from 1, ..., T , we let T .
Then, we are ready to state the main result.

Theorem 5
The strategy x (T min) output by the randomized algorithm for the min player (against the adversarial player), which has the O( 1 √ T )-average regret property, is a O( 1 √ T )approximate equilibrium strategy with high probability.
Proof 6 For the min player, we have that by the linearity of expectation and for any y ′ . For each t, applying Inequality (11) that accounts for estimation, we obtain with at least probability of 1 − 2/T (by a union bound) Due to the fact that f is affine in x (t) , the right-hand side of the inequality is equivalent to  One does not necessarily have to use linear objectives. For example, the objective of sum of the node players' costs is not a linear one. Although we focus on computing the min player's equilibrium strategy due to our model structure in this paper. It does not preclude the possibility of exploring other suitable models for competitive opinion optimization that might allow computing or learning equilibrium-inducing strategies for all players.
As future directions, we can generalize competitive opinion optimization to multi-player non-zero-sum games with different (linear) objectives in terms of expressed opinions for different players each optimizing her own objective. Playing certain no-regret algorithms, the average strategy of each player then might converge to certain more permissive equilibrium (Nash equilibrium, correlated equilibrium, etc.). It does not really make sense in a zero-sum game to ask about the price of anarchy. Nevertheless, the price-of-anarchy type of questions becomes interesting and meaningful in a non-zero-sum game setting again.

A Computing Matrix Q U B
We restate the computation from Section 3.3 of [12]. The transition matrix P is constructed by normalizing each row vector of the weight matrix W . Given the set of absorbing nodes B and the set of transient nodes U , then P can be partitioned into submatrices P UB , P UU , identity matrix I, and all-zero matrix 0, where P UB is the |U | × |B| submatrix with the transition probabilities from transient nodes to absorbing nodes and P UU is the |U | × |U | submatrix with the transition probabilities between transient nodes.
The probability of transition from i to j in exactly l steps is denoted as the (i, j) entry of the matrix P l UU . We can construct the |U | × |U | fundamental matrix F of the absorbing random walk where the (i, j) entry is the probability that such random walk starting from i ends up at j without being absorbed. Finally, we have that where each entry Q UB i,j of such |U | × |B| matrix is the probability that a random walk starting at transient node i gets absorbed at absorbing node j.