`Allocations.Allocations`

— Module`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 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
```

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.conf`

— Constant`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.Additive`

— Type`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.Additive`

— Method`Additive(n, m)`

Create an additive profile for `n`

agents and `m`

items where all values are set to zero.

`Allocations.Allocation`

— Type`struct Allocation <: Any`

A mapping `A`

from agents `i`

to their assigned bundles `bundle(A, i)`

. Agents and items are represented as `Int`

s, and bundles as `Set`

s of `Int`

s. 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.Allocation`

— Method`Allocation(n::Int, m::Int)`

Construct an empty allocation with `n`

agents and `m`

items.

`Allocations.Allocation`

— Method`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.Allocation`

— Method`Allocation()`

Construct an empty allocation with zero agents and items.

`Allocations.Category`

— Type`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.Conflicts`

— Type`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.Constraint`

— Type`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.Counts`

— Type`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.Counts`

— Method`Counts(args::Pair...)`

Create a `Counts`

object where each pair `x => k`

becomes a category with members `Set(x)`

and threshold `k`

.

`Allocations.OrderedCategory`

— Type`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.Profile`

— Type`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.Profile`

— Method`Profile(X::Matrix)`

Alias for `Additive(X)`

.

`Allocations.Reduction`

— Type`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.Reduction`

— Method`Reduction(V, λi, λg, transform)`

A simplified constructor for when there are no constraints.

`Allocations.Reduction`

— Method`Reduction(V, C)`

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

`Allocations.Reduction`

— Method`Reduction(V)`

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

`Allocations.Reduction`

— Method`Reduction(R::Reduction, C)`

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

`Allocations.Submodular`

— Type`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.agent`

— Method`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.agents`

— Method`agents(X)`

Returns the set of agents associated with (e.g., profile or allocation) `X`

), as an iterable of `Int`

s.

`Allocations.alloc_bb18_3`

— Method`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_1`

— Method`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_2`

— Method```
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

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

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_ef1`

— Method`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_efx`

— Function`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_ggi`

— Function`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 *in*equality (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_4`

— Method`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_4b`

— Method`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_gmt18`

— Method`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_mms`

— Function`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_1`

— Methodalloc*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 (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_mm`

— Function`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_mms`

— Function`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_mnw`

— Function`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:

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`

; andExtra 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 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_ef1`

— Method`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_rand`

— Method`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:

- Give the items random priorities, corresponding to a permutation selected uniformly at ramdom.
- Tentatively allocate each item randomly to an agent, without concern for the item conflicts.
- 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_rand`

— Method`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_rand`

— Method`alloc_rand(n::Int, m::Int, C::Conflicts)`

Same as `alloc_rand(V, C)`

, for `n`

agents and `m`

items.

`Allocations.alloc_rand`

— Method`alloc_rand(n::Int, m::Int)`

Same as `alloc_rand(V)`

, for `n`

agents and `m`

items.

`Allocations.bundle`

— Method`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_n`

— Method`ceil_n(c::OrderedCategory, n)`

One `n`

th of the number of items in the category, rounded up.

`Allocations.chain`

— Method`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.check`

— Function`check(V, A, C)`

Check that the allocation `A`

obeys the `Constraint`

`C`

, given the profile `V`

.

`Allocations.check`

— Method`check(V, A, C::Conflicts)`

Check whether the allocation `A`

respects the item conflicts `C`

.

`Allocations.check`

— Method`check(V, A, C::Counts)`

Check whether the allocation `A`

respects the cardinality constraints `C`

.

`Allocations.check_complete`

— Method`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_ef`

— Method`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_ef1`

— Method`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_efx`

— Method`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_partition`

— Method`check_partition(A)`

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

`Allocations.constraint`

— Method`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_n`

— Method`floor_n(c::OrderedCategory, n)`

One `n`

th 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.graph`

— Method`graph(C::Conflicts)`

Return the conflict graph wrapped by a `Conflicts`

object.

`Allocations.isintegral`

— Function`isintegral(V::Profile)`

Test whether every value provided by `V`

is an integer.

`Allocations.isnonnegative`

— Function`isnonnegative(V::Profile)`

Test whether every value provided by `V`

is nonnegative.

`Allocations.item`

— Method`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.items`

— Method`items(X)`

Returns the set of items associated with (e.g., profile or allocation) `X`

, as an iterable of `Int`

s.

`Allocations.matrix`

— Method`matrix(V::Additive)`

Return the underlying valuation matrix of `V`

.

`Allocations.matrix`

— Method`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.mms`

— Function`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_alpha`

— Method`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.na`

— Function`na(X)`

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

.

`Allocations.nash_welfare`

— Method`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.ni`

— Function`ni(X)`

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

.

`Allocations.normalize`

— Method`normalize(V::Additive)`

Scale the values of `V`

such that $v_i(M) = n$ for all agents $i$.

`Allocations.order`

— Method`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.order`

— Method`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.owned`

— Method`owned(A, g)`

Whether or not the item `g`

is owned by any agent in the allocation `A`

.

`Allocations.owner`

— Method`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.owners`

— Method`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.profile`

— Method`profile(R::Reduction)`

Returns the valuation profile for the reduced instance.

`Allocations.prop_alpha`

— Method`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.reduce`

— Method`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.reduce`

— Method`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.reduce`

— Method`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.reduce`

— Method`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.reduce`

— Method`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.reduce`

— Method`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.reduce`

— Method`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.reduceutil`

— Method`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.reducevaluation`

— Method`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.reducevaluation`

— Method`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.required`

— Method`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.revert`

— Method`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.revert`

— Method`revert(V::Additive, A)`

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

`Allocations.revert`

— Method`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.threshold`

— Method`threshold(c::Category)`

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

constraint.

`Allocations.transform`

— Method`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.utility`

— Method`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.value`

— Function```
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.value`

— Method`value(V::Additive, i, g::Int)`

The value of item `g`

, according to agent `i`

under valuation profile `V`

.

`Allocations.value`

— Method`value(V::Profile, i, A::Allocation)`

The value agent `i`

receives in allocation `A`

, under the profile `V`

.

`Allocations.value_1`

— Function`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_x`

— Function`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_gini`

— Method`wt_gini(i, n)`

The (unnormalized) weights used in the ordered weighted average in the Gini social-evaluation function, where the utility of the `i`

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