More Like this

1. Equilibrium Computation in Multidimensional Congestion Games: CSP and Learning Dynamics Approaches

   Irfan, Mohammad T; Chan, Hau; Soundy, Jared (July 2024, The 40th Conference on Uncertainty in Artificial Intelligence (UAI 2024))

   We present algorithms of two flavors—one rooted in constraint satisfaction problems (CSPs) and the other in learning dynamics—to compute pure-strategy Nash equilibrium (PSNE) in k-dimensional congestion games (k-DCGs) and their variants. The two algorithmic approaches are driven by whether or not a PSNE is guaranteed to exist. We first show that deciding the existence of a PSNE in a k-DCG is NP-complete even when players have binary and unit demand vectors. For general cost functions (potentially non-monotonic), we devise a new CSP-inspired algorithmic framework for PSNE computation, leading to algorithms that run in polynomial time under certain assumptions while offering exponential savings over standard CSP algorithms. We further refine these algorithms for variants of k-DCGs. Our experiments demonstrate the effectiveness of this new CSP framework for hard, non-monotonic k-DCGs. We then provide learning dynamics-based PSNE computation algorithms for linear and exponential cost functions. These algorithms run in polynomial time under certain assumptions. For general cost, we give a learning dynamics algorithm for an (α, β)-approximate PSNE (for certain α and β). Lastly, we also devise polynomial-time algorithms for structured demands and cost functions. 

   more » « less
2. On the existence of Nash Equilibrium in games with resource-bounded players

   Halpern, Joseph Y; Pass, Rafael; Reichman, Daniel (September 2019, Proceedings of the 12th International Symposium on A Game Theory (SAGT)})

   We consider computational games, sequences of games G = (G1,G2,...) where, for all n, Gn has the same set of players. Computational games arise in electronic money systems such as Bitcoin, in cryptographic protocols, and in the study of generative adversarial networks in machine learning. Assuming that one-way functions exist, we prove that there is 2-player zero-sum computational game G such that, for all n, the size of the action space in Gn is polynomial in n and the utility function in Gn is computable in time polynomial in n, and yet there is no ε-Nash equilibrium if players are restricted to using strategies computable by polynomial-time Turing machines, where we use a notion of Nash equilibrium that is tailored to computational games. We also show that an ε-Nash equilibrium may not exist if players are constrained to perform at most T computational steps in each of the games in the sequence. On the other hand, we show that if players can use arbitrary Turing machines to compute their strategies, then every computational game has an ε-Nash equilibrium. These results may shed light on competitive settings where the availability of more running time or faster algorithms can lead to a “computational arms race”, precluding the existence of equilibrium. They also point to inherent limitations of concepts such as “best response” and Nash equilibrium in games with resource-bounded players. 

   more » « less
3. Fast and Simple Solutions of Blotto Games

   https://doi.org/10.1287/opre.2022.2261  

   Behnezhad, Soheil; Dehghani, Sina; Derakhshan, Mahsa; Hajiaghayi, Mohammedtaghi; Seddighin, Saeed (May 2022, Operations Research)

   In the Colonel Blotto game, which was initially introduced by Borel in 1921, two colonels simultaneously distribute their troops across different battlefields. The winner of each battlefield is determined independently by a winner-takes-all rule. The ultimate payoff for each colonel is the number of battlefields won. The Colonel Blotto game is commonly used for analyzing a wide range of applications from the U.S. Presidential election to innovative technology competitions to advertising, sports, and politics. There are persistent efforts to find the optimal strategies for the Colonel Blotto game. However, the first polynomial-time algorithm for that has very recently been provided by Ahmadinejad, Dehghani, Hajiaghayi, Lucier, Mahini, and Seddighin. Their algorithm consists of an exponential size linear program (LP), which they solve using the ellipsoid method. Because of the use of the ellipsoid method, despite its significant theoretical importance, this algorithm is highly impractical. In general, even the simplex method (despite its exponential running time in practice) performs better than the ellipsoid method in practice. In this paper, we provide the first polynomial-size LP formulation of the optimal strategies for the Colonel Blotto game using linear extension techniques. Roughly speaking, we consider the natural representation of the strategy space polytope and transform it to a higher dimensional strategy space, which interestingly has exponentially fewer facets. In other words, we add a few variables to the LP such that, surprisingly, the number of constraints drops down to a polynomial. We use this polynomial-size LP to provide a simpler and significantly faster algorithm for finding optimal strategies of the Colonel Blotto game. We further show this representation is asymptotically tight, which means there exists no other linear representation of the strategy space with fewer constraints. We also extend our approach to multidimensional Colonel Blotto games, in which players may have different sorts of budgets, such as money, time, human resources, etc. By implementing this algorithm, we are able to run tests that were previously impossible to solve in a reasonable time. This information allows us to observe some interesting properties of Colonel Blotto; for example, we find out the behavior of players in the discrete model is very similar to the continuous model Roberson solved. 

   more » « less
4. Computing Equilibria in Binary Networked Public Goods Games

   Yu, Sixie; Zhou, Kai; Brantingham, Jeff; Vorobeychik, Yevgeniy (January 2020, Proceedings of the AAAI Conference on Artificial Intelligence)

   Public goods games study the incentives of individuals to contribute to a public good and their behaviors in equilibria. In this paper, we examine a specific type of public goods game where players are networked and each has binary actions, and focus on the algorithmic aspects of such games. First, we show that checking the existence of a pure-strategy Nash equilibrium is NP-Complete. We then identify tractable instances based on restrictions of either utility functions or of the underlying graphical structure. In certain cases, we also show that we can efficiently compute a socially optimal Nash equilibrium. Finally, we propose a heuristic approach for computing approximate equilibria in general binary networked public goods games, and experimentally demonstrate its effectiveness. 

   more » « less
5. Indistinguishability obfuscation from well-founded assumptions.

   Jain, Aayush; Lin, Huijia; Sahai, Amit (January 2021, STOC)

   null (Ed.)

   Indistinguishability obfuscation, introduced by [Barak et. al. Crypto2001], aims to compile programs into unintelligible ones while preserving functionality. It is a fascinating and powerful object that has been shown to enable a host of new cryptographic goals and beyond. However, constructions of indistinguishability obfuscation have remained elusive, with all other proposals relying on heuristics or newly conjectured hardness assumptions. In this work, we show how to construct indistinguishability obfuscation from subexponential hardness of four well-founded assumptions. We prove: Informal Theorem: Let 𝜏∈ (0,∞), 𝛿∈ (0,1), 𝜖∈ (0,1) be arbitrary constants. Assume sub-exponential security of the following assumptions: - the Learning With Errors (LWE) assumption with subexponential modulus-to-noise ratio 2^{𝑘^𝜖} and noises of magnitude polynomial in 𝑘,where 𝑘 is the dimension of the LWE secret, - the Learning Parity with Noise (LPN) assumption over general prime fields Z𝑝 with polynomially many LPN samples and error rate 1/ℓ^𝛿 ,where ℓ is the dimension of the LPN secret, - the existence of a Boolean Pseudo-Random Generator (PRG) in NC0 with stretch 𝑛^{1+𝜏}, where 𝑛 is the length of the PRG seed, - the Decision Linear (DLIN) assumption on symmetric bilinear groups of prime order. Then, (subexponentially secure) indistinguishability obfuscation for all polynomial-size circuits exists. Further, assuming only polynomial security of the aforementioned assumptions, there exists collusion resistant public-key functional encryption for all polynomial-size circuits. 

   more » « less