13
$\begingroup$

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?

$\endgroup$
21
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Shouldn't the inequality be reversed? (unless I'm missing something) $\endgroup$ – George Jan 23 '13 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$ – Sasho Nikolov Jan 23 '13 at 23:24
11
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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.

$\endgroup$
  • 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$ – Martin Berger Jan 23 '13 at 22:41
6
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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...

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.