Dr John Fearnley

Lecturer Computer Science

    Publications

    2019

    Hiring Secretaries over Time: The Benefit of Concurrent Employment (Journal article)

    Disser, Y., Fearnley, J., Gairing, M., Göbel, O., Klimm, M., Schmand, D., . . . Tönnis, A. (n.d.). Hiring Secretaries over Time: The Benefit of Concurrent Employment. Mathematics of Operations Research. doi:10.1287/moor.2019.0993

    DOI: 10.1287/moor.2019.0993

    Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem (Conference Paper)

    Deligkas, A., Fearnley, J. S., Melissourgos, T., & Spirakis, P. G. (n.d.). Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem. In ICALP 2019.

    Unique End of Potential Line (Conference Paper)

    Fearnley, J. S., Gordon, S., Mehta, R., & Savani, R. (n.d.). Unique End of Potential Line. In ICALP 2019.

    Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem (Journal article)

    Deligkas, A., Fearnley, J., Melissourgos, T., & Spirakis, P. G. (n.d.). Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem. Retrieved from http://arxiv.org/abs/1903.03101v1

    An Ordered Approach to Solving Parity Games in Quasi-Polynomial Time and Quasi-Linear Space (Journal article)

    Fearnley, J. S., Jain, S., De Keijzer, B., Schewe, S., Stephan, F., & Wojtczak, D. (n.d.). An Ordered Approach to Solving Parity Games in Quasi-PolynomialTime and Quasi-Linear Space. International Journal on Software Tools for Technology Transfer.

    2018

    Approximating the Existential Theory of the Reals (Conference Paper)

    Deligkas, A., Fearnley, J., Melissourgos, T., & Spirakis, P. G. (n.d.). Approximating the Existential Theory of the Reals. Retrieved from http://arxiv.org/abs/1810.01393v2

    Unique End of Potential Line (Other)

    Fearnley, J., Gordon, S., Mehta, R., & Savani, R. (n.d.). Unique End of Potential Line. Retrieved from http://arxiv.org/abs/1811.03841v1

    The Complexity of All-switches Strategy Improvement. (Journal article)

    Fearnley, J., & Savani, R. (2018). The Complexity of All-switches Strategy Improvement.. Logical Methods in Computer Science, 14.

    Inapproximability results for constrained approximate Nash equilibria (Journal article)

    Deligkas, A., Fearnley, J., & Savani, R. (2018). Inapproximability results for constrained approximate Nash equilibria. INFORMATION AND COMPUTATION, 262, 40-56. doi:10.1016/j.ic.2018.06.001

    DOI: 10.1016/j.ic.2018.06.001

    An Improved Envy-Free Cake Cutting Protocol for Four Agents (Journal article)

    Amanatidis, G., Christodoulou, G., Fearnley, J., Markakis, E., Psomas, C. -A., & Vakaliou, E. (n.d.). An Improved Envy-Free Cake Cutting Protocol for Four Agents. Lecture Notes in Computer Science. doi:10.1007/978-3-319-99660-8_9

    DOI: 10.1007/978-3-319-99660-8_9

    Distributed Methods for Computing Approximate Equilibria (Journal article)

    Czumaj, A., Deligkas, A., Fasoulakis, M., Fearnley, J., Jurdziński, M., & Savani, R. (2019). Distributed Methods for Computing Approximate Equilibria. Algorithmica, 81(3), 1205-1231. doi:10.1007/s00453-018-0465-y

    DOI: 10.1007/s00453-018-0465-y

    End of Potential Line (Other)

    Fearnley, J., Gordon, S., Mehta, R., & Savani, R. (n.d.). End of Potential Line. Retrieved from http://arxiv.org/abs/1804.03450v2

    An Improved Envy-Free Cake Cutting Protocol for Four Agents. (Conference Paper)

    Amanatidis, G., Christodoulou, G., Fearnley, J., Markakis, E., Psomas, C. -A., & Vakaliou, E. (2018). An Improved Envy-Free Cake Cutting Protocol for Four Agents.. In X. Deng (Ed.), SAGT Vol. 11059 (pp. 87-99). Springer. Retrieved from https://doi.org/10.1007/978-3-319-99660-8

    Market Making via Reinforcement Learning (Other)

    Spooner, T., Fearnley, J., Savani, R., Koukorinis, A., & ACM. (2018). Market Making via Reinforcement Learning. In PROCEEDINGS OF THE 17TH INTERNATIONAL CONFERENCE ON AUTONOMOUS AGENTS AND MULTIAGENT SYSTEMS (AAMAS' 18) (pp. 434-442). Retrieved from http://gateway.webofknowledge.com/

    Market Making via Reinforcement Learning. (Conference Paper)

    Spooner, T., Fearnley, J., Savani, R., & Koukorinis, A. (2018). Market Making via Reinforcement Learning.. In E. André, S. Koenig, M. Dastani, & G. Sukthankar (Eds.), AAMAS (pp. 434-442). International Foundation for Autonomous Agents and Multiagent Systems Richland, SC, USA / ACM. Retrieved from http://dl.acm.org/citation.cfm?id=3237383

    Reachability Switching Games. (Conference Paper)

    Fearnley, J., Gairing, M., Mnich, M., & Savani, R. (2018). Reachability Switching Games.. In I. Chatzigiannakis, C. Kaklamanis, D. Marx, & D. Sannella (Eds.), ICALP Vol. 107 (pp. 124:1). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. Retrieved from http://www.dagstuhl.de/dagpub/978-3-95977-076-7

    2017

    Reachability Switching Games (Other)

    Fearnley, J., Gairing, M., Mnich, M., & Savani, R. (n.d.). Reachability Switching Games. Retrieved from http://arxiv.org/abs/1709.08991v3

    Computing Constrained Approximate Equilibria in Polymatrix Games (Conference Paper)

    Deligkas., Fearnley., & Savani, R. S. J. (2017). Computing Constrained Approximate Equilibria in Polymatrix Games. In Symposium on Algorithmic Game Theory (SAGT) (pp. 93-105). doi:10.1007/978-3-319-66700-3_8

    DOI: 10.1007/978-3-319-66700-3_8

    An Ordered Approach to Solving Parity Games in Quasi Polynomial Time and Quasi Linear Space (Conference Paper)

    Fearnley, J., Jain, S., Schewe, S., Stephan, F., & Wojtczak, D. (2017). An Ordered Approach to Solving Parity Games in Quasi Polynomial Time and Quasi Linear Space. In SPIN'17: PROCEEDINGS OF THE 24TH ACM SIGSOFT INTERNATIONAL SPIN SYMPOSIUM ON MODEL CHECKING OF SOFTWARE (pp. 112-121). doi:10.1145/3092282.3092286

    DOI: 10.1145/3092282.3092286

    Efficient Parallel Strategy Improvement for Parity Games (Conference Paper)

    Fearnley, J. S. (2017). Efficient Parallel Strategy Improvement for Parity Games. In Computer Aided Verification 2017.

    Computing Approximate Nash Equilibria in Polymatrix Games (Journal article)

    Deligkas, A., Fearnley, J., Savani, R., & Spirakis, P. (2017). Computing Approximate Nash Equilibria in Polymatrix Games. ALGORITHMICA, 77(2), 487-514. doi:10.1007/s00453-015-0078-7

    DOI: 10.1007/s00453-015-0078-7

    An Ordered Approach to Solving Parity Games in Quasi Polynomial Time and Quasi Linear Space. (Journal article)

    Fearnley, J., Jain, S., Schewe, S., Stephan, F., & Wojtczak, D. (2017). An Ordered Approach to Solving Parity Games in Quasi Polynomial Time and Quasi Linear Space.. CoRR, abs/1703.01296.

    CLS: New Problems and Completeness (Other)

    Fearnley, J., Gordon, S., Mehta, R., & Savani, R. (n.d.). CLS: New Problems and Completeness. Retrieved from http://arxiv.org/abs/1702.06017v2

    Computing Constrained Approximate Equilibria in Polymatrix Games. (Journal article)

    Deligkas, A., Fearnley, J., & Savani, R. (2017). Computing Constrained Approximate Equilibria in Polymatrix Games.. CoRR, abs/1705.02266.

    Efficient Parallel Strategy Improvement for Parity Games. (Conference Paper)

    Fearnley, J. (2017). Efficient Parallel Strategy Improvement for Parity Games.. In R. Majumdar, & V. Kuncak (Eds.), CAV (2) Vol. 10427 (pp. 137-154). Springer. Retrieved from https://doi.org/10.1007/978-3-319-63390-9

    2016

    Distributed Methods for Computing Approximate Equilibria (Conference Paper)

    Czumaj, A., Deligkas, A., Fasoulakis, M., Fearnley, J. S., Jurdzinski, M., & Savani, R. (2016). Distributed Methods for Computing Approximate Equilibria. In WINE 2016: The 12th Conference on Web and Internet Economics. doi:10.1007/978-3-662-54110-4_2

    DOI: 10.1007/978-3-662-54110-4_2

    Inapproximability Results for Approximate Nash Equilibria. (Conference Paper)

    Deligkas, A., Fearnley, J., & Savani, R. (2016). Inapproximability Results for Approximate Nash Equilibria.. In Y. Cai, & A. Vetta (Eds.), WINE Vol. 10123 (pp. 29-43). Springer. Retrieved from https://doi.org/10.1007/978-3-662-54110-4

    Approximate Well-supported Nash Equilibria Below Two-thirds (Journal article)

    Fearnley, J., Goldberg, P. W., Savani, R., & Sorensen, T. B. (2016). Approximate Well-supported Nash Equilibria Below Two-thirds. ALGORITHMICA, 76(2), 297-319. doi:10.1007/s00453-015-0029-3

    DOI: 10.1007/s00453-015-0029-3

    Inapproximability Results for Approximate Nash Equilibria (Journal article)

    Deligkas, A., Fearnley, J., & Savani, R. (n.d.). Inapproximability Results for Approximate Nash Equilibria. Retrieved from http://arxiv.org/abs/1608.03574v3

    Finding Approximate Nash Equilibria of Bimatrix Games via Payoff Queries (Journal article)

    Fearnley, J., & Savani, R. (2016). Finding Approximate Nash Equilibria of Bimatrix Games via Payoff Queries. ACM Transactions on Economics and Computation, 4(4), 1-19. doi:10.1145/2956579

    DOI: 10.1145/2956579

    Hiring Secretaries over Time: The Benefit of Concurrent Employment (Report)

    Disser, Y., Fearnley, J., Gairing, M., Göbel, O., Klimm, M., Schmand, D., . . . Tönnis, A. (n.d.). Hiring Secretaries over Time: The Benefit of Concurrent Employment. Retrieved from http://arxiv.org/abs/1604.08125v2

    Efficient approximation of optimal control for continuous-time Markov games (Journal article)

    Fearnley, J., Rabe, M. N., Schewe, S., & Zhang, L. (2016). Efficient approximation of optimal control for continuous-time Markov games. INFORMATION AND COMPUTATION, 247, 106-129. doi:10.1016/j.ic.2015.12.002

    DOI: 10.1016/j.ic.2015.12.002

    An Empirical Study on Computing Equilibria in Polymatrix Games (Conference Paper)

    Deligkas, A., Fearnley, J., Igwe, T. P., Savani, R., & Machinery, A. C. (2016). An Empirical Study on Computing Equilibria in Polymatrix Games. In AAMAS'16: PROCEEDINGS OF THE 2016 INTERNATIONAL CONFERENCE ON AUTONOMOUS AGENTS & MULTIAGENT SYSTEMS (pp. 186-195). Retrieved from http://gateway.webofknowledge.com/

    An Empirical Study on Computing Equilibria in Polymatrix Games. (Report)

    Deligkas, A., Fearnley, J., Igwe, T. P., & Savani, R. (2016). An Empirical Study on Computing Equilibria in Polymatrix Games..

    Lipschitz Continuity and Approximate Equilibria (Journal article)

    Deligkas, A., Fearnley, J., & Spirakis, P. (2016). Lipschitz Continuity and Approximate Equilibria. ALGORITHMIC GAME THEORY, SAGT 2016, 9928, 15-26. doi:10.1007/978-3-662-53354-3_2

    DOI: 10.1007/978-3-662-53354-3_2

    THE COMPLEXITY OF ALL-SWITCHES STRATEGY IMPROVEMENT (Conference Paper)

    Fearnley, J., & Savani, R. (2018). THE COMPLEXITY OF ALL-SWITCHES STRATEGY IMPROVEMENT. In LOGICAL METHODS IN COMPUTER SCIENCE Vol. 14. doi:10.23638/LMCS-14(4:9)2018

    DOI: 10.23638/LMCS-14(4:9)2018

    2015

    Synthesis of succinct systems (Journal article)

    Fearnley, J., Peled, D., & Schewe, S. (2015). Synthesis of succinct systems. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 81(7), 1171-1193. doi:10.1016/j.jcss.2015.02.005

    DOI: 10.1016/j.jcss.2015.02.005

    Learning Equilibria of Games via Payoff Queries (Journal article)

    Fearnley, J., Gairing, M., Goldberg, P. W., & Savani, R. (2015). Learning Equilibria of Games via Payoff Queries. JOURNAL OF MACHINE LEARNING RESEARCH, 16, 1305-1344. Retrieved from http://gateway.webofknowledge.com/

    Reachability in two-clock timed automata is PSPACE-complete (Journal article)

    Fearnley, J., & Jurdzinski, M. (2015). Reachability in two-clock timed automata is PSPACE-complete. INFORMATION AND COMPUTATION, 243, 26-36. doi:10.1016/j.ic.2014.12.004

    DOI: 10.1016/j.ic.2014.12.004

    An Empirical Study of Finding Approximate Equilibria in Bimatrix Games (Conference Paper)

    Fearnley, J., Igwe, T. P., & Savani, R. (2015). An Empirical Study of Finding Approximate Equilibria in Bimatrix Games. In EXPERIMENTAL ALGORITHMS, SEA 2015 Vol. 9125 (pp. 339-351). doi:10.1007/978-3-319-20086-6_26

    DOI: 10.1007/978-3-319-20086-6_26

    An Empirical Study of Finding Approximate Equilibria in Bimatrix Games. (Conference Paper)

    Fearnley, J., Igwe, T. P., & Savani, R. (2015). An Empirical Study of Finding Approximate Equilibria in Bimatrix Games.. In E. Bampis (Ed.), SEA Vol. 9125 (pp. 339-351). Springer. Retrieved from https://doi.org/10.1007/978-3-319-20086-6

    Distributed Methods for Computing Approximate Equilibria (Report)

    Czumaj, A., Deligkas, A., Fasoulakis, M., Fearnley, J., Jurdzinski, M., & Savani, R. (2019). Distributed Methods for Computing Approximate Equilibria. doi:10.1007/s00453-018-0465-y

    DOI: 10.1007/s00453-018-0465-y

    The Complexity of the Simplex Method (Conference Paper)

    Fearnley, J., Savani, R., & Machinery, A. C. (2015). The Complexity of the Simplex Method. In STOC'15: PROCEEDINGS OF THE 2015 ACM SYMPOSIUM ON THEORY OF COMPUTING (pp. 201-208). doi:10.1145/2746539.2746558

    DOI: 10.1145/2746539.2746558

    The complexity of all-switches strategy improvement (Report)

    Fearnley, J., & Savani, R. (2016). The complexity of all-switches strategy improvement.

    2014

    Computing Approximate Nash Equilibria in Polymatrix Games (Conference Paper)

    Deligkas, A., Fearnley, J., Savani, R., & Spirakis, P. (2014). Computing Approximate Nash Equilibria in Polymatrix Games. In WEB AND INTERNET ECONOMICS Vol. 8877 (pp. 58-71). Retrieved from http://gateway.webofknowledge.com/

    Finding approximate nash equilibria of bimatrix games via payoff queries (Conference Paper)

    Fearnley, J., & Savani, R. (2014). Finding approximate nash equilibria of bimatrix games via payoff queries. In Proceedings of the fifteenth ACM conference on Economics and computation - EC '14. ACM Press. doi:10.1145/2600057.2602847

    DOI: 10.1145/2600057.2602847

    The Complexity of the Simplex Method. (Journal article)

    Fearnley, J., & Savani, R. (2014). The Complexity of the Simplex Method.. CoRR, abs/1404.0605.

    2013

    Finding Approximate Nash Equilibria of Bimatrix Games via Payoff Queries (Journal article)

    Fearnley, J., & Savani, R. (n.d.). Finding Approximate Nash Equilibria of Bimatrix Games via Payoff Queries. Retrieved from http://arxiv.org/abs/1310.7419v2

    Learning Equilibria of Games via Payoff Queries (Conference Paper)

    Fearnley, J., Gairing, M., Goldberg, P., & Savani, R. (n.d.). Learning Equilibria of Games via Payoff Queries. Retrieved from http://arxiv.org/abs/1302.3116v4

    Reachability in Two-Clock Timed Automata is PSPACE-complete (Conference Paper)

    Fearnley, J., & Jurdziński, M. (n.d.). Reachability in Two-Clock Timed Automata is PSPACE-complete. doi:10.1016/j.ic.2014.12.004

    DOI: 10.1016/j.ic.2014.12.004

    Synthesis of Succinct Systems (Journal article)

    Fearnley, J., Peled, D., & Schewe, S. (2012). Synthesis of Succinct Systems. Unknown Journal, 208-222. doi:10.1007/978-3-642-33386-6_18

    DOI: 10.1007/978-3-642-33386-6_18

    Time and Parallelizability Results for Parity Games with Bounded Tree and DAG Width (Journal article)

    Fearnley, J., & Schewe, S. (n.d.). Time and Parallelizability Results for Parity Games with Bounded Tree and DAG Width. Logical Methods in Computer Science, Volume 9, Issue 2 (June 18, 2013) lmcs:791. doi:10.2168/LMCS-9(2:6)2013

    DOI: 10.2168/LMCS-9(2:6)2013

    2012

    Bounded Satisfiability for PCTL (Conference Paper)

    Bertrand, N., Fearnley, J., & Schewe, S. (n.d.). Bounded Satisfiability for PCTL. Retrieved from http://arxiv.org/abs/1204.0469v1

    Synthesis of Succinct Systems (Conference Paper)

    Fearnley, J., Peled, D., & Schewe, S. (n.d.). Synthesis of Succinct Systems. Retrieved from http://arxiv.org/abs/1202.5449v2

    Approximate Well-Supported Nash Equilibria Below Two-Thirds (Conference Paper)

    Fearnley, J., Goldberg, P. W., Savani, R., & Sørensen, T. B. (2012). Approximate Well-Supported Nash Equilibria Below Two-Thirds. In Unknown Conference (pp. 108-119). Springer Berlin Heidelberg. doi:10.1007/978-3-642-33996-7_10

    DOI: 10.1007/978-3-642-33996-7_10

    Time and Parallelizability Results for Parity Games with Bounded Treewidth (Conference Paper)

    Fearnley, J., & Schewe, S. (2012). Time and Parallelizability Results for Parity Games with Bounded Treewidth. In AUTOMATA, LANGUAGES, AND PROGRAMMING, ICALP 2012, PT II Vol. 7392 (pp. 189-200). Retrieved from http://gateway.webofknowledge.com/

    2011

    Efficient Approximation of Optimal Control for Continuous-Time Markov Games (Conference Paper)

    Fearnley, J., Rabe, M., Schewe, S., & Zhang, L. (2011). Efficient Approximation of Optimal Control for Continuous-Time Markov Games. In S. Chakraborty, & A. Kumar (Eds.), Foundations of Software Technology and Theoretical Computer Science (FSTTCS) Vol. 13 (pp. 399-410). Dagstuhl: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik. doi:10.4230/LIPIcs.FSTTCS.2011.399

    DOI: 10.4230/LIPIcs.FSTTCS.2011.399

    Efficient Approximation of Optimal Control for Continuous-Time Markov Games (Conference Paper)

    Fearnley, J., Rabe, M., Schewe, S., & Zhang, L. (2011). Efficient Approximation of Optimal Control for Continuous-Time Markov Games. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (pp. (Accepted)). Bombay: Leibniz International Proceedings in Informatics.

    Parity Games On Graphs With Medium Tree-width (Conference Paper)

    Fearnley, J., & Lachish, O. (2011). Parity Games On Graphs With Medium Tree-width. In 36th International Symposium on Mathematical Foundations of Computer Science (pp. 303-314). Warsaw: Springer-Verlag.

    Playing Muller Games in a Hurry (Conference Paper)

    Fearnley, J., & Zimmermann, M. (n.d.). Playing Muller Games in a Hurry. In EPTCS 25, 2010, pp. 146-161. doi:10.4204/EPTCS.25.15

    DOI: 10.4204/EPTCS.25.15

    Strategy iteration algorithms for games and Markov decision processes (Thesis / Dissertation)

    Fearnley, J. (2011). Strategy iteration algorithms for games and Markov decision processes. (PhD Thesis, The University of Warwick).

    2010

    Efficient Approximation of Optimal Control for Markov Games (Journal article)

    Fearnley, J., Rabe, M., Schewe, S., & Zhang, L. (n.d.). Efficient Approximation of Optimal Control for Markov Games. Retrieved from http://arxiv.org/abs/1011.0397v2

    Exponential Lower Bounds For Policy Iteration (Conference Paper)

    Fearnley, J. (n.d.). Exponential Lower Bounds For Policy Iteration. Retrieved from http://arxiv.org/abs/1003.3418v1

    Non-oblivious Strategy Improvement (Conference Paper)

    Fearnley, J. (n.d.). Non-oblivious Strategy Improvement. doi:10.1007/978-3-642-17511-4_13

    DOI: 10.1007/978-3-642-17511-4_13

    Linear Complementarity Algorithms for Infinite Games (Conference Paper)

    Fearnley, J., Jurdzinski, M., & Savani, R. (2010). Linear Complementarity Algorithms for Infinite Games. In SOFSEM 2010: THEORY AND PRACTICE OF COMPUTER SCIENCE, PROCEEDINGS Vol. 5901 (pp. 382-+). Retrieved from http://gateway.webofknowledge.com/

    Linear complementarity algorithms for infinite games (Conference Paper)

    Fearnley, J., Jurdziński, M., & Savani, R. (2010). Linear complementarity algorithms for infinite games. In 36th Conference on Current Trends in Theory and Practice of Computer Science (pp. 382-393). Czech Republic: Springer-Verlag.

    Playing Muller games in a hurry (Conference Paper)

    Fearnley, J., & Zimmermann, M. (2010). Playing Muller games in a hurry. In First International Symposium on Games, Automata, Logics and Formal Verification (pp. 146-162). Minori: EPTCS. Retrieved from http://eptcs.org/content.cgi?GANDALF10