So, I have some prizes and a list of winners to distribute them to. Every winner can name the prizes they’d like to get and the prizes they’d prefer not to get. Is there a mathematical solution to this kind of problem? A kind of solution similar to what I had to go through as a kid with my sister: One of us gets to cut something in half and the other gets to pick first. Some old *Scientific American* article I should read? 😄 Right now I just use my intuition to solve this “best fit” problem. It’s not bad, but I’d love to be able to say that I can *prove* that I’ve been as fair as possible.
#RPG #Math #1PDC
(Please contact me if you want to remove your comment.)
⁂
I love that you are taking the time to agonize over this. Good luck on distribution, I have no clue as to optimal distribution systems.
Well, except that it would be optimal if I got my choices and screw everyone else. ;)
– Dyson Logos 2011-05-16 21:02 UTC
---
I don’t even know the correct jargon to help me google for an answer. Simplistic googling finds statements such as these on StackOverflow: “You want to look for a job-assignment algorithm, or a Hungarian algorithm for example a weighted perfect match in a bipartite graph, or maybe the all-pair Floyd-Warshall algorithm. My idea is that this can be represent as a bipartite graph.” ¹
Yikes! :braindamaged:
– Alex Schroeder 2011-05-16 22:47 UTC
---
Argh... big words make tiny head hurt.
Imagine that Prizes are magnetically drawn to Winners.
When a winner wants a prize, there is more pull to that prize (magnetism+1). When a winner doesn’t want it, the pull is lessened (magnetism-1).
Each Prize is drawn to the Winner with the greatest pull.
If multiple winners want the same prize the same amount, the prize is randomly or humanly distributed and the winner is removed from the group.
Something like that?
– Marco 2011-05-17 08:45 UTC
---
That is more or less my intuitive method. 😄 The number of nominations received also produces tiers, which allow me to go by small groups. Within each tier, I try to give everybody what the want. In the case of a tie, I look at second choices. If one of them has indicated that there is no strong priority, then that one gets second choice. Or random. I try to avoid random, though. Repeat for all tiers, then return to the top—since we have multiple prizes. The prizes that have not shown up on a wish list get distributed at random while avoiding black lists.
– Alex Schroeder 2011-05-17 09:07 UTC
---
But the tips are good - it is a bipartite graph, with all winners in one set and all the prizes in the other. You can just ask every winner to give you an order of their prize preference and use that to weigh the edges.
– Jonas 2011-05-17 12:53 UTC
---
Hm, you are right! Now I just need to quickly write an implementation of Dulmage–Mendelsohn decomposition using Perl… 😄
Dulmage–Mendelsohn decomposition
– Alex Schroeder 2011-05-17 13:10 UTC
---
Well, the problem is clearly that you write code in perl, not the algorithm itself 😄
– Jonas 2011-05-17 13:14 UTC
---
Hahaha. Well, there’s code in MATLAB ².
– Alex Schroeder 2011-05-17 13:17 UTC
---
There’s a bit in Cryptonomicon where the professor divides up an inheritance. I’m a bit hazy on the details but the thrust of the argument was based on the fact that the items were heavy and thus making people carry them was a good measure of the desirability of the item.
You could also ask Tim Harford.
– AlokSingh 2011-05-19 08:02 UTC
---
Oh man, you know this isn’t worth the effort when Cryptonomicon gets quoted 😄
– Adrian 2011-05-20 13:59 UTC
---
Hahaha! It’s an intriguing mental exercise. But for this contest at least, I’m already through half the loot to be distributed...
– Alex Schroeder 2011-05-20 17:00 UTC