[Colloquium] Theory Seminars at Computer Science

[Donna Brooms]

COMBINATORICS & THEORETICAL COMPUTER SCIENCE SEMINAR

Tuesday, November 3, 2015
3:00 pm
Ryerson 251

Zoran Sunic
Texas A&M University
www.math.tamu <http://www.math.tamu/>.edu
 
Title: “Infinity Laplacian Boundary Problem and random-turn games”

Abstract: 
We provide an algorithm, running in polynomial time in the number of vertices, computing the unique solution to the Infinity Laplacian Boundary Problem (ILBP) on finite graphs.

The problem is motivated on the one hand by problems in auction theory and on the other as a basis for a numerical method of solving certain partial differential equations. For our purposes the following probabilistic interpretation suffices.


Let G be a finite graph with boundary V_0 (any subset of vertices) and boundary condition g : V_0 -> R (any real-valued function). We may think of g as the pay-off function in a random-turn two-player zero-sum game on G played as follows. In the beginning a token is placed at a non-boundary vertex. At every step one of the two players randomly gets the right to move and moves the token to any neighboring vertex.  The game ends when the token reaches a boundary vertex b, at which point Player I wins the amount g(b) from Player II.


The solution u to the ILBP is the value of the game, i.e., for every vertex x, u(x) is the expected pay-off for Player I under optimal strategy of play by both players when the game starts with the token at x.


Joint work with Yuval Peres, Microsoft Research, Redmond WA


Host: Prof. Laszlo Babi

Refreshments will be served before the talk in Ry 255 at 2:30pm    

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20151102/d24d42e0/attachment-0001.htm