Envy-graph procedure
The envy-graph procedure (also called the envy-cycles procedure) is a procedure for fair item allocation. It can be used by several people who want to divide among them several discrete items, such as
Maximin share
Maximin share (MMS) is a criterion of fair item allocation. Given a set of items with different values, the 1-out-of-n maximin-share is the maximum value that can be gained by partitioning the items i
Picking sequence
A picking sequence is a protocol for fair item assignment. Suppose m items have to be divided among n agents. One way to allocate the items is to let one agent select a single item, then let another a
Selfridge–Conway procedure
The Selfridge–Conway procedure is a discrete procedure that produces an envy-free cake-cutting for three partners. It is named after John Selfridge and John Horton Conway. Selfridge discovered it in 1
Even–Paz protocol
The Even–Paz algorithm is an computationally-efficient algorithm for fair cake-cutting. It involves a certain heterogeneous and divisible resource, such as a birthday cake, and n partners with differe
Random priority item allocation
Random priority (RP), also called Random serial dictatorship (RSD), is a procedure for fair random assignment - dividing indivisible items fairly among people. Suppose partners have to divide (or fewe
Levmore–Cook moving-knives procedure
The Levmore–Cook moving-knives procedure is a procedure for envy-free cake-cutting among three partners. It is named after Saul X. Levmore and Elizabeth Early Cook who presented it in 1981.It assumes
Barbanel–Brams moving-knives procedure
The Barbanel–Brams rotating-knife procedure is a procedure for envy-free cake-cutting of a cake among three partners. It makes only two cuts, so each partner receives a single connected piece. Its mai
Proportional-fair scheduling
Proportional-fair scheduling is a compromise-based scheduling algorithm. It is based upon maintaining a balance between two competing interests: Trying to maximize total throughput of the network (wir
Fair pie-cutting
The fair pie-cutting problem is a variation of the fair cake-cutting problem, in which the resource to be divided is circular. As an example, consider a birthday cake shaped as a disk. The cake should
Brams–Taylor–Zwicker procedure
The Brams–Taylor–Zwicker procedure is a protocol for envy-free cake-cutting among 4 partners. The procedure uses a variation of Austin's procedure for two partners and general fractions. That procedur
Strongly-proportional division
A strongly-proportional division (sometimes called super-proportional division) is a kind of a fair division. It is a division of resources among n partners, in which the value received by each partne
Simultaneous eating algorithm
A simultaneous eating algorithm (SE) is an algorithm for allocating divisible objects among agents with ordinal preferences. "Ordinal preferences" means that each agent can rank the items from best to
AL procedure
The AL procedure is a procedure for fair item assignment between two people. It finds an envy-free item assignment of a subset of the items. Moreover, the resulting allocation is Pareto efficient in t
Truthful cake-cutting
Truthful cake-cutting is the study of algorithms for fair cake-cutting that are also truthful mechanisms, i.e., they incentivize the participants to reveal their true valuations to the various parts o
Simmons–Su protocols
The Simmons–Su protocols are several protocols for envy-free division. They are based on Sperner's lemma. The merits of these protocols is that they put few restrictions on the preferences of the part
Stromquist moving-knives procedure
The Stromquist moving-knives procedure is a procedure for envy-free cake-cutting among three players. It is named after who presented it in 1980. This procedure was the first envy-free moving knife pr
Decreasing Demand procedure
The Decreasing Demand procedure is a procedure for fair item allocation. It yields a Pareto-efficient division that maximizes the rank of the agent with the lowest rank. This corresponds to the Rawlsi
Brams–Taylor procedure
The Brams–Taylor procedure (BTP) is a procedure for envy-free cake-cutting. It explicated the first finite procedure to produce an envy-free division of a cake among any positive integer number of pla
Adjusted winner procedure
Adjusted Winner (AW) is a procedure for envy-free item allocation. Given two agents and some goods, it returns a partition of the goods between the two agents with the following properties: 1.
* Envy
Truthful resource allocation
Truthful resource allocation is the problem of allocating resources among agents with different valuations over the resources, such that agents are incentivized to reveal their true valuations over th
Round-robin item allocation
Round robin is a procedure for fair item allocation. It can be used to allocate several indivisible items among several people, such that the allocation is "almost" envy-free: each agent believes that
Undercut procedure
The undercut procedure is a procedure for fair item assignment between two people. It provably finds a complete envy-free item assignment whenever such assignment exists. It was presented by Brams and
Weighted fair queueing
Weighted fair queueing (WFQ) is a network scheduling algorithm. WFQ is both a packet-based implementation of the generalized processor sharing (GPS) policy, and a natural extension of fair queuing (FQ
Last diminisher
The last diminisher procedure is a procedure for fair cake-cutting. It involves a certain heterogenous and divisible resource, such as a birthday cake, and n partners with different preferences over d
Rental harmony
Rental harmony is a kind of a fair division problem in which indivisible items and a fixed monetary cost have to be divided simultaneously. The housemates problem and room-assignment-rent-division are
Divide and choose
Divide and choose (also Cut and choose or I cut, you choose) is a procedure for fair division of a continuous resource, such as a cake, between two parties. It involves a heterogeneous good or resourc
Partial allocation mechanism
The Partial Allocation Mechanism (PAM) is a mechanism for truthful resource allocation. It is based on the max-product allocation - the allocation maximizing the product of agents' utilities (also kno
Edmonds–Pruhs protocol
Edmonds–Pruhs protocol is a protocol for fair cake-cutting. Its goal is to create a partially proportional division of a heterogeneous resource among n people, such that each person receives a subset
Lone divider
The lone divider procedure is a procedure for proportional cake-cutting. It involves a heterogenous and divisible resource, such as a birthday cake, and n partners with different preferences over diff
Surplus procedure
The surplus procedure (SP) is a fair division protocol for dividing goods in a way that achieves proportional equitability. It can be generalized to more than 2=two people and is strategyproof. For th
Fink protocol
The Fink protocol (also known as Successive Pairs or Lone Chooser) is a protocol for proportional division of a cake. Its main advantage is that it can work in an online fashion, without knowing the n
Robertson–Webb envy-free cake-cutting algorithm
The Robertson–Webb protocol is a protocol for envy-free cake-cutting which is also near-exact. It has the following properties:
* It works for any number (n) of partners.
* It works for any set of w
Hill–Beck land division problem
The following variant of the fair cake-cutting problem was introduced by Ted Hill in 1983. There is a territory D adjacent to n countries. Each country values the different subsets of D differently. T
Chore division
Chore division is a fair division problem in which the divided resource is undesirable, so that each participant wants to get as little as possible. It is the mirror-image of the fair cake-cutting pro
Envy minimization
In computer science and operations research, the envy minimization problem is the problem of allocating discrete items among agents with different valuations over the items, such that the amount of en
Austin moving-knife procedures
The Austin moving-knife procedures are procedures for equitable division of a cake. They allocate each of n partners, a piece of the cake which this partner values as exactly of the cake. This is in c
Robertson–Webb rotating-knife procedure
The Robertson–Webb rotating-knife procedure is a procedure for envy-free cake-cutting of a two-dimensional cake among three partners. It makes only two cuts, so each partner receives a single connecte