We consider two-player stochastic games on a graph. Two-player stochastic games are a generalization of  two-player games and Markov decision processes. Each state in the graph is controlled by one of the two players P1 and P2.

The "nearest neighbor (NN) classifier" labels a new data instance by taking a majority vote over the k most similar instances seen in the past. With an appropriate setting of k, it is capable of modeling arbitrary decision rules.

Information theoretically secure multiparty computation (MPC) is a central primitive in modern cryptography.

Partial function extension is a basic problem that underpins multiple research topics in optimization, including learning, property testing, and game theory.