1
$\begingroup$

Context: I play in a simulated online basketball league (a la the NBA) where each human player controls one of the teams. When each simulated basketball player is a free agent (that is, their previous contract with a team has expired) they field offers from teams and a group of moderators decides which team that player will join. Teams have a limited budget, players have different values to different teams, and teams need to be able to bid on more players than they can afford using a list ordered by priority so that they can use all of their budget.

Our current system for handling the free agency period has several problems so I would like to devise a new system.

I would like to write a script that takes in a set of ordered bid lists (one for each team in our league) and outputs an order in which each item should be sent to a decision function (i.e. in this case, the group of moderators that decide among the bids for that item) optimized such that each team wins the auctions for their highest priority bids possible. Lower priority bids may become invalid as a result of teams using their budget by winning higher priority auctions.

I think there will be circular dependencies between auctions such that the algorithm will not be able to determine which should be send to the decision function first, and that's okay as long as that group of circularly dependent auctions is output and the moderators can decide those on a case-by-case basis.

I have found some papers (one, two) about similar scenarios but in these papers the items for auction are identical.

My hunch is that this problem for unbounded N (teams) and M (players) is intractable but for our limited N=30, M~=100 I think it should be possible to compute in a reasonable amount of time. I'm also okay with an approximation instead of an optimal solution, or to find out that no optimal solution exists - just a solution that approaches 'good enough' is good enough for me.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.