Research Papers and Publications

Paul Goldberg

Return to main page

Links labelled “DOI” point to the official web page for the paper.

The unifying theme of my research is the rigorous mathematical analysis of algorithms, and their provable performance guarantees. Also the study of computational challenges for which we are interested in designing algorithms having proven performance guarantees. Until around the year 2001 the main emphasis was on computational learning theory, subsequently the emphasis has been computational game theory (and AI in general), also “total search problems” (details below). Most of my work in game theory splits into 3 lines:

• Equilibrium computation, which in turn has in turn attracted my interest in more abstract computational complexity questions. More details follow below.
• Market intermediation, how a middleman or intermediary can facilitate trade
• Search for game-theoretic equilibria using query protocols, where an algorithm can query individual payoffs of a game, or best-response behaviour of the players (see WINE 2018 paper with F Marmolejo-Cossío).

Total search problems: The paper The Complexity of Computing a Nash Equilibrium (more detail below) has given me a strong interest in so-called total search problems, in which the challenge is to compute a solution that is known to exist by virtue of a computationally inefficient existence proof. For example, Nash’s famous theorem guaranteeing the existence of Nash equilibria of games, does not tell us how to efficiently compute Nash equilibria. The paper shows that Nash equilibria are (in the worst case) hard to compute, despite Nash’s theorem guaranteeing their existence. See The World of TFNP by Allyn Jackson, for an easy-to-read introduction to total search problems.

• The Complexity of Computing a Nash Equilibrium (2006,09, co-authored with Constantinos Daskalakis and Christos Papadimitriou) is the best-known paper I have co-authored; it’s not the paper that started my interest in Algorithmic Game Theory, but it affected much of my subsequent work. This paper, showing that computation of Nash equilibrium is complete for the complexity class PPAD, raised questions about what classes of games are “hard” to solve and which are easy, also in what sense can we convince ourselves that “PPAD-complete” indicate hardness. A more general research theme is: TFNP is a class of problems that seem to be hard but are (very) unlikely to be NP-hard, so we want to understand the “complexity landscape” of this interesting region between P and NP. PPAD is just a small part of this picture…
• New paper (STOC ’21 best paper, article in Quanta Magazine, also in Wired): The Complexity of Gradient Descent: CLS=PPAD∩PLS, co-authored with John Fearnley, Alexandros Hollender, and Rahul Savani. Gradient Descent is important and widely used in continuous optimisation. Solutions are guaranteed to exist due to the “PLS principle” and also the “PPAD principle”. We show that the search for GD solutions is as hard as it can possibly be, subject to those guarantees! As the title suggests, we also show that the complexity class CLS is the intersection of PPAD and PLS.
• Recent papers (2018,2019): The Complexity of Splitting Necklaces and Bisecting Ham Sandwiches, showing that two important (and reasonably easy-to-understand) computational problems are complete for the class PPA, whose definition is similar to PPAD, but more is known about the hardness indicated by PPA-completeness. Another contribution to the above-mentioned complexity landscape of TFNP is The Hairy Ball Problem is PPAD-Complete, identifying the complexity of the computational problem associated with the classical “hairy ball theorem” and in the process, showing equivalence of the End-of-line problem (that characterises PPAD) with certain natural variants of it.

Working Papers

John Fearnley, Paul W. Goldberg, Alexandros Hollender, Rahul Savani. The Complexity of Computing KKT Solutions of Quadratic Programs CoRR: ArXiv:2311.13738 (uploaded in November 2023), to appear in STOC’24

Simon Finster, Paul W. Goldberg, and Edwin Lock. Divisible goods markets with budget constraints: a unification of revenue and welfare. presented at CMiD and EARIE. Newer version: Substitutes markets with budget constraints: solving for competitive and optimal prices at WINE’23.

Paul W. Goldberg and Ioana Iaru. Equivalence of Models of Cake-Cutting Protocols. CoRR: ArXiv:2108.03641 (uploaded in August 2021)

Paul W. Goldberg. The Complexity of the Path-following Solutions of Two-dimensional Sperner/Brouwer Functions. CoRR: ArXiv:1506.04882 (uploaded in June 2015)

Paul W. Goldberg and Utku Ünver. Editorial from the New Co-Editors-in-Chief of ACM Transactions on Economics and Computation. ACM TEAC, Vol. 11, Issue 3-4, pp.1–2 (Dec 2023)
DOI: 10.1145/3631669;

Refereed Journal Papers

Elizabeth Baldwin, Paul W. Goldberg, Paul Klemperer, Edwin Lock. Solving Strong-Substitutes Product-Mix Auctions. Mathematics of Operations Research (online, August 2023)
DOI: 10.1287/moor.2019.0248
CoRR: ArXiv:1909.07313 (last uploaded in July 2023). Also here as Nuffield College working paper 2019-W08.

Paul W. Goldberg and Matthew Katzman. PPAD-complete approximate pure Nash equilibria in Lipschitz games. Theoretical Computer Science Vol. 980, pp.1–24 (Nov 2023). link (Special issue for SAGT 2022)
DOI: 10.1016/j.tcs.2023.114218;

Paul W. Goldberg and Matthew Katzman. Lower Bounds for the Query Complexity of Equilibria in Lipschitz Games. Theoretical Computer Science Vol. 962, pp.1–14 (June 2023) open access version (May 2023). (Special issue for SAGT 2021)
DOI: 10.1016/j.tcs.2023.113931;

John Fearnley, Paul W. Goldberg, Alexandros Hollender, and Rahul Savani. The Complexity of Gradient Descent: CLS=PPAD∩PLS. Journal of the ACM, Vol. 70, Issue 1, Article No. 7, pp. 1–74 (Feb. 2023).
DOI: 10.1145/3568163; ACM link;

Edwin Lock, Paul W. Goldberg, and Francisco J. Marmolejo-Cossío. Learning Strong Substitutes Demand via Queries. ACM Transactions on Economics and Computation, Vol. 10, Issue 2, pp 1–22 (June 2022).
DOI: 10.1145/3546604
Earlier versions have the same title but authors in alphabetical order.
Conference version in Procs. of 16th WINE conference, pp. 401–415 (Dec. 2020). DOI: 10.1007/978-3-030-64946-3_28
arxiv preprint ArXiv:2005.01496

Aris Filos-Ratskias and Paul W. Goldberg. The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich. SIAM Journal on Computing, Vol. 52, No. 2, pp. STOC19-200–STOC19-268 (2022).
DOI 10.1137/20M1312678 (Special issue for STOC 2019. The paper also includes results of STOC 2018 paper “Consensus Halving is PPA-Complete”)

Paul W. Goldberg and Francisco J. Marmolejo-Cossío. Learning Convex Partitions and Computing Game-theoretic Equilibria from Best Response Queries. ACM Transactions on Economics and Computation, Vol. 9, No. 1, pp. 3:1–3:36, (2021).
DOI: 10.1145/3434412 (Special issue of TEAC for the 2018 WINE conference, see link/details below for the conference version, also below for link to arxiv version)

Paul W. Goldberg and Alexandros Hollender. The Hairy Ball problem is PPAD-complete. Journal of Computer and System Sciences, 122, pp. 34–62 (2021).
DOI 10.1016/j.jcss.2021.05.004 (previously at ICALP conference, see link/details below, also link to arxiv version)

Paul W. Goldberg, Alexandros Hollender, and Warut Suksompong. Contiguous Cake Cutting: Hardness Results and Approximation Algorithms. Journal of Artificial Intelligence Research, 69, pp. 109–141 (2020).
DOI 10.1613/jair.1.12222; arxiv preprint ArXiv:1911.05416 (last uploaded in Jan 2020); previously in AAAI 2020 conference

Luka Gligic, Andrey Kormilitzin, Paul Goldberg, Alejo Nevado-Holgado. Named entity recognition in electronic health records using transfer learning bootstrapped Neural Networks. Neural Networks, 121, pp. 132–139 (2020).
PDF (local copy); ScienceDirect link; DOI 10.1016/j.neunet.2019.08.032.

Riccardo Colini-Baldeschi, Paul Goldberg, Bart de Keijzer, Stefano Leonardi, Tim Roughgarden, and Stefano Turchetta. Approximately Efficient Two-Sided Combinatorial Auctions. ACM Trans. Economics and Comput., 8(1), pp. 4:1–4:29 (2020).
DOI 10.1145/3381523;

Paul W. Goldberg, Francisco Marmolejo Cossío, and Steven Wu. Logarithmic Query Complexity for Approximate Nash Computation in Large Games. Theory of Computing Systems, 63(1), pp. 26–53 (2019).
Springer link; DOI 10.1007/s00224-018-9851-8.
Links to conference (SAGT 2016) and CoRR versions are below.

Paul W. Goldberg and C.H. Papadimitriou. Towards a Unified Complexity Theory of Total Functions. Journal of Computer and System Sciences, 94, pp. 167–192 (2018).
link; DOI 10.1016/j.jcss.2017.12.003
Electronic Colloquium on Computational Complexity, Report TR17-056, link; PDF (April 2017)
Links to conference (ITCS 2018) version below.

Paul W. Goldberg and Stefano Turchetta. Query Complexity of Approximate Equilibria in Anonymous Games. Journal of Computer and System Sciences, 90, pp. 80–98 (2017).
link; DOI 10.1016/j.jcss.2017.07.002.
(earlier version on arxiv: CoRR: ArXiv:1412.6455 (first uploaded in Dec 2014; last revision 5 May 2016))
Links to conference (WINE 2015) version below.

Xiaotie Deng, Paul W. Goldberg, Yang Sun, Bo Tang and Jinshan Zhang. Pricing Ad Slots with Consecutive Multi-unit Demand. Autonomous Agents and Multi-Agent Systems, 31(3) pp. 584–605 (2017).
link; DOI 10.1007/s10458-016-9335-7 ; full text view-only link.

D. Ferraioli, P.W. Goldberg and C. Ventre. Decentralized Dynamics for Finite Opinion Games. Theoretical Computer Science 648 pp. 96–115 (Oct 2016). DOI 10.1016/j.tcs.2016.08.011 PDF;

Paul W. Goldberg and Aaron Roth. Bounds for the Query Complexity of Approximate Equilibria. ACM Transactions on Economics and Computation 4(4) pp. 24:1–25 (Aug. 2016). (special issue for ACM-EC 2014) PDF (local copy); ACM DL link; DOI 10.1145/2956582. Links to conference and arxiv versions are below.

John Fearnley, Martin Gairing, Paul W. Goldberg, and Rahul Savani. Learning Equilibria of Games via Payoff Queries. Journal of Machine Learning Research 16 pp. 1305–1344 (2015). PDF (local copy); PDF at JMLR. Links to conference and arxiv versions are below.

John Fearnley, Paul W. Goldberg, Rahul Savani and Troels Bjerre Sørensen. Approximate Well-supported Nash Equilibria Below Two-thirds. Algorithmica 76(2) pp. 297–319 (2016). (first online July 2015) PDF (local copy); Springer link DOI 10.1007/s00453-015-0029-3 Links to conference and arxiv versions are below.

Ning Chen, Xiaotie Deng, Paul W. Goldberg, and Jinshan Zhang. On Revenue Maximization with Sharp Multi-Unit Demands. Journal of Combinatorial Optimization 31(3) pp. 1174–1205 (2016, first online Dec 2014). PDF (local copy); Online First link; DOI link.

Xiaotie Deng, Paul W. Goldberg, Bo Tang, and Jinshan Zhang. Multi-unit Bayesian Auction with Demand or Budget Constraints. Computational Intelligence 32(3) pp. 366–368. PDF (local copy); DOI link (August 2016, first published online in 2014).

Xiaotie Deng, Paul W. Goldberg, Bo Tang, and Jinshan Zhang. Revenue Maximization in a Bayesian Double Auction Market. Theoretical Computer Science 539: 1–12 (2014)
PDF (local copy); link; DOI link; (journal version of ISAAC 2012 paper, below)

Paul W. Goldberg and Arnoud Pastink. On the Communication Complexity of Approximate Nash Equilibria. Games and Economic Behavior, 85, pp. 19–31 (May 2014)
PDF (local copy); link; DOI link (journal version of SAGT 2012 paper, below)

Leslie A. Goldberg, Paul W. Goldberg, Piotr Krysta, and Carmine Ventre. Ranking Games that have Competitiveness-based Strategies. Theoretical Computer Science 476 pp.24–37 (2013). Journal version of ACM-EC 2010 paper below. DOI;
Available on arxiv

Paul W. Goldberg, Troels Bjerre Sørensen, Rahul Savani, and Carmine Ventre. On the Approximation Performance of Fictitious Play in Finite Games. International Journal of Game Theory 42(4) pp.1059–1083 (2013) DOI; Springer link; PDF

Paul W. Goldberg, Christos H. Papadimitriou, and Rahul Savani. The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions ACM Transactions on Economics and Computation 1(2) pp.9:1–9:25 (2013) DOI; PDF

Heiner Ackermann, Paul W. Goldberg, Vahab Mirrokni, Heiko Röglin, and Berthold Vöcking. Uncoordinated Two-Sided Matching Markets. SIAM J. Comput..  40(1) pp. 92–106. (2011) PDF; DOI
(Journal version of ACM-EC’08 paper below)

Edith Elkind, Leslie A. Goldberg, Paul W. Goldberg, and Michael J. Wooldridge. A Tractable and Expressive Class of Marginal Contribution Nets and Its Applications. Mathematical Logic Quarterly 55(4), pp. 362–376 (Aug 2009). PDF DOI
(Journal version of AAMAS’08 paper below)

Edith Elkind, Leslie A. Goldberg, Paul W. Goldberg, and Michael J. Wooldridge. On the Computational Complexity of Weighted Voting Games. Annals of Mathematics and Artificial Intelligence. Vol. 56, No. 2 pp. 109–131 (June 2009). PDF of online version PDF of preprint DOI
(special issue for BISFAI’07 workshop; this is journal version of AAAI’07 paper below, having a slightly different title)

Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou. The Complexity of Computing a Nash Equilibrium. Communications of the ACM Vol. 52 No. 02 pp. 89–97 (Feb 2009). PDF; DOI
This is an expository version of the SICOMP paper that appears in the “research highlights” section of the CACM; it is intended to give the intuition and ideas of the result, and the complexity class PPAD. See also Ehud Kalai’s “technical perspective” article just beforehand (DOI).

Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou. The Complexity of Computing a Nash Equilibrium. SIAM Journal on Computing Vol. 39 No. 1 pp. 195–259 (May 2009). PDF; DOI; URL
(special issue of SICOMP for STOC’06). This paper was awarded the Game Theory and Computer Science prize at GAMES 08, the 3rd World Congress of the Game Theory Society, and a SIAM Oustanding Paper Prize in 2011.

H. Ackermann, P.W. Goldberg, V. Mirrokni, H. Röglin, and B. Vöcking. A Unified Approach to Congestion Games and Two-Sided Markets. Internet Mathematics 5(4) pp. 439–457 (2008). PDF; URL; DOI
(special issue for WINE 2007)

P. Berenbrink, T.K. Friedetzky, L.A. Goldberg, P.W. Goldberg, R. Martin. Distributed Selfish Load Balancing. SIAM Journal on Computing. Vol. 37 No. 4, pp. 1163–1181 (2007). DOI
postscript of preprint; PDF of preprint

N. Palmer and P.W. Goldberg. PAC-learnability of Probabilistic Deterministic Finite State Automata in terms of Variation Distance. Theoretical Computer Science. Vol. 387 Issue 1 (2007), pp. 18–31. (Nov 2007) DOI
postscript of preprint; PDF of preprint

P. Berenbrink, L.A. Goldberg, P.W. Goldberg and R. Martin. Utilitarian Resource Assignment Journal of Discrete Algorithms Vol. 4 Issue 4, (Dec. 2006), pp. 567–587. DOI
postscript of preprint; PDF (final version)

P.W. Goldberg. Some Discriminant-based PAC Algorithms Journal of Machine Learning Research Vol. 7 (2006), pp. 283–306.
postscript of preprint; PDF of preprint; Abstract and on-line final version.

P.W. Goldberg. A Bound on the Precision Required to Estimate a Boolean Perceptron from its Average Satisfying Assignment SIAM Journal on Discrete Mathematics Vol. 20 Issue 2 (2006), pp. 328–343. DOI
postscript (preprint 17.11.05.); PDF (final version)

S. Cenk Sahinalp, Evan Eichler, P.W. Goldberg, Petra Berenbrink, Tom Friedetzky, Funda Ergun. Identifying Uniformly Mutated Segments within Repeats. Journal of Bioinformatics and Computational Biology Vol. 2 Issue 4, pp. 657–668 (Dec. 2004) DOI
postscript; PDF

P.W. Goldberg. Learning Fixed-dimension Linear Thresholds from Fragmented Data. Information and Computation, Vol. 171 Issue 1, pp. 98–122 (2001) DOI
postscript; PDF

L.A. Goldberg, P.W. Goldberg, M.S. Paterson, P. Pevzner, C. Sahinalp and E. Sweedyk. The Complexity of Gene Placement. Journal of Algorithms Vol. 41 Issue 2, pp. 225–243 (2001) DOI
postscript (preprint); PDF (final version)

Mary Cryan, Leslie Ann Goldberg and Paul W. Goldberg. Evolutionary Trees can be Learned in Polynomial Time in the Two-State General Markov Model. SIAM Journal on Computing, Vol. 31 Issue 2, pp. 375–397 (2001). DOI
postscript (preprint); PDF (final version)

N.H. Bshouty, P.W. Goldberg, S.A. Goldman, H.D. Mathias. Exact Learning of Discretized Geometric Concepts. SIAM Journal on Computing, 28 No. 2, pp. 674–699 (1998). (Tech. report WUCS-94-19, Dept. of Computer Science, Washington University (1994), 30pp.)
postscript; PDF; gzipped postscript.

L.A. Goldberg, P.W. Goldberg, C.A. Phillips, G. Sorkin. Constructing Computer Virus Phylogenies. Journal of Algorithms, 26(1) (Jan. 98) pp. 188–208.
PDF (final version); PDF (earlier version); DOI link;

L.A. Goldberg, P.W. Goldberg, C.A. Phillips, Z Sweedyk, T. Warnow. Minimizing Phylogenetic Number to find Good Evolutionary Trees. Discrete Applied Mathematics, 71, Issues 1-3 (Dec. 1996) pp. 111–136. (special issue on combinatorial problems in biology)
PDF; DOI link.

P.W. Goldberg, S.A. Goldman, S.D. Scott. PAC Learning of One-dimensional Patterns. Machine Learning, 25(1), pp. 51–70, (October 1996) Tech. report WUCS-95-10, dept. of Computer Science, Washington University (1995), 20pp.
PDF; DOI: 10.1007/BF00115300 DOI: 10.1023/A:1018396106080

P.W. Goldberg, M.C. Golumbic, H. Kaplan, R. Shamir. Four Strikes Against Physical Mapping of DNA. Journal of Computational Biology. Vol. 2, No. 1 (1995), pp. 139–152. Tech. report 287/93, Dept. of Computer Science, Tel Aviv University (1993), 18pp.
DOI: 10.1089/cmb.1995.2.139

P.W. Goldberg and M.R. Jerrum. Bounding the Vapnik-Chervonenkis Dimension of Concept Classes Parameterized by Real Numbers. Machine Learning, 18, pp. 131–148, (1995) (special issue for COLT 93).
PDF; DOI: 10.1007/BF00993408

Conference Papers

Emanuel Tewolde, Caspar Oesterheld, Vincent Conitzer, Paul W. Goldberg. The Computational Complexity of Single-Player Imperfect-Recall Games. Proceedings of the 32nd IJCAI, pp. 2878–2887 (2023).
DOI: 10.24963/ijcai.2023/321 PDF (local copy);
arxiv preprint ArXiv:2305.17805

Abheek Ghosh and Paul W. Goldberg. Best-Response Dynamics in Lottery Contests short version in procs of 24th ACM-EC (July 2023).
DOI: 10.1145/3580507.3597777
arxiv preprint ArXiv:2305.10881

Paul W. Goldberg and Matthew Katzman. Lower Bounds for the Query Complexity of Equilibria in Lipschitz Games. Procs of 14th SAGT LNCS 12885, pp. 124–139 (Sept. 2021).
DOI: 10.1007/978-3-030-85947-3_9; PDF (local copy);
arxiv preprint ArXiv:2107.03898

John Fearnley, Paul W. Goldberg, Alexandros Hollender, and Rahul Savani. The Complexity of Gradient Descent: CLS=PPAD∩PLS. STOC 2021: 53rd Annual ACM Symposium on the Theory of Computing, pp. 46–59 (June 2021).
DOI: 10.1145/3406325.3451052; PDF (local copy);
arxiv preprint ArXiv:2011.01929

Paul W. Goldberg, Alexandros Hollender, Ayumi Igarashi, Pasin Manurangsi, and Warut Suksompong. Consensus Halving for Sets of Items. Procs of 16th International Conference on Web and Internet Economics (WINE), LNCS 12495, pp. 384–397 (Dec, 2020).
DOI 10.1007/978-3-030-64946-3_27; PDF (local copy);
arxiv preprint ArXiv:2007.06754

Paul W. Goldberg, Alexandros Hollender, and Warut Suksompong. Contiguous Cake Cutting: Hardness Results and Approximation Algorithms. AAAI 2020: 34th AAAI Conference on Artificial Intelligence, pp. 1990–1997 (Feb 2020). (last uploaded in Jan 2020); PDF (local copy).
arxiv preprint ArXiv:1911.05416

Paul W. Goldberg and Alexandros Hollender. The Hairy Ball Problem is PPAD-Complete. ICALP 2019: Procs. of 46th International Colloquium on Automata, Languages and Programming, pp. 65:1–65:14 (July 2019).
DOI: 10.4230/LIPIcs.ICALP.2019.65
arxiv preprint ArXiv:1902.07657 (last uploaded in May 2019)

Aris Filos-Ratsikas and Paul W. Goldberg. The Complexity of Splitting Necklaces and Bisecting Ham Sandwiches. STOC 2019: 51st Annual ACM Symposium on the Theory of Computing, pp. 638–649 (June 2019).
DOI: 10.1145/3313276.3316334
arxiv preprint ArXiv:1805.12559 (last uploaded in Nov 2018) PDF (local copy);

Matthias Gerstgrasser, Paul W. Goldberg, Bart de Keijzer, Philip Lazos, and Alexander Skopalik. Multi-unit Bilateral Trade. Procs. of 33rd AAAI, pp. 1973–1980, (2019).
DOI: 10.1609/aaai.v33i01.33011973
arxiv preprint ArXiv:1811.05130

Paul W. Goldberg and Francisco J. Marmolejo-Cossío. Learning Convex Partitions and Computing Game-theoretic Equilibria from Best Response Queries. Procs of 14th WINE, LNCS 11316, pp. 168–187, (Dec. 2018).
DOI: 10.1007/978-3-030-04612-5_12
Full version: CoRR: ArXiv:1807.06170 (uploaded in July 2018)

Aris Filos-Ratsikas, Søren Kristoffer Stiil Frederiksen, Paul W. Goldberg, and Jie Zhang. Hardness Results for Consensus-Halving. Procs. of 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) pp. 24:1–24:16 (August 2018).
Links: proceedings web site; DOI 10.4230/LIPIcs.MFCS.2018.24; local copy
arxiv preprint ArXiv:1609.05136 (uploaded in Sept 2016)

Aris Filos-Ratsikas and Paul W. Goldberg. Consensus Halving is PPA-Complete. STOC 2018: Procs. of the 50th STOC symposium, pp. 51–64 (June 2018).
Links: local copy (PDF); DOI: 10.1145/3188745.3188880
arxiv preprint ArXiv:1711.04503 (uploaded in Nov 2017)

Paul W. Goldberg and C.H. Papadimitriou. Towards a Unified Complexity Theory of Total Functions. Procs. of the 9th Innovations in Theoretical Computer Science (ITCS) conference, pp. 37:1–37:20 (January 2018).
paper available at Proceedings website; link to PDF; DOI 10.4230/LIPIcs.ITCS.2018.37; Conference website

Riccardo Colini-Baldeschi, Paul Goldberg, Bart de Keijzer, Stefano Leonardi, Stefano Turchetta. Fixed Price Approximability of the Optimal Gain From Trade. Procs of 13th International Conference on Web and Internet Economics (WINE), LNCS 10660, pp. 146–160 (Dec, 2017). DOI 10.1007/978-3-319-71924-5_11; local copy (PDF); ArXiv:1710.08394.

Haris Aziz, Paul W. Goldberg and Toby Walsh. Equilibria in Sequential Allocation. Procs of 5th ADT LNAI 10576, pp. 270–283 (Oct, 2017).
DOI: 10.1007/978-3-319-67504-6_19; ArXiv:1705.09444.

Riccardo Colini-Baldeschi, Paul Goldberg, Bart de Keijzer, Stefano Leonardi, Tim Roughgarden, and Stefano Turchetta. Approximately Efficient Two-Sided Combinatorial Auctions. In EC ’17 Proceedings of the 18th ACM Conference on Economics and Computation pp. 591–608. Cambridge, Massachusetts, USA, June 26–30, 2017 link; DOI link; PDF (local copy); ArXiv:1611.05342 (uploaded in Nov 2016)

Paul W. Goldberg and Christos H. Papadimitriou. TFNP: An Update. Procs of 10th CIAC LNCS 10236, pp. 3–9, (May, 2017).
link; PDF (local copy), DOI link.

Matthias Gerstgrasser, Paul W. Goldberg, and Elias Koutsoupias. Revenue Maximization for Market Intermediation with Correlated Priors Procs of 9th SAGT LNCS 9928, pp. 273–285, (Sept. 2016).
PDF (local copy), DOI link.

Paul W. Goldberg, Francisco Marmolejo Cossío, and Steven Wu. Logarithmic Query Complexity for Approximate Nash Computation in Large Games PDF, DOI link. Procs of 9th SAGT LNCS 9928, pp. 3–14, (Sept. 2016). Full version: ArXiv:1610.08906 (uploaded in Oct 2016)

Baharak Rastegari, Paul Goldberg, David Manlove. Preference Elicitation in Matching Markets via Interviews: A Study of Offline Benchmarks. 2-page summary in AAMAS. (2016) AAMAS procs (2pp) (camera ready version). EXPLORE workshop procs (camera ready version); ArXiv full version. EXPLORE workshop program

George Christodoulou, Aris Filos-Ratsikas, Soren Kristoffer Stiil Frederiksen, Paul W. Goldberg, Jie Zhang, and Jinshan Zhang. Social Welfare in One-Sided Matching Mechanisms. 2-page summary in AAMAS. (2016)
AAMAS procs (2pp) (camera ready version);
There’s a longer version in the AAMAS 2016 workshops (best papers) volume (the paper was presented at the EXPLORE workshop) associated with AAMAS, which should be cited as follows. In: Osman N., Sierra C. (eds) Autonomous Agents and Multiagent Systems. AAMAS 2016. Lecture Notes in Computer Science, vol 10002, pp. 30–50. Springer.
DOI link. EXPLORE workshop procs (camera ready version); EXPLORE workshop program. In LNAI 10002 (AAMAS 2016 workshops, best papers)
earlier version on arxiv (same authors): Welfare Ratios in One-Sided Matching Mechanisms. CoRR: ArXiv:1502.03849 (uploaded in Feb 2015)

Paul W. Goldberg and Stefano Turchetta. Query Complexity of Approximate Equilibria in Anonymous Games. Procs of 11th WINE LNCS 9470, pp. 357–369 (Dec. 2015). proceedings version; DOI link.

Paul W. Goldberg and Bo Tang. Auction Design with a Revenue Target. Procs of 8th SAGT LNCS 9347, pp. 137–149 (2015). proceedings version; DOI link.

Paul W. Goldberg and Aaron Roth. Bounds for the Query Complexity of Approximate Equilibria. Procs of ACM-EC pp. 639–656 (2014). proceedings version; DOI link; (earlier version: ECCC Technical Report number 136 (Sept. 2013))

Xiaotie Deng, Paul W. Goldberg, Yang Sun, Bo Tang and Jinshan Zhang. Pricing Ad Slots with Consecutive Multi-unit Demand. Procs of SAGT LNCS 8146, pp. 255–266 (2013). proceedings version (PDF, local copy); link; DOI 10.1007/978-3-642-41392-6_22.

John Fearnley, Martin Gairing, Paul W. Goldberg, and Rahul Savani. Learning Equilibria of Games via Payoff Queries. Procs of ACM-EC pp. 397–414 (2013). proceedings version; available on arXiv.

Paul W. Goldberg and Carmine Ventre. Using Lotteries to Approximate the Optimal Revenue. Proceedings of 12th AAMAS, pp. 643–650 (2013). link to AAMAS paper
Available on arxiv

Paul W. Goldberg and Antony McCabe. Shortest Paths with Bundles and Non-Additive Weights is Hard. Procs of the 8th CIAC LNCS 7878 pp. 264–275 (2013). proceedings version;

Xiaotie Deng, Paul W. Goldberg, Bo Tang and Jinshan Zhang. Revenue Maximization in a Bayesian Double Auction Market. Procs. of the 23rd ISAAC LNCS 7676 pp. 690–699 (Dec. 2012) proceedings version; link; DOI

P.W Goldberg and Arnoud Pastink. On the Communication Complexity of Approximate Nash Equilibria. Procs of the 5th International Symposium on Algorithmic Game Theory LNCS 7615 pp. 192–203 (Oct 2012). proceedings version;
Available on arxiv

P.W Goldberg and Antony McCabe. Commodity Auctions and Frugality Ratios. Procs of the 5th International Symposium on Algorithmic Game Theory LNCS 7615 pp. 180–191 (Oct 2012). proceedings version;

J. Fearnley, P.W Goldberg, R. Savani and T.B. Sørensen. Approximate Well-supported Nash Equilibria Below Two-thirds. Procs of the 5th International Symposium on Algorithmic Game Theory LNCS 7615 pp. 108–119 (Oct 2012). proceedings version; available on arXiv.

D. Ferraioli, P.W Goldberg and C. Ventre. Decentralized Dynamics for Finite Opinion Games. Procs of the 5th International Symposium on Algorithmic Game Theory LNCS 7615 pp. 144–155 (Oct 2012). proceedings version;

X. Deng, P.W. Goldberg, B. Tang, and J. Zhang. Multi-unit Bayesian Auction with Demand or Budget Constraints. WIT-EC workshop, WIT-EC procs version; slightly updated version

P.W. Goldberg, C.H. Papadimitriou and Rahul Savani. The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions. 52nd FOCS pp. 67–76 (Oct 2011). New version, August 2011; Also available on arxiv. FOCS procs version; DOI of FOCS procs paper

P.W. Goldberg, T.B. Sørensen, Rahul Savani and Carmine Ventre. On the Approximation Performance of Fictitious Play in Finite Games procs of 19th ESA, LNCS 6942, pp. 93–105 (Sept 2011). ESA version; Available on arxiv March 2011; DOI of ESA procs paper
A journal version in International Journal on Game Theory is listed above.

P.W. Goldberg. How do you like your equilibrium selection problems? Hard, or very hard? short summary of invited talk at 3rd SAGT LNCS 6386, pp. 15–17 (Oct 2010).
PDF; DOI 10.1007/978-3-642-16170-4_2.

L.A. Goldberg, P.W. Goldberg, P. Krysta and C. Ventre. Ranking Games that have Competitiveness-based Strategies. Procs of the 11th ACM-EC Harvard University, MA, USA. (July 2010). pp. 335–344
postscript; PDF; DOI of ACM-EC procs paper

E. Elkind, L.A. Goldberg, P.W. Goldberg and M.J. Wooldridge. On the Dimensionality of Voting Games. Procs. of the 23rd AAAI Conference on AI Chicago, USA. (July 2008).
postscript; PDF;

H. Ackermann, P.W. Goldberg, V. Mirrokni, H. Röglin, and B. Vöcking. Uncoordinated Two-Sided Matching Markets. Procs. of the 9th ACM Conference on Electronic Commerce (EC’08) Chicago, USA (July 2008). postscript; PDF;
This paper received an “outstanding paper” award at the EC conference. There is a 6-page summary article in the July 2009 issue of sigecom exchanges. (Vol 8 No. 1 July 2009)

H. Ackermann, P.W. Goldberg, V. Mirrokni, H. Röglin, and B. Vöcking. A Unified Approach to Congestion Games and Two-Sided Markets. Procs. of the 3rd Workshop on Internet and Network Economics (WINE) San Diego, CA, USA, Springer LNCS 4858 pp. 30–41 (Dec 2007). DOI
PDF;
Journal version in Internet Mathematics (see above), special issue for WINE 2007.

E. Elkind, L.A. Goldberg, P.W. Goldberg and M.J. Wooldridge. A Tractable and Expressive Class of Marginal Contribution Nets and Its Applications. Procs. of the 7th Int’l Conf on Autonomous Agents and Multiagent Systems (AAMAS) Estoril, Portugal (May 2008).
Conference programme; PDF

E. Elkind, L.A. Goldberg, P.W. Goldberg and M.J. Wooldridge. Computational Complexity of Weighted Threshold Games. Procs. of the 22nd AAAI Conference on AI Vancouver, BC, Canada, pp. 718–723 (July 2007).
conference procs; PDF

E. Elkind, L.A. Goldberg and P.W. Goldberg. Computing Good Nash Equilibria in Graphical Games. Procs. of the 8th ACM Conference on Electronic Commerce (ACM EC) San Diego, CA, USA, pp. 162–171 (2007). DOI 10.1145/1250910.1250935
Full version on ArXiv; PDF

E. Elkind, L.A. Goldberg and P.W. Goldberg. Frugality Ratios and Improved Truthful Mechanisms for Vertex Cover. Procs. of the 8th ACM Conference on Electronic Commerce (ACM EC) San Diego, CA, USA, pp. 336–345 (2007).
DOI link; Full version on ArXiv; PDF

E. Elkind, L.A. Goldberg and P.W. Goldberg. Nash Equilibria in Graphical Games on Trees Revisited. Procs. of the 7th ACM Conference on Electronic Commerce (ACM EC) Ann Arbor, Michigan, USA, pp. 100–109 (2006).
PDF (local copy); DOI link; earlier version in ECCC

C. Daskalakis, P.W. Goldberg and C.H. Papadimitriou. The Complexity of Computing a Nash Equilibrium. Procs. of the 38th Symp. on Theory of Computing (STOC) Seattle, Washington, USA, pp. 71–78 (May 2006).
PDF; DOI 10.1145/1132516.1132527.
earlier version in ECCC

P.W. Goldberg and C.H. Papadimitriou. Reducibility Among Equilibrium Problems. Procs. of the 38th Symp. on Theory of Computing (STOC) Seattle, Washington, USA, pp. 61–70 (May 2006). DOI
STOC procs PDF; earlier version in ECCC

P. Berenbrink, T.K. Friedetzky, L.A. Goldberg, P.W. Goldberg, R. Martin. Distributed Selfish Load Balancing. Procs. of the 17th ACM-SIAM Symp. on Discrete Algorithms (SODA) pp. 354–363 (2006). DOI
postscript; PDF; gzipped postscript (A journal version of this paper is available, see above).

N. Palmer and P.W. Goldberg. PAC-learnability of Probabilistic Deterministic Finite State Automata in terms of Variation Distance. Procs of the 16th Algorithmic Learning Theory (ALT) conference, LNAI 3734, pp. 157–170 (Oct. 2005). DOI of procs DOI
PDF

P.W. Goldberg. Bounds for the Convergence Rate of Randomized Local Search in a Multiplayer, Load-balancing Game. Procs of the 23rd Annual ACM SIGACT-SIGOPS Symp. on Principles of Distributed Computing (PODC) pp. 131–140 (July 2004).
postscript; PDF; gzipped postscript.

M. Adler, P. Berenbrink, T. Friedetzky, L.A. Goldberg, P.W. Goldberg and M. Paterson. A Proportionate Fair Scheduling Rule with Good Worst-case Performance Procs of SPAA 2003, pp 101–8. June 7-9, San Diego, USA.
postscript; A journal submission of this paper is below.

S.C. Sahinalp, E. Eichler, P.W. Goldberg, P. Berenbrink, T. Friedetzky, F. Ergun. Statistical Identification of Uniformly Mutated Segments within Repeats Procs of the 2002 Combinatorial Pattern Matching conference (Fukuoka, Japan, July 3-5 2002) LNCS 2373, pp. 249–261 gzipped PS

P. Boonmee, P.W. Goldberg, N.J. Saunders, S.A. Jarvis. A Computational Framework for the Detection and Identification of Horizontal Gene Transfer in Bacteria The International Conference on Bioinformatics (InCoB 2002), Bangkok, Thailand. 6-8th February 2002. gzipped .doc

P.W. Goldberg. When Can Two Unsupervised Learners Achieve PAC Separation? Procs of the 2001 COLT-EUROCOLT conference (Amsterdam, Netherlands, July 2001), LNAI 2111 pp. 303–319
postscript; PDF; gzipped postscript. A journal version improves and extends this work; it is entitled “Some Discriminant-based PAC Algorithms”, above.

P.W. Goldberg. Estimating A Boolean Perceptron From Its Average Satisfying Assignment: A Bound on the Precision Required. Procs of the 2001 COLT-EUROCOLT conference (Amsterdam, Netherlands, July 2001), LNAI 2111 pp. 116–127
gzipped postscript; The journal version is above; it corrects a mistake in the proof.

P.W. Goldberg and S. Kwek. The Precision of Query Points as a Resource for Learning Convex Polytopes with Membership Queries. Procs of the 13th Conference on Computational Learning Theory (COLT) pp. 225–235 (Morgan-Kaufmann) (2000).
PDF;

P.W. Goldberg. Learning Fixed-dimension Linear Thresholds from Fragmented Data. Procs of the 1999 Conference on Computational Learning Theory, pp. 88–99 July 1999.

L.A. Goldberg, P.W. Goldberg, M.S. Paterson, P. Pevzner, C. Sahinalp, E. Sweedyk. The Complexity of Gene Placement. procs. of Symp. on Discrete Algorithms , pp. 386–395, Jan. 1999.

L.A. Goldberg, P.W. Goldberg, M. Cryan. Evolutionary Trees can be Learned in Polynomial Time in the Two-State General Markov Model. 39th Symp. on Foundations of Computer Science , pp. 436–445, Nov. 1998.

P.W. Goldberg, C.K.I. Williams, C.M. Bishop. Regression with Input-dependent Noise: A Gaussian Process Treatment. Advances in Neural Information Processing Systems, pp. 493–499, (Dec. 1997).
PDF (as in proceedings); older version

L.A. Goldberg, P.W. Goldberg, C.A. Phillips, G. Sorkin. Constructing Computer Virus Phylogenies In Proceedings of the seventh annual symposium on Combinatorial Pattern Matching (1996), pp 253–270.
PDF (as in proceedings); DOI link

L.A. Goldberg, P.W. Goldberg, C.A. Phillips, Z Sweedyk, T. Warnow. Minimizing Phylogenetic Number to find Good Evolutionary Trees In Proceedings of the sixth annual symposium on Combinatorial Pattern Matching (1995), 26pp.

P.W. Goldberg and S.A. Goldman. Learning One-Dimensional Geometrical Patterns Under One-Sided Random Misclassification Noise In Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory, pp. 246–255 (July 1994). (Also presented at the 1993 Computational Learning and Natural Learning Workshop, September 1993. Provincetown, MA.)

P.W. Goldberg, S.A. Goldman, H.D. Mathias. Learning Unions of Boxes with Membership and Equivalence Queries In Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory, pp. 198–207 (July 1994).

P.W. Goldberg and M.R. Jerrum. Bounding the Vapnik-Chervonenkis Dimension of Concept Classes Parameterized by Real Numbers In Proceedings of the Sixth Annual ACM Conference on Computational Learning Theory, pp. 361–369 (July 1993).
DOI 10.1145/168304.168377.

Other Papers

Alexandros Hollender and Paul W. Goldberg. The Complexity of Multi-source Variants of the End-of-Line Problem, and the Concise Mutilated Chessboard. Electronic Colloquium on Computational Complexity, Report TR18-120 (June 2018).

Luka Gligic, Andrey Kormilitzin, Paul Goldberg, Alejo Nevado-Holgado. Named Entity Recognition in Electronic Health Records Using Transfer Learning Bootstrapped Neural Networks. CoRR: ArXiv:1901.01592 (uploaded in January 2019)

Maximilian Hofer, Andrey Kormilitzin, Paul Goldberg, Alejo Nevado-Holgado. Few-shot Learning for Named Entity Recognition in Medical Text. CoRR: ArXiv:1811.05468 (uploaded in November 2018)

Paul W. Goldberg, Yishay Mansour, and Paul Dütting. Game Theory Meets Computational Learning Theory (Dagstuhl Seminar 17251). Dagstuhl Reports 7(6): pp. 68–85 (2017). link; DOI link; local copy (PDF).

Paul W. Goldberg. Learning Game-Theoretic Equilibria Via Query Protocols. In: Díaz J., Kirousis L., Ortiz-Gracia L., Serna M. (eds) Extended Abstracts Summer 2015. Trends in Mathematics 6: pp. 67–72 (Feb 2017). preprint; link; DOI link.

John Fearnley, Martin Gairing, Paul W. Goldberg and Rahul Savani. Learning Equilibria of Games via Payoff Queries available on arXiv. (Feb 2013)

Ning Chen, Xiaotie Deng, Paul W. Goldberg and Jinshan Zhang. On Revenue Maximization with Sharp Multi-Unit Demands available on arXiv. (Oct 2012)

P. Goldberg. A Survey of PPAD-Completeness for Computing Nash Equilibria Surveys in Combinatorics 2011 (London Mathematical Society Lecture Note Series 392) pp. 51-82, Cambridge University Press;
PDF (as it appears in the volume); Available on arxiv March 2011 (perhaps preferable to the version in the Surveys in Combinatorics volume since diagrams are in colour).

P. Briest, P.W. Goldberg and H. Röglin. Approximate Equilibria in Games with Few Players available on arXiv.

Heiner Ackermann, Paul W. Goldberg, Vahab S. Mirrokni, Heiko Röglin, and Berthold Vöcking Uncoordinated Two-Sided Markets RWTH-Aachen Dept. Computer Science Tech Rept. 2007-22.

E. Elkind, L.A. Goldberg and P.W. Goldberg. Frugality Ratios And Improved Truthful Mechanisms for Vertex Cover available on arXiv.

N. Palmer and P.W. Goldberg. PAC Classification Based on PAC Estimates of Label Class Distributions University of Warwick research report CS-RR-411 (last updated Jul 06) postscript; PDF; gzipped postscript. Also available on arXiv.

M. Adler, P. Berenbrink, T. Friedetzky, L.A. Goldberg, P.W. Goldberg and M. Paterson. A Proportionate Fair Scheduling Rule with Good Worst-case Performance
postscript; PDF; gzipped postscript.

P. Berenbrink, L.A. Goldberg, P.W. Goldberg, R. Martin. Utilitarian Resource Assignment. University of Warwick research report CS-RR-405
postscript; PDF; gzipped postscript; available from arXiv.

The Gap Between Sample Size Requirements for Learning Problems and VC-dimension Based Bounds. P.W. Goldberg. NCRG Tech. Report 97-001, Aston University.

Minimum-dilation multiple sequence alignment. J.E. Atkins, P.W. Goldberg, P. Mackenzie, C.A. Phillips and R. Ravi. Sandia National Laboratories Technical Report number SAND97-0273, 1997.

Complexity of Systems and Control Theory Problems. P.W. Goldberg, G.L. Heileman, and C. Abdallah. IMACS 95 Workshop on Computer Algebra, Albuquerque, NM, May, 1995. (Abstract)

PAC-Learning Geometrical Figures. Ph.D. dissertation, Department of Computer Science, University of Edinburgh, November 1992. 101pp.

Ground Completion. MSc thesis, Department of Computer Science, University of Edinburgh and Laboratoire de Recherche en Informatique, Université Paris-Sud, September 1989. 36pp.