2 citations · 4 across the 8 of their papers we have counts for
9 papers
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-spars…
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…
Best-Response Dynamics in Tullock Contests with Convex Costs
Abheek Ghosh
We study the convergence of best-response dynamics in Tullock contests with convex cost functions (these games always have a unique pure-strategy Nash equilibrium). We show that be…
Best-Response Dynamics in Lottery Contests
Abheek Ghosh, Paul W. Goldberg
We study the convergence of best-response dynamics in lottery contests. We show that best-response dynamics rapidly converges to the (unique) equilibrium for homogeneous agents but…
Indexability is Not Enough for Whittle: Improved, Near-Optimal Algorithms for Restless Bandits
Abheek Ghosh, Dheeraj Nagaraj, Manish Jain +1
We study the problem of planning restless multi-armed bandits (RMABs) with multiple actions. This is a popular model for multi-agent systems with applications like multi-channel co…
Simultaneous Contests with Equal Sharing Allocation of Prizes: Computational Complexity and Price of Anarchy
Edith Elkind, Abheek Ghosh, Paul W. Goldberg
We study a general scenario of simultaneous contests that allocate prizes based on equal sharing: each contest awards its prize to all players who satisfy some contest-specific cri…
Contests to Incentivize a Target Group
Edith Elkind, Abheek Ghosh, Paul Goldberg
We study how to incentivize agents in a target group to produce a higher output in the context of incomplete information, by means of rank-order allocation contests. We describe a…
Complexity of Deliberative Coalition Formation
Edith Elkind, Abheek Ghosh, Paul Goldberg
Elkind et al. (AAAI, 2021) introduced a model for deliberative coalition formation, where a community wishes to identify a strongly supported proposal from a space of alternatives,…
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…