We propose a non-asymptotic approach to analyze kidney exchange that builds on the random graph model of kidney exchange introduced in Ashlagi, Garmarnik, Rees and Roth's "The need for (long) chains in kidney exchange" (2012). We analyze a two phase procedure where random walks are used to allocate chains, followed by allocation via matching in cycles. Random walks preserve the probabilistic structure of residual graphs, greatly facilitating analysis without sending the number of nodes to infinity. We derive useful analytical bounds that illustrate the performance of our procedure and more general kidney allocation procedures. Our results complement previous asymptotic results for large (limit) graphs on the benefits of using chains in kidney exchange and empirical results based on data from fielded kidney exchanges.

We analyze the complexity of computing pure strategy Nash equilibria (PSNE) in symmetric games with a fixed number of actions. We restrict ourselves to "compact" representations, meaning that the number of players can be exponential in the representation size. We show that in the general case, where utility functions are represented as arbitrary circuits, the problem of deciding the existence of PSNE is NP-complete. For the special case of games with two actions, we show that there always exists a PSNE and give a polynomial-time algorithm for finding one. We then focus on a specific compact representation: piecewise-linear utility functions. We give polynomial-time algorithms for finding a sample PSNE, counting the number of PSNEs, and also provide an FPTAS for finding social-welfare-maximizing equilibria. We extend our piecewise-linear representation to achieve what we believe to be the first compact representation for parameterized families of (symmetric) games. We provide methods for answering questions about a parameterized family without needing to solve each game from the family separately.