The Brams–Kilgour–Klamler (BKK) procedures are several procedures for fair item assignment between two (and sometimes more) people. Their main advantage is that they do not require the people to specify numeric valuations to items, or to rank bundles of items. All the agents have to report is their ranking over individual items. The guarantees of the procedures are valid for every additive utility function that is consistent with the ranking.
Requirements edit
All the BKK procedures make the following assumptions on the people:
- Each person can rank the items from best to worst (i.e, each person can report a strict preference relation on the items).
- Each person has a preference relation on bundles of items which is compatible with the responsive set extension of the ordering on items.
It is not assumed that the people can report their preference relation on bundles. There are many bundles, and it may be difficult to report a ranking on all of them.
Therefore, the procedure should return an allocation that is fair for every preference relation that is consistent with the item ranking. In other words, the procedure should return an allocation that is necessarily envy-free (NEF).[1]: 303
Suppose the two people are Alice and George. An allocation is NEF for Alice if there is an injection f from George's items to Alice's items, such that for each item x received by George, Alice prefers f(x) to x. An allocation is NEF for George if the symmetric property is satisfied. An item assignment is NEF if it is NEF for both partners. Note that in a NEF assignment, Alice and George receive the same number of items.
BT procedure edit
As an introduction, consider the following simple division procedure:
- Put all items on the table.
- While there are items on the table, do:
- Ask the partners to choose their favorite item from all items on the table.
- If the choices are different, then give each partner his/her favorite item and continue.
- If the choices are identical, then send the chosen item to the Contested Pile. It will not be allocated.
This procedure returns a NEF allocation. It is very simple but not very efficient, since many items are discarded to the contested pile. The AL procedure is slightly more complicated, but it guarantees that the contested pile is never larger, and may be smaller than under BT.
AL procedure edit
The AL procedure finds an envy-free item assignment. The resulting allocation is second-best Pareto efficient. I.e, there is no other envy-free allocation which is better for one person and not worse for the other person.
The AL procedure was first published by Brams and Kilgour and Klamler.[2] It was later generalized by Haris Aziz to handle the case where agents may express indifferences.[3]
The AL procedure works similarly to the BT procedure, but, before moving an item to the contested pile, it tries to allocate it to one partner while compensating the other partner with another item. Only if this doesn't succeed, the item is sent to the contested pile.
For example, suppose there are 4 items (1, 2, 3, 4) and the preferences of the partners are:
- Alice: 1 > 2 > 3 > 4
- George: 2 > 3 > 4 > 1
The BT procedure gives 1 to Alice and 2 to George, since these are their favorites and they are different. Then, both Alice and George choose 3 so it is discarded. Then, both choose 4 so it is also discarded. The final allocation is: Alice←{1}, George←{2}. It is NEF but not PE.
The AL procedure also starts by giving 1 to Alice and 2 to George. Then, instead of discarding item 3, it is given to Alice, and George is compensated with item 4. The final allocation is: Alice←{1,3}, George←{2,4}. It is NEF and PE.
Both procedures are manipulable: a partner can gain by reporting incorrect preferences. However, such manipulation requires knowledge of the other partner's preferences, so it is difficult in practice.
AL procedure with indifferences edit
The original AL procedure crucially relies on the assumption that the item rankings are strict.
Aziz[3] generalized this procedure to general rankings, with possible indifferences.
SD procedure edit
The SD (Singles-Doubles) procedure [4] finds an allocation that is rank-maximin - it maximizes the minimum rank of items that the agents receive. Moreover, if there exists a PO+EF allocation, it will be returned.
SA procedure edit
The SA (Sequential-Allocation) procedure ...
References edit
- ^ Brandt, Felix; Conitzer, Vincent; Endriss, Ulle; Lang, Jérôme; Procaccia, Ariel D. (2016). Handbook of Computational Social Choice. Cambridge University Press. ISBN 9781107060432. (free online version)
- ^ Brams SJ, Kilgour DM, Klamler C (1 February 2014). "Two-Person Fair Division of Indivisible Items: An Efficient, Envy-Free Algorithm". Notices of the American Mathematical Society. 61 (2): 130. doi:10.1090/noti1075.
- ^ a b Aziz, Haris (2015). "A generalization of the AL method for fair allocation of indivisible objects". Economic Theory Bulletin. 4 (2): 307. doi:10.1007/s40505-015-0089-1.
- ^ Brams, Steven J.; Kilgour, D. Marc; Klamler, Christian (2016). "Maximin Envy-Free Division of Indivisible Items". Group Decision and Negotiation. 26: 115. doi:10.1007/s10726-016-9502-x.