betaFeedback

WorksComputer Science

Stochastic Games with Distributional Entropy Objectives

Abstract

We introduce stochastic games with distributional entropy objectives, two-player zero-sum games whose configurations are probability distributions over the states of a finite arena and whose stage reward is Shannon entropy. Over an infinite discounted horizon, MIN seeks to concentrate the distribution, while MAX seeks to disperse it. Because entropy is nonlinear, it matters whether strategic and transition randomness are averaged before entropy is evaluated or sampled first. We formalise three resulting semantics: averaged-distribution, sampled-profile, and sampled-transition. This semantic choice fundamentally changes the game-theoretic structure. Averaged-distribution games need not be determined, even on a four-state deterministic arena, whereas both sampled semantics are determined and admit optimal stationary randomised strategies. We give contractive Bellman characterisations and convergent finite-horizon approximations for the upper and lower averaged values and the two sampled values. Moreover, even the lower value under averaged-distribution semantics dominates the value under either sampled semantics, while the sampled-profile and sampled-transition values are incomparable in general. For fixed rational discount and positive rational promise gap, the averaged-distribution (upper and lower value) gap problems and both sampled gap problems lie in PSPACE; for a single entropy minimiser, the averaged and sampled-profile problems lie in NP. Finally, under all three semantics, entropy optimisation is NP-hard to approximate within a suitable fixed additive constant, already for deterministic one-player games, where pure memoryless strategies are optimal.

Introduction

Stochastic games are a canonical model of quantitative adversarial decision making under uncertainty [31]. In the classical finite discounted setting, the current configuration is a single state of an arena. The players choose actions, the arena makes a stochastic transition, and the resulting rewards are accumulated in expectation. Such games have a value and admit optimal stationary strategies. Their values are characterised as the unique fixed point of a contractive Shapley operator, giving rise to value- and policy-iteration algorithms. Underlying this theory is the affine manner in which strategic randomisation and stochastic transitions enter the expected payoff.

Probability distributions as configurations. In many systems, however, the current configuration is naturally represented by a distribution rather than a single state. Consider a distributed computing system in which a fixed population of jobs moves among a collection of servers. The system operator controls routing at some servers, while an adversary controls compromised servers. The operator seeks to spread the workload across the system, whereas the adversary seeks to concentrate it at a few servers and create bottlenecks. The resulting configuration is described by a distribution μ\mu over the servers, where μ(s)\mu(s) is the fraction of jobs at server ss. Its Shannon entropy, H(μ)=−∑sμ(s)log⁡2μ(s)\mathbf{H}(\mu)=-\sum_s\mu(s)\log_2\mu(s), measures workload dispersion: high entropy corresponds to a broadly distributed load, while low entropy indicates concentration. Analogous configurations arise in transportation networks, where mass represents vehicles distributed across locations, and in epidemiological and ecological models, where it represents populations distributed across regions or compartments.

A complementary interpretation arises in security, surveillance, and active sensing, where the distribution represents uncertainty about a hidden system state. In quantitative opacity and information-flow analysis, for example, a defender may seek to keep an observer’s belief dispersed across several possible states, while the observer seeks to concentrate it sufficiently to infer a secret [20, 25, 15, 33]. Thus, across these settings, opposing objectives may favour either dispersion or concentration.

Motivated by these examples, we introduce stochastic games with distributional entropy objectives, two-player zero-sum games played over a finite arena whose configurations are probability distributions over its states. Shannon entropy of the distribution serves as the stage reward, and the payoff is its infinite discounted sum. We discount because this makes the Bellman operators contractions and the values well defined for every continuous stage reward; it also weights the early rounds more, so the objective is about how dispersed the distribution becomes soon. A mean-payoff variant is a natural alternative that we leave open (§ 8). The entropy-minimising player Min seeks to concentrate the distribution, while the entropy-maximising player Max seeks to disperse it.

Three roles for probability. Once distributions themselves become game configurations, probability plays three conceptually different roles: the current distribution may represent either population mass or uncertainty over states, the players may randomise their decisions, and the transitions of the arena may be stochastic. This raises a modelling question that does not arise for state-based games: when forming the next distribution, which sources of randomness describe fractional flow, and which describe an event that is actually realised?

One possible interpretation is that all probabilities describe fractional flow. If a routing decision selects two routes with probabilities 0.3 and 0.7, then the corresponding fractions of the population follow those routes. A stochastic transition with probabilities 0.2 and 0.8 similarly divides the population in those proportions. Once the players’ mixed decisions are fixed, strategic and transition randomness therefore produce a single successor distribution. We call this averaged-distribution semantics.

A second possibility is that strategic randomisation selects a control regime rather than dividing the population. At the beginning of a time interval, for example, each player may randomly select one complete routing plan. The selected plans are realised, but the population subsequently moves according to their transition rates. Thus, action profiles are sampled, while stochastic transitions continue to represent fractional population flow. We call this sampled-profile semantics.

Finally, transition probabilities may themselves describe uncertainty about a common environmental condition. A transition probability may, for example, specify whether a communication link is available during the interval. The link is either available or unavailable, and all jobs at a given source server experience the same realised outcome. In this interpretation, both the control regime and the stochastic environment are realised before entropy is evaluated on the resulting distribution. We call this sampled-transition semantics.

These interpretations are indistinguishable when rewards are affine in the distribution, since affine functions commute with averaging. Entropy behaves differently: it is strictly concave, so mixing distinct distributions produces greater entropy than the corresponding average of their entropies. Formally, if μ~\tilde{\mu} is a random successor distribution, Jensen’s inequality gives H(E[μ~])≥E[H(μ~)]H(\mathbb{E}[\tilde{\mu}]) \ge\mathbb{E}[H(\tilde{\mu})], with strict inequality whenever μ~\tilde{\mu} is not almost surely constant. Thus, averaging random outcomes before evaluating entropy need not agree with first realising those outcomes and then averaging their entropies. The three semantics accordingly capture different interpretations of probability: distributional mass or belief, randomised decisions, and uncertainty over realised worlds.

This leads to the central theoretical question of the paper: which parts of the classical theory of discounted stochastic games survive when configurations are probability distributions and rewards are nonlinear functions of those distributions? Our results show that the answer depends sharply on how randomness is interpreted.

Determinacy: averaging versus sampling. Under averaged-distribution semantics, the continuation value is applied to the distribution produced jointly by the players’ mixed choices. Because this dependence is nonlinear, the classical minimax argument no longer applies. More strongly, determinacy itself can fail, even in a four-state arena with deterministic transitions. In the game shown in Figure 1, the initial distribution places equal mass on smin⁡s_{\min} controlled by Min and smax⁡s_{\max} controlled by Max. Each player routes its mass to one of two absorbing states. If xx and yy are the probabilities with which Min and Max, respectively, choose the second absorbing state, then the normalised discounted payoff is

Gγ(x,y)=(1−γ)+γh(x+y2)G_\gamma(x,y)=(1-\gamma)+\gamma h\left(\frac{x+y}{2}\right)

where hh is binary entropy, h(z)=−zlog⁡2z−(1−z)log⁡2(1−z)h(z)=-z\log_2z-(1-z)\log_2(1-z). The initial distribution is uniform on {smin⁡,smax⁡}\{s_{\min},s_{\max}\}, so the first stage has entropy 11, and its discounted weight gives the first term (1−γ)⋅1(1-\gamma)\cdot1. From the second stage on, the mass is (1−x+y2,x+y2)\left(1-\frac{x+y}{2},\frac{x+y}{2}\right) on the two absorbing states and stays fixed there, so every later stage has entropy h(x+y2)h\left(\frac{x+y}{2}\right), and together they contribute the second term γh(x+y2)\gamma h\left(\frac{x+y}{2}\right). The two orders of optimisation give

inf⁡x∈[0,1]sup⁡y∈[0,1]Gγ(x,y)=1>(1−γ)+γh(14)=sup⁡y∈[0,1]inf⁡x∈[0,1]Gγ(x,y).\inf_{x\in[0,1]}\sup_{y\in[0,1]}G_\gamma(x,y)=1>(1-\gamma)+\gamma h\left(\frac{1}{4}\right)=\sup_{y\in[0,1]}\inf_{x\in[0,1]}G_\gamma(x,y).

Thus, the upper and lower values differ: averaging the players’ mixed choices before applying entropy can destroy determinacy. Averaging can destroy determinacy without destroying Bellman structure: the two ordered Bellman operators remain contractions, separately characterising the upper and lower values and yielding convergent finite-horizon approximations.

The situation changes under the two sampled semantics. Once a pair of pure action profiles has been selected, it determines a scalar continuation payoff: the value at the resulting successor distribution under sampled-profile semantics, and the expected value over realised transitions under sampled-transition semantics. Randomisation over pure-profile pairs therefore produces a payoff that is bilinear in the players’ mixed strategies. The one-step interaction becomes a finite zero-sum matrix game, allowing minimax to be applied at every distribution. We prove that both sampled semantics are determined and that both players have optimal stationary randomised strategies, even against opponents whose strategies depend on the complete history of observed distributions.

We compare the values induced by the three interpretations. Even the lower value under averaged-distribution semantics dominates the value under either sampled semantics

(Theorem 5). The sampled-profile and sampled-transition values, however, are incomparable (Example 39). With a single entropy-minimising player, averaged-distribution and sampled-profile semantics coincide, and their common value dominates that under sampled-transition semantics (Theorem 5).

Algorithms and complexity. The Bellman characterisations yield convergent finite-horizon approximations. Under averaged-distribution semantics, separate ordered recursions approximate the upper and lower values; under either sampled semantics, each Bellman update is a finite zero-sum matrix game.

For every fixed rational discount and positive rational promise gap, the averaged-distribution (upper and lower value) gap problems and both sampled gap problems lie in PSPACE. Averaged-distribution semantics uses a rational grid for mixed actions; sampled-profile semantics uses sparse near-optimal mixtures over pure profiles; and sampled-transition semantics additionally enumerates transition realisations sequentially. Depth-first evaluation keeps the space polynomial.

For a single entropy-minimising player, the averaged-distribution and sampled-profile problems improve to NP, since pure profiles suffice over the truncated horizon; sampled-transition remains in PSPACE. Conversely, entropy optimisation is NP-hard under all three semantics, already for deterministic one-player games, where pure memoryless strategies are optimal, and remains NP-hard to approximate within a suitable fixed additive constant. This contrasts with classical discounted MDPs, which are solvable in polynomial time [29].

Table 1 summarises the upper bounds. The averaged-distribution and sampled-profile one-player cases are tight; the remaining cases lie between NP-hardness and PSPACE. The lower bounds follow immediately from the one-player construction of Theorem 13.

SemanticsOne playerGeneral games
Averaged distributionNP (Lemma 26)PSPACE (Theorem 7)
Sampled profileNP (Lemma 27)PSPACE (Theorem 9)
Sampled transitionPSPACE (Lemma 28)PSPACE (Theorem 10)

Table 1. Upper bounds for the discounted gap problem for rational γ\gamma and ε0>0\varepsilon_0 > 0; the general-game averaged-distribution entry holds for both V+V^+ and V−.V^-.

Related Work. Opacity enforcement in discrete-event systems modifies system dynamics to prevent an observer from inferring a secret predicate [20, 25, 37], while quantitative information flow studies how much uncertainty about a secret is retained or revealed through observations [15, 23, 33, 8]. Moving-target defence can similarly be viewed as maintaining uncertainty against an entropy-minimising observer. Our setting instead treats this uncertainty as the state of a sequential two-player game in which both players influence the entropy of the evolving distribution. Entropy-based objectives have also been studied in single-agent exploration and control [17], whereas we consider a zero-sum interaction between entropy minimisation and maximisation. Cyber-physical security games likewise model adversarial interaction [19], but typically use state- or action-based rewards rather than Shannon entropy of the full state distribution. Entropy has appeared in stochastic games through entropic-risk objectives [11], where an exponential transformation is applied to accumulated conventional reward.

Games called entropy games in [10, 2, 3] have a payoff given by the growth rate of the number of behaviours, equivalently of matrix products (in the operator view of [2, 3], a mean-payoff game with relative-entropy payments over action simplices); there is no state distribution, and the reward is not the Shannon entropy of one. Maximising the entropy (rate) of the path distribution of Markov chains, interval Markov chains and MDPs [13, 14, 30] concerns a single controller and the entropy of the induced distribution on paths, whereas we study a two-player zero-sum game on the entropy of the state distribution at each step. MDPs and Markov chains have been analysed as transformers of probability distributions, with properties given by linear predicates on the distribution, temporal and monadic logics of probability over such predicates, and safety of the distribution inside a polytope [24, 1, 12, 4], but not with a nonlinear quantitative payoff on the distribution. A related distinction between chance (sampled) and mass (averaged) readings of probabilities is studied by Tsai et al. [35] for a single agent and threshold reachability, with configurations read as mass. Belief-dependent rewards, including entropy of the belief, appear in ρ\rho-POMDPs [9]; there a single agent controls the belief, while here two players with opposed aims control the distribution, and the averaged and sampled semantics distinguish how randomisation reaches it.

Finally, [5] study entropy objectives for a single controller in a standard MDP: they minimise the worst-case (over time, after a warm-up) entropy of the state distribution induced by a policy, allow history-dependent policies, and show that memoryless policies do not suffice for their objective. For memoryless policies their update is our one-player averaged-distribution update, but they have no analogue of the sampled semantics, no adversary, and a different objective (worst case over time rather than a discounted sum). In the one-player case both hardness proofs use a one-step deterministic gadget; theirs is a randomized reduction from bounded-occurrence MAX-3SAT [34], so it needs NP≠RP\mathrm{NP} \ne\mathrm{RP}, whereas our Theorem 13 is a deterministic reduction from the gap of [28] and needs only P≠NP\mathrm{P} \ne\mathrm{NP}, so it also yields their hardness result under the weaker assumption.

Contributions. Our main contributions are:

  1. Model and semantics. We introduce stochastic games with distributional entropy objectives, in which the stage reward is the Shannon entropy of the state distribution and two players with opposed aims control that distribution. We formalise three semantics (averaged distribution, sampled profile, sampled transition), which differ in how randomisation reaches the distribution, and show that they give different values: we establish dominance and incomparability relations among them.

  1. Determinacy and Bellman characterisations. We give contractive Bellman characterisations of the upper and lower averaged values and the two sampled values. Averaged-distribution semantics may be nondetermined even on a four-state deterministic arena, whereas both sampled semantics are determined and admit optimal stationary randomised strategies.

  1. Upper bounds. For fixed rational discount and positive rational promise gap, the averaged-distribution (upper and lower value) gap problems and both sampled gap problems lie in PSPACE; for a single entropy-minimising player, the averaged and sampled-profile problems lie in NP.

  1. Hardness. Under all three semantics, for every discount there is a constant ϵ0>0\epsilon_0 > 0 such that the gap problem is NP-hard already for deterministic one-player games, where pure memoryless strategies are optimal. The reduction is deterministic, so the hardness holds unless P=NP\mathrm{P} = \mathrm{NP}.

Problem Definition

For a finite set XX, let D(X):={μ:X→[0,1]∣∑x∈Xμ(x)=1}\mathcal{D}(X) := \{\mu: X \to[0,1] \mid\sum_{x\in X}\mu(x) = 1\} denote the set of probability distributions over XX. For μ∈D(X)\mu\in\mathcal{D}(X), let supp⁡(μ):={x:μ(x)>0}\operatorname{supp}(\mu) := \{x : \mu(x) > 0\}, and write δx\delta_x for the Dirac distribution concentrated at xx. For μ∈D(X)\mu\in\mathcal{D}(X) and g:X→Rg : X \to\mathbb{R}, the expectation of gg under μ\mu is Ex∼μ[g(x)]:=∑xμ(x)g(x)\mathbb{E}_{x\sim\mu}[g(x)] := \sum_x \mu(x)g(x). For vector-valued gg, expectation is taken componentwise.

Entropy. The Shannon entropy of μ∈D(X)\mu\in\mathcal{D}(X) is

H(μ):=−∑x∈supp⁡(μ)μ(x)log⁡2μ(x),0log⁡20:=0.\mathrm{H}(\mu) := - \sum_{x\in\operatorname{supp}(\mu)} \mu(x)\log_2\mu(x), \qquad0\log_2 0 := 0.

For ∣X∣=n|X| = n, 0≤H(μ)≤log⁡2n0 \le\mathrm{H}(\mu) \le\log_2 n; H\mathrm{H} is strictly concave and continuous on D(X)\mathcal{D}(X). For X={0,1}X = \{0,1\}, write h(z):=−zlog⁡2z−(1−z)log⁡2(1−z)h(z) := -z\log_2 z - (1-z)\log_2(1-z); its restriction to [0,12][0,\frac{1}{2}] is a strictly increasing bijection onto [0,1][0,1]. See Proposition 16, Appendix § 11.§ 1 for these standard facts.

Our game setting. A stochastic game with distributional entropy objectives is a finite turn-based stochastic arena E=(S,Smin⁡,Smax⁡,A,Δ,μ0)\mathcal{E} = (S,S_{\min},S_{\max},A,\Delta,\mu_0), where S=Smin⁡⊎Smax⁡S = S_{\min} \uplus S_{\max}, each s∈Ss \in S has enabled actions A(s)⊆AA(s) \subseteq A, Δ:S×A→D(S)\Delta: S \times A \to\mathcal{D}(S), and initial distribution μ0∈D(S)\mu_0 \in\mathcal{D}(S). The game state is a distribution μ∈D(S)\mu\in\mathcal{D}(S), so mass may lie simultaneously on states controlled by both players.

A pure profile a∈Pmin⁡a \in\mathcal{P}_{\min} assigns an enabled action a(s)a(s) to every s∈Smin⁡s \in S_{\min} (likewise b∈Pmax⁡b \in\mathcal{P}_{\max}). Writing ρa,b(s)=a(s)\rho_{a,b}(s) = a(s) on Smin⁡S_{\min} and b(s)b(s) on Smax⁡S_{\max}, define

Φa,b(μ)(s′):=∑s∈Sμ(s)Δ(s,ρa,b(s),s′).\Phi_{a,b}(\mu)(s') := \sum_{s\in S} \mu(s)\Delta(s,\rho_{a,b}(s),s').

A statewise mixed action for Min is x:Smin⁡→D(A)x : S_{\min} \to\mathcal{D}(A) with x(s)x(s) supported on A(s)A(s); write X\mathcal{X} for all such xx, and analogously Y\mathcal{Y} for Max. With πx,y(s)=x(s)\pi_{x,y}(s) = x(s) on Smin⁡S_{\min} and y(s)y(s) on Smax⁡S_{\max},

Υx,y(μ)(s′):=∑s∈Sμ(s)∑α∈A(s)πx,y(s)(α)Δ(s,α,s′).\Upsilon_{x,y}(\mu)(s') := \sum_{s\in S}\mu(s)\sum_{\alpha\in A(s)}\pi_{x,y}(s)(\alpha)\Delta(s,\alpha,s').

Thus Φa,b=Υx,y\Phi_{a,b} = \Upsilon_{x,y} for x(s)=δa(s)x(s) = \delta_{a(s)} and y(s)=δb(s)y(s) = \delta_{b(s)}. Mixed actions induce product profile laws x^(a):=∏s∈Smin⁡x(s)(a(s))\widehat{x}(a) := \prod_{s\in S_{\min}}x(s)(a(s)) and analogously y^\widehat{y}.

Three semantics. In words, the semantics differ in which randomness is averaged into the distribution and which is sampled before entropy is evaluated:

players’ randomisationtransition randomisation
avaveragedaveraged
spsampled (a pure profile)averaged
stsampled (a pure profile)sampled (a successor per state)

Table 2.

A fourth combination, which we do not consider, averages the players’ mixed actions but samples transitions: it splits the mass at each state across actions and lets each part move to its own sampled successor. Throughout, the game starts from the distribution μ0\mu_0 itself, with mass μ0(s)\mu_0(s) at each state ss; starting from a single state drawn from μ0\mu_0 is the case of a Dirac start. Strategies observe the sequence of distributions. Under av nothing else is revealed; under sp the sampled profile is also revealed through the next distribution; under st the realised successors are revealed as well.

References

  1. [1]Manindra Agrawal, S. Akshay, Blaise Genest, and P. S. Thiagarajan. Approximate verification of the symbolic dynamics of Markov chains. Journal of the ACM, 62(1):2:1–2:34, 2015. doi: 10.1145/2629417.DOI
  2. [2]Marianne Akian, Stéphane Gaubert, Julien Grand-Clément, and Jérémie Guillaud. The operator approach to entropy games. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), volume 66 of LIPIcs, pages 6:1–6:14, 2017. doi:10.4230/LIPIcs.STACS.2017.6.
  3. [3]Marianne Akian, Stéphane Gaubert, Julien Grand-Clément, and Jérémie Guillaud. The operator approach to entropy games. Theory of Computing Systems, 63(5):1089–1130, 2019. doi:10.1007/s00224-019-09925-z.DOI
  4. [4]S Akshay, Blaise Genest, and Nikhil Vyas. Distribution-based objectives for markov decision processes. In Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, pages 36–45, 2018.arxiv.org/abs/1804.09341
  5. [5]S. Akshay, Raghav Goyal, Aditya Neeraje, and Piyush Srivastava. Entropy objectives in markov decision processes, 2026. URL: https://arxiv.org/abs/2606.21726, arXiv:2606.21726.
  6. [6]Charalambos D. Aliprantis and Kim C. Border. Infinite Dimensional Analysis: A Hitchhiker’s Guide. Springer, Berlin, 2006. doi:10.1007/3-540-29587-9.DOI
  7. [7]Ingo Althöfer. On sparse approximations to randomized strategies and convex combinations. Linear Algebra and its Applications, 199:339–355, 1994.DOI
  8. [8]Mário S. Alvim, Kostas Chatzikokolakis, Catuscia Palamidessi, and Geoffrey Smith. Measuring information leakage using generalized gain functions. In 2012 IEEE 25th Computer Security Foundations Symposium, pages 265–279, 2012. doi:10.1109/CSF.2012.26.DOI
  9. [9]Mauricio Araya-López, Olivier Buffet, Vincent Thomas, and François Charpillet. A POMDP extension with belief-dependent rewards. In Advances in Neural Information Processing Systems 23 (NIPS 2010), 2010.
  10. [10]Eugene Asarin, Julien Cervelle, Aldric Degorre, Catalin Dima, Florian Horn, and Victor Kozyakin. Entropy games and matrix multiplication games. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016), volume 47 of LIPIcs, pages 11:1–11:14, 2016. doi:10.4230/LIPIcs.STACS.2016.11.
  11. [11]Christel Baier, Krishnendu Chatterjee, Tobias Mggendorfer, and Jakob Piribauer. Entropic risk for turn-based stochastic games. Information and Computation, 301:105214, 2024. doi: 10.1016/j.ic.2024.105214.
  12. [12]Danièle Beauquier, Alexander Moshe Rabinovich, and Anatol Slissenko. A logic of probability with decidable model-checking. In Computer Science Logic (CSL 2002), volume 2471 of Lecture Notes in Computer Science, pages 306–321. Springer, 2002. doi:10.1007/3-540-45793-3_21.DOI
  13. [13]Fabrizio Biondi, Axel Legay, Bo Friis Nielsen, and Andrzej Wąsowski. Maximizing entropy over Markov processes. Journal of Logical and Algebraic Methods in Programming, 83(5-6):384–399, 2014. doi:10.1016/j.jlamp.2014.05.001.DOI
  14. [14]Taolue Chen and Tingting Han. On the complexity of computing maximum entropy for Markovian models. In FSTTCS 2014, volume 29 of LIPIcs, pages 571–583, 2014. doi:10.4230/LIPIcs.FSTTCS.2014.571.DOI
  15. [15]David Clark, Sebastian Hunt, and Pasquale Malacaria. Quantitative information flow, relations and polymorphic types. Journal of Logic and Computation, 15(2):181–199, 2005.DOI
  16. [16]Gerald B. Folland. Real Analysis: Modern Techniques and Their Applications. John Wiley & Sons, 1999.
  17. [17]Elad Hazan, Sham Kakade, Karan Singh, and Abby Van Soest. Provably efficient maximum entropy exploration. In International conference on machine learning, pages 2681–2691. PMLR, 2019.arxiv.org/abs/1812.02690
  18. [18]Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13–30, 1963. doi:10.1080/01621459.1963.10500830.DOI
  19. [19]Linan Huang and Quanyan Zhu. A dynamic games approach to proactive defense strategies against advanced persistent threats in cyber-physical systems. Computers & Security, 89:101660, 2020.DOI
  20. [20]Romain Jacob, Jean-Jacques Lesage, and Jean-Marc Faure. Overview of discrete event systems opacity: Models, validation, and quantification. Annual reviews in control, 41:135–146, 2016.DOI
  21. [21]Olav Kallenberg. Foundations of Modern Probability. Springer, 1997.
  22. [22]Richard M. Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations, pages 85–103. Springer US, 1972. doi:10.1007/978-1-4684-2001-2_9.DOI
  23. [23]Boris Köpf and David Basin. An information-theoretic model for adaptive side-channel attacks. In Proceedings of the 14th ACM conference on Computer and communications security, pages 286–296, 2007.
  24. [24]Vijay Anannd Korthikanti, Mahesh Viswanathan, Gul Agha, and YoungMin Kwon. Reasoning about MDPs as transformers of probability distributions. In Proc. QEST, pages 199–208. IEEE, 2010. doi:10.1109/QEST.2010.35.DOI
  25. [25]Stéphane Lafortune, Feng Lin, and Christoforos N Hadjicostis. On the history of diagnosability and opacity in discrete event systems. Annual Reviews in Control, 45:257–266, 2018.DOI
  26. [26]Richard J. Lipton and Neal E. Young. Simple strategies for large zero-sum games with applications to complexity theory. In Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing (STOC), pages 734–740. ACM, 1994. doi:10.1145/195058.195447.DOI
  27. [27]Angus Macintyre and Alex J. Wilkie. On the decidability of the real exponential field. In Piergiorgio Odifreddi, editor, Kreiseliana: About and Around Georg Kreisel, pages 441–467. A K Peters, Wellesley, MA, 1996.
  28. [28]Erez Petrank. The hardness of approximation: Gap location. Computational Complexity, 4(2):133–157, 1994. doi:10.1007/BF01202286.DOI
  29. [29]Martin L. Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
  30. [30]Yagiz Savas, Melkior Ornik, Murat Cubuktepe, and Ufuk Topcu. Entropy maximization for constrained markov decision processes. In 2018 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 911–918. IEEE, 2018.DOI
  31. [31]Lloyd S Shapley. Stochastic games. Proceedings of the national academy of sciences, 39(10):1095–1100, 1953.
  32. [32]Maurice Sion. On General Minimax Theorems. Pacific Journal of Mathematics, 8:171–176, 1958.DOI
  33. [33]Geoffrey Smith. On the Foundations of Quantitative Information Flow. In International Conference on Foundations of Software Science and Computational Structures. Springer, 2009.DOI
  34. [34]Luca Trevisan. Non-approximability results for optimization problems on bounded degree instances. In Proceedings of the thirty-third annual ACM symposium on Theory of computing, pages 453–461, 2001.DOI
  35. [35]Yun Chen Tsai, Kittiphon Phalakarn, S. Akshay, and Ichiro Hasuo. Chance and mass interpretations of probabilities in Markov decision processes. In 36th International Conference on Concurrency Theory (CONCUR 2025), volume 348 of LIPIcs, pages 33:1–33:19, 2025. doi:10.4230/LIPIcs.CONCUR.2025.33.
  36. [36]John von Neumann. Zur Theorie der Gesellschaftsspiele. Mathematische Annalen, 100:295–320, 1928.DOI
  37. [37]Yi-Chin Wu and Stéphane Lafortune. Synthesis of insertion functions for enforcement of opacity security properties. Automatica, 50(5):1336–1348, 2014.DOI

Paper details

vlnc:W_jmekkeyh
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents