Add venue rotation feature

[czlee]

The idea is to (automatically) rotate venues so that the same teams aren't always far away in every round. This is probably nontrivial, some preliminary thoughts:

• The primary new information would presumably be some indication of distance attached to each venue. It might be tempting to overload this onto existing fields, for example:

  • We might use "priority" as an inverse of distance.
  • Instead of tying this to venues, we might be tempted to tie it to venue groups for convenience.

  My inclination is against both of these, for the following reasons:

  • Low-priority rooms might not always be far away, for example, they might be a nearby room that's just not very nice.
  • Not all venues in a group, for whatever reason, might be the same distance away. Also, if venues can have multiple groups, the idea of tying distance to venue groups just makes no sense.

  So I think we'd just want to add a new field distance to Venue.

• distance should be a float, and it should be optional. Tabbycat should show a useful error if venue rotation is enabled, and it tries to allocate venues, but any venue lacks a distance.

• We'd have to get this to work with venue constraints somehow. Venue constraints are strict priority, so presumably constraints would always win over rotation.

• We'd have to know venue history, but that's easy enough, because the information's already in the draw.

The natural thing to do would be to allocate the nearest rooms to those debates with teams that have had the farthest history, choosing randomly between those that have the same distance. This wouldn't require any optimization—you just run a strict pairing between an ordered list of venues and an ordered list of debates, with ties in the ordering resolved randomly. But this might have odd effects: It might cause some teams to ricochet between very far rooms and very near rooms, in some circumstances, rather than allowing them a chance at "moderate" rooms at some stage.

[philipbelesky]

This seems like its being made overly complicated. Adding distances on a per-Venue basis is a lot of data entry work that I imagine almost no tournaments would use. Requiring this limits a feature that is most likely strictly better than random allocation to a handful of tournaments rather than making it a broad and universal improvement over random allocation.

I think a much simpler solution that would deliver the vast majority of the benefit would be:

• Constraints always win over rotation
• Assume VenueGroups/Categories are a good enough proxy for distance. For each team prefer finding a Venue in VenueGroup/Category that it has not been before, or (failing that) a VenueGroup/Category it has been in the least.
• Within each assigned VenueGroup/Category check and ensure the actual Venue itself is not a repeat of an earlier allocation.

For this to provide value to small/medium sized tournaments it should work automagically without needing data input that will not be done (I can't see why this wouldn't be default-enabled). At large/extra-large tournaments there are typically 5-10 location based categories (green, red, etc) with huge amounts of venues and smaller numbers of 'marker' categories (accessible, tab-adjacent).

The marker categories are mostly assigned via constraints, and have few enough rooms that they wouldn't really distort the results. Because they overlap with a location-based category as well I think the 'prefer a new category' rule would still have the intended effect regardless. As a general rule the amount of location-based categories is roughly similar (+/- 50%) to the number of rounds so rotating through them is going to avoid 99% of the "I had four rounds in the middle-of-no-where block" scenarios that spur the need for this feature.

If we must require some new bit of information to precisely optimise distances travelled it should definitely be added as an optional field for VenueGroups/Categories. Even then it could just be a Boolean — disregard_for_rotation or something that demarcates which Categories should be skipped.

Also if we do go with some sort of option that requires a distance it definitely shouldn't throw an error when a distance is not set — it should fall back on some a sensible proxy like VenueGroups/Category (as described above) to ensure a good-enough rotation.

[czlee]

Following offline discussion, here's where I think we're at:

1. There are three options: random, group rotation and distance rotation.
2. Distance rotation is what I outlined above: it tries to give teams that have walked far nearer rooms, and vice versa. I think this is the level of complexity we'd want to do for a tournament with as many rooms as WUDC.
3. Group rotation is what you outlined above: it tries to give teams different groups in every round, but doesn't know anything about about how far/near they are.
4. Distance and group rotation are fairly different ideas, so would just be different algorithms.

I think there are subtle details left to work out regarding exactly which one is used and when and what happened when there is incomplete data (even group rotation requires every venue to have a group), but as a rough idea:

• Group rotation could be the default if the requisite data exists.
• Distance rotation requires user input of distances, so would require active user opt-in.

[tienne-B]

I'd be interested in exploring venue allocation.

There are many more possible objectives than what it seems here; to get everyone to walk the same distance on average. I think that objective is actually one of the least important. Walking is really no big deal (except with reduced mobility; but that is handled with constraints). With the data that is already available, an objective that would be easily implemented and could be preferred is the quality of the rooms (which may include distance in score calculation). It seems that the quality is somewhat conflated with distance. People may rather walk a little more for a nice room than be near to a poor one :)

I do like @philipbelesky's group rotation, but believe the objective should be flipped; rather than rotating teams to be in the most different groups, that it would be preferable to preferentially keep teams in the same group (or near). If rooms are hard to find (and they often are), it is better to have an idea of the area (as you've already been near) to easily find the room. I prefer familiarity to exploration :)

To improve on this, It would be useful for VenueCategoryies to be subsets of other categories. I agree for the new rotate boolean field to determine whether to use for this purpose, which would exclude the "marker" categories.

[czlee]

Hmm, maybe. I can see how this would be highly context-dependent. But the main use case for a feature like this is very large tournaments like WUDC, where rooms can be as far as 10 minutes away, which (given you have 15 minutes before the debate starts) is very annoying if you're having to do it repeatedly.

At WUDC, because it's large and international and high-stakes, organizers tend to have signs plastered and people stationed everywhere, so that you can't have trouble finding a room. So while this is a problem at something like Yale IV, it's not really a routine problem for WUDC. You're of course right that we're using "distance" as an inverse proxy for "quality", and that we could use a more generic term to capture different notions of how desirable rooms are and what to factor into the rotation. But in the use case we were thinking of, distance is in fact a very good proxy.

You do provide a case for why this shouldn't be enabled by default, though, I guess? If some tournaments will want to try to rotate teams between venues, and other tournaments will want to do the opposite…

[tienne-B]

Could be simple to use the Hungarian algorithm to assign debates to venues. This would entail needing to set weights (preferences?) for the constraints. As the two objectives are pretty much opposite, there could be an option to "flip" it (probably not as simple as that). Thoughts on creating a category hierarchy?

[czlee]

What do you mean by category hierarchy? Do you mean the category subset thing? We had concerns about overcomplicating this in the discussion above (see @philipbelesky's first comment); in principle I'd like it to be exactly as complicated as a real-world tournament (say, WUDC, but could be another tournament) is known to need it to be, and no more.

[philipbelesky]

I'd prefer to try and work with the model structure we have — this feature is probably going to be a minor enhancement to the very largest tournaments but otherwise not particularly useful. So, given that, I don't think we want to add extra complexity to the general use case of venues by adding in additional data entry considerations such as a category hierarchy

Returning to my earlier comment, I'd be fine with either priority or category being used as a proxy for desirability/distance/whatever. Not sure how compatible that is with the Hungarian allocator — it seems something more akin to position rotation might be a good fit?

[tienne-B]

Yeah, subsets are not really necessary, and the effect would be similar to just having venues in many categories.

I do think however that venue optimisation is more than just minor, and that it would be appreciated in smaller tournaments as well! :) I'd go with the group rotation. I see venue allocation as a simple assignment problem between debates (with panels) and venues. That makes the Hungarian algorithm applicable. The Hungarian allocator that exists for pairings may not be applicable though.

I do not understand how position rotation could be similarly used (and the Hungarian algorithm is used for position rotation in BP AFAIK).

[czlee]

Yeah, the Hungarian algorithm's pretty agnostic to exactly how you assign costs to venue assignments. All you need to be able to do is define a cost matrix C comprising costs c(v,d) for every venue v (say, rows of the matrix) and every debate d (say, columns). The algorithm then just finds the venue-debate pairing minimizing the total cost. We currently use it for both adjudicator allocation and position rotation; the costs for each are defined differently. (It's actually an assignment problem; the Hungarian algorithm is just one algorithm for solving it.)

[tienne-B]

Removing from WUDC 2022 as it'll be online.