Infinity Laplacian
In mathematics, the infinity Laplace (or formula_1-Laplace) operator is a 2nd-order partial differential operator, commonly abbreviated formula_2. It is alternately defined by or The first version avoids the singularity which occurs when the gradient vanishes, while the second version is homogeneous of order zero in the gradient. Verbally, the second version is the second derivative in the direction of the gradient. In the case of the infinity Laplace equation formula_5, the two definitions are equivalent. While the equation involves second derivatives, usually (generalized) solutions are not twice differentiable, as evidenced by the well-known Aronsson solution  formula_6. For this reason the correct notion of solutions is that given by the viscosity solutions. Viscosity solutions to the equation formula_5 are also known as infinity harmonic functions. This terminology arises from the fact that the infinity Laplace operator first arose in the study of absolute minimizers for formula_8, and it can be viewed in a certain sense as the limit of the p-Laplacian as formula_9. More recently, viscosity solutions to the infinity Laplace equation have been identified with the payoff functions from randomized tug-of-war games. The game theory point of view has significantly improved the  understanding of the partial differential equation itself. Discrete version and game theory. A defining property of the usual formula_10-harmonic functions is the mean value property. That has a natural and important discrete version: a real-valued function formula_11 on a finite or infinite graph formula_12 is discrete harmonic on a subset formula_13 if for all formula_15. Similarly, the vanishing second derivative in the direction of the gradient has a natural discrete version: In this equation, we used sup and inf instead of max and min because the graph formula_12 does not have to be locally finite (i.e., to have  finite degrees): a key example is when formula_18 is the set of points in a domain in formula_19, and formula_20 if their Euclidean distance is at most formula_21. The importance of this example lies in the following. Consider a bounded open set formula_22 with smooth boundary formula_23, and a continuous function formula_24. In the formula_10-case, an approximation of the harmonic extension of "f" to "D" is given by taking a lattice formula_26 with small mesh size formula_21, letting formula_28 and formula_29 be the set of vertices with degree less than "2d", taking a natural approximation formula_30, and then taking  the unique discrete harmonic extension of formula_31 to "V". However, it is easy to see by examples that this does not work for the formula_1-case. Instead, as it turns out, one should take the "continuum graph" with all edges of length at most formula_21, mentioned above. Now, a probabilistic way of looking at the formula_10-harmonic extension of formula_31 from formula_36 to formula_37 is that where formula_39 is the simple random walk on formula_40 started at formula_41, and formula_42 is the hitting time of formula_36. For the formula_1-case, we need game theory. A token is started at location  formula_45, and formula_46 is given. There are two players, in each turn they flip a fair coin, and the winner can move the token to any neighbour of the current location. The game ends when the token reaches formula_36 at some time formula_42 and location formula_49, at which point the first player gets the amount formula_50 from the second player. Therefore, the first player wants to maximize formula_50, while the second player wants to minimize it. If both players play optimally (which has a well-defined meaning in game theory), the expected payoff formula_52 to the first player is a  discrete infinity harmonic function, as defined above. There is a game theory approach to the p-Laplacian, too, interpolating between simple random walk and the above random tug-of-war game.