Paul W. Goldberg

ORCID

Publication Activity (10 Years)

Years Active: 1993-2024
Publications (10 Years): 71

Top Venues

Publications

John Fearnley, Paul W. Goldberg, Alexandros Hollender, Rahul Savani
The Complexity of Computing KKT Solutions of Quadratic Programs. STOC (2024)
Edith Elkind, Abheek Ghosh, Paul W. Goldberg
Continuous-Time Best-Response and Related Dynamics in Tullock Contests with Convex Costs. CoRR (2024)
Emanuel Tewolde, Brian Hu Zhang, Caspar Oesterheld, Manolis Zampetakis, Tuomas Sandholm, Paul W. Goldberg, Vincent Conitzer
Imperfect-Recall Games: Equilibrium Concepts and Their Complexity. CoRR (2024)
Paul W. Goldberg, Kasper Høgh, Alexandros Hollender
The Frontier of Intractability for EFX with Two Agents. SAGT (2023)
Paul W. Goldberg, Matthew J. Katzman
PPAD-complete approximate pure Nash equilibria in Lipschitz games. Theor. Comput. Sci. 980 (2023)
Simon Finster, Paul W. Goldberg, Edwin Lock
Substitutes markets with budget constraints: solving for competitive and optimal prices. CoRR (2023)
Abheek Ghosh, Paul W. Goldberg
Best-Response Dynamics in Lottery Contests. CoRR (2023)
John Fearnley, Paul W. Goldberg, Alexandros Hollender, Rahul Savani
The Complexity of Computing KKT Solutions of Quadratic Programs. CoRR (2023)
Abheek Ghosh, Paul W. Goldberg
Best-Response Dynamics in Lottery Contests. EC (2023)
Emanuel Tewolde, Caspar Oesterheld, Vincent Conitzer, Paul W. Goldberg
The Computational Complexity of Single-Player Imperfect-Recall Games. CoRR (2023)
Emanuel Tewolde, Caspar Oesterheld, Vincent Conitzer, Paul W. Goldberg
The Computational Complexity of Single-Player Imperfect-Recall Games. IJCAI (2023)
Paul W. Goldberg, Matthew J. Katzman
Lower bounds for the query complexity of equilibria in Lipschitz games. Theor. Comput. Sci. 962 (2023)
Paul W. Goldberg, Kasper Høgh, Alexandros Hollender
The Frontier of Intractability for EFX with Two Agents. CoRR (2023)
Paul W. Goldberg, Matthew J. Katzman
PPAD-Complete Pure Approximate Nash Equilibria in Lipschitz Games. SAGT (2022)
Edith Elkind, Abheek Ghosh, Paul W. Goldberg
Contests to Incentivize a Target Group. IJCAI (2022)
Paul W. Goldberg, Matthew J. Katzman
PPAD-Complete Pure Approximate Nash Equilibria in Lipschitz Games. CoRR (2022)
Paul W. Goldberg, Jiawei Li
Consensus Division in an Arbitrary Ratio. CoRR (2022)
Edwin Lock, Paul W. Goldberg, Francisco J. Marmolejo Cossío
Learning Strong Substitutes Demand via Queries. ACM Trans. Economics and Comput. 10 (2) (2022)
Edith Elkind, Abheek Ghosh, Paul W. Goldberg
Simultaneous Contests with Equal Sharing Allocation of Prizes: Computational Complexity and Price of Anarchy. CoRR (2022)
Paul W. Goldberg, Alexandros Hollender, Ayumi Igarashi, Pasin Manurangsi, Warut Suksompong
Consensus Halving for Sets of Items. Math. Oper. Res. 47 (4) (2022)
Edith Elkind, Abheek Ghosh, Paul W. Goldberg
Simultaneous Contests with Equal Sharing Allocation of Prizes: Computational Complexity and Price of Anarchy. SAGT (2022)
Paul W. Goldberg, Alexandros Hollender
The Hairy Ball problem is PPAD-complete. J. Comput. Syst. Sci. 122 (2021)
Paul W. Goldberg, Matthew J. Katzman
Lower Bounds for the Query Complexity of Equilibria in Lipschitz Games. SAGT (2021)
Paul W. Goldberg, Ioana Iaru
Equivalence of Models of Cake-Cutting Protocols. CoRR (2021)
Paul W. Goldberg, Matthew J. Katzman
Lower Bounds for the Query Complexity of Equilibria in Lipschitz Games. CoRR (2021)
Paul W. Goldberg, Francisco J. Marmolejo Cossío
Learning Convex Partitions and Computing Game-theoretic Equilibria from Best-response Queries. ACM Trans. Economics and Comput. 9 (1) (2021)
Edith Elkind, Abheek Ghosh, Paul W. Goldberg
Contest Design with Threshold Objectives. WINE (2021)
John Fearnley, Paul W. Goldberg, Alexandros Hollender, Rahul Savani
The complexity of gradient descent: CLS = PPAD ∩ PLS. STOC (2021)
Paul W. Goldberg, Alexandros Hollender, Warut Suksompong
Contiguous Cake Cutting: Hardness Results and Approximation Algorithms. AAAI (2020)
Paul W. Goldberg, Edwin Lock, Francisco J. Marmolejo Cossío
Learning Strong Substitutes Demand via Queries. WINE (2020)
Paul W. Goldberg, Alexandros Hollender, Ayumi Igarashi, Pasin Manurangsi, Warut Suksompong
Consensus Halving for Sets of Items. CoRR (2020)
Paul W. Goldberg, Alexandros Hollender, Ayumi Igarashi, Pasin Manurangsi, Warut Suksompong
Consensus Halving for Sets of Items. WINE (2020)
Paul W. Goldberg, Edwin Lock, Francisco J. Marmolejo Cossío
Learning Strong Substitutes Demand via Queries. CoRR (2020)
John Fearnley, Paul W. Goldberg, Alexandros Hollender, Rahul Savani
The Complexity of Gradient Descent: CLS = PPAD ∩ PLS. CoRR (2020)
Riccardo Colini-Baldeschi, Paul W. Goldberg, Bart de Keijzer, Stefano Leonardi, Tim Roughgarden, Stefano Turchetta
Approximately Efficient Two-Sided Combinatorial Auctions. ACM Trans. Economics and Comput. 8 (1) (2020)
Aris Filos-Ratsikas, Paul W. Goldberg
The complexity of splitting necklaces and bisecting ham sandwiches. STOC (2019)
Paul W. Goldberg, Alexandros Hollender, Warut Suksompong
Contiguous Cake Cutting: Hardness Results and Approximation Algorithms. CoRR (2019)
Paul W. Goldberg, Alexandros Hollender
The Hairy Ball Problem is PPAD-Complete. ICALP (2019)
Paul W. Goldberg, Alexandros Hollender
The Hairy Ball Problem is PPAD-Complete. CoRR (2019)
Elizabeth Baldwin, Paul W. Goldberg, Paul Klemperer, Edwin Lock
Solving Strong-Substitutes Product-Mix Auctions. CoRR (2019)
Paul W. Goldberg, Francisco J. Marmolejo Cossío, Zhiwei Steven Wu
Logarithmic Query Complexity for Approximate Nash Computation in Large Games. Theory Comput. Syst. 63 (1) (2019)
Matthias Gerstgrasser, Paul W. Goldberg, Bart de Keijzer, Philip Lazos, Alexander Skopalik
Multi-Unit Bilateral Trade. AAAI (2019)
Paul W. Goldberg, Christos H. Papadimitriou
Towards a Unified Complexity Theory of Total Functions. ITCS (2018)
Paul W. Goldberg, Francisco J. Marmolejo Cossío
Learning Convex Partitions and Computing Game-theoretic Equilibria from Best Response Queries. CoRR (2018)
Aris Filos-Ratsikas, Paul W. Goldberg
The Complexity of Splitting Necklaces and Bisecting Ham Sandwiches. CoRR (2018)
Paul W. Goldberg, Francisco J. Marmolejo Cossío
Learning Convex Partitions and Computing Game-Theoretic Equilibria from Best Response Queries. WINE (2018)
Aris Filos-Ratsikas, Søren Kristoffer Stiil Frederiksen, Paul W. Goldberg, Jie Zhang
Hardness Results for Consensus-Halving. MFCS (2018)
Matthias Gerstgrasser, Paul W. Goldberg, Bart de Keijzer, Philip Lazos, Alexander Skopalik
Multi-unit Bilateral Trade. CoRR (2018)
Paul W. Goldberg, Christos H. Papadimitriou
Towards a unified complexity theory of total functions. J. Comput. Syst. Sci. 94 (2018)
Aris Filos-Ratsikas, Paul W. Goldberg
Consensus halving is PPA-complete. STOC (2018)
Riccardo Colini-Baldeschi, Paul W. Goldberg, Bart de Keijzer, Stefano Leonardi, Stefano Turchetta
Fixed Price Approximability of the Optimal Gain from Trade. WINE (2017)
Riccardo Colini-Baldeschi, Paul W. Goldberg, Bart de Keijzer, Stefano Leonardi, Stefano Turchetta
Fixed Price Approximability of the Optimal Gain From Trade. CoRR (2017)
Paul W. Goldberg, Stefano Turchetta
Query complexity of approximate equilibria in anonymous games. J. Comput. Syst. Sci. 90 (2017)
Paul W. Goldberg, Yishay Mansour, Paul Dütting
Game Theory Meets Computational Learning Theory (Dagstuhl Seminar 17251). Dagstuhl Reports 7 (6) (2017)
Xiaotie Deng, Paul W. Goldberg, Yang Sun, Bo Tang, Jinshan Zhang
Pricing ad slots with consecutive multi-unit demand. Auton. Agents Multi Agent Syst. 31 (3) (2017)
Paul W. Goldberg, Christos H. Papadimitriou
TFNP: An Update. CIAC (2017)
Riccardo Colini-Baldeschi, Paul W. Goldberg, Bart de Keijzer, Stefano Leonardi, Tim Roughgarden, Stefano Turchetta
Approximately Efficient Two-Sided Combinatorial Auctions. EC (2017)
Paul W. Goldberg, Christos H. Papadimitriou
Towards a Unified Complexity Theory of Total Functions. Electron. Colloquium Comput. Complex. 24 (2017)
Aris Filos-Ratsikas, Paul W. Goldberg
Consensus Halving is PPA-Complete. CoRR (2017)
Paul W. Goldberg, Francisco J. Marmolejo Cossío, Zhiwei Steven Wu
Logarithmic Query Complexity for Approximate Nash Computation in Large Games. CoRR (2016)
John Fearnley, Paul W. Goldberg, Rahul Savani, Troels Bjerre Sørensen
Approximate Well-supported Nash Equilibria Below Two-thirds. Algorithmica 76 (2) (2016)
Paul W. Goldberg, Francisco J. Marmolejo Cossío, Zhiwei Steven Wu
Logarithmic Query Complexity for Approximate Nash Computation in Large Games. SAGT (2016)
George Christodoulou, Aris Filos-Ratsikas, Søren Kristoffer Stiil Frederiksen, Paul W. Goldberg, Jie Zhang, Jinshan Zhang
Social Welfare in One-Sided Matching Mechanisms: (Extended Abstract). AAMAS (2016)
Paul W. Goldberg, Aaron Roth
Bounds for the Query Complexity of Approximate Equilibria. ACM Trans. Economics and Comput. 4 (4) (2016)
Ning Chen, Xiaotie Deng, Paul W. Goldberg, Jinshan Zhang
On revenue maximization with sharp multi-unit demands. J. Comb. Optim. 31 (3) (2016)
Riccardo Colini-Baldeschi, Paul W. Goldberg, Bart de Keijzer, Stefano Leonardi, Tim Roughgarden, Stefano Turchetta
Approximately Efficient Two-Sided Combinatorial Auctions. CoRR (2016)
George Christodoulou, Aris Filos-Ratsikas, Søren Kristoffer Stiil Frederiksen, Paul W. Goldberg, Jie Zhang, Jinshan Zhang
Social Welfare in One-Sided Matching Mechanisms. AAMAS Workshops (Selected Papers) (2016)
Matthias Gerstgrasser, Paul W. Goldberg, Elias Koutsoupias
Revenue Maximization for Market Intermediation with Correlated Priors. SAGT (2016)
Diodato Ferraioli, Paul W. Goldberg, Carmine Ventre
Decentralized dynamics for finite opinion games. Theor. Comput. Sci. 648 (2016)
Xiaotie Deng, Paul W. Goldberg, Bo Tang, Jinshan Zhang
Multi-Unit Bayesian Auction with Demand or Budget Constraints. Comput. Intell. 32 (3) (2016)
Aris Filos-Ratsikas, Søren Kristoffer Stiil Frederiksen, Paul W. Goldberg, Jie Zhang
Hardness Results for Consensus-Halving. CoRR (2016)
George Christodoulou, Aris Filos-Ratsikas, Søren Kristoffer Stiil Frederiksen, Paul W. Goldberg, Jie Zhang, Jinshan Zhang
Welfare Ratios in One-Sided Matching Mechanisms. CoRR (2015)
Paul W. Goldberg
The Complexity of the Path-following Solutions of Two-dimensional Sperner/Brouwer Functions. CoRR (2015)
Paul W. Goldberg
Algorithmic Game Theory (Tutorial). STACS (2015)
John Fearnley, Martin Gairing, Paul W. Goldberg, Rahul Savani
Learning equilibria of games via payoff queries. J. Mach. Learn. Res. 16 (2015)
Paul W. Goldberg, Bo Tang
Auction Design with a Revenue Target. SAGT (2015)
Paul W. Goldberg, Stefano Turchetta
Query Complexity of Approximate Equilibria in Anonymous Games. WINE (2015)
Paul W. Goldberg, Stefano Turchetta
Query Complexity of Approximate Equilibria in Anonymous Games. CoRR (2014)
Paul W. Goldberg, Aaron Roth
Bounds for the query complexity of approximate equilibria. EC (2014)
Paul W. Goldberg, Arnoud Pastink
On the communication complexity of approximate Nash equilibria. Games Econ. Behav. 85 (2014)
Xiaotie Deng, Paul W. Goldberg, Bo Tang, Jinshan Zhang
Revenue maximization in a Bayesian double auction market. Theor. Comput. Sci. 539 (2014)
Diodato Ferraioli, Paul W. Goldberg, Carmine Ventre
Decentralized Dynamics for Finite Opinion Games. CoRR (2013)
Paul W. Goldberg, Antony McCabe
Shortest Paths with Bundles and Non-additive Weights Is Hard. CIAC (2013)
Paul W. Goldberg, Rahul Savani, Troels Bjerre Sørensen, Carmine Ventre
On the approximation performance of fictitious play in finite games. Int. J. Game Theory 42 (4) (2013)
John Fearnley, Martin Gairing, Paul W. Goldberg, Rahul Savani
Learning Equilibria of Games via Payoff Queries CoRR (2013)
Xiaotie Deng, Paul W. Goldberg, Yang Sun, Bo Tang, Jinshan Zhang
Pricing Ad Slots with Consecutive Multi-unit Demand. CoRR (2013)
Leslie Ann Goldberg, Paul W. Goldberg, Piotr Krysta, Carmine Ventre
Ranking Games that have Competitiveness-based Strategies CoRR (2013)
Leslie Ann Goldberg, Paul W. Goldberg, Piotr Krysta, Carmine Ventre
Ranking games that have competitiveness-based strategies. Theor. Comput. Sci. 476 (2013)
John Fearnley, Martin Gairing, Paul W. Goldberg, Rahul Savani
Learning equilibria of games via payoff queries. EC (2013)
Paul W. Goldberg, Arnoud Pastink
On the Communication Complexity of Approximate Nash Equilibria CoRR (2013)
Xiaotie Deng, Paul W. Goldberg, Yang Sun, Bo Tang, Jinshan Zhang
Pricing Ad Slots with Consecutive Multi-unit Demand. SAGT (2013)
Paul W. Goldberg, Aaron Roth
Bounds for the Query Complexity of Approximate Equilibria. Electron. Colloquium Comput. Complex. 20 (2013)
Paul W. Goldberg, Carmine Ventre
Using lotteries to approximate the optimal revenue. AAMAS (2013)
Paul W. Goldberg, Christos H. Papadimitriou, Rahul Savani
The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions. ACM Trans. Economics and Comput. 1 (2) (2013)
John Fearnley, Paul W. Goldberg, Rahul Savani, Troels Bjerre Sørensen
Approximate Well-Supported Nash Equilibria Below Two-Thirds. SAGT (2012)
Paul W. Goldberg, Antony McCabe
Commodity Auctions and Frugality Ratios. SAGT (2012)
John Fearnley, Paul W. Goldberg, Rahul Savani, Troels Bjerre Sørensen
Approximate Well-supported Nash Equilibria below Two-thirds CoRR (2012)
Ning Chen, Xiaotie Deng, Paul W. Goldberg, Jinshan Zhang
On Revenue Maximization with Sharp Multi-Unit Demands CoRR (2012)
Paul W. Goldberg, Arnoud Pastink
On the Communication Complexity of Approximate Nash Equilibria. SAGT (2012)
Diodato Ferraioli, Paul W. Goldberg, Carmine Ventre
Decentralized Dynamics for Finite Opinion Games. SAGT (2012)

Paul W. Goldberg.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Paul W. Goldberg