More Like this

1. The Dyson and Coulomb games

   Carmona, Rene; Cerenzia, Mark; Palmer, Aaron Zeff (October 2019, ArXivorg)

   We introduce and investigate certain N player dynamic games on the line and in the plane that admit Coulomb gas dynamics as a Nash equilibrium. Most significantly, we find that the universal local limit of the equilibrium is sensitive to the chosen model of player information in one dimension but not in two dimensions. We also find that players can achieve game theoretic symmetry through selfish behavior despite non-exchangeability of states, which allows us to establish strong localized convergence of the N-Nash systems to the expected mean field equations against locally optimal player ensembles, i.e., those exhibiting the same local limit as the Nash-optimal ensemble. In one dimension, this convergence notably features a nonlocal-to-local transition in the population dependence of the N-Nash system. 

   more » « less
2. On non-unique solutions in mean field games

   https://doi.org/10.1109/CDC40024.2019.9029906  

   Hajek, Bruce; Livesay, Michael (December 2019, 2019 58th Conference on Decision and Control)

   The theory of mean field games is a tool to understand noncooperative dynamic stochastic games with a large number of players. Much of the theory has evolved under conditions ensuring uniqueness of the mean field game Nash equilibrium. However, in some situations, typically involving symmetry breaking, non-uniqueness of solutions is an essential feature. To investigate the nature of non-unique solutions, this paper focuses on the technically simple setting where players have one of two states, with continuous time dynamics, and the game is symmetric in the players, and players are restricted to using Markov strategies. All the mean field game Nash equilibria are identified for a symmetric follow the crowd game. Such equilibria correspond to symmetric $$\epsilon$$-Nash Markov equilibria for $$N$$ players with $$\epsilon$$ converging to zero as $$N$$ goes to infinity. In contrast to the mean field game, there is a unique Nash equilibrium for finite $N.$ It is shown that fluid limits arising from the Nash equilibria for finite $$N$$ as $$N$$ goes to infinity are mean field game Nash equilibria, and evidence is given supporting the conjecture that such limits, among all mean field game Nash equilibria, are the ones that are stable fixed points of the mean field best response mapping. 

   more » « less
3. Factorized class S theories and surface defects

   https://doi.org/10.1007/JHEP12(2021)041  

   Ergun, Behzat; Hao, Qianyu; Neitzke, Andrew; Yan, Fei (December 2021, Journal of High Energy Physics)

   A bstract It is known that some theories of class S are actually factorized into multiple decoupled nontrivial four-dimensional $$ \mathcal{N} $$ N = 2 theories. We propose a way of constructing examples of this phenomenon using the physics of half-BPS surface defects, and check that it works in one simple example: it correctly reproduces a known realization of two copies of $$ \mathcal{N} $$ N = 2 superconformal SU(2) QCD, describing this factorized theory as a class S theory of type A 3 on a five-punctured sphere with a twist line. Separately, we also present explicit checks that the Coulomb branch of a putative factorized class S theory has the expected product structure, in two examples. 

   more » « less
4. Class Fairness in Online Matching

   https://doi.org/10.1609/aaai.v37i5.25704  

   Hosseini, Hadi; Huang, Zhiyi; Igarashi, Ayumi; Shah, Nisarg (June 2023, Proceedings of the AAAI Conference on Artificial Intelligence)

   We initiate the study of fairness among classes of agents in online bipartite matching where there is a given set of offline vertices (aka agents) and another set of vertices (aka items) that arrive online and must be matched irrevocably upon arrival. In this setting, agents are partitioned into a set of classes and the matching is required to be fair with respect to the classes. We adopt popular fairness notions (e.g. envy-freeness, proportionality, and maximin share) and their relaxations to this setting and study deterministic and randomized algorithms for matching indivisible items (leading to integral matchings) and for matching divisible items (leading to fractional matchings).For matching indivisible items, we propose an adaptive-priority-based algorithm, MATCH-AND-SHIFT, prove that it achieves (1/2)-approximation of both class envy-freeness up to one item and class maximin share fairness, and show that each guarantee is tight. For matching divisible items, we design a water-filling-based algorithm, EQUAL-FILLING, that achieves (1-1/e)-approximation of class envy-freeness and class proportionality; we prove (1-1/e) to be tight for class proportionality and establish a 3/4 upper bound on class envy-freeness. 

   more » « less
5. Fast Approximate Counting of Cycles

   https://doi.org/10.4230/LIPIcs.ICALP.2024.37  

   Censor-Hillel, Keren; Even, Tomer; Vassilevska_Williams, Virginia (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Bringmann, Karl; Grohe, Martin; Puppis, Gabriele; Svensson, Ola (Ed.)

   We consider the problem of approximate counting of triangles and longer fixed length cycles in directed graphs. For triangles, Tětek [ICALP'22] gave an algorithm that returns a (1±ε)-approximation in Õ(n^ω/t^{ω-2}) time, where t is the unknown number of triangles in the given n node graph and ω < 2.372 is the matrix multiplication exponent. We obtain an improved algorithm whose running time is, within polylogarithmic factors the same as that for multiplying an n× n/t matrix by an n/t × n matrix. We then extend our framework to obtain the first nontrivial (1± ε)-approximation algorithms for the number of h-cycles in a graph, for any constant h ≥ 3. Our running time is Õ(MM(n,n/t^{1/(h-2)},n)), the time to multiply n × n/(t^{1/(h-2)}) by n/(t^{1/(h-2)) × n matrices. Finally, we show that under popular fine-grained hypotheses, this running time is optimal. 

   more » « less