Allocations.AllocationsModule
Allocations

Algorithms for fair allocation of indivisible items.

Basic use

To specify an allocation problem instance, create a valuation profile:

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

Profile is an abstract class, and Profile(X::Matrix) is an alias for Additive(X). Once you have a valuation profile, you can use an allocation function (ones called alloc_...), e.g., for finding a maximum Nash welfare (MNW) allocation:

julia> res = alloc_mnw(V);
Note

Note that the first time you call an allocation function, it may take some time to finish, because there's quite a lot of compilation going on behind the scenes. From then on, in the same REPL session, there will be much less overhead.

These functions take a Profile as input and return a named tuple with the field alloc referring to an Allocation:

julia> A = res.alloc
Allocation with 2 agents and 3 items:
  1 => {3}
  2 => {1, 2}

The bundles of each agent is available through the bundle function:

julia> bundle(A, 2)
Set{Int64} with 2 elements:
  2
  1
Note

Bundles should not be modified directly, as the Allocation also maintains an inverse mapping, from items to agents. Rather, use the give! and deny! functions.

Some allocation functions may produce other results as well, such as properties of the allocation that are naturally computed as part of the allocation process. For the MNW case, the objective value (the Nash welfare, which is being maximinzed) is available as mnw:

julia> res.mnw
15.0

The allocation functions also permit a matrix argument as a shortcut, implicitly creating an Additive. For example, you can find a maximin share (MMS) allocation as follows:

julia> alloc_mms([1 1 2 3; 2 1 2 3]).alloc
Allocation with 2 agents and 4 items:
  1 => {2, 3}
  2 => {1, 4}

Several allocation functions use mixed-integer linear programming via JuMP. Depending on the choice of MIP solver, solving even moderately-sized instances may take a significant amount of time. Choosing a different solver (from the default HiGHS.Optimizer) may speed things up considerably. For example, with the appropriate license, one could use use Gurobi as follows:

Allocations.conf.MIP_SOLVER = Gurobi.Optimizer

It is also possible to supply the Optimizer (or other optimizer factories, e.g., constructed using optimizer_with_attributes) as the solver keyword argument to the relevant allocation functions.

Allocations.confConstant
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].

Allocations.AdditiveType
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.

Allocations.AdditiveMethod
Additive(n, m)

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

Allocations.AllocationType
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.AllocationMethod
Allocation(n::Int, m::Int)

Construct an empty allocation with n agents and m items.

Allocations.AllocationMethod
Allocation(V::Profile)

Construct an empty allocation with a number of agents and items equal to that of the instance (i.e., profile) V.

Allocations.CategoryType
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 threashold is available through the threshold accessor.

Allocations.ConflictsType
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 accessor.

Allocations.ConstraintType
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.

Allocations.CountsType
struct Counts{T} <: Constraint

The cardinality constraints introduced 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.

Allocations.CountsMethod
Counts(args::Pair...)

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

Allocations.OrderedCategoryType
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.

Allocations.ProfileType
abstract struct 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).

Allocations.ReductionType
mutable struct Reduction{S, T, U, V}

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).

Allocations.ReductionMethod
Reduction(V, λi, λg, transform)

A simplified constructor for when there are no constraints.

Allocations.ReductionMethod
Reduction(V, C)

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

Allocations.ReductionMethod
Reduction(V)

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

Allocations.ReductionMethod
Reduction(R::Reduction, C)

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

Allocations.SubmodularType
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).

Allocations.agentMethod
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.

Allocations.agentsMethod
agents(X)

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

Allocations.alloc_bb18_3Method
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_ghhs18_4b), with possible reallocation of items to satisfy the constraints. Both keyword arguments, a and ghss18_4b_warn, are passed directly to alloc_ghhs18_4b as respectively the keyword arguments a and x_warn. See alloc_ghhs18_4b for documentation on how to use them.

Allocations.alloc_bkv18_1Method
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.

Allocations.alloc_bkv18_2Method
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. (https://doi.org/10.1145/3355902), 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. (http://arxiv.org/abs/2007.06073) 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.

Note

Despite the use of randomization here, by default, this is the deterministic procedure of Halpern et al. They also describe a randomized procedure, which functions in an entirely different manner.

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).

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

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).

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

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

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).

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.).

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

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$, without $\alpha$, $\alpha'$, $\beta$ and $\beta'$) 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).

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.

Allocations.alloc_ghss18_4Method
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.

Allocations.alloc_ghss18_4bMethod
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.

Allocations.alloc_gmt18Method
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.

Allocations.alloc_half_mmsFunction
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.

Allocations.alloc_hh22_1Method

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

The 1/2-approximate MMS allocation under cardinality constraints algorithm (Algorithm 3) described by Hummel and Hetland (to be published as part of https://link.springer.com/book/9783031206139). 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 $⌊length(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 $⌈length(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.

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

Create an egalitarion 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).

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

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.

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

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.

Note

The warnings are based on the lower bounds described by Caragiannis et al. On the one hand, the bound is only used to test whether current floating-point precision is sufficient; any tolerance or gap used by the solver is not used, which might in principle mean that false negative are possible. On the other hand, these bounds, especially the one for exact MNW, may in practice be quite loose, with small variations in agent utilities leading to large changes in objective value, unless the changes are finely tuned to cancel out.

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).

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

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.

Allocations.alloc_randMethod
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.

Allocations.alloc_randMethod
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).

Allocations.alloc_randMethod
alloc_rand(n::Int, m::Int, C::Conflicts)

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

Allocations.bundleMethod
bundle(A, i)

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

Allocations.ceil_nMethod
ceil_n(c::OrderedCategory, n)

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

Allocations.chainMethod
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).

Allocations.checkFunction
check(V, A, C)

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

Allocations.checkMethod
check(V, A, C::Conflicts)

Check whether the allocation A respects the item conflicts C.

Allocations.checkMethod
check(V, A, C::Counts)

Check whether the allocation A respects the cardinality constraints C.

Allocations.check_completeMethod
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.

Allocations.check_efMethod
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.

Allocations.check_ef1Method
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.

Allocations.check_efxMethod
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.

Allocations.check_partitionMethod
check_partition(A)

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

Allocations.constraintMethod
constraint(R::Reduction)

Returns the constraint object for the reduced instance

Allocations.deny!Method
deny!(A, i, g)

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

Allocations.fill_even!Method
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).

Allocations.fill_random!Method
fill_random!(A)

Fill out the allocation by distributing the unallocated items randomly.

Allocations.floor_nMethod
floor_n(c::OrderedCategory, n)

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

Allocations.give!Method
give!(A, i, B)

Give agent i the bundle B in the Allocation A.

Allocations.give!Method
give!(A, i, g::Int)

Give agent i the object g in the Allocation A.

Allocations.graphMethod
graph(C::Conflicts)

Return the conflict graph wrapped by a Conflicts object.

Allocations.isintegralFunction
isintegral(V::Profile)

Test whether every value provided by V is an integer.

Allocations.itemMethod
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.

Allocations.itemsMethod
items(X)

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

Allocations.matrixMethod
matrix(V::Additive)

Return the underlying valuation matrix of V.

Allocations.matrixMethod
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.

Allocations.mmsFunction
mms(V, i[, C]; solver=conf.MIP_SOLVER)

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).

Allocations.mms_alphaMethod
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)
Allocations.naFunction
na(X)

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

Allocations.nash_welfareMethod
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.

Allocations.niFunction
ni(X)

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

Allocations.normalizeMethod
normalize(V::Additive)

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

Allocations.orderMethod
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.

Allocations.orderMethod
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.

Allocations.ownedMethod
owned(A, g)

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

Allocations.ownerMethod
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.

Allocations.ownersMethod
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.

Allocations.profileMethod
profile(R::Reduction)

Returns the valuation profile for the reduced instance.

Allocations.prop_alphaMethod
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.

Allocations.reduceMethod
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.

Allocations.reduceMethod
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.

Allocations.reduceMethod
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.

Allocations.reduceMethod
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.

Allocations.reduceMethod
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.

Allocations.reduceMethod
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.

Allocations.reduceMethod
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.

Allocations.reduceutilMethod
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.

Allocations.reducevaluationMethod
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.

Allocations.reducevaluationMethod
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.

Allocations.requiredMethod
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.

Allocations.revertMethod
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.

Allocations.revertMethod
revert(V::Additive, A)

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

Allocations.revertMethod
revert(V::Additive, C::Counts, C′::Counts, A)

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

Allocations.thresholdMethod
threshold(c::Category)

The maximum number of items any agent can receive from the given category, as part of a Counts constraint.

Allocations.transformMethod
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.

Allocations.utilityMethod
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.

Allocations.valueFunction
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.

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

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

Allocations.valueMethod
value(V::Additive, i, g::Int)

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

Allocations.valueMethod
value(V::Profile, i, A::Allocation)

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

Allocations.value_1Function
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.

Allocations.value_xFunction
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.

Allocations.wt_giniMethod
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.)