3 papers
cs.CC2026
The Complexity of Sparse Win-Lose Bimatrix Games
Eleni Batziou, John Fearnley, Abheek Ghosh +1
We prove that computing an -approximate Nash equilibrium of a win-lose bimatrix game with constant sparsity is PPAD-hard for inverse-polynomial . Our result holds for 3-spa…
cs.GT2025
Contest Design with Threshold Objectives
Edith Elkind, Abheek Ghosh, Paul W. Goldberg
We study contests where the designer's objective is an extension of the widely studied objective of maximizing the total output: The designer gets zero marginal utility from a play…
cs.GT2024
Continuous-Time Best-Response and Related Dynamics in Tullock Contests with Convex Costs
Edith Elkind, Abheek Ghosh, Paul W. Goldberg
Tullock contests model real-life scenarios that range from competition among proof-of-work blockchain miners to rent-seeking and lobbying activities. We show that continuous-time b…