DRMacIver's Notebook

Follow on to misc thoughts about voting design for talk scheduling.

Here's how a system that is much closer to classic STV could work. Assume everyone has a ranking of all the talks they wish to attend (this isn't actually reasonable to ask for, but you could get people to score talks according to some ordinal scores and then randomly tie break, or tie break in organiser preferred order or something).

The system has the following three parameters:

  1. The number of time slots.
  2. The number of talks per time slot.
  3. The minimum number of attendees required for a talk to be worthwhile (should be at least one). Callt his the threshold.

You also need to pick a quota system. Either the Droop or the Hare quota are the obvious choices. My natural bias is to use the Hare quota, as it's better for minority interests and I think that's a nice feature to have in your conference talk selection (conferences have a tendency to have the same talks over and over again and I think this would help offset that).

The system could easily be adapted to more complicated constraints in which not all talk/time slot combinations are valid, but I'm going to ignore that.

Conceptually what happens is everyone is given one voting-buck, and a talk slot "costs" an amount of voting-bucks equal to the quota. People band together to form buying blocs and each spend the same percentage of their remaining pool of voting money to buy a slot (this is basically how normal STV works too).

The system involves running the following process to a fixed point:

  1. Set the list of eligible talks to all talks which have at least the threshold number of people voted for them.
  2. Give everyone exactly one vote (note: as the process evolves, people will have fractional votes).
  3. People vote for (talk, slot) pairs, where the slot has not already been filled and the talk is both eligible and not yet scheduled. They will vote for a pair if:
    1. The talk their highest ranked talk among the available talks.
    2. If there are slots which have no talks they want to see in them, they will only vote for pairs in those slots. Otherwise they will vote for pairs where they prefer the talk to the one currently scheduled there. Note that a voter can vote for multiple (talk, slot) pairs.
  4. If there are no such pairs, we have scheduled all of the talks we can (even if there still unfilled slots). Stop and report this as the schedule.
  5. If any of the pairs has a total number of votes exceeding the quota, pick the one with the most votes and schedule that. For each voter who voted for it, multiply their remaining vote by \(1 - \frac{q}{r}\), where \(q\) is the quota and \(r\) is the total vote for the elected slot (i.e. we've removed \(q\) from their total vote and everybody pays it equally).
  6. If no pair was elected, take the talk with the lowest maximum vote over all vote pairs, and remove it from the list of eligible talks.
  7. If a pair was elected, now check if any talks can no longer meet the threshold - i.e. if for every slot you could schedule them in, count the number of people for whom that is their favourite talk in that slot. If there are no slots where this exceeds the threshold, remove the talk from the eligible list.
  8. If we removed any talks from the eligible list, reset all of the state except the list of eligible talks and go back to step 2. Otherwise go back to step 3.

Most of this is just variant STV, with some of the specific details owing to specific types of STV. The main difference is that because the same voter may cast their vote for multiple options simultaneously, we need to be careful not to elect more than one "candidate" at once, plus the specialised drop-out rule for talks that fail to meet the threshold.

Most of my problems with it are the same as my problems with STV in general: It looks like an iterative optimisation process, but it's not at all clear what it is you are optimising for. So it might work well, but I'm not really sure how you would measure "well" in this context. It seems plausibly worth a try though.