- Applied mathematics
- >
- Theoretical computer science
- >
- Algorithms
- >
- Fair division protocols

- Fields of mathematics
- >
- Applied mathematics
- >
- Algorithms
- >
- Fair division protocols

- Fields of mathematics
- >
- Game theory
- >
- Fair division
- >
- Fair division protocols

- Fields of mathematics
- >
- Mathematical logic
- >
- Algorithms
- >
- Fair division protocols

- Fields of mathematics
- >
- Recreational mathematics
- >
- Fair division
- >
- Fair division protocols

- Mathematical economics
- >
- Game theory
- >
- Fair division
- >
- Fair division protocols

- Philosophy of mathematics
- >
- Mathematical logic
- >
- Algorithms
- >
- Fair division protocols

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

Approximate Competitive Equilibrium from Equal Incomes

Approximate Competitive Equilibrium from Equal Incomes (A-CEEI) is a procedure for fair item assignment. It was developed by Eric Budish.

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

Proportional cake-cutting with different entitlements

In the fair cake-cutting problem, the partners often have different entitlements. For example, the resource may belong to two shareholders such that Alice holds 8/13 and George holds 5/13. This leads

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

© 2023 Useful Links.