16 citations · 22 across the 10 of their papers we have counts for
13 papers
Binary -Center under a Hard Threshold with Applications to Delegated Voting
Jakub Dargaj, Aris Filos-Ratsikas, Paul W. Goldberg
We study the problem of covering binary strings of the same length, possibly with missing entries, by a fixed number of center strings, such that each input string is within a give…
Equilibria of Round-Robin: Computational Hardness and Fairness for Few Subadditive Agents
Paul W. Goldberg, Alexandros Hollender, Giannis Tyrovolas
The round-robin procedure is a simple and well-studied fair division mechanism where agents pick goods in turns. Motivated by draft mechanisms in sports leagues, we investigate str…
The Computational Complexity of Single-Player Imperfect-Recall Games
Emanuel Tewolde, Caspar Oesterheld, Vincent Conitzer +1
We study single-player extensive-form games with imperfect recall, such as the Sleeping Beauty problem or the Absentminded Driver game. For such games, two natural equilibrium conc…
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…
The Frontier of Intractability for EFX with Two Agents
Paul W. Goldberg, Kasper Høgh, Alexandros Hollender
We consider the problem of sharing a set of indivisible goods among agents in a fair manner, namely such that the allocation is envy-free up to any good (EFX). We focus on the prob…
PPAD-Complete Pure Approximate Nash Equilibria in Lipschitz Games
Paul W. Goldberg, Matthew J. Katzman
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…
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…
Consensus Division in an Arbitrary Ratio
Paul W. Goldberg, Jiawei Li
We consider the problem of partitioning a line segment into two subsets, so that finite measures all have the same ratio of values for the subsets. Letting denote t…
Contiguous Cake Cutting: Hardness Results and Approximation Algorithms
Paul W. Goldberg, Alexandros Hollender, Warut Suksompong
We study the fair allocation of a cake, which serves as a metaphor for a divisible resource, under the requirement that each agent should receive a contiguous piece of the cake. Wh…
The Hairy Ball Problem is PPAD-Complete
Paul W. Goldberg, Alexandros Hollender
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) c…
Named Entity Recognition in Electronic Health Records Using Transfer Learning Bootstrapped Neural Networks
Luka Gligic, Andrey Kormilitzin, Paul Goldberg +1
Neural networks (NNs) have become the state of the art in many machine learning applications, especially in image and sound processing [1]. The same, although to a lesser extent [2…
The Complexity of Splitting Necklaces and Bisecting Ham Sandwiches
Aris Filos-Ratsikas, Paul W. Goldberg
We resolve the computational complexity of two problems known as NECKLACE-SPLITTING and DISCRETE HAM SANDWICH, showing that they are PPA-complete. For NECKLACE SPLITTING, this resu…
Approximately Efficient Two-Sided Combinatorial Auctions
Riccardo Colini-Baldeschi, Paul Goldberg, Bart de Keijzer +3
Mechanism design for one-sided markets has been investigated for several decades in economics and in computer science. More recently, there has been an increased attention on mecha…