Fair choice allocation using Edmonds Karp, adding group choices

33 Views Asked by At

I have an algorithm that uses Edmonds-Karp algorithm to distribute users into groups in a fair manner given a rating for their choice of groups. Currently a given graph for two users ($u1$, $u2$) and two available choices ($c1$, $c2$) might look like this.

image of graph:
Link to image of graph, sorry cant post images yet

The weights on the edges represent the user's preference for the given choice. The shortest path is repeatedly searched until all users have been distributed. A distribution is represented by a path being chosen as the shortest. $(s, u1, c2, t)$ represents "user1" being distributed into "choice2".

Now I want to add the ability for users to make their choices in groups. My requirements for this are as follows:

  1. Users that made their choice as a group should not have an advantage over users that did not
  2. If there is space in a choice for a group, that choice should be preferred
  3. If there is no space for a group, users of that group should be distributed individually, with the same weights as users without a group

My idea was to represent groups by user nodes being linked by an edge with weight $0$. So if "user1" and "user2" were in a group the graph might look like this.

Graph with groups

This was easy enough to implement and satisfies requirements $1$ and $3$, however it does not satisfy requirement $2$, as the individual paths have the same weight as those that go through multiple users.

How can I modify the graph in a way that satisfies all three requirements. Is this even possible? Help would be so greatly appreciated, I am really starting to doubt my sanity over this.

Update: I have managed to think of a solution using a graph with lower bounds, upper bounds and costs per edge. However now the problem has become finding an algorithm that can calculate the max flow for such a graph. The only one I found is the Out-Of-Kilter-Algorithm. I couldn't find any implementation for that one though, only this one https://github.com/MichalNowicki/NumericalAlgebraCodes which produces solutions that dont conserve flow (so basically, not solutions). Is there a better algorithm for this or implementations for that algorithm that work?