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?
$\begingroup$
$\endgroup$
3
asked Jan 22, 2013 at 20:28
-
6$\begingroup$ en.wikipedia.org/wiki/Algorithmic_game_theory $\endgroup$– KavehCommented Jan 22, 2013 at 20:32
-
8$\begingroup$ Vijay V. Vazirani, Noam Nisan, Tim Roughgarden, and Éva Tardos, "Algorithmic Game Theory", 2007. $\endgroup$– KavehCommented Jan 22, 2013 at 20:35
-
1$\begingroup$ 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. $\endgroup$– Chandra ChekuriCommented Jun 20, 2020 at 15:32
Add a comment
|
10 Answers
$\begingroup$
$\endgroup$
2
One of the most famous examples of game theory in computer science is Yao's minimax 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, where one player provides the input and the other provides the algorithm.
-
2$\begingroup$ Shouldn't the inequality be reversed? (unless I'm missing something) $\endgroup$– GeorgeCommented Jan 23, 2013 at 20:01
-
$\begingroup$ 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... $\endgroup$ Commented Jan 23, 2013 at 23:24
$\begingroup$
$\endgroup$
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.
answered Jan 27, 2013 at 2:12
$\begingroup$
$\endgroup$
1
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.
answered Jan 23, 2013 at 19:31
-
2$\begingroup$ 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. $\endgroup$ Commented Jan 23, 2013 at 22:41
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
Combinatorial game theory plays a role in logic and computer science as in, for example, the Ehrenfeucht-fraïssé 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...
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
The article in Distributed Computing Column 42 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.
$\begingroup$
$\endgroup$
In Formal Verification game theory is a recurring theme. I think that one of the most important applications is to define the Simulation Preorder as a game between two players: Spoiler (he) and Duplicator (she). Given a 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", Lorenzo Clemente and Richard Mayr, define a wide variety of simulation relations using games.
$\begingroup$
$\endgroup$
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)
$\begingroup$
$\endgroup$
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) 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 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.
