computer science

Random priority item allocation

Random priority item allocation is a computer science topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Random priority item allocation rather than just read about it. In short: Random priority (RP), also called random serial dictatorship (RSD), is a procedure for fair random assignment - dividing indivisible items fairly among people. Suppose n {\displaystyle n} partners have to divide n {\displaystyle n} (or fewer) different items among them.

Key takeaways

Random priority item allocation belongs to computer science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Random priority item allocation to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Random priority item allocation from memory before moving on to harder problems.

Reference excerpt

Random priority (RP), also called random serial dictatorship (RSD), is a procedure for fair random assignment - dividing indivisible items fairly among people. Suppose n {\displaystyle n} partners have to divide n {\displaystyle n} (or fewer) different items among them. Since the items are indivisible, some partners will necessarily get the less-preferred items (or no items at all). RSD attempts to insert fairness into this situation in the following way. Draw a random permutation of the agents from the uniform distribution. Then, let them successively choose an object in that order (so the first agent in the ordering gets first pick and so on).

Properties RSD is a truthful mechanism when the number of items is at most the number of agents. Given only one opportunity to pick an item, an obviously dominant strategy in this opportunity is to pick the best available item. RSD always yields an ex-post Pareto efficient (PE) outcome. Moreover, in an assignment problem, every deterministic PE assignment is the outcome of SD for some ordering of the agents. However, RSD is not ex-ante PE when the agents have Von Neumann-Morgenstern utilities over random allocations, i.e., lotteries over objects (Note that ex-ante envy-freeness is weaker than ex-post envy-freeness, but ex-ante Pareto-efficiency is stronger than ex-post Pareto-efficiency). As an example, suppose there are three agents, three items and the VNM utilities are:

RSD gives a 1/3 chance of every object to each agent (because their preferences over sure objects coincide), and a profile of expected utility vector (0.6, 0.4, 0.4). But assigning item y to Alice for sure and items x,z randomly between Bob and Carl yields the expected utility vector (0.8, 0.5, 0.5). So the original utility vector is not Pareto efficient. Moreover, when agents have ordinal rankings, RSD fails even the weaker property of sd-efficiency. When the rankings of the agents over the objects are drawn uniformly at random, the probability that the allocation given by RSD is ex-ante PE approaches zero as the number of agents grows. An alternative rule, the probabilistic-serial rule, is sd-efficient (which implies ex-post PE) and sd-envy-free (which implies ex-ante envy-freeness), but it is not truthful. It is impossible to enjoy the advantages of both mechanisms:

With cardinal additive utility functions, no mechanism is symmetric, truthful and ex-ante PE. With ordinal utility functions, no mechanism is sd-efficient, strategyproof, and treats equals equally.

Generalizations

More objects than agents When there are more than n {\displaystyle n} objects, some agents may get more than one object. There are several ways to extend RSD to this case.

One way is to define a quota for each agent (such that the sum of quotas equals the number of objects), and let each agent in turn pick items up to his/her quota. This procedure remains strategyproof, but it is very unfair. Another way is to let each agent pick a single object, and then do another round in which each agent picks a single object, until all objects are taken; this leads to the round-robin item allocation procedure. This procedure is fairer, but it is not strategyproof. Both procedures are special cases of a picking sequence.

General decision-making RSD can be defined for the more general setting in which the group has to select a single alternative from a set of alternatives. In this setting, RSD works as follows: First, randomly permute the agents. Starting with the set of all alternatives, ask each agent in the order of the permutation to choose his favorite alternative(s) among the remaining alternatives. If more than one alternative remains after taking the preferences of all agents into account, RSD uniformly randomizes over those alternatives. In the item division setting mentioned earlier, the alternatives correspond to the allocations of items to agents. Each agent has large equivalence classes in his preference, since he is indifferent between all the allocations in which he gets the same item. In this general setting, if all agents have strict preferences over the alternatives, then RSD reduces to drawing a random agent and choosing the alternative that the agent likes best. This procedure is known as random dictatorship (RD), and is the unique procedure that is efficient and strategyproof when preferences are strict. When agents can have weak preferences, however, no procedure that extends RD (which includes RSD) satisfies both efficiency and strategyproofness.

See also The page on fair random assignment compares RSD to other procedures for solving the same problem, such as the probabilistic-serial rule. The page on dictatorship mechanism describes RSD is a general rule for social choice - not necessarily for item allocation.

References

Worked examples

Example 1 — a first encounter with Random priority item allocation

Start with the simplest possible case. Write down what Random priority item allocation claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In computer science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Random priority item allocation before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Random priority item allocation ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Random priority item allocation

In research: Random priority item allocation appears in computer science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Random priority item allocation in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Random priority item allocation is common in secondary-school and first-year university syllabi. It links to neighbouring topics Fair division protocols, Randomized algorithms, so understanding it makes those chapters shorter.
In everyday life: Look for Random priority item allocation outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Random priority item allocation in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Random priority item allocation means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Random priority item allocation out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Random priority item allocation in simple terms?

Why does Random priority item allocation matter?

Because it connects several computer science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Random priority item allocation?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Random priority item allocation.