We introduce the notion of Local Computation Mechanism Design - designing game theoretic mechanisms that run in sublinear time and space. Local computation mechanisms reply to each query efficiently, and the replies to different queries are consistent with the same global feasible solution.
We present local computation mechanisms in a variety of classical game-theoretical settings, focusing on stable matching. We show that some of our techniques have implications to the global setting; specifically, we show that when the men's preference lists are bounded, we can achieve an arbitrarily good approximation to the stable matching within a fixed number of iterations of the Gale-Shapley algorithm.
This is joint work with Avinatan Hassidim and Yishay Mansour
Speaker's bio : Shai Vardi is a postdoctoral fellow in Computer Science and Applied Mathematics at the Weizmann Institute for Science. He recently completed his PhD studies in Computer Science in Tel Aviv University under the supervision of Yishay Mansour, and holds MSc and BSc degrees in Computer Science, also from Tel Aviv University. Shai works on local computation algorithms, online algorithms, and algorithmic game theory, most notably dynamic fair allocation.