Cover Image

The Computational Complexity of Variational Inequalities and Applications in Game Theory

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Kapron, Bruce M., Samieefar, Koosha
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity Computer Science and Game Theory 68Q17 F.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Two-player Domino games
by: de Menibus, Benjamin Hellouin, et al.
Published: (2023)

Optimal Portfolio Compression for Priority-Proportional Clearing with Defaulting Costs
by: Csáji, Gergely, et al.
Published: (2026)

A Characterization of Complexity in Public Goods Games
by: Gilboa, Matan
Published: (2023)

Low communication protocols for fair allocation of indivisible goods
by: Feige, Uriel
Published: (2024)

An MDL-Style Cost Functional KC, Distribution-Preserving Reductions ($A2^d$), and an $AC^0$+log Lower Bound for 3SAT via Balanced 3XOR
by: Lela, Marko
Published: (2025)

On Small-depth Frege Proofs for PHP
by: Håstad, Johan
Published: (2024)

How do humans succeed in tasks like proving Fermat's Theorem or predicting the Higgs boson?
by: Levin, Leonid A.
Published: (2022)

NP-Completeness Proofs of All or Nothing, Water Walk, and Remembered Length Using the T-Metacell Framework
by: Eua-anant, Pakapim, et al.
Published: (2025)

The Complexity of Graph Exploration Games
by: Fuchs, Janosch, et al.
Published: (2023)

Completeness classes in algebraic complexity theory
by: Bürgisser, Peter
Published: (2024)

On Binary Networked Public Goods Game with Altruism
by: Maiti, Arnab, et al.
Published: (2022)

NP-hardness of p-adic linear regression
by: Baker, Gregory D.
Published: (2026)

Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hard
by: Dorochko, Leonid, et al.
Published: (2026)

Computational Complexity of Determining the Assembly Index
by: Masierak, Piotr
Published: (2026)

On the Complexity of the Optimal Correlated Equilibria in Extensive-Form Games
by: Cheval, Vincent, et al.
Published: (2025)

Smaller Depth-2 Linear Circuits for Disjointness Matrices
by: Ye, Lixi
Published: (2026)

Explicit separations between randomized and deterministic Number-on-Forehead communication
by: Kelley, Zander, et al.
Published: (2023)

Fair allocations with subadditive and XOS valuations
by: Feige, Uriel, et al.
Published: (2025)

On MMS, APS and XOS
by: Feige, Uriel, et al.
Published: (2026)

Undefinability of Approximation of 2-to-2 Games
by: Dawar, Anuj, et al.
Published: (2025)

Imperfect-Recall Games: Equilibrium Concepts and Their Complexity
by: Tewolde, Emanuel, et al.
Published: (2024)

Doubly Fair Parity Games
by: Hausmann, Daniel, et al.
Published: (2023)

Computing Game Symmetries and Equilibria That Respect Them
by: Tewolde, Emanuel, et al.
Published: (2025)

Red-Blue Pebbling with Multiple Processors: Time, Communication and Memory Trade-offs
by: Böhnlein, Toni, et al.
Published: (2024)

Computational Complexity of Finding Subgroups of a Given Order
by: Lakshmanan, K.
Published: (2025)

Quantum Time-Space Tradeoffs for Matrix Problems
by: Beame, Paul, et al.
Published: (2024)

On the Parallel Complexity of Group Isomorphism via Weisfeiler-Leman
by: Grochow, Joshua A., et al.
Published: (2021)

IECZ-III: Hardcore Condensation Lift with Size-Aware Invariants
by: Lela, Marko
Published: (2025)

Complexity of Unambiguous Problems in $Σ^P_2$
by: Gilboa, Matan, et al.
Published: (2025)

Simple Stochastic Stopping Games: A Generator and Benchmark Library
by: Rudich, Avi, et al.
Published: (2024)

Required-edge Cycle Cover Problem: an ASP-Completeness Framework for Graph Problems and Puzzles
by: Susukita, Kosuke, et al.
Published: (2026)

Generalisations of Matrix Partitions : Complexity and Obstructions
by: Barsukov, Alexey, et al.
Published: (2021)

Markets are competitive if and only if P != NP
by: Maymin, Philip Z.
Published: (2026)

Formula Size-Depth Tradeoffs for Iterated Sub-Permutation Matrix Multiplication
by: Rossman, Benjamin
Published: (2024)

Counting Martingales for Measure and Dimension in Complexity Classes
by: Hitchcock, John M., et al.
Published: (2025)

Shifted Partial Derivative Polynomial Rank and Codimension
by: Edwards, Darren J.
Published: (2025)

Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers
by: Hakoniemi, Tuomas, et al.
Published: (2024)

DAG Scheduling in the BSP Model
by: Papp, Pál András, et al.
Published: (2023)

On the complexity of epimorphism testing with virtually abelian targets
by: Elder, Murray, et al.
Published: (2025)

Curved Boolean Logic: A Contextual Generalization of Propositional Logic with Algorithmic Consequences
by: von Liechtenstein, Maximilian R. P.
Published: (2025)