Reference

struct Additive{T <: AbstractMatrix} <: Profile

An additive valuation profile, representing how each agent values all possible bundles. Because of additivity, this is easily "lifted" from the values of individual items, by addition, with an empty bundle given a value of zero. By default, the profile is constructed from a real matrix X, supplied to the default constructor, where X[i, g] is agent i's value for item g.

Additive(n, m)

Create an additive profile for n agents and m items where all values are set to zero.

struct Allocation <: Any

A mapping A from agents i to their assigned bundles bundle(A, i). Agents and items are represented as Ints, and bundles as Sets of Ints. The Allocation also maintains an inverse mapping, from items g to their set of owners, owners(A, g). To keep these in sync, the bundles should be modified using give! and deny!, rather than altering the bundle sets directly.

Allocations support iteration (along with length and isempty), which acts as for a map from agents to bundles, i.e., it generates a series of pairs i => S, where i is an agent, and S is the corresponding bundle.

Allocation(n::Int, m::Int[, bundles])
Allocation(n::Int, m::Int, bundles::Pair...)

Construct an empty allocation with n agents and m items. If the bundles argument is provided, it should be iterable, with length-2 elements, such as Pairs or 2-tuples (i, x) or agents i and bundles – or individual items – x they should receive. Agents may occur multiple times, and will then receive all the bundles or items specified. These bundle assignments need not form a partition of the item set.

Examples

julia> Allocation(5, 10, [1 => [1, 2, 3]])
Allocation with 5 agents and 10 items, 7 unallocated:
  1 => {1, 2, 3}
  2 => {}
  3 => {}
  4 => {}
  5 => {}

The bundles assignment pairs may also be provided as individual Pairs:

julia> Allocation(3, 3, 1 => [2], 2 => [3, 1], 3 => 2, 3 => 3)
Allocation with 3 agents and 3 items:
  1 => {2}
  2 => {1, 3}
  3 => {2, 3}

Allocation(A::Allocation)

Construct a new allocation that has the same agents, items and bundles as A. Because an Allocation is an iterable collection of agent–bundle pairs, this is equivalent to the more general Allocation(bundles) constructor, just slightly more efficient, because the number of agents and items are retrieved directly from A.

Allocation(bundles)
Allocation(bundles::Pair...)

Equivalent to Allocation(n, m, bundles), where n and m are determined from the bundles argument.

Examples

julia> Allocation([1 => [1, 2, 3]])
Allocation with 1 agent and 3 items:
  1 => {1, 2, 3}

julia> Allocation(1 => [2], 2 => [3, 1], 3 => 2, 3 => 3)
Allocation with 3 agents and 3 items:
  1 => {2}
  2 => {1, 3}
  3 => {2, 3}

Allocation(V::Profile, args...)

Construct an allocation with a number of agents and items equal to that of the instance (i.e., profile) V. Additional arguments may be provided as for the constructor with explicit n and m arguments.

Examples

julia> V = Profile([1 2; 2 1])
Additive{Matrix{Int64}} with 2 agents and 2 items:
 1  2
 2  1

julia> A = Allocation(V, 1 => 2)
Allocation with 2 agents and 2 items, 1 unallocated:
  1 => {2}
  2 => {}

Allocation()

Construct an empty allocation with zero agents and items.

mutable struct Category

One of the categories in a Counts constraint, from which each agent can hold at most a given number of items. The category supports iteration (over its members), and the threshold is available through the threshold attribute.

struct Conflicts{T <: AbstractGraph} <: Constraint

A kind of constraint – or set of constraints – that indicates that certain items conflict, and thus cannot be allocated to the same agent. The constraints are represented as a conflict graph (Graphs.AbstractGraph), with items as nodes, and edges representing conflicts. The Conflicts type is just a wrapper for dispatch purposes, with the underlying graph available through the graph attribute.

abstract type Constraint <: Any

Abstract supertype of various kinds of constraints. An instance of the allocation problem is assumed to consist of a Profile object and at most one Constraint object, embodying any and all constraints placed on feasible solutions.

struct Constraints{T <: Tuple{Vararg{Constraint}}} <: Constraint

A thin wrapper around a tuple of constraints, acting as a single, combined constraint. May be constructed with a single tuple argument, or with zero or more Constraint objects. Its meaning is the conjunction of its constituent parts. That is, an allocation that is to satisfy Constraints(A, B) would need to satisfy both A and B. The wrapped tuple is available via the parts attribute.

struct Counts{T} <: Constraint

The cardinality constraints used by Biswas and Barman in their 2018 paper Fair Division Under Cardinality Constraints. This is a form of constraint consisting of several Category objects, available through indexing or iteration. Any agent may hold at most a given number of items from any given category.

Counts(args::Pair...)

Create a Counts object where each pair x => k becomes a category with members Set(x) and threshold k.

struct Forbidden{T} <: Constraint

An exclusion constraint, which specifies objects that agents are forbidden from receiving. These object sets are simply specified by an Allocation (or an Allocation-like object), provided to the constructor.

This constraint is asymmetric (see Symmetry).

struct MatroidConstraint <: Constraint

A constraint defined by a matroid. An allocation satisfies the matroid constraint if every bundle is independent in the given matroid.

struct MatroidConstraints <: Constraint

A constraint defined by multiple matroids, one for each agent. An allocation satisfies the matroid constraints if every agent's bundle is independent in their corresponding matroid.

MatroidConstraints(itr)

Create a MatroidConstraints object from the given iterable object.

struct MatroidRank <: Profile

A matroid rank valuation profile, representing how each agent values all possible bundles. The profile is constructed from n matroids, one for each agent, each matroid over the set of goods [m].

mutable struct OrderedCategory

Used in place of Category when handling an ordered instance. The instance is assumed to be such that items in the range index:index + n_items - 1 belong to the given category, i.e., the items of a category occupy a contiguous range of integers.

struct Permitted{T} <: Constraint

A constraint that specifies objects that agents are permitted to receive, implicitly forbidding all others (cf. Forbidden). These object sets are simply specified by an Allocation (or an Allocation-like object), provided to the constructor.

This constraint is asymmetric (see Symmetry).

abstract type Profile <: Any

An abstract type representing an valuation profile. Which functions are used to query it depends on the kind of valuation functions it represents. Additive valuations act on individual objects, and simply sum those values over a bundle, but profiles with quite different kinds of queries are possible for valuations with other properties (see, e.g., Fair Allocation of Indivisible Goods: Improvements and Generalizations by Ghodsi et al., 2018).

Profile(X::Matrix)

Alias for Additive(X).

mutable struct Reduction{S, T, I, G}

A reduction from one instance of a fair allocation problem to another. Contains information about the profiles in the reduced instance, through an object of type S. There must exist functions agents(s::S) and items(s::S) that return iterators of, respectively, the agents and items in the reduced instance. The reduction can also contain information about the constraints in the reduced instance, through an object of type T.

In addition, the reduction contains two mappings (vectors), λi (of type I) and λg (of type G). Both types should be indexable (for i ∈ agents(s) and g ∈ items(s), respectively). λi[i] and λg[g] should return the agent and item identifier in the original instance of, respectively, agent i and item g in the reduced instance.

The reduction also contains a function that can convert an allocation in the reduced instance to one in the original instance.

The default constructor is Reduction(V, C, λi, λg, transform::Function), for a profile V and constraint C.

Reduction(V, λi, λg, transform)

A simplified constructor for when there are no constraints.

Reduction(V, C)

A simplified constructor for when either no changes have been performed or changes only concern the profiles and/or constraints.

Reduction(V)

A simplified constructor for when either no changes have been performed or changes only concern the profiles.

Reduction(R::Reduction, C)

A simplified constructor to create a copy of a reduction with constraints attached.

struct Required{T} <: Constraint

An inclusion constraint, which specifies objects that agents are required to receive. These object sets are simply specified by an Allocation (or an Allocation-like object), provided to the constructor.

This constraint is asymmetric (see Symmetry).

struct Submodular <: Profile

A submodular valuation profile, representing how each agent values all possible bundles. The profile is constructed from a set of n submodular valuation functions, one per agent, as well as the number of items, m. The profile functions should, when supplied with a Set of items (a subset of 1:m), return the value of that set of items to the given agent (i.e., acting as so-called query oracles).

Symmetry(instance)
Symmetry(T::Type)

Indicate whether a constraint instance or type is symmetric or asymmetric (indicated by a return value of Symmetric() or Asymmetric(), where Symmetric and Asymmetric are empty concrete subtypes of Symmetry). A symmetric constraint is one that is invariant under permutation of the agents, while an asymmetric constraint is not. That is, an asymmetric constraint is one that permits individual variations in the constraints placed on the bundles of different agents.

An instance has the same asymmetry as its type, and by default, this is Symmetric().

agent(R::Reduction, i)

Converts the agent identifier i from the reduced instance to the agent identifier of the same agent in the original instance.

agents(X)

Returns the set of agents associated with (e.g., profile or allocation) X), as an iterable of Ints.

bundle(A, i)

The set of items allocated to agent i in the allocation A. The returned Set should be treated as read-only.

ceil_n(c::OrderedCategory, n)

One nth of the number of items in the category, rounded up.

chain(R₁::Reduction, R₂::Reduction)

Assumes that R₂ is a reduction of the reduced instance of R₁. Combines the two reductions, so that the original instance is the original instance of R₁ and the reduced instance is the reduced instance of R₂ (essentially diagram-order composition of the reductions).

deny!(A, i, g)

Deny agent i the object g, which it has previously been given, in the allocation A.

fill_even!(A)

Fill out the allocation by distributing the unallocated items evenly, by repeatedly giving the next unallocated item to the agent with the fewest items (ties broken arbitrarily).

fill_random!(A)

Fill out the allocation by distributing the unallocated items randomly.

floor_n(c::OrderedCategory, n)

One nth of the number of items in the category, rounded down.

give!(A, i, B)

Give agent i the bundle B in the Allocation A.

give!(A, i, g::Int)

Give agent i the object g in the Allocation A.

isintegral(V::Profile)

Test whether every value provided by V is an integer.

isnonnegative(V::Profile)

Test whether every value provided by V is nonnegative.

item(R::Reduction, g)

Converts the item identifier g from the reduced instance to the item identifier of the same item in the original instance.

items(X)

Returns the set of items associated with (e.g., profile or allocation) X, as an iterable of Ints.

marginal_value(V::MatroidRank, A, i, g)

Returns the marginal value of adding element g to bundle A_i.

matrix(V::Additive)

Return the underlying valuation matrix of V.

matrix(V::Profile)

Return a matrix X where X[i, g] is value(V, i, g). May not be very useful in general (especially if calculating single-item values isn't efficient to begin with), but if such a matrix is available as part of the profile implementation (as with Additive), it may be returned directly.

na(X)

The number of agents represented by (e.g., profile or allocation) X.

ni(X)

The number of items represented by (e.g., profile or allocation) X.

normalize(V::Additive)

Scale the values of V such that $v_i(M) = n$ for all agents $i$.

owned(A, g)

Whether or not the item g is owned by any agent in the allocation A.

owner(A, g)

The agent to which item g has been allocated in the allocation A. Will produce an error if g has been allocated to more than one agent.

owners(A, g)

The set of agents to which item g has been allocated in the allocation A. The returned Set should be treated as read-only.

required(c::OrderedCategory, n)

The number of items the next agent must take in order to keep the instance valid, i.e., for there to be a maximum of (n - 1) * threshold remaining items.

transform(R::Reduction, A::Allocation)

Converts the given allocation for the reduced instance to one for original instance. The way the convertion occurs depends on the given reduction.

value(V::Profile, i, S)
value(V::Profile, i, g::Int)

The value agent i places on bundle S, according to the profile V. The second form is a shortcut for value(V, i, [g]); the shortcut will generally be more efficient. Note that the value of S may not in general be the sum of the values of its items; that property is unique to Additive profiles.

value!(V::Additive, i, g::Int, v)

Set the value of item g, according to agent i, to v in profile V.

value(V::Additive, i, g::Int)

The value of item g, according to agent i under valuation profile V.

value(V::Profile, i, A::Allocation)

The value agent i receives in allocation A, under the profile V.

value(V::Additive, i, A::T) where {T <: AbstractMatrix}

Similar to the case where A is an Allocation, except the allocation is expressed as a binary matrix, where A[i, g] indicates whether i has item g (1) or not (0). May also be used, e.g., with a matrix of variable references, when constructing MIPs with JuMP.

value_1(V::Profile, i, S)

The value agent i places on bundle S, up to one item, that is, the smallest value i can place on bundle S after removing (at most) one item, according to the profile V.

value_x(V::Profile, i, S)

The value agent i places on bundle S, up to any item, that is, the largest value i can place on bundle S after removing one item (or no items, if the bundle is empty), according to the profile V.

copy(A::Allocation)

Creates a new allocation that has the same agents, items and bundles as A.

SmallBitSet([itr])

Construct a set represented by a bit string (like Julia's BitSet) backed by a single UInt64, in order to achieve a smaller memory size.

check(V, A, C)

Check that the allocation A obeys the Constraint C, given the profile V.

check(V, A, C::Conflicts)

Check whether the allocation A respects the item conflicts C.

check(V, A, C::Counts)

Check whether the allocation A respects the cardinality constraints C.

check(V, A, C::MatroidConstraints)

Check whether the allocation A respects the matroid constraints C.

check(V, A, C::MatroidConstraint)

Check whether the allocation A respects the matroid constraint C.

check(V, A, C::Nothing)

Trivial check that A satisfies a null-constraint. Always returns true.

check_complete(A)

Check that the allocation is complete, or effective, in the sense that each item has been allocated to at least one agent.

check_ef(V, A)

Check whether the allocation A is envy-free for the profile V, i.e., if no agent strictly prefers another agent's bundle.

check_ef1(V, A)

Check whether the allocation A is envy-free up to one item for the profile V, i.e., if no agent strictly prefers another agent's bundle, given that an appropriate (e.g., the most valuable) item is removed.

check_efx(V, A)

Check whether the allocation A is envy-free up to any item for the profile V, i.e., if no agent strictly prefers another agent's bundle, given that an appropriate (e.g., the least valuable) item is removed.

check_partition(A)

Check that the allocation is a partition, i.e., that each item has been allocated to exactly one agent.

function mms_i(V, i)

Finds the maximin share of agent i in the instance V.

prop(V::MatroidRank, i, S)

The proportional share of agent i, that is, the value i places on the set of all goods, divided by the numder of agents.

prop_1(V::Profile, i, S)

The proportional share of agent i, minus a highest-valued item not allocated to i.

prop_x(V::Profile, i, S)

The proportional share of agent i, minus a least positively-valued item not allocated to i.

prop_x0(V::Profile, i, S)

The proportional share of agent i, minus a least-valued (possibly 0-valued) item not allocated to i.

ef1_alpha(V, A)

Find the approximation factor for envy-freeness up to one item in the allocation A with the valuation profile V, i.e., how close to EF1 each agent is guaranteed to get.

If every agent values all other agents' bundles as 0, the alpha returned by this function will be Inf. This is the case even if the agents also value their own bundles as 0.

ef_alpha(V, A)

Find the approximation factor for envy-freeness in the allocation A with the valuation profile V, i.e., how close to envy-freeness each agent is guaranteed to get.

If every agent values all other agents' bundles as 0, the alpha returned by this function will be Inf. This is the case even if the agents also value their own bundles as 0.

efx_alpha(V, A)

Find the approximation factor for envy-freeness up to any item in the allocation A with the valuation profile V, i.e., how close to EFX each agent is guaranteed to get.

If every agent values all other agents' bundles as 0, the alpha returned by this function will be Inf. This is the case even if the agents also value their own bundles as 0.

nash_welfare(V, A; nonzero=true)

Compute the Nash welfare of the allocation A, given the profile V, i.e., the product of the individual agent utilities resulting from A. The nonzero keyword indicates that agents with a utility of zero are left out. If no agents with nonzero utility exist, the result is zero. To avoid overflow with large utilities, the product is performed using floating-point arithmetic, even if the utilities are integral.

prop_alpha(V, A)

Compute the fraction of proportionality guaranteed to every agent, that is, what fraction each agent is guaranteed to get of 1/n of their value for the grand bundle M.

utility(V, A)

Compute the utilitarian welfare of the allocation A, given the profile V, i.e., the sum of the individual agent utilities (i.e., the bundle values) resulting from A.

alloc_algmms_bv21(V::MatroidRank)

Barman and Verma's ALGMMS (2021), which computes a utilitarian social welfare-maximizing and MMS-fair allocation.

alloc_bb18_3(V::Additive, C::Counts; a=3, ghss18_4b_warn=true)

The 1/3-approximate MMS-allocation under cardinality constraints algorithm (Section 5) described by Biswas and Barman in their 2018 paper Fair Division Under Cardinality Constraints. Finds a 1/3-approximate MMS allocation for an instance of the fair allocation problem under cardinality constraints by converting the additive instance under cardinality constraints to a submodular instance without cardinality constraints. The allocation is then found by using the method of Ghodsi et al. (alloc_ghss18_4b), with possible reallocation of items to satisfy the constraints. Both keyword arguments, a and ghss18_4b_warn, are passed directly to alloc_ghss18_4b as respectively the keyword arguments a and x_warn. See alloc_ghss18_4b for documentation on how to use them.

alloc_bkv18_1(V; randpri=true)

The first algorithm (Alg-Identical) described by Barman, Krishnamurty and Vaish in their 2018 paper Greedy Algorithms for Maximizing Nash Social Welfare. The algorithm finds a 1.061-approximate MNW allocation when agents have identical valuations, i.e., for any agents i, j and item g, value(V, i, g) == value(V, j, g). (This approximation ratio applies to the geometric mean of agent utilities, not the raw product.) The result will also be envy-free up to any item (EFX).

The algorithm follows a straightforward greedy allocation procedure, where in each iteration, the most valuable item is allocated to the agent with the lowest utility. By default, ties are broken by giving the agents random priorities; if randpri is set to false, they are instead broken lexicographically (as specified by Barman et al.), so that the agent with the lower index is preferred.

alloc_bkv18_2(V; randpri=true, complete=false)
alloc_hpps20_1(V; randpri=true, complete=false) # alias

The second algorithm (Alg-Binary) described by Barman, Krishnamurty and Vaish in their 2018 paper Greedy Algorithms for Maximizing Nash Social Welfare. The algorithm finds MNW allocations in polynomial time for binary additive valuations, i.e., where each agent values any given object at 0 or 1 (e.g., an Additive{BitMatrix}). It also works in a more general setting, where value(V, i, S), for any given i, is a concave function of the number of items g in S for which value(V, i, g) == 1.

The original algorithm builds on an initial allocation, but does not specify what this allocation should be. It also does not deal with the case where one or more agents ends up with zero utility; in fact the procedure will not work even if we start with two or more agents with zero utility in the intial allocation. The strategy followed here is the same as that of Caragiannis et al., where a maximum cardinality set of agents achieving positive utility is found using bipartite matching (with no fairness considerations). The remaining items are randomly allocated to agents among these that value them, if any. Remaining agents and items are ignored by the procedure.

Following the algorithm of Barman et al., the tie-breaking procedure (Algorithm 1) of Halpern et al. is used, where the MNW allocation is transformed into the lexicographically greatest MNW, according to some ordering of the agents, providing group-strategyproofness (GSP) in addition to the EF1 and PO guarantees that follow from MNW. By default, the agent ordering/priority is random; if this randomization is turned off (with randpri set to false), the default ordering is used, with agent 1 receiving the highest priority, etc.

Finally, if the complete argument is set to true, the allocation is completed with fill_even! (which means that some agents that must necessarily get a utility of zero can still receive items valued zero, if that evens out the bundle cardinalities). Note that this undermines the GSP guarantee, which requires that these items be discarded. The return value is a named tuple with the fields alloc (the Allocation) and mnw (the Nash welfare, ignoring agents with zero utility).

alloc_eit_bciz21(V::MatroidRank)

The Envy-Induced Transfer algorithm, Algorithm 1 in Benabbou, Chakraborty, Igarashi and Zick (2021) computes a MAX-USW, EF1 allocation.

alloc_ghss18_4(V::Submodular, MMSs)

The fourth algorithm (Algorithm 4) described by Ghodsi et al. in the 2018 paper Fair allocation of Indivisible Goods: Improvements and Generalizations. The algorithm finds a 1/3-approximate MMS allocation for a given submodular instance and corresponding maximin shares for the agents (MMSs[i] should be the MMS of agent i). If the supplied maximin shares, are higher than the actual maximin shares, the method may fail. In that case, this will be indicated in the result, where res.fail will be set to true and res.agent will be set to the agent last considered when the method failed to improve. If the maximin shares are unknown, use alloc_ghss18_4b.

alloc_ghss18_4b(V::Submodular; a=3, x_warn=true)

A variation on the fourth algorithm (Algorithm 4) described by Ghodsi et al. in the 2018 paper Fair allocation of Indivisible Goods: Improvements and Generalizations. The algorithm finds a 1/3-approximate MMS allocation for a given submodular instance. The method starts by overestimating the MMS of each agent and slowly decreasing the MMS of specific agents until alloc_ghss18_4 returns an allocation.

The amount that the MMS of an agent should be reduced by in each iteration is not specified by Ghodsi et al. One can show that if the factor is 1/(1 + 1/x), where x ≥ 3n - 1, then the algorithm will successfully find a 1/3-approximate MMS allocation. One way to show this, is to modify Lemma 4.6 in their paper to assume that each of the bundles Sᵢ is valued at least 1/(1 + 1/x). Using this modified version of Lemma 4.6, one can modify the proof of Theorem 4.7 to show that as long as x ≥ 3n - 1, the change in expectance from moving an item is at least 1/(3m). The value of x used in this implementation is x = an, where the keyword argument a is set to 3 by default (i.e., x = 3n). If a is set so that x < 3n - 1 a warning will be given. The warning can be turned off by setting x_warn to false.

alloc_gmt18(V)

The 2/3-approximate MMS allocation algorithm described by Garg, McGlaughlin and Taki in their 2018 paper Approximating Maximin Share Allocations. The algorithm finds a 2/3-approximate MMS allocation for an instance with additive valuations. The algorithm works by performing a set of reductions to simplify the instance, limiting the maximum value of a good and the number of high-valued goods. The algorithm then uses bag-filling to allocate the remaining goods to the remaining agents.

alloc_half_mms(V::Additive, C::Counts)

Find a 1/2-approximate MMS allocation that obeys the constraints imposed by C. The allocation is found using alloc_hh22_1. See alloc_hh22_1 for a detailed description of how the method works.

alloc_hh22_1(V::Additive, C::Counts; α=0.5)

The 1/2-approximate MMS allocation under cardinality constraints algorithm (Algorithm 3) described by Hummel and Hetland in their Maximin Shares Under Cardinality Constraints (2022). First the instance is reduced to an ordered normalized instance where each good is worth less than 1/2. While there are more than one agent remaining, the algorithm creates a bundle with the $⌊|\text{category}|/n⌋$ lowest-valued items in each category. Repeatedly, it converts each of these to the highest-valued remaining item in the category until it either runs out of items to convert or an agent values the bundle at least 1/2. If the procedure runs out of items to convert, it adds the highest-valued remaining item in each category, in order, to get $⌈|\text{category}|/n⌉$ items from each category. After each such item is added, the value is again checked for each agent. Since the instance was ordered normalized and without items worth 1/2 or more, the bundle created will always be worth more than 1/2 to one of the remaining agents before the procedure runs out of items to add to it or convert from low- to high-valued.

Another approximation ratio, α, can be supplied. If α ≤ 0.5 the algorithm is guaranteed to succeed. Otherwise, the method will try to find an allocation with an approximation ratio of α, but may fail. In the latter case, the results will indicate a failure by setting res.fail to true.

alloc_rand(V, C::Conflicts)

Allocate items to agents randomly, respecting the item conflicts. Uses the randomized coloring procedure with symmetry-breaking of Pemmaraju and Srinivasan, which works as follows:

1. Give the items random priorities, corresponding to a permutation selected uniformly at ramdom.
2. Tentatively allocate each item randomly to an agent, without concern for the item conflicts.
3. If an agent has received conflicting items, it keeps the highest-priority item (i.e., earliest in the permutation), and the others are reallocated arbitrarily.

This final arbitrary reallocation is also performed randomly in this implementation, by going through the items in random order, allocating each to a randomly selected agent among those able to receive it.

The valuation profile V is not used, other than to determine the number of agents and items.

For this algorithm to function properly, the maximum degree of the conflict graph should be strictly less than the number of agents.

alloc_rand(V)

A straightforward lottery that allocates the items randomly to the agents. For each item, its agent is selected uniformly at random. The valuation profile V is not used, other than to determine the number of agents and items. The return value is a named tuple with the field alloc (the Allocation).

alloc_rand(n::Int, m::Int, C::Conflicts)

Same as alloc_rand(V, C), for n agents and m items.

alloc_rand(n::Int, m::Int)

Same as alloc_rand(V), for n agents and m items.

yankee_swap(V::MatroidRank)

Viswanathan and Zick's Yankee Swap algorithm (2022) for matroid-rank valuations. The agents are prioritized according to index.

order(V::Additive, C::Counts)

Create an ordered instance for the given weights and categories. The items are reorded such that each category has a continous range of indices for its items. Returns a reduction, with a transformation that converts an allocation to one in the original instance where each agent gets at least the same value as in the ordered instance.

order(V::Additive)

Create an ordered instance for the given weights. The weights are reordered for each agent such that item 1 is worth the most and item m is worth the least. Returns new additive valuations and a function to convert an allocation in the ordered instance into one for the original instance.

reduceutil(V::Profile, assignments::Pair...)

Utility function that given valuations and a collection of assignments of bundles to agents (i => B), creates a reduced instance, translation tables from the reduced instance and a function to convert an allocation in the reduced instance to one in the original instance – including the given assignements. The function returns a Reduction object without any constraints.

reducevaluation(V::Additive, λi, λg)

Utility function that given additive valuations prior to a reduction and translation tables for the reduction, returns new additive valuations for the reduced instance. The new valuations are as prior to the reduction, except for missing items/agents and changes in item/agent numbers.

reducevaluation(V::Submodular, λi, λg)

Utility function that given submodular valuations prior to a reduction and translation tables for the reduction, returns new submodular valuations for the reduced instance. The new valuations are as prior to the reduction, except for missing items/agents and changes in item/agent numbers. That is, the new valuation functions work by translating the item numbers to what they would be prior to the reduction and calling the valuation function of the agent prior to the reduction.

revert(λi, λg, assignments, A)

Convert an allocation for a reduced instance to one for the original instance, including giving the removed bundles to the removed agents.

revert(V::Additive, A)

Convert an allocation for the ordered instance to one for the original instance.

revert(V::Additive, C::Counts, C′::Counts, A)

Convert an allocation for the ordered instance (C′) to one for the original instance (V, C).

reduce(V::Additive, C::Counts{OrderedCategory}, i, B)

Reduce the instance given by the pair (V, C) to a new instance by giving the supplied agent, i, the supplied bundle, B. Returns a reduction, where the transformation, in addition to converting the allocation to one for the original instance, allocates B to i.

reduce(V::Additive, C::Counts{OrderedCategory}, α)

Reduce an ordered instance by normalizing the values and giving any agent that value an individual item greater than or equal to α the item and any low value items required to reduce to a valid instance. This reduction is performed recursively until no more such items exist. The reduction does not decrease the MMS guarantee of any remaining agents and all agents that are allocated a bundle in the reduction is guaranteed to value their bundle at least α of their MMS guarantee.

reduce(V::Additive, α::Real; greedy::Bool=true)

Reduce an ordered instance by normalizing the values and giving any agent that value an individual item greater than or equal to α the item. This reduction is performed recursively until no more such items exist. The reduction does not decrease the MMS guarantee of any remaining agents and all agents that are allocated a bundle in the reduction is guaranteed to value their bundle at least α of their MMS guarantee. The agent-item pairs are either selected greedily or by finding a maximum matching between agents and such items.

reduce(V::Additive, F::Function...)

Reduce an instance V by repeatedly applying the functions f ∈ F to find bundles to be allocated. The functions in F are expected to return either a pair, (i, B), consisting of an agent i and the bundle B to be assigned to agent i, or the value nothing if the function couldn't find a valid bundle-agent-pair. The functions are called in prioritized order and the instance is reduced and normalized between each invocation. The functions are invoked with the valuation matrix.

reduce(V::Profile, α::Real)

Produce a reduced instance by giving an item to any agent that values it at α or more. This reduction is performed repeatedly, until no such item exists.

reduce(V::Valuation, assignment::Pair...)

Reduce the instance given to a new instance where the involved agents and bundles in the assignments are removed. Returns new valuations and a function that turns an allocation in the reduced instance into one for the original instance, including giving the supplied agent the supplied bundle.

reduce(V::Submodular, i, B)

Reduce the instance given by V to a new instance by giving the specified bundle, B, to agent i. Returns a reduction, where the transformation, in addition to converting the allocation to one for the original instance, allocates B to i.

alloc_ef1(V, C; solver=conf.MIP_SOLVER, kwds...)

Create an Allocation that is envy-free up to one item (EF1), based on the valuation profile V, possibly subject to the constraints given by the Constraint object C. The solution is found using a straightforward mixed-integer program, and is most suitable for constraints where no specialized algorithm exists. For example, without constraints, a straightforward round robin picking sequence yields EF1, and a similar strategy works for cardinality constraints. (It is still possible to use this function without constraints, by explicitly supplying nothing for the constraint argument C.) The return value is a named tuple with the fields alloc (the Allocation) and model (the JuMP model used in the computation).

Lower and upper limits on the size of each bundle and the number of owners for each item may be supplied using the keyword arguments min_bundle, max_bundle, min_owners and max_owners, the latter two of which default to 1. If one of these is nothing, the limit is simply absent. Otherwise, the argument is broadcast to the appropriate size.

Note that for some constraints, there may not be an EF1 allocation, in which case the function will fail with an exception.

alloc_efx(V[, C]; solver=conf.MIP_SOLVER, kwds...)

Create an Allocation that is envy-free up to any item (EFX), based on the valuation profile V, possibly subject to the constraints given by the Constraint object C. The solution is found using a straightforward mixed-integer program. The return value is a named tuple with the fields alloc (the Allocation) and model (the JuMP model used in the computation).

Lower and upper limits on the size of each bundle and the number of owners for each item may be supplied using the keyword arguments min_bundle, max_bundle, min_owners and max_owners, the latter two of which default to 1. If one of these is nothing, the limit is simply absent. Otherwise, the argument is broadcast to the appropriate size.

Note that while some constraints may prevent an exact EFX allocation, it is currently (Mar 2021) an open question whether EFX always exists in the unconstrained case (see, e.g., Improving EFX Guarantees through Rainbow Cycle Number by Chaudhury et al.).

alloc_ggi(V[, C]; wt=wt_gini, solver=conf.MIP_SOLVER, kwds...)

Maximizes a generalized Gini index (GGI), also known as a generalized Gini social-evaluation functions. The function being maximized is an ordered weighted average (OWA) of agent utilities, utilities, where the weight is based on utility rank i, from the least happy (1) to the most happy (n), parameterized by the function wt(i, n). It is generally assumed that the weights are nondecreasing in i. Note that there is no need to use normalized weights (i.e., to produce a weighted average, despite the term OWA), as is often the case when such measures are used to measure inequality (e.g., by subtracting the OWA from an ordinary average, cf. Generalized gini inequality indices by John A. Weymark).

The default wt_gini gives the (non-normalized) weights of the original Gini social-evaluation. Two other notable cases for wt are (i, _) -> i == 1, which yields a maximin allocation, and (i, _) -> 1, which yields a purely utilitarian allocation (with no consideration for fairness). The solution method used is based on that of Lesca and Perny (linear formulation $\Pi'_W$) in their paper 2010 paper “LP Solvable Models for Multiagent Fair Allocation Problems”. The return value is a named tuple with the fields alloc (the Allocation that has been produced) and model (the JuMP model used in the computation).

Lower and upper limits on the size of each bundle and the number of owners for each item may be supplied using the keyword arguments min_bundle, max_bundle, min_owners and max_owners, the latter two of which default to 1. If one of these is nothing, the limit is simply absent. Otherwise, the argument is broadcast to the appropriate size.

In the original inequality measures, the mean agent utility is included as a normalizing term, which is harmless for the case of identical valuations functions (and when looking at, say, the distribution of incomes), but when valuations differ, this mean will vary with the allocations. As pointed out by Lesca and Perny, such a measure is not monotone with Pareto dominance – the optimization will tend to drive the mean utility down. Therefore only the term measuring (in)equality (i.e., the ordered weighted sum of agent utilities) is used.

alloc_lmm(V[, C]; solver=conf.MIP_SOLVER, kwds...)

Create a lexicographic maximin (leximin) Allocation, i.e., one where the lowest bundle value is maximized, and subject to that, the second lowest is maximized, etc. The return value is a named tuple with fields alloc (the Allocation) and model (the JuMP model used in the computation).

The method used for leximin optimization is that of Ogryczak and Śliwiński ("On Direct Methods for Lexicographic Min-Max Optimization", 2006).

Lower and upper limits on the size of each bundle and the number of owners for each item may be supplied using the keyword arguments min_bundle, max_bundle, min_owners and max_owners, the latter two of which default to 1. If one of these is nothing, the limit is simply absent. Otherwise, the argument is broadcast to the appropriate size.

alloc_mm(V[, C]; cutoff=nothing, ignored_agents=[],
    solver=conf.MIP_SOLVER, kwds...)

Create an egalitarian or maximin Allocation, i.e., one where the minimum bundle value is maximized. The cutoff, if any, is a level at which we are satisfied, i.e., any allocation where all agents attain this value is acceptable. The return value is a named tuple with fields alloc (the Allocation), mm (the lowest agent utility) and model (the JuMP model used in the computation).

The ignored_agents argument indicates agents that should be ignored when maximizing the minimum. These agents may still receive items, and will participate in forming a feasible allocation (possibly with respect to some constraint C); they are only ignored in the objective.

Lower and upper limits on the size of each bundle and the number of owners for each item may be supplied using the keyword arguments min_bundle, max_bundle, min_owners and max_owners, the latter two of which default to 1. If one of these is nothing, the limit is simply absent. Otherwise, the argument is broadcast to the appropriate size.

alloc_mms(V[, C]; cutoff=false, solver=conf.MIP_SOLVER,
          mms_kwds=(), kwds...)

Find an MMS allocation, i.e., one that satisfies the maximin share guarantee, where each agent gets a bundle it weakly prefers to its maximin share (introduced by Budish, in his 2011 paper The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes). The return value is a named tuple with fields alloc (the Allocation), mmss, the individual MMS values for the instance, alpha, the lowest fraction of MMS that any agent achieves (is at least 1 exactly when the allocation is MMS), model (the JuMP model used in computing alpha) and mms_models (the JuMP models used to compute the individual maximin shares). If cutoff is set to true, this fraction is capped at 1.

If all agents have an MMS of zero, alpha will be unbounded, represented by the value Inf. This is the case even if one or more agents get a value of 0.

Lower and upper limits on the size of each bundle and the number of owners for each item may be supplied using the keyword arguments min_bundle, max_bundle, min_owners and max_owners, the latter two of which default to 1. If one of these is nothing, the limit is simply absent. Otherwise, the argument is broadcast to the appropriate size.

When finding an MMS partition for each individual agent, the constraint and options act a little differently than when finding the actual allocation. If an asymmetric Constraint C is supplied (i.e., one that is different for the different agents), agent i's version is enforced on every bundle to determine which partitions are feasible.

The same holds for min_bundle and max_bundle. Apart from those two, the keywords kwds are also used for the MMS partitions.

alloc_mms(V, C, mms_kwds=(min_owner=0,))

alloc_mnw(V[, C]; mnw_warn=false, solver=conf.MIP_SOLVER, kwds...)

Create an Allocation attaining maximum Nash welfare (MNW), based on the valuation profile V, possibly subject to the constraints given by the Constraint object C. The solution is found using the approach of Caragiannis et al. in their 2019 paper The Unreasonable Fairness of Maximum Nash Welfare, with two minor modifications:

1. Rather than hard-coding a maximum valuation (arising from the assumption that the values of each agent sum to 1000), this maximum is extracted from V; and

2. Extra constraints are permitted (through the object C), possibly lowering the attainable MNW.

Because of how the integer program is constructed, it may be affected by precision effects, where a high number of agents can make it impossible to guarantee Pareto optimalty (PO), EF1 or MNW. If the precision is too low, the appropriate warning will be issued, but the computation is not halted. Note that these warnings are quite conservative (see note below). This is particularly true of the one for MNW, which is disabled by default, in part because of its sensitivity, and in part because it will generally be useful to find solutions that satisfy PO and EF1, even if it may not be exactly MNW. The MNW warning can be enabled by setting the mnw_warn keyword to true.

The return value is a named tuple with fields alloc (the Allocation), mnw (the achieved Nash welfare for the agents with nonzero utility), mnw_prec (whether or not there was enough precision to satisfy the lower bound guaranteeing exact MNW) and model (the JuMP model used in the computation).

Lower and upper limits on the size of each bundle and the number of owners for each item may be supplied using the keyword arguments min_bundle, max_bundle, min_owners and max_owners, the latter two of which default to 1. If one of these is nothing, the limit is simply absent. Otherwise, the argument is broadcast to the appropriate size.

alloc_mnw_ef1(V, C; mnw_warn=true, solver=conf.MIP_SOLVER, kwds...)

Equivalent to alloc_mnw, except that EF1 is enforced. Without any added constraints, MNW implies EF1, so this function is not needed in that case. Therefore the argument C is not optional.

Lower and upper limits on the size of each bundle and the number of owners for each item may be supplied using the keyword arguments min_bundle, max_bundle, min_owners and max_owners, the latter two of which default to 1. If one of these is nothing, the limit is simply absent. Otherwise, the argument is broadcast to the appropriate size.

alloc_rand_mip(V[, C]; solver=conf.MIP_SOLVER, rng=default_rng(),
               kwds...)

Allocate items to agents randomly, in a similar manner to alloc_rand. The implementation is inspired by the randomized coloring procedure with symmetry-breaking of Pemmaraju and Srinivasan, and is generalized to work with any Constraint.

The profile V is not used directly, other than to determine the number of agents and items.

A random priority profile is generated using rand_priority_profile, such that any constraints will remove the items with lowest priority first. To ensure that the MIP respects this priority profile, the utilitarian welfare of the allocation is maximized.

Lower and upper limits on the size of each bundle and the number of owners for each item may be supplied using the keyword arguments min_bundle, max_bundle, min_owners and max_owners, the latter two of which default to 1. If one of these is nothing, the limit is simply absent. Otherwise, the argument is broadcast to the appropriate size.

mms(V::Additive, i[, C]; solver=conf.MIP_SOLVER, kwds...)

Determine the maximin share of agent i, i.e., the bundle value she is guaranteed to attain if she partitions the items and the other agents choose their bundles. Useful, e.g., as a point of reference when determining the empirical approximation ratios of approximate MMS allocation algorithms. Also used as a subroutine in alloc_mms. The return value is a named tuple with the fields mms (the maximin share of agent i) and model (the JuMP model used in the computation).

Lower and upper limits on the size of each bundle and the number of owners for each item may be supplied using the keyword arguments min_bundle, max_bundle, min_owners and max_owners, the latter two of which default to 1. If one of these is nothing, the limit is simply absent. Otherwise, the argument is broadcast to the appropriate size.

If a constraint C is supplied, and this is asymmetric (i.e., different for the different agents), agent i's version is enforced on every bundle to determine which partitions are feasible.

mms_alpha(V, A, mmss)

Utility function to find the fraction of the maximin share guarantee attained by the allocation A, under the valuation profile V, where mmss[i] is the MMS of agent i. This makes it possible, for example, to use the mmss field from the result of alloc_mms to find the MMS approximation provided by an allocation constructed by other means. For example:

mmss = alloc_mms(V).mmss
A = alloc_rand(V).alloc
alpha = mms_alpha(V, A, mmss)

If all agents have an MMS of zero, alpha will be unbounded, represented by the value Inf. This is the case even if one or more agents get a value of 0.

rand_priority_profile(n, m; rng=default_rng())

Generate a random valuation profile, based on a random prioritization of the items. To ensure that the item priorities will overrule any other considerations, the valuation profile is filled using powers of 2. Therefore, this function does not work for values of m ≥ 63.

wt_gini(i, n)

The (unnormalized) weights used in the ordered weighted average in the Gini social-evaluation function, where the utility of the ith agent, ordered by increasing utility, is given weight $2(n - i) + 1$. (The normalized weights yielding the original Gini social-evaluation function are divided by $n^2$, but this makes no difference to the optimization problem.)

knuth_matroid(m, X)
knuth_matroid(V::Profile, X)

Knuth's matroid construction (1975). Generates a matroid in terms of its closed sets, given by the size of the universe m and a list of enlargements X.

knuth_matroid_erect(m, enlargements)

An improved version of KMC we are also finding the independent sets and circuits of the matroid during generation.

This version assigns the Hamming weight of all subsets of E upfront. This is infeasible for values of n much larger than 16.

rand_additive(; n=2:10, m=n->2n:4n, v=(n, m)->Uniform(), rng=default_rng())
rand_profile(; n=2:10, m=n->2n:4n, v=(n, m)->Uniform(), rng=default_rng())

Generate a random additive valuation profile (an Additive object) with the number of agents and items, agents and values chosen using rand with the given values as the first argument. Here n is used directly, while m should be a function of the number of agents, which returns an argument for rand. Similarly, v should be a function of both the number of agents and items.

The defaults for n and m are taken from Hummel and Hetland, who based them on based on real-world data from Caragiannis et al., with n at most 10, and the average m/n approximately 3.

The distribution for the values can be univariate, in which case it is used independently for each value. For example, to generate Gaussian valuations, with the Distributions package, use v=(n, m)->Normal().

However, it can also be multivariate, in which case each sample should be a vector of the same length as the number of items, representing the valuation function of a single agent. For example, to get a Dirichlet distribution, where an agent's values sum to 1, you could use v=(n, m)->Dirichlet(m, 2).

It is also possible to use a matrix-variate distribution, such as a matrix normal distribution, where each sample should then be an m by n matrix, with each column representing the valuation function of a single agent.

rand_profile is an alias for rand_additive.

rand_conflicts_ba02(m; k=1:m, rng=default_rng())
rand_conflicts_ba02(V::Profile; ...)

Generate a random Conflicts contraint, whose underlying graph is constructed according to the Barabási–Albert model. The keyword argument k specifies the possible values for the corresponding parameter $k$, which is generated using rand.

rand_conflicts_er59(m, p=Uniform(), rng=default_rng())
rand_conflicts_er59(V::Profile; ...)
rand_conflicts(m; ...)
rand_conflicts(m::Profile; ...)

Generate a random Conflicts contraint, whose underlying graph is constructed according to the Erdős–Rényi model. The keyword argument p specifies the possible values for the corresponding parameter $p$, which is generated using rand.

rand_conflicts is an alias for rand_conflicts_er59.

rand_conflicts_ws98(m; k=2:2:div(m, 2), β=Uniform(), rng=default_rng())
rand_conflicts_ws98(V::Profile; ...)

Generate a random Conflicts contraint, whose underlying graph is constructed according to the Watts–Strogatz model. The keyword arguments k and β specify the possible values for the corresponding parameters $k$ and $\beta$, which are generated using rand. The defaults are taken from Hummel and Hetland. Note that the parameter $k$ should be an even number, which Watts and Strogatz assume to be much smaller than $m$.

rand_matroid_er59(m; n=nothing, rng=default_rng())
rand_matroid_er59(V::Profile; ...)

Generate a random GraphicMatroid, whose underlying graph is constructed according to the Erdős–Rényi model . The keyword argument verts specifies the possible values for the parameter $n$ (i.e., how many vertices to generate), which is generated using rand.

rand_matroid_er59_asym(n, m; kwds...)

Generate a random Matroid for each agent n.

See rand_matroid_er59 for the supported keyword arguments.

rand_matroid_knu75(m; r=2:m÷2, track_indep=false, rng=default_rng())
rand_matroid_knu75(V::Profile; ...)

Generate a random Matroid based on the process described in Knuth's 1975 paper. The matroid will have a ground set of 1:m.

The keyword argument r specifies the possible values for the target rank of the matroid, and is by default 2:m÷2. track_indep controls whether the matroid generation should keep track of independent sets under construction.

rand_matroid_knu75_asym(n, m; kwds...)

Generate a random Matroid for each agent n.

See rand_matroid_knu75 for the supported keyword arguments.

bases(M::Matroid)

Finds the set of bases of the matroid M.

closure(M::Matroid, S)

Returns the closure of a set S in the matroid M.

Given a set S ⊆ E, add all elements x ∈ E such that S has no increase in rank.

is_circuit(M::Matroid, S)

Determines whether S is a circuit in M (i.e., rank(M, S) == length(S) - 1).

is_closed(M::Matroid, S)

Returns true if the given set S is closed in the matroid M, i.e., if the closure of S is equal to itself.

is_indep(M::Matroid, S)

Determine whether the set S is independent in the matroid M.

matroid_c1(M::Union{ClosedSetsMatroid, FullMatroid})

The first axiom for a matroid defined by closed sets, as described in Knuth's 1975 paper:

The ground set is closed. $E ∈ F$.

matroid_c2(M::Union{ClosedSetsMatroid, FullMatroid})

The second axiom for a matroid defined by closed sets, as described in Knuth's 1975 paper:

The intersection of two closed sets is a closed set. If $A, B ∈ F$, then $A ∩ B ∈ F$.

matroid_c3(M::Union{ClosedSetsMatroid, FullMatroid})

The third axiom for a matroid defined by closed sets, as described in Knuth's 1975 paper:

If $A ∈ F$ and $a, b ∈ E - A$, then $b$ is a member of all sets containing $A ∪ {a}$ if and only if $a$ is a member of all sets containing $A ∪ {b}$.

minimal_spanning_subset(M::Matroid, S)

Finds a minimal spanning subset of S in M. If S is the ground set of M, this produces a basis of M.

minimal_spanning_subsets(M::Matroid, S)

Finds all minimal spanning subsets of S in M. If S is the ground set of M, this finds all the bases of M.

See also bases.

rank(M::Matroid, S)

Returns the rank of the set S in M, i.e., the size of the largest independent subset of S.

conf

A struct with fields for global configuration of the Allocations module.

Fields

MIP_SOLVER::Any

The (factory for the) JuMP optimizer to be used (by default) for mixed-integer programming. Initially set to HiGHS.Optimizer, with log_to_console set to false. This can be overridden either by setting MIP_SOLVER to another value (e.g., using the JuMP function optimizer_with_attributes) or by passing the solver directly to the appropriate allocation functions.

MIP_SUCCESS::Any

Container of acceptable MIP statuses. By default, has the value [MOI.OPTIMAL].