Jason Hutchens: marriage problem

Jason Hutchens: marriage problem

A society consists of equal numbers of males and females. Each female knows all the males and vice versa. Each female has a priority list of the males she would like to marry, and vice versa. The task is to marry them all off with the least shortfall in expectations, that is, with maximum of priorities being satisfied.

Let's say that there are X males in a village, and, as luck would have it, there are also X females. Assuming monogamy, each and every bloke is guaranteed a partner, although she may turn out to be more of a ball-and-chain (and vice-versa---let's not be sexist).

Being of a well-organised race, the villagers carry around with them, at all times, a stone tablet, onto which they carve the names of their favourite members of the opposite sex. In fact, they're so fastidious about this that they keep the names of *every* member of the opposite sex, ranked from most desirable (assigned a ranking of 1), to the least desirable (assigned a ranking of X).

Whenever two villagers of the opposite sex meet, they compare notes (so to speak). Each quotes the rank they've assigned the other, so that both parties know their Mutual Attractiveness Factor, which is defined as the sum of the two separate ranks.

Hundreds of years ago, a rather forward-thinking village chief built a chess-board in the centre of the village, containing X*X squares in total. Each row of this board is inscribed with the name of a male villager, while the columns are reserved for the females. Whenever a couple meet, they make a pilgrimage to the board, and place upon the square at the intersection of their names a number of pebbles. The number they choose is always exactly the same as their M.A.F. (due to some ancient tradition, no doubt).

Each spring, when a man's fancy turns to... chess, the village idiot stops playing with his dead rats, and instead sweeps the chess board free of pebbles. He does this with a straw broom, babbling all the while, about such things as "en-pee-'ard" and "low-cal-mini-mah". The village idiot who, fortunately, is hermaphrodite, sweeps the board free of pebbles in a very strange way (using a process which he refers to as a "seaweed-with-musical-timing").

What he does is this: he first looks for a pile of pebbles which, if it were to be swept away, would cause either the row or column which intersects it to become pebble-free. If such a pile is found, it is carefully gathered up and transferred to a leather sack, and the names associated with the row and column are recorded on a list. The row and column are then rather haphazardly swept clear. On the other hand, if no such pile is found, then the largest pile of stones on the board is swept into the forest. In the case when more than one such pile exists, the village idiot selects between them at random (there isn't space here to describe how he makes the selection; suffice it to say that the process involves a chicken, several lengths of twine, and boundless patience).

This process, or "algae-rhythm", is repeated until the board is free of rocks. When this happens, the village idiot hands his list to the local clergyman, who promptly marries all of the couples on it. The idiot then divides his bag of pebbles into 2X evenly-sized groups (which, more often than not, involves smashing the pebbles into bits). The number of pebbles in each group represents the average rank assigned to a person by their partner in marriage (which explains the low divorce rate, perhaps).

Once the weddings have taken place, the village idiot is given a bag of gold by the grateful couples, which he promptly spends on beer and rats.