Tournament Scheduler Improvement - Pyosch/powertac-server GitHub Wiki

The text below has fist been send in an e-mail. John has already responded to this. His response is included at the bottom. Later this will be used to create a good page about the possibilities of improving the tournament scheduler.

Suggestions for improving the tournament scheduler

A round in a PowerTAC tournament consists of a number of games. Not all of them can be played at the same time. The number of games that can be played simultaneously is limited by both the number of slaves and the number of available agents. Therefore, a good scheduler is important. This game scheduler has two challenges. First, the length of a tournament needs to be as short as possible, and second, this length should be predictable. The current way of scheduling games does not necessarily provide the best solution for both challenges. A newly proposed scheduler could improve this.

Analyzing the Current Scheduler

In a tournament round a number of brokers play three different game types against each other. Each type is defined by the number of brokers participating in those games and for each possible combination a game is generated. An optional multiplier allows for duplicate games. The length of the games is chosen randomly to make sure that brokers do not know when a game will end and come up with some clever end game tactics that destroy the whole purpose of the tournament. This length is determined when the game starts which also makes it difficult to schedule predictively and efficiently.

During the tournament of 2013 the following numbers applied:

7 brokers
2 agents per broker
5 slaves
4 games with 7 brokers
35 games with 4 brokers
21 games with 2 brokers

It is easy to see that the problem in scheduling lies in the amount of agents, and not in the amount of slaves. There are 60 games (4+35+21) and 210 times an agent is needed to participate in a game (4x7 + 35x4 + 21x2). Assuming each game takes the same amount of time t, with 5 slaves, 60 games could be able to run in a time of 12t. On the other hand, considering that each broker has only two agents, there are no more than 14 agents to use at the same time. This means that when 210 times an agent is needed to participate in a game, this will take at least a time of 15t.

The availability of agents has an even greater impact on efficient and predictable scheduling. Each slave can host every single game that needs to be played, but an agent is only needed in a subset of all the games in that round. Therefore it could be that four agents are available, and there are still games of size four that need to be played, but none of these games can be started, because the agents do not match. In the future, it could well be possible that multiple rounds will be played simultaneously. This would mean that the availability of agents assigned to one round has no influence on the difficulty of scheduling the other round. The question is then, what will be the bottleneck of the schedule? Will it be the number of slaves, or will it be the number of brokers? In either case, a good scheduling algorithm is needed to assure an efficient and predictive tournament schedule.

The current scheduler can be seen as an ad hoc algorithm. At any given time it checks whether a new game can be started. When more than one game can be started, it chooses the one with the most agents. Although this strategy seems highly efficient since it aims at reusing slaves as fast as possible, it appears that it works counterproductive.

Assuming the scheduler works efficiently, there will be many moments when all agents are active in a game. When this is the case and one of these games finishes, the agents who participated in that game are available again. Unfortunately, the game with all these agents is already played, since it is the game that just finished. Thus, the only option to start a new game right away, is to start a game with a subset of the available agents. This means that the smaller games are highly favored in scheduling. This is unfortunate, since it will leave most of the larger games to be scheduled at the end of the tournament. Since they are difficult to combine, it will be extremely difficult to make sure all agents are used simultaneously, making the tournament inefficient and unpredictable.

This effect can be seen in the log files of the latest tournament. With 60 games in total, the last 19 games to finish were all games with four agents which are the most difficult to schedule. To make matters worse, seven of the last nine games to finish were depending on the same broker. As comparison, another broker was participating in only three of these last nine games.

To conclude, the scheduler uses an ad hoc algorithm that starts games as soon as it can. This highly favors the smaller, easy to schedule games. Because of this, later on in the tournament, it will be difficult to schedule the remaining games. Therefore, the available resources, agents and slaves, cannot be used efficiently and it will be difficult to predict when the tournament finishes.

A New Scheduling Method

The proposed method works with slots. A slot is a set of games that are played simultaneously. They start at the same time and when all games in a slot are finished, a new slot can be started. In this way, every time a slot is started, all the agents are available so the most efficient combination of games can be chosen. Of course, the algorithm aims at fitting all the games of a round in as little slots as possible. A smart backtracking algorithm should not have too much trouble in finding a compact schedule for these slots.

Since all games can be scheduled at once, it is easy to give a good estimation of the length of the tournament. Right from the beginning, he amount of slots needed is known. The only unknown feature is the exact length of each of those slots, but a good estimation for those can be given. The length of a slot is determined by the longest game in that slot.

Still, two issues need to be addressed. First, since the length of each game is chosen randomly, it can easily be that a long game is in the same slot as a short game. This would mean that when this short game finishes, the corresponding slave and agents remain idle until the long game finishes, making the use of resources inefficient. A solution would be to choose (roughly) the same length for all games in the same slot. Then, brokers would still not know the length of their game, and the tournament is scheduled more efficiently.

Second, it could be that something goes wrong with a game and it needs to be played again. With a fixed schedule that aims at filling slots, it could be assumed there is no possibility to squeeze this game in the current schedule. This means that when a game fails, all remaining games need to be rescheduled. When initially the round has been scheduled perfectly, a failed game will in general mean that an extra slot needs to be added. However, it is not to be expected that this will cause the tournament round to take more time than when this malfunction would have happened in the current setup. Also, when a second game would fail after that, it could be scheduled in the extra slot. This means that in that case, the length of the tournament will stay the same, which is not to be expected of the current setup.

Thus, the aim of the scheduler is to come up with a schedule that is both efficient and predictable. A scheduler that works with slots is more predictive than the current setup. When all games in the same slot will have (roughly) the same length, it is also much more efficient. When, on the other hand, it is important that the length of the game remains determined at the beginning of that game, instead of per slot, then it is to be assumed that working with slots would still be at least as efficient as the current setup.

Response of John Collins

The length of a game is current determined when the sim server starts, but that's not a requirement. In a tournament setting, game length (or rather the number of timeslots in a game) could be determined by the TS.
Your argument is qualitative, and I am not immediately convinced that this method would result in better resource utilization. You would need to write a small simulator, using the game-length formula in the spec.
Game length is not entirely determined by the number of timeslots. It can also be influenced by network congestion and resource contention, which for example can cause delays in broker logins and clock pauses. It might be interesting to go through the logs and discover something about the relationship between number of timeslots and overall length. Note that overall length should be just the first field (process msec) in the last entry of the trace log. I also do not know how much time is lost between the TS ordering the start of a game and the actual start of the sim process. Also, it would be interesting to know the distribution of the time of the first clock tick after process start in tournament sims.
The slot approach could lead to considerably more resource contention than the current method, simply because all the sims are starting at essentially the same time. The current method distributes the overhead of startup/shutdown pretty evenly.
Keep in mind that each game in a tournament also needs a boot record. With the current scheme, games can start as soon as the first boot record is ready; the other boot records can be generated later by sim hosts that cannot be scheduled due to lack of agent availability.
There's nothing inherently wrong with on-the-fly incremental optimization, but I agree with you that the current greedy method is too simplistic. The problem is not that large; if we compute game lengths ahead of time, it should be possible to solve it with a straightforward A* method, and it could be re-solved whenever there is a "disturbance" such as the need to re-run a game, or a game being delayed beyond some threshold, or perhaps every time we need to start a new game.