USF Home > College of Arts and Sciences > Department of Mathematics & Statistics

Mathematics & Statistics
Colloquium Archive

# Colloquia — Fall 2019

## Friday, December 6, 2019

Title
Speaker

Time
Place

TBA
Tommy Hofmann
TU Kaiserslautern
3:00pm–4:00pm
CMC 130
Jean-François Biasse

Abstract

TBA

## Friday, November 22, 2019

Title
Speaker

Time
Place

Tug-of-war games and Biased Infinity Laplacian Boundary Problem on finite graphs
Zoran Šunić
Hofstra University
3:00pm–4:00pm
CMC 130
Milé Krajčevski

Abstract

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

The problem is, on the one hand, motivated by problems in auction theory, and on the other, it forms a basis for a numerical method for certain partial differential equations. We will discuss neither of these in depth. The following probabilistic/graph theoretic interpretation suffices for our purposes.

Let $$G$$ be a finite graph with boundary $$B$$ (any subset of vertices) and boundary condition $$g: B \to R$$ (any real-valued function defined on the boundary). We may think of $$g$$ as the pay-off function for a random-turn two-player zero-sum game played on $$G$$ as follows. In the beginning a token is placed at a non-boundary vertex. At every step, one of the players randomly (decided by a biased coin) gets the right to move and then chooses (not randomly!) a neighboring vertex to which the token is moved. The game ends when the token reaches a boundary vertex, say $$b$$, at which point Player I wins the amount $$g(b)$$ from Player II.

A solution to the Boundary Problem is the value of the game, that is, a function $$p: V(G) \to R$$ such that, for every vertex $$v$$ in $$V(G)$$, $$p(v)$$ is the expected pay-off for Player I under optimal strategy by both players when the game starts with the token at $$v$$.

The algorithm is based on an adjusted (biased) notion of a slope of a function on a path in a graph.

Title
Speaker

Time
Place