Georgia Institute of Technology College of Sciences

The theme of this talk is walks in a random environment of "signposts" altered by the walker. I'll focus on three related examples: 1. Rotor walk on Z^2. Your initial signposts are independent with the uniform distribution on {North,East,South,West}. At each step you rotate the signpost at your current location clockwise 90 degrees and then follow it to a nearest neighbor. Priezzhev et al. conjectured that in n such steps you will visit order n^{2/3} distinct sites. I'll outline an elementary proof of a lower bound of this order. The upper bound, which is still open, is related to a famous question about the path of a light ray in a grid of randomly oriented mirrors. This part is joint work with Laura Florescu and Yuval Peres. 2. p-rotor walk on Z. In this walk you flip the signpost at your current location with probability 1-p and then follow it. I'll explain why your scaling limit will be a Brownian motion perturbed at its extrema. This part is joint work with Wilfried Huss and Ecaterina Sava-Huss. 3. p-rotor walk on Z^2. Rotate the signpost at your current location clockwise with probability p and counterclockwise with probability 1-p, and then follow it. This walk “organizes” its environment of signposts. The stationary environment is an orientation of the uniform spanning forest, plus one additional edge. This part is joint work with Swee Hong Chan, Lila Greco and Boyao Li.

We study stable marriage where individuals strategically submit private preference information to a publicly known stable marriage algorithm. We prove that no stable marriage algorithm ensures actual stability at every Nash equilibrium when individuals are strategic. More specifically, we show that any rational marriage, stable or otherwise, can be obtained at a Nash equilibrium. Thus the set of Nash equilibria provides no predictive value nor guidance for mechanism design. We propose the following new minimal dishonesty equilibrium refinement, supported by experimental economics results: an individual will not strategically submit preference list L if there exists a more honest L' that yields as preferred an outcome. Then for all marriage algorithms satisfying monotonicity and IIA, every minimally dishonest equilibrium yields a sincerely stable marriage. This result supports the use of algorithms less biased than the (Gale-Shapley) man-optimal, which we prove yields the woman-optimal marriage in every minimally dishonest equilibrium. However, bias cannot be totally eliminated, in the sense that no monotonic IIA stable marriage algorithm is certain to yield the egalitarian-optimal marriage in a minimally dishonest equilibrium – thus answering a 28-year old open question of Gusfield and Irving's in the negative. Finally, we show that these results extend to student placement problems, where women are polygamous and honest, but not to admissions problems, where women are both polygamous and strategic. Based on joint work with Craig Tovey at Georgia Tech.

Continuing from last time, we will discuss Hilden and Montesinos' result that every smooth closed oriented three manifold is a three fold branched cover over the three sphere, and also there is a representation by bands.

I will continue the discussion on the group actions of the graph Jacobian on the set of spanning trees. After reviewing the basic definitions, I will explain how polyhedral geometry leads to a new family of such actions. These actions can be described combinatorially, but proving that they are simply transitive uses geometry in an essential way. If time permits, I will also explain the following surprising connection: the canonical group action for a plane graph (via rotor-routing or Bernardi process) is related to the canonical tropical geometric structure of its dual graph. This is joint work with Spencer Backman and Matt Baker.