Suppose I have n individuals and n unique, indivisible objects of potential value. I want to allocate those objects so as to make total welfare as great as possible, subject to the constraint that no single individual is hurt too badly by the allocation.

Now, if this were a voting situation where we were choosing a single policy, one approach would be to use the Borda count (BC) The BC is sometimes said to promote consensus, as it considers the rankings of everyone in such a way that it rarely selects an outcome preferred by the majority if there is a substantial minority that can not live with it.

It is also pretty easy to understand and to administer. It produces an outcome from rankings (semi-strict directed graphs (ties allowed) over each person's own allocation (only), without requiring inter-personally comparable cardinal utility. As a result, it is most justified when individuals can be said to hold their preferences with comparable intensity, or if we choose to regard them as comparable because we believe that everyone's preferences should be given equal weight.

So my question is whether there is a feasible algorithm to allocate n items among n individuals in such a way as to maximize the BC. Assume that n is large enough that a brute force approach of testing every possible outcome is infeasible.

I would also welcome pointers to other algorithms likely to produce comparably good results overall with a lower computational cost.

  • $\begingroup$ Selling mechanisms can do the job. $\endgroup$ – superhulk Feb 13 '19 at 16:03
  • $\begingroup$ Why is it computationally difficult to maximise the Borda Count? $\endgroup$ – user17900 Feb 14 '19 at 0:28
  • $\begingroup$ Why not the Nobel-worthy Gale-Shapley deferred acceptance algorithm? $\endgroup$ – Herr K. Feb 14 '19 at 4:40

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.