<p>One of the most famous examples of game theory in computer science is <a href="http://en.wikipedia.org/wiki/Yao%27s_principle">Yao's minimax principle</a>.  Let $X$ be a set of inputs for some problem, and let $A$ be a set of (deterministic) algorithms for that problem.  Yao's principle states that
$$
\max_{x\in X} \operatorname{E}\limits_{a\in A} \left[T(a,x)\right]
\ge
\min_{a\in A} \operatorname{E}\limits_{x\in X} \left[T(a,x)\right] ,
$$
where the expectations on the left and right are taken with respect to <em>any</em> desired probability distribution over algorithms and inputs, respectively.</p>

<p>For example: Any deterministic comparison-based sorting algorithm requires $\Omega(n\log n)$ time on average to sort an array permuted uniformly at random.  (<strong>Proof:</strong> In any binary tree with $N$ leaves, at least half the leaves have depth at least $(\lg N)/2$. $\square$)  So Yao's principle implies that the worst-case expected running time of any <em>randomized</em> comparison-based sorting algorithm is also $\Omega(n\log n)$.</p>

<p>Yao's minmax principle follow easily from von Neumann's <a href="http://en.wikipedia.org/wiki/Minimax_theorem#Minimax_theorem">minimax theorem for two-player zero-sum games</a>, where one player provides the input and the other provides the algorithm.</p>

CC BY-SA 3.0
2013-01-23T20:01:46.603Z
Shouldn't the inequality be reversed? (unless I'm missing something)
George
CC BY-SA 3.0
2013-01-23T23:24:14.147Z
on one hand this is just weak LP duality and it may be helpful to think of it that way, because finding a feasible dual solution is a nice general way to lower bound the optimum of a minimization problem. on the other, maybe it's helpful to think of the "algorithms" player and the "inputs" player...
Sasho Nikolov
CC BY-SA 3.0
2013-01-23T03:57:49.897Z
2013-01-24T04:02:49.197Z
2013-01-24T04:02:49.197Z
Jeffε
<p>There are a number of game-theoretic characterizations of complexity classes. The most famous may be </p>

<ul>
<li><p>AP=PSPACE (figuring out who wins a deterministic game which lasts for a polynomial number of moves is a PSPACE-complete question), </p></li>
<li><p>IP=PSPACE (in a polynomial-length deterministic game played against a player who makes random moves, distinguishing between the cases where your chance of winning is >0.9 and &lt;0.1 is PSPACE-complete), </p></li>
</ul>

<p>but there are many, many more. </p>

CC BY-SA 3.0
2013-01-27T02:12:02.770Z
2013-01-27T02:12:02.770Z
Peter Shor 
<p>Another famous example of using game theory is in CS is synthesis: in synthesis we get a specification over inputs I and outputs O (e.g. in temporal logic, or as an automaton), and we want to automatically generate a system (i.e. a finite-state transducer), that guarantees that for every input sequence of the environment, the computation induced by the transducer satisfies the specification. </p>

<p>As it turns out, synthesis can be formulated as a game between the environment and the system, where a winning strategy for the system corresponds to a transducer. </p>

<p>A very important tool from game theory that is used in this context is Borel-determinancy, especially when we work over infinite computations.</p>

<p>You can start reading about this in <a href="http://www.cs.rice.edu/~vardi/papers/fmco06.ps.gz">Moshe Vardi's survey</a>.</p>

CC BY-SA 3.0
2015-04-22T07:03:16.063Z
2015-04-22T07:03:16.063Z
Shaull
<p>Combinatorial game theory plays a role in logic and computer science as in, for example, the <a href="https://en.wikipedia.org/wiki/Ehrenfeucht%E2%80%93Fra%C3%AFss%C3%A9_game" rel="noreferrer">Ehrenfeucht-fraïssé game</a>, which is a logic game played on model-theoretic structures. At each turn, the first player chooses an element from one of the two structures, and the second has to chose an element from the other, trying to maintain a local isomorphisms between the elements chosen up to that point.</p>

<p>The main theorem regarding this game roughly says that if Player 2 has a winning strategy in a game over two structures, then there does not exist a first-order logic formula that differentiate the two structures. </p>

<p>This result is used in a large number of expressibility results for first order logic and for other logics as well (there's notably an extension of the theorem to monadic second-order logic).</p>

<p>These expressiveness results in turn have strong applications in computer science, e.g. to formal verification, database theory, etc...</p>

CC BY-SA 3.0
2015-07-09T23:25:46.817Z
2015-07-10T17:28:21.917Z
2015-07-10T17:28:21.917Z
Nicola Gigante
<p>Game theory played a significant role in solutions to the "full abstraction problem" in programming language semantics.  In particular, the first fully-abstract semantics for Plotkin's PCF were given using games as models.</p>

<p>The relevant citations are:</p>

<p><em>Full Abstraction for PCF</em>, by Samson Abramsky, Radha Jagadeesan, and Pasquale Malacaria</p>

<p>and </p>

<p><em>On Full Abstraction for PCF: I, II, and III</em>, by J.M.E. Hyland and C.-H.L. Ong</p>

<p>which both appeared in <em>Information and Computation</em>, Volume 163, Issue 2, 15 December 2000.</p>

CC BY-SA 3.0
2013-01-23T22:41:52.243Z
That's a different notion of game, in that it doesn't have a (non-trivial) notion of pay-off, unlike the games from an "economist's perspective". As an aside, in the context of full abstracion for PCF, Hanno Nickau's "Hereditarily Sequential Functionals" should also be mentioned.
Martin Berger
CC BY-SA 3.0
2013-01-23T19:31:45.680Z
2013-01-23T19:31:45.680Z
Sam Tobin-Hochstadt
<p>It is easier for me to think of applications of computer science (techniques) to game theory, than the other way around.  There is a very active field of algorithmic game theory which focuses on the development of efficient algorithms (or complexity results) for, e.g., Nash equilibria, Shapley values, and other such standard game theoretic concepts.  Often, these concepts are easy to define, but prohibitively difficult to compute directly from the definitions.  This work extends at least as far as mechanism design, where we attempt to manipulate the rules of auctions in order to guarantee agent behavior (e.g., we would like them to report truthful bids) or overall results (e.g., we would like to guarantee maximal revenue.)</p>

<p>Noam Nisan, Yoav Shoham, Tim Roughgarden, and many others have some fascinating papers on the subject of mechanism design from a theory point of view; Vince Conitzer has applied AI techniques to the problem to develop automated mechanism design. </p>

<p>On the more applied side in artificial intelligence, it's difficult to think of multi-agent systems without thinking of them as games.  The Partially Observable Stochastic Game (POSG) framework is often used to discuss to multi-agent settings; under the right reward function criteria it becomes a DEC-POMDP.  </p>

CC BY-SA 3.0
2013-01-23T00:06:05.607Z
2013-01-23T00:06:05.607Z
Novak
<p>The article in <a href="http://webee.technion.ac.il/~idish/sigactNews/DC-col42-Jun11.pdf" rel="nofollow">Distributed Computing Column 42</a> attempts to bring a game-theoretic perspective to distributed computing problems.</p>

<blockquote>
  <p><em>Distributed Computing Meets Game Theory: Combining Insights From Two Fields</em>. Ittai Abraham, Lorenzo Alvisi, Joseph Y. Halpern SIGACT News 42(2) June 2011, pp. 68-76</p>
</blockquote>

<p>Quoted from "Idit Keidar", the editor at that time:</p>

<p>Game theory and fault tolerance offer two different flavors of robustness to distributed systems – the former is robust against participants attempting to maximize their own utilities, whereas the latter offers
robustness against unexpected faults. This column takes a look at attempts to combine the two. It features a review of recent work that provides both flavors of robustness by Ittai Abraham, Lorenzo Alvisi, and Joe
Halpern. Ittai, Lorenzo, and Joe discuss how game theory-style strategic behavior can be accounted for in fault-tolerant distributed protocols. They make a compelling case for bringing a game-theoretic perspective
to distributed computing problems.</p>

CC BY-SA 3.0
2016-01-08T14:18:05.963Z
2016-01-08T14:18:05.963Z
hengxin
<p>In <a href="https://en.wikipedia.org/wiki/Formal_verification" rel="nofollow noreferrer">Formal Verification</a> game theory is a recurring theme. I think that one of the most important applications is to define the <a href="https://en.wikipedia.org/wiki/Simulation_preorder" rel="nofollow noreferrer">Simulation Preorder</a> as a game between two players: Spoiler (he) and Duplicator (she). Given a <a href="https://en.wikipedia.org/wiki/Transition_system" rel="nofollow noreferrer">Transition System</a> (in other words, one set <span class="math-container">$S$</span> equipped with a <em>labelled transition</em> relation <span class="math-container">$S \rightarrow S$</span>) Spoiler, starting from a given state, chooses a transition and makes a move. Duplicator has to match the labelled transition and make a move from her starting state. Then, Spoiler makes another move from his last state and Duplicator has to match that transition again, and game goes on in this way. Spoiler first state <em>simulates</em> Duplicator's first state if she has a <em>winning strategy</em> in this game. In their paper <a href="https://dl.acm.org/doi/abs/10.1145/2480359.2429079" rel="nofollow noreferrer">&quot;Advanced automata minimization&quot;</a>, Lorenzo Clemente and Richard Mayr, define a wide variety of <em>simulation relations</em> using games.</p>

CC BY-SA 4.0
2020-06-19T18:52:59.457Z
2020-06-19T18:59:11.887Z
2020-06-19T18:59:11.887Z
greps
<p>Since the title is about CS and not TCS, maybe an answer about applications of game theory to networking can be of some interest.</p>
<p>Questions about game theory and equilibria arise naturally in networking, since the networks that make Internet are economic competitors and belong to different companies, but they need to collaborate in order to ensure connectivity. A lot of work was done about routing policy leading to equilibria, and the impact of the price of anarchy on Internet performances. Such problems are generally called &quot;routing games&quot;.</p>
<p>The seminal work of Roughgarden and Tardos was the starting point of hundreds of papers about equilibria and routing. You can find below some examples (mostly works of Eitan Altman or Ariel Orda).</p>
<p>Roughgarden, T., &amp; Tardos, É. (2002). How bad is selfish routing?. Journal of the ACM (JACM), 49(2), 236-259.</p>
<p>Eitan Altman, Jocelyne Elias, Fabio Martignon:
A game theoretic framework for joint routing and pricing in networks with elastic demands. VALUETOOLS 2009: 57</p>
<p>Giovanni Accongiagioco, Eitan Altman, Enrico Gregori, Luciano Lenzini:
Peering vs transit: A game theoretical model for autonomous systems connectivity. Networking 2014: 1-9</p>
<p>Giovanni Accongiagioco, Eitan Altman, Enrico Gregori, Luciano Lenzini:
A game theoretical study of peering vs transit in the internet. INFOCOM Workshops 2014: 783-788</p>
<p>Ron Banner, Ariel Orda:
Bottleneck Routing Games in Communication Networks. INFOCOM 2006</p>
<p>Liane Lewin-Eytan, Joseph Naor, Ariel Orda:
Maximum-lifetime routing: system optimization &amp; game-theoretic perspectives. MobiHoc 2007: 160-169</p>
<p>Gideon Blocq, Ariel Orda:
How good is bargained routing? INFOCOM 2012: 2453-2461</p>
<p>Gideon Blocq, Ariel Orda:
&quot;Beat-Your-Rival&quot; Routing Games. SAGT 2015: 231-243</p>
<p>Gideon Blocq, Ariel Orda:
Coalitions in Routing Games: A Worst-Case Perspective. IEEE Trans. Netw. Sci. Eng. 6(4): 857-870 (2019)</p>

CC BY-SA 4.0
2020-06-27T18:43:58.893Z
2020-06-27T18:43:58.893Z
Lamine
<p>One surprising intersection is that of <strong>cryptography and game theory</strong>.</p>
<p>In cryptography you often want to get rid of <em>trusted parties.</em> For example, imagine some parties wanting to perform a sealed-bid auction—where everybody gives the auctioneer a sealed envelop with a bid inside—but <em>(a)</em> no trusted auctioneer is in sight and <em>(b)</em> the bidders definitely do not trust each other.</p>
<p>Are they doomed? No, there are several cryptographic solutions to this; the subfield of secure multi-party computation (<a href="https://en.wikipedia.org/wiki/Secure_multi-party_computation" rel="nofollow noreferrer">MPC</a>) studies this problem.
Little game theory so far, except that this scenario can &quot;simulate&quot; the one with an actual trusted auctioneer and thus standard equilibria results should hold (with some caveats, e.g. these are <em>computational equilibria</em>, that is they hold only for polynomial-time machines, otherwise they could break underlying cryptographic assumptions).</p>
<p>Things get interesting, for example, if parties want not only to get a good deal out of the auction but also, in the meantime, learn something about the other parties' evaluations. Here a trickier mixture of cryptography and game theory is required. <a href="https://www.researchgate.net/publication/225575735_Privacy-Enhancing_Auctions_Using_Rational_Cryptography" rel="nofollow noreferrer">This</a> paper goes in that direction.</p>
<p>There are several other interesting applications of game theory to cryptography (and viceversa!). A nice—although slightly outdated—survey is <a href="https://www.cs.umd.edu/%7Ejkatz/papers/tcc-gt.pdf" rel="nofollow noreferrer">this one</a>.</p>

CC BY-SA 4.0
2020-06-19T09:13:24.600Z
2020-06-19T09:13:24.600Z
funnyhow0x3f
<p>As a computer science student, I have been introduced to game theory, but not seen much detail on the subject. I have searched on Google and looked at some books about game theory and they provided confirmation of its usage in computer science. I have started a formal study of game theory from the economist's perspective. Now I want to know the applications of game theory in computer science. What are some recent major achievements of computer scientists in fields like Artificial Intelligence and Complexity Theory which utilize elements of game theory? Is there a way to approach game theory that is more rooted in computer science than economics?</p>

CC BY-SA 3.0
2013-01-22T20:32:10.247Z
http://en.wikipedia.org/wiki/Algorithmic_game_theory
Kaveh
CC BY-SA 3.0
2013-01-22T20:35:10.850Z
Vijay V. Vazirani, Noam Nisan, Tim Roughgarden, and Éva Tardos, "[Algorithmic Game Theory](http://www.cambridge.org/journals/nisan/downloads/Nisan_Non-printable.pdf)", 2007.
Kaveh
CC BY-SA 4.0
2020-06-20T15:32:17.377Z
Blockchains  are recent example of incentives/game theory playing an important role in how and whether the protocols work in the presence of adversarial and strategic agents.
Chandra Chekuri
<reference-request><gt.game-theory>
Applications of Game theory in computer science?
S. M. Shahinul Islam
# Applications of Game theory in computer science?

(Asked by: username_0 on 2013-01-22)

As a computer science student, I have been introduced to game theory, but not seen much detail on the subject. I have searched on Google and looked at some books about game theory and they provided confirmation of its usage in computer science. I have started a formal study of game theory from the economist's perspective. Now I want to know the applications of game theory in computer science. What are some recent major achievements of computer scientists in fields like Artificial Intelligence and Complexity Theory which utilize elements of game theory? Is there a way to approach game theory that is more rooted in computer science than economics?

**Tags:** reference-request, gt.game-theory

> **Comments:**
> **username_1**: http://en.wikipedia.org/wiki/Algorithmic_game_theory  
> **username_1**: Vijay V. Vazirani, Noam Nisan, Tim Roughgarden, and Éva Tardos, "[Algorithmic Game Theory](http://www.cambridge.org/journals/nisan/downloads/Nisan_Non-printable.pdf)", 2007.  
> **username_2**: Blockchains  are recent example of incentives/game theory playing an important role in how and whether the protocols work in the presence of adversarial and strategic agents.  

---

## 10 answers

### Answer by username_3 on 2013-01-23. Score: 23

One of the most famous examples of game theory in computer science is [Yao's minimax principle](http://en.wikipedia.org/wiki/Yao%27s_principle). Let $X$ be a set of inputs for some problem, and let $A$ be a set of (deterministic) algorithms for that problem. Yao's principle states that
$$
\max\_{x\in X} \operatorname{E}\limits\_{a\in A} \left[T(a,x)\right]
\ge
\min\_{a\in A} \operatorname{E}\limits\_{x\in X} \left[T(a,x)\right] ,
$$
where the expectations on the left and right are taken with respect to *any* desired probability distribution over algorithms and inputs, respectively.

For example: Any deterministic comparison-based sorting algorithm requires $\Omega(n\log n)$ time on average to sort an array permuted uniformly at random. (**Proof:** In any binary tree with $N$ leaves, at least half the leaves have depth at least $(\lg N)/2$. $\square$) So Yao's principle implies that the worst-case expected running time of any *randomized* comparison-based sorting algorithm is also $\Omega(n\log n)$.

Yao's minmax principle follow easily from von Neumann's [minimax theorem for two-player zero-sum games](http://en.wikipedia.org/wiki/Minimax_theorem#Minimax_theorem), where one player provides the input and the other provides the algorithm.

> **Comments:**
> **username_4**: Shouldn't the inequality be reversed? (unless I'm missing something)  
> **username_5**: on one hand this is just weak LP duality and it may be helpful to think of it that way, because finding a feasible dual solution is a nice general way to lower bound the optimum of a minimization problem. on the other, maybe it's helpful to think of the "algorithms" player and the "inputs" player...  

---

### Answer by username_6 on 2013-01-27. Score: 12

There are a number of game-theoretic characterizations of complexity classes. The most famous may be

* AP=PSPACE (figuring out who wins a deterministic game which lasts for a polynomial number of moves is a PSPACE-complete question),
* IP=PSPACE (in a polynomial-length deterministic game played against a player who makes random moves, distinguishing between the cases where your chance of winning is >0.9 and <0.1 is PSPACE-complete),

but there are many, many more.


---

### Answer by username_9 on 2013-01-23. Score: 10

Game theory played a significant role in solutions to the "full abstraction problem" in programming language semantics. In particular, the first fully-abstract semantics for Plotkin's PCF were given using games as models.

The relevant citations are:

*Full Abstraction for PCF*, by Samson Abramsky, Radha Jagadeesan, and Pasquale Malacaria

and

*On Full Abstraction for PCF: I, II, and III*, by J.M.E. Hyland and C.-H.L. Ong

which both appeared in *Information and Computation*, Volume 163, Issue 2, 15 December 2000.

> **Comments:**
> **username_10**: That's a different notion of game, in that it doesn't have a (non-trivial) notion of pay-off, unlike the games from an "economist's perspective". As an aside, in the context of full abstracion for PCF, Hanno Nickau's "Hereditarily Sequential Functionals" should also be mentioned.  

---

### Answer by username_7 on 2015-04-22. Score: 8

Another famous example of using game theory is in CS is synthesis: in synthesis we get a specification over inputs I and outputs O (e.g. in temporal logic, or as an automaton), and we want to automatically generate a system (i.e. a finite-state transducer), that guarantees that for every input sequence of the environment, the computation induced by the transducer satisfies the specification.

As it turns out, synthesis can be formulated as a game between the environment and the system, where a winning strategy for the system corresponds to a transducer.

A very important tool from game theory that is used in this context is Borel-determinancy, especially when we work over infinite computations.

You can start reading about this in [Moshe Vardi's survey](http://www.cs.rice.edu/~vardi/papers/fmco06.ps.gz).


---

### Answer by username_8 on 2015-07-09. Score: 8

Combinatorial game theory plays a role in logic and computer science as in, for example, the [Ehrenfeucht-fraïssé game](https://en.wikipedia.org/wiki/Ehrenfeucht%E2%80%93Fra%C3%AFss%C3%A9_game), which is a logic game played on model-theoretic structures. At each turn, the first player chooses an element from one of the two structures, and the second has to chose an element from the other, trying to maintain a local isomorphisms between the elements chosen up to that point.

The main theorem regarding this game roughly says that if Player 2 has a winning strategy in a game over two structures, then there does not exist a first-order logic formula that differentiate the two structures.

This result is used in a large number of expressibility results for first order logic and for other logics as well (there's notably an extension of the theorem to monadic second-order logic).

These expressiveness results in turn have strong applications in computer science, e.g. to formal verification, database theory, etc...


---

### Answer by username_11 on 2013-01-23. Score: 6

It is easier for me to think of applications of computer science (techniques) to game theory, than the other way around. There is a very active field of algorithmic game theory which focuses on the development of efficient algorithms (or complexity results) for, e.g., Nash equilibria, Shapley values, and other such standard game theoretic concepts. Often, these concepts are easy to define, but prohibitively difficult to compute directly from the definitions. This work extends at least as far as mechanism design, where we attempt to manipulate the rules of auctions in order to guarantee agent behavior (e.g., we would like them to report truthful bids) or overall results (e.g., we would like to guarantee maximal revenue.)

Noam Nisan, Yoav Shoham, Tim Roughgarden, and many others have some fascinating papers on the subject of mechanism design from a theory point of view; Vince Conitzer has applied AI techniques to the problem to develop automated mechanism design.

On the more applied side in artificial intelligence, it's difficult to think of multi-agent systems without thinking of them as games. The Partially Observable Stochastic Game (POSG) framework is often used to discuss to multi-agent settings; under the right reward function criteria it becomes a DEC-POMDP.


---

### Answer by username_12 on 2016-01-08. Score: 3

The article in [Distributed Computing Column 42](http://webee.technion.ac.il/~idish/sigactNews/DC-col42-Jun11.pdf) attempts to bring a game-theoretic perspective to distributed computing problems.

> *Distributed Computing Meets Game Theory: Combining Insights From Two Fields*. Ittai Abraham, Lorenzo Alvisi, Joseph Y. Halpern SIGACT News 42(2) June 2011, pp. 68-76

Quoted from "Idit Keidar", the editor at that time:

Game theory and fault tolerance offer two different flavors of robustness to distributed systems – the former is robust against participants attempting to maximize their own utilities, whereas the latter offers
robustness against unexpected faults. This column takes a look at attempts to combine the two. It features a review of recent work that provides both flavors of robustness by Ittai Abraham, Lorenzo Alvisi, and Joe
Halpern. Ittai, Lorenzo, and Joe discuss how game theory-style strategic behavior can be accounted for in fault-tolerant distributed protocols. They make a compelling case for bringing a game-theoretic perspective
to distributed computing problems.


---

### Answer by username_13 on 2020-06-19. Score: 2

In [Formal Verification](https://en.wikipedia.org/wiki/Formal_verification) game theory is a recurring theme. I think that one of the most important applications is to define the [Simulation Preorder](https://en.wikipedia.org/wiki/Simulation_preorder) as a game between two players: Spoiler (he) and Duplicator (she). Given a [Transition System](https://en.wikipedia.org/wiki/Transition_system) (in other words, one set $S$ equipped with a *labelled transition* relation $S \rightarrow S$) Spoiler, starting from a given state, chooses a transition and makes a move. Duplicator has to match the labelled transition and make a move from her starting state. Then, Spoiler makes another move from his last state and Duplicator has to match that transition again, and game goes on in this way. Spoiler first state *simulates* Duplicator's first state if she has a *winning strategy* in this game. In their paper ["Advanced automata minimization"](https://dl.acm.org/doi/abs/10.1145/2480359.2429079), Lorenzo Clemente and Richard Mayr, define a wide variety of *simulation relations* using games.


---

### Answer by username_14 on 2020-06-27. Score: 1

Since the title is about CS and not TCS, maybe an answer about applications of game theory to networking can be of some interest.

Questions about game theory and equilibria arise naturally in networking, since the networks that make Internet are economic competitors and belong to different companies, but they need to collaborate in order to ensure connectivity. A lot of work was done about routing policy leading to equilibria, and the impact of the price of anarchy on Internet performances. Such problems are generally called "routing games".

The seminal work of Roughgarden and Tardos was the starting point of hundreds of papers about equilibria and routing. You can find below some examples (mostly works of Eitan Altman or Ariel Orda).

Roughgarden, T., & Tardos, É. (2002). How bad is selfish routing?. Journal of the ACM (JACM), 49(2), 236-259.

Eitan Altman, Jocelyne Elias, Fabio Martignon:
A game theoretic framework for joint routing and pricing in networks with elastic demands. VALUETOOLS 2009: 57

Giovanni Accongiagioco, Eitan Altman, Enrico Gregori, Luciano Lenzini:
Peering vs transit: A game theoretical model for autonomous systems connectivity. Networking 2014: 1-9

Giovanni Accongiagioco, Eitan Altman, Enrico Gregori, Luciano Lenzini:
A game theoretical study of peering vs transit in the internet. INFOCOM Workshops 2014: 783-788

Ron Banner, Ariel Orda:
Bottleneck Routing Games in Communication Networks. INFOCOM 2006

Liane Lewin-Eytan, Joseph Naor, Ariel Orda:
Maximum-lifetime routing: system optimization & game-theoretic perspectives. MobiHoc 2007: 160-169

Gideon Blocq, Ariel Orda:
How good is bargained routing? INFOCOM 2012: 2453-2461

Gideon Blocq, Ariel Orda:
"Beat-Your-Rival" Routing Games. SAGT 2015: 231-243

Gideon Blocq, Ariel Orda:
Coalitions in Routing Games: A Worst-Case Perspective. IEEE Trans. Netw. Sci. Eng. 6(4): 857-870 (2019)


---

### Answer by username_15 on 2020-06-19. Score: 0

One surprising intersection is that of **cryptography and game theory**.

In cryptography you often want to get rid of *trusted parties.* For example, imagine some parties wanting to perform a sealed-bid auction—where everybody gives the auctioneer a sealed envelop with a bid inside—but *(a)* no trusted auctioneer is in sight and *(b)* the bidders definitely do not trust each other.

Are they doomed? No, there are several cryptographic solutions to this; the subfield of secure multi-party computation ([MPC](https://en.wikipedia.org/wiki/Secure_multi-party_computation)) studies this problem.
Little game theory so far, except that this scenario can "simulate" the one with an actual trusted auctioneer and thus standard equilibria results should hold (with some caveats, e.g. these are *computational equilibria*, that is they hold only for polynomial-time machines, otherwise they could break underlying cryptographic assumptions).

Things get interesting, for example, if parties want not only to get a good deal out of the auction but also, in the meantime, learn something about the other parties' evaluations. Here a trickier mixture of cryptography and game theory is required. [This](https://www.researchgate.net/publication/225575735_Privacy-Enhancing_Auctions_Using_Rational_Cryptography) paper goes in that direction.

There are several other interesting applications of game theory to cryptography (and viceversa!). A nice—although slightly outdated—survey is [this one](https://www.cs.umd.edu/%7Ejkatz/papers/tcc-gt.pdf).


---

