Arrow Research search

Author name cluster

Paul Stursberg

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers
1 author row

Possible papers

4

AIJ Journal 2018 Journal Article

Fixing balanced knockout and double elimination tournaments

  • Haris Aziz
  • Serge Gaspers
  • Simon Mackenzie
  • Nicholas Mattei
  • Paul Stursberg
  • Toby Walsh

Balanced knockout tournaments are one of the most common formats for sports competitions, and are also used in elections and decision-making. We consider the computational problem of finding the optimal draw for a particular player in such a tournament. The problem has generated considerable research within AI in recent years. We prove that checking whether there exists a draw in which a player wins is NP-complete, thereby settling an outstanding open problem. Our main result has a number of interesting implications on related counting and approximation problems. We present a memoization-based algorithm for the problem that is faster than previous approaches. Moreover, we highlight two natural cases that can be solved in polynomial time. All of our results also hold for the more general problem of counting the number of draws in which a given player is the winner. Finally, we show that our main NP-completeness result extends to a variant of balanced knockout tournaments called double-elimination tournaments.

Details DOI

IJCAI Conference 2016 Conference Paper

Interdependent Scheduling Games

  • Andres Abeliuk
  • Haris Aziz
  • Gerardo Berbeglia
  • Serge Gaspers
  • Petr Kalina
  • Nicholas Mattei
  • Dominik Peters
  • Paul Stursberg

We propose a model of interdependent scheduling games in which each player controls a set of services that they schedule independently. A player is free to schedule his own services at any time; however, each of these services only begins to accrue reward for the player when all predecessor services, which may or may not be controlled by the same player, have been activated. This model, where players have interdependent services, is motivated by the problems faced in planning and coordinating large-scale infrastructures, e. g. , restoring electricity and gas to residents after a natural disaster or providing medical care in a crisis when different agencies are responsible for the delivery of staff, equipment, and medicine. We undertake a game-theoretic analysis of this setting and in particular consider the issues of welfare maximization, computing best responses, Nash dynamics, and existence and computation of Nash equilibria.

PDF Details

AAAI Conference 2014 Conference Paper

A Generalization of Probabilistic Serial to Randomized Social Choice

  • Haris Aziz
  • Paul Stursberg

The probabilistic serial rule is one of the most wellestablished and desirable rules for the random assignment problem. We present the egalitarian simultaneous reservation social decision scheme — an extension of probabilistic serial to the more general setting of randomized social choice. We consider various desirable fairness, efficiency, and strategic properties of social decision schemes and show that egalitarian simultaneous reservation compares favorably against existing rules. Finally, we define a more general class of social decision schemes called simultaneous reservation, that contains egalitarian simultaneous reservation as well as the serial dictatorship rules. We show that outcomes of simultaneous reservation characterize efficiency with respect to a natural refinement of stochastic dominance.

PDF Details

AAAI Conference 2014 Conference Paper

Fixing a Balanced Knockout Tournament

  • Haris Aziz
  • Serge Gaspers
  • Simon Mackenzie
  • Nicholas Mattei
  • Paul Stursberg
  • Toby Walsh

Balanced knockout tournaments are one of the most common formats for sports competitions, and are also used in elections and decision-making. We consider the computational problem of finding the optimal draw for a particular player in such a tournament. The problem has generated considerable research within AI in recent years. We prove that checking whether there exists a draw in which a player wins is NP-complete, thereby settling an outstanding open problem. Our main result has a number of interesting implications on related counting and approximation problems. We present a memoization-based algorithm for the problem that is faster than previous approaches. Moreover, we highlight two natural cases that can be solved in polynomial time. All of our results also hold for the more general problem of counting the number of draws in which a given player is the winner.

PDF Details
v2026.09.13