Paul Goldberg, Prof


Personal Statement

I started at Liverpool as a Reader in the Computer Science department in August 2006. Prior to that I was a Lecturer and then a Reader in Computer Science at the University of Warwick.

Publications

  • Fearnley J, Gairing M, Goldberg PW and Savani R (2013) Learning Equilibria of Games via Payoff Queries. 'Proceedings of the 14th ACM Conference on Electronic Commerce'. Philadelphia pp 397-414
  • Goldberg PW, Papadimitriou CH, Savani R (2012) The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions. ACM Transactions on Economics and Computation vol 1 issue 2
  • PW Goldberg and A Pastink (2012) On the Communication Complexity of Approximate Nash Equilibria. In: M Serna ed(s) 5th International Symposium on Algorithmic Game Theory. Springer-Verlag, Barcelona pp 192-203
  • J Fearnley, PW Goldberg, R Savani and TB S?rensen (2012) Approximate Well-supported Nash Equilibria Below Two-thirds. In: M Serna ed(s) 5th International Symposium on Algorithmic Game Theory. Springer-Verlag, Barcelona pp 108-119
  • PW Goldberg and A McCabe (2012) Commodity Auctions and Frugality Ratios. In: M Serna ed(s) 5th International Symposium on Algorithmic Game Theory. Springer-Verlap, Barcelona pp 180-191
  • D Ferraioli PW Goldberg and C Ventre (2012) Decentralized Dynamics for Finite Opinion Games. In: M Serna ed(s) 5th International Symposium on Algorithmic Game Theory. Springer-Verlag, Barcelona pp 144-155
  • X Deng, PW Goldberg, B Tang and J Zhang (2012) Multi-unit Bayesian Auction with Demand or Budget Constraints. In: S Marsh, J Zhang and C Jensen ed(s) First Workshop on Incentives and Trust in E-Commerce. ACM, Valencia pp 13-23
  • Goldberg PW, Savani R, S?rensen TB, Ventre C (2011) On the Approximation Performance of Fictitious Play in Finite Games. European Symposium on Algorithms (ESA). Saarbrucken pp 93-105
  • Goldberg PW, Papadimitriou CH, Savani R (2011) The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions.. 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2011). IEEE, Palm Springs pp 67-76
  • Ackermann H, Goldberg PW, Mirrokni V, Roeglin H and Voecking B (2011) Uncoordinated Two-Sided Matching Markets. SIAM Journal on Computing vol 40 issue 1 pp 92-106
  • L.A. Goldberg, P.W. Goldberg, P. Krysta, and C. Ventre (2010) Ranking games that have competitiveness-based strategies. Proceedings of the 11th ACM conference on Electonic commerce. ACM, Boston, USA pp 335-344
  • Leslie Ann Goldberg, Paul W. Goldberg, Piotr Krysta and Carmine Ventre (2010) Ranking games that have competitiveness-based strategies. Proceedings of ACM EC 2010. ACM, Cambridge pp 335-344
  • Edith Elkind, Leslie Ann Goldberg, Paul W Goldberg, Michael Wooldridge (2009) A tractable and expressive class of marginal contribution nets and its applications. Mathematical Logic Quarterly vol 55 issue 4 pp 362-376
  • Daskalakis C, Goldberg PW and Papadimitriou CH (2009) The Complexity of Computing a Nash Equilibrium. Communications of the ACM vol 52 issue 2 pp 89-97
  • Elkind E, Goldberg LA, Goldberg PW and Wooldridge M (2009) On the Computational Complexity of Weighted Voting Games. Annals of Mathematics and Artificial Intelligence vol 56 issue 2 pp 109-131
  • Edith Elkind, Leslie Ann Goldberg, Paul W Goldberg and Michael Wooldridge (2008) A Tractable and Expressive Class of Marginal Contribution Nets and Its Applications. The 7th International Conferenence on Autonomous Agents and Multiagent Systems. aamas, Estoril pp 1007-1004
  • Edith Elkind, Leslie Ann Goldberg, Paul Goldberg and Michael Wooldridge (2008) On the dimensionality of voting games. 23rd AAAI Conference on Artificial Intelligence. AAAI, Chicago pp 69-74
  • Ackermann H, Goldberg PW, Mirrokni VS, Roeglin H and Voecking B (2008) Uncoordinated two-sided matching markets. In: Fortnow L, Riedl J and Sandholm T ed(s) Procedings of 9th ACM Conference on Electronic Commerce (EC-2008). ACM, Chicago pp 256-263
  • Paul W. Goldberg and Ullrich Endriss. ed(s) (2008) 2nd International Workshop on Computational Social Choice. none, Liverpool
  • Ackermann H, Goldberg PW, Mirrokni V, Roeglin H and Voecking B (2008) A Unified Approach to Congestion Games and Two-Sided Markets. Internet Mathematics vol 5 issue 4 pp 439-457
  • Edith Elkind and Leslie Ann Goldberg and Paul Goldberg and Michael Wooldridge (2007) Computational Complexity of Weighted Threshold Games. Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence (AAAI-07). AAAI Press, Menlo Park, California pp 718-723
  • Edith Elkind and Leslie Ann Goldberg and Paul Goldberg (2007) Frugality ratios and improved truthful mechanisms for vertex cover. Proceedings of the 8th ACM conference on Electronic commerce . ACM Press, New York, NY, USA pp 336-345
  • Petra Berenbrink, Tom Friedetzky, Leslie Ann Goldberg, Zengjian Hu, Russell Martin (2007) Distributed Selfish Load Balancing. SIAM Journal on Computing vol 37 issue 4 pp 1163-1181
  • Edith Elkind and Leslie Ann Goldberg and Paul Goldberg (2007) Computing good nash equilibria in graphical games. Proceedings of the 8th ACM conference on Electronic commerce . ACM Press, New York, NY, USA pp 162-171
  • Palmer N and Goldberg PW (2007) PAC-Learnability of Probabilistic Deterministic State Automata in Terms of Variation Distance. Theoretic Computer Science vol 387 issue 1 pp 18-31
  • Ackermann H, Goldberg PW, Mirrokni V, Roeglin H and Voecking B (2007) A Unified Approach to Congestion Games and Two-Sided Markets. Procs of the 3rd Workshop on Internet and Network Ecomonics (WINE). Springer, San Diego pp 30-41
  • Petra Berenbrink, Tom Friedetzky, Leslie Ann Goldberg, Paul Goldberg, Zengjian Hu, and Russell Martin (2006) Distributed selfish load balancing. Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006). Association of Computing Machinery and Society for Industrial and Applied Mathematics, New York, NY pp 354-363
  • P.W. Goldberg (2006) Some discriminant-based PAC algorithms. Journal of Machine Learning Research vol 7 pp 283-306
  • Goldberg PW and Papadimitriou CH (2006) Reducibility Among Equilibrium Problems. Procs. of the 38th Symp. on Theory of Computing (STOC). ACM, Seattle pp 61-70
  • P.W. Goldberg (2006) 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 pp 328-343
  • Berenbrink P, Friedetzky TK, Goldberg LA, Goldberg PW and Martin R (2006) Distributed selfish load balancing. Proceedings of the 17th ACM-SIAM Symp. on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, Miami pp 10
  • P. Berenbrink, L.A. Goldberg, P. Goldberg, R. Martin (2006) Utiliitarian Resource Assignment. Journal of Discrete Algorithms vol 4 issue 4 pp 567-587
  • E. Elkind, L.A. Goldberg and P.W Goldberg (2006) Nash Equilibria in Graphical Games on Trees Revisited. ACM EC. ACM, xxx pp -
  • C. Daskalakis, P.W. Goldberg and C.H. Papadimitriou. (2006) The complexity of computing a Nash equilibrium. Proceedings of the 38th Symposium on Theory of Computing (STOC). ACM Press, Seattle pp 8
  • N. Palmer and P.W. Goldberg. (2005) PAC-learnability of Probabilistic Deterministic Finite State Automata in terms of Variation Distance. Lecture Notes in Artificial Intelligence. Springer, Singapore pp 157-170
  • Mary Cryan, Leslie Ann Goldberg and Paul W. Goldberg (2001) 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

Professional Memberships

  • Game Theory Society
  • Association for Computing Machinery

Personal Distinctions

  • SIAM Outstanding Paper prize (SIAM (Society for Industrial and Applied Mathematics) journals 2011)
  • plenary talk at BCC (British Combinatorial Committee 2011)
  • plenary talk at SAGT (SAGT steering committee 2010)
  • invited talk at BCTCS (BCTCS committee 2009)
  • Game Theory and Computer Science Prize (Game Theory Society 2008)