Neoclassical Assignment Problem

I'm moving into a house with five other people. There are six bedrooms in the house; we will each get one. Each bedroom is different, in terms of space, location, furnishing, etc; each person has a different taste in rooms. How can we best allocate rooms to people?

This is a pretty obvious problem in welfare economics - given a set of N things, and a set of N actors each with their own utility function for the things, assign the things to the actors in the way that maximises utility.

In the classical paradigm, this is easy to solve: it's called the AssignmentProblem, and there are a number of reasonably efficient algorithms for it (and for the N = 6 case, it's also amenable to brute force).

However, the classical paradigm is old hat - CardinalUtility? is out, OrdinalUtility? is in - and this is the age of neoclassical economics. I want a way to solve this problem neoclassically, using preferences rather than raw utility.

Any suggestions?

-- TomAnderson

This problem is related to voting; rather than combining actors' preferences for things into a collective preference for things, we combine them into a collective assignment of things to actors. Indeed, you can transform this problem into a voting problem by thinking in terms of assignments (specifications of who gets what; more or less the same as permutations of the things), in which case the task is to combine actors' preferences for things into a collective preference for assignments (to get from preferences for things to preferences for assignments, we assume that people prefer one assignment to another if they prefer the thing that they are assigned in it to the that which they are assigned in the other). Now, we know from ArrowsTheorem that there cannot be a perfect social choice function (although there can be very good ones), so one might think that something similar applies to this problem, but it's not obvious that this is true - the transformation step introduces entropy (in that there are preferences for assignments which are not derivable from preferences for rooms), so the assignment problem is, i think, simpler, and so may be solvable (switching fields a bit, just because a P-complete problem can be transformed into an NP-complete problem doesn't make it NP-complete!). -- ta

We can obviously find all the ParetoOptimal solutions by brute force, and perhaps by somewhat cleverer means (BranchAndBound?), and the optimal solution must be one of those. No idea how to choose between them, though! -- ta

Am i making any sense? -- ta

You've defined a nonmetric space, so ParetoOptimal would seem to be completely irrelevant, and preferences certainly allow cycles. This does in fact sound like purely a voting problem, so it would seem that the solution should be a CondorcetMethod?, something like CopelandsMethod?, with cyclic ambiguity resolution. -- dm

Er, surely you can have ParetoOptimality in nonmetric spaces (if i understand that term correctly - OrdinalUtility? isnonmetric)? ParetoOptimal just means that there's no change you can make which makes nobody worse off. In fact, the concept is more appropriate to this situation than in a metric space - Pareto's work is a foundation of neoclassical economics. -- ta

---

I think this is related to fair and envy-free division problems. The problem is not that the devision is fair, that is easy, see e.g.

http://rec-puzzles.org/new/sol.pl/decision/division

To make it envy-free is as far as I know still an open problem. See

http://mathworld.wolfram.com/CakeCutting.html

See EnvyFreeFairDivisionProtocol

Interesting (although the URLs don't actually point to an algorithm), but all this assumes a metric, whereas the requested OrdinalUtility? is inherently nonmetric. -- dm

---

There seems to be something new here:

  http://science.slashdot.org/story/12/04/07/0151200/how-to-share-a-cake-over-the-internet

I looked into the main article

  http://arxiv.org/abs/1203.0100v1

and it seems that this is as fair as it gets even when the participants try to use the game sementics against it (there are quite a few examples, but oberall it is a rather dry article esp. at the end where we hope for the algorithms).