{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreig2hbhaepkfqptbiyalkmmicvbdbev3d3ebg3hx56o3t4rbex5wdm",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mfj454dhyko2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2602.18380v1",
  "publishedAt": "2026-02-23T01:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Eleni Batziou",
    "John Fearnley",
    "Abheek Ghosh",
    "Rahul Savani"
  ],
  "textContent": "**Authors:** Eleni Batziou, John Fearnley, Abheek Ghosh, Rahul Savani\n\nWe 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-sparse games, which is tight given that 2-sparse win-lose bimatrix games can be solved in polynomial time.",
  "title": "The Complexity of Sparse Win-Lose Bimatrix Games"
}