BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Paul W. Goldberg

Paul W. Goldberg appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Computer Science and Game TheoryComputational ComplexityData Structures and AlgorithmsArtificial Intelligenceecon.THMachine Learning

Catalog footprint

What is connected

16works
6topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

16 published item(s)

preprint2026arXiv

Efficient Ensemble Selection from Binary and Pairwise Feedback

Organizations increasingly deploy multiple AI systems across task domains, but selecting a small, high-performing ensemble can require costly model calls, benchmark runs, and human evaluation. We study this selection problem as a distributional variant of multiwinner voting: tasks are drawn from an unknown domain distribution, each task induces feedback over candidate experts, and a committee's value on a task is determined by its best-performing member. We analyze both binary feedback, for tasks with correct/incorrect outcomes, and pairwise feedback, for tasks where candidate outputs are compared by preference. In the binary setting, the induced objective is coverage. We give exhaustive-elicitation baselines and matching worst-case query lower bounds, and we design a failure-conditioned greedy algorithm that preserves the standard $(1-1/e)$ guarantee while obtaining instance-dependent query savings. In the pairwise setting, we study $θ$-winning committees. We show that full-information optimization admits a PTAS but no EPTAS under Gap-ETH, and that the objective is monotone but not submodular. This motivates a weighted ordinal coverage relaxation, which is submodular and supports a failure-conditioned greedy oracle under pairwise feedback. We then convert this oracle back into $θ$-type guarantees through finite-family auditing or a minimax wrapper. We also provide small-scale LLM experiments illustrating the predicted query savings and the role of complementarity in committee selection.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

PPAD-Complete Pure Approximate Nash Equilibria in Lipschitz Games

Lipschitz games, in which there is a limit $λ$ (the Lipschitz value of the game) on how much a player's payoffs may change when some other player deviates, were introduced about 10 years ago by Azrieli and Shmaya. They showed via the probabilistic method that $n$-player Lipschitz games with $m$ strategies per player have pure $ε$-approximate Nash equilibria, for $ε\geqλ\sqrt{8n\log(2mn)}$. Here we provide the first hardness result for the corresponding computational problem, showing that even for a simple class of Lipschitz games (Lipschitz polymatrix games), finding pure $ε$-approximate equilibria is PPAD-complete, for suitable pairs of values $(ε(n), λ(n))$. Novel features of this result include both the proof of PPAD hardness (in which we apply a population game reduction from unrestricted polymatrix games) and the proof of containment in PPAD (by derandomizing the selection of a pure equilibrium from a mixed one). In fact, our approach implies containment in PPAD for any class of Lipschitz games where payoffs from mixed-strategy profiles can be deterministically computed.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Simultaneous Contests with Equal Sharing Allocation of Prizes: Computational Complexity and Price of Anarchy

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 criterion, and the value of this prize to a winner decreases as the number of winners increases. The players produce outputs for a set of activities, and the winning criteria of the contests are based on these outputs. We consider two variations of the model: (i) players have costs for producing outputs; (ii) players do not have costs but have generalized budget constraints. We observe that these games are exact potential games and hence always have a pure-strategy Nash equilibrium. The price of anarchy is $2$ for the budget model, but can be unbounded for the cost model. Our main results are for the computational complexity of these games. We prove that for general versions of the model exactly or approximately computing a best response is NP-hard. For natural restricted versions where best response is easy to compute, we show that finding a pure-strategy Nash equilibrium is PLS-complete, and finding a mixed-strategy Nash equilibrium is (PPAD$\cap$PLS)-complete. On the other hand, an approximate pure-strategy Nash equilibrium can be found in pseudo-polynomial time. These games are a strict but natural subclass of explicit congestion games, but they still have the same equilibrium hardness results.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

The Hairy Ball Problem is PPAD-Complete

The Hairy Ball Theorem states that every continuous tangent vector field on an even-dimensional sphere must have a zero. We prove that the associated computational problem of (a) computing an approximate zero is PPAD-complete, and (b) computing an exact zero is FIXP-hard. We also consider the Hairy Ball Theorem on toroidal instead of spherical domains and show that the approximate problem remains PPAD-complete. On a conceptual level, our PPAD-membership results are particularly interesting, because they heavily rely on the investigation of multiple-source variants of END-OF-LINE, the canonical PPAD-complete problem. Our results on these new END-OF-LINE variants are of independent interest and provide new tools for showing membership in PPAD. In particular, we use them to provide the first full proof of PPAD-completeness for the IMBALANCE problem defined by Beame et al. in 1998.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Learning Strong Substitutes Demand via Queries

This paper addresses the computational challenges of learning strong substitutes demand when given access to a demand (or valuation) oracle. Strong substitutes demand generalises the well-studied gross substitutes demand to a multi-unit setting. Recent work by Baldwin and Klemperer shows that any such demand can be expressed in a natural way as a finite list of weighted bid vectors. A simplified version of this bidding language has been used by the Bank of England. Assuming access to a demand oracle, we provide an algorithm that computes the unique list of weighted bid vectors corresponding to a bidder's demand preferences. In the special case where their demand can be expressed using positive bids only, we have an efficient algorithm that learns this list in linear time. We also show super-polynomial lower bounds on the query complexity of computing the list of bids in the general case where bids may be positive and negative. Our algorithms constitute the first systematic approach for bidders to construct a bid list corresponding to non-trivial demand, allowing them to participate in `product-mix' auctions.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Logarithmic Query Complexity for Approximate Nash Computation in Large Games

We investigate the problem of equilibrium computation for "large" $n$-player games. Large games have a Lipschitz-type property that no single player's utility is greatly affected by any other individual player's actions. In this paper, we mostly focus on the case where any change of strategy by a player causes other players' payoffs to change by at most $\frac{1}{n}$. We study algorithms having query access to the game's payoff function, aiming to find $ε$-Nash equilibria. We seek algorithms that obtain $ε$ as small as possible, in time polynomial in $n$. Our main result is a randomised algorithm that achieves $ε$ approaching $\frac{1}{8}$ for 2-strategy games in a {\em completely uncoupled} setting, where each player observes her own payoff to a query, and adjusts her behaviour independently of other players' payoffs/actions. $O(\log n)$ rounds/queries are required. We also show how to obtain a slight improvement over $\frac{1}{8}$, by introducing a small amount of communication between the players. Finally, we give extension of our results to large games with more than two strategies per player, and alternative largeness parameters.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Query Complexity of Approximate Equilibria in Anonymous Games

We study the computation of equilibria of anonymous games, via algorithms that may proceed via a sequence of adaptive queries to the game's payoff function, assumed to be unknown initially. The general topic we consider is \emph{query complexity}, that is, how many queries are necessary or sufficient to compute an exact or approximate Nash equilibrium. We show that exact equilibria cannot be found via query-efficient algorithms. We also give an example of a 2-strategy, 3-player anonymous game that does not have any exact Nash equilibrium in rational numbers. However, more positive query-complexity bounds are attainable if either further symmetries of the utility functions are assumed or we focus on approximate equilibria. We investigate four sub-classes of anonymous games previously considered by \cite{bfh09, dp14}. Our main result is a new randomized query-efficient algorithm that finds a $O(n^{-1/4})$-approximate Nash equilibrium querying $\tilde{O}(n^{3/2})$ payoffs and runs in time $\tilde{O}(n^{3/2})$. This improves on the running time of pre-existing algorithms for approximate equilibria of anonymous games, and is the first one to obtain an inverse polynomial approximation in poly-time. We also show how this can be utilized as an efficient polynomial-time approximation scheme (PTAS). Furthermore, we prove that $Ω(n \log{n})$ payoffs must be queried in order to find any $ε$-well-supported Nash equilibrium, even by randomized algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Social Welfare in One-Sided Matching Mechanisms

We study the Price of Anarchy of mechanisms for the well-known problem of one-sided matching, or house allocation, with respect to the social welfare objective. We consider both ordinal mechanisms, where agents submit preference lists over the items, and cardinal mechanisms, where agents may submit numerical values for the items being allocated. We present a general lower bound of $Ω(\sqrt{n})$ on the Price of Anarchy, which applies to all mechanisms. We show that two well-known mechanisms, Probabilistic Serial, and Random Priority, achieve a matching upper bound. We extend our lower bound to the Price of Stability of a large class of mechanisms that satisfy a common proportionality property, and show stronger bounds on the Price of Anarchy of all deterministic mechanisms.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

The Complexity of the Path-following Solutions of Two-dimensional Sperner/Brouwer Functions

There are a number of results saying that for certain "path-following" algorithms that solve PPAD-complete problems, the solution obtained by the algorithm is PSPACE-complete to compute. We conjecture that these results are special cases of a much more general principle, that all such algorithms compute PSPACE-complete solutions. Such a general result might shed new light on the complexity class PPAD. In this paper we present a new PSPACE-completeness result for an interesting challenge instance for this conjecture. Chen and Deng~\cite{CD} showed that it is PPAD-complete to find a trichromatic triangle in a concisely-represented Sperner triangulation. The proof of Sperner's lemma --- that such a solution always exists --- identifies one solution in particular, that is found via a natural "path-following" approach. Here we show that it is PSPACE-complete to compute this specific solution, together with a similar result for the computation of the path-following solution of two-dimensional discrete Brouwer functions.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Approximate Well-supported Nash Equilibria below Two-thirds

In an epsilon-Nash equilibrium, a player can gain at most epsilon by changing his behaviour. Recent work has addressed the question of how best to compute epsilon-Nash equilibria, and for what values of epsilon a polynomial-time algorithm exists. An epsilon-well-supported Nash equilibrium (epsilon-WSNE) has the additional requirement that any strategy that is used with non-zero probability by a player must have payoff at most epsilon less than the best response. A recent algorithm of Kontogiannis and Spirakis shows how to compute a 2/3-WSNE in polynomial time, for bimatrix games. Here we introduce a new technique that leads to an improvement to the worst-case approximation guarantee.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Decentralized Dynamics for Finite Opinion Games

Game theory studies situations in which strategic players can modify the state of a given system, due to the absence of a central authority. Solution concepts, such as Nash equilibrium, are defined to predict the outcome of such situations. In multi-player settings, it has been pointed out that to be realistic, a solution concept should be obtainable via processes that are decentralized and reasonably simple. Accordingly we look at the computation of solution concepts by means of decentralized dynamics. These are algorithms in which players move in turns to improve their own utility and the hope is that the system reaches an "equilibrium" quickly. We study these dynamics for the class of opinion games, recently introduced by Bindel et al. [Bindel et al., FOCS2011]. These are games, important in economics and sociology, that model the formation of an opinion in a social network. We study best-response dynamics and show upper and lower bounds on the convergence to Nash equilibria. We also study a noisy version of best-response dynamics, called logit dynamics, and prove a host of results about its convergence rate as the noise in the system varies. To get these results, we use a variety of techniques developed to bound the mixing time of Markov chains, including coupling, spectral characterizations and bottleneck ratio.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Ranking Games that have Competitiveness-based Strategies

An extensive literature in economics and social science addresses contests, in which players compete to outperform each other on some measurable criterion, often referred to as a player's score, or output. Players incur costs that are an increasing function of score, but receive prizes for obtaining higher score than their competitors. In this paper we study finite games that are discretized contests, and the problems of computing exact and approximate Nash equilibria. Our motivation is the worst-case hardness of Nash equilibrium computation, and the resulting interest in important classes of games that admit polynomial-time algorithms. For games that have a tie-breaking rule for players' scores, we present a polynomial-time algorithm for computing an exact equilibrium in the 2-player case, and for multiple players, a characterization of Nash equilibria that shows an interesting parallel between these games and unrestricted 2-player games in normal form. When ties are allowed, via a reduction from these games to a subclass of anonymous games, we give approximation schemes for two special cases: constant-sized set of strategies, and constant number of players.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Using Lotteries to Approximate the Optimal Revenue

There has been much recent work on the revenue-raising properties of truthful mechanisms for selling goods to selfish bidders. Typically the revenue of a mechanism is compared against a benchmark (such as, the maximum revenue obtainable by an omniscient seller selling at a fixed price to at least two customers), with a view to understanding how much lower the mechanism's revenue is than the benchmark, in the worst case. We study this issue in the context of {\em lotteries}, where the seller may sell a probability of winning an item. We are interested in two general issues. Firstly, we aim at using the true optimum revenue as benchmark for our auctions. Secondly, we study the extent to which the expressive power resulting from lotteries, helps to improve the worst-case ratio. We study this in the well-known context of {\em digital goods}, where the production cost is zero. We show that in this scenario, collusion-resistant lotteries (these are lotteries for which no coalition of bidders exchanging side payments has an advantage in lying) are as powerful as truthful ones.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

A Survey of PPAD-Completeness for Computing Nash Equilibria

PPAD refers to a class of computational problems for which solutions are guaranteed to exist due to a specific combinatorial principle. The most well-known such problem is that of computing a Nash equilibrium of a game. Other examples include the search for market equilibria, and envy-free allocations in the context of cake-cutting. A problem is said to be complete for PPAD if it belongs to PPAD and can be shown to constitute one of the hardest computational challenges within that class. In this paper, I give a relatively informal overview of the proofs used in the PPAD-completeness results. The focus is on the mixed Nash equilibria guaranteed to exist by Nash's theorem. I also give an overview of some recent work that uses these ideas to show PSPACE-completeness for the computation of specific equilibria found by homotopy methods. I give a brief introduction to related problems of searching for market equilibria.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On the Approximation Performance of Fictitious Play in Finite Games

We study the performance of Fictitious Play, when used as a heuristic for finding an approximate Nash equilibrium of a 2-player game. We exhibit a class of 2-player games having payoffs in the range [0,1] that show that Fictitious Play fails to find a solution having an additive approximation guarantee significantly better than 1/2. Our construction shows that for n times n games, in the worst case both players may perpetually have mixed strategies whose payoffs fall short of the best response by an additive quantity 1/2 - O(1/n^(1-delta)) for arbitrarily small delta. We also show an essentially matching upper bound of 1/2 - O(1/n).

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions

We show that the widely used homotopy method for solving fixpoint problems, as well as the Harsanyi-Selten equilibrium selection process for games, are PSPACE-complete to implement. Extending our result for the Harsanyi-Selten process, we show that several other homotopy-based algorithms for finding equilibria of games are also PSPACE-complete to implement. A further application of our techniques yields the result that it is PSPACE-complete to compute any of the equilibria that could be found via the classical Lemke-Howson algorithm, a complexity-theoretic strengthening of the result in [Savani and von Stengel]. These results show that our techniques can be widely applied and suggest that the PSPACE-completeness of implementing homotopy methods is a general principle.

0 citations0 reviewsNo code linkedOpen access