An exact analysis of stable allocation

Details An exact analysis of stable allocation An exact analysis of stable allocation

1995-03-20

arxiv.org/abs/math/9503235v1

J. Algorithms 20 (1996), no. 2, 431--44

Mathematics

Optimization and Control

Scientific paper

Shapley and Scarf introduced a notion of stable allocation between traders and indivisible goods, when each trader has rank-ordered each of the goods. The purpose of this note is to prove that the distribution of ranks after allocation is the same as the distribution of search distances in uniform hashing, when the rank-orderings are independent and uniformly random. Therefore the average sum of final ranks is just $(n+1)H_n-n$, and the standard deviation is O(n). The proof involves a family of interesting one-to-one correspondences between permutations of a special kind.

Affiliated with

Also associated with

No associations

Rating

An exact analysis of stable allocation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An exact analysis of stable allocation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An exact analysis of stable allocation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-328443