# Reference

`julia> using Allocations`

**Function naming:** Allocation functions that use a straightforward procedure, or simply use a solver to enforce some property, are named after that procedure or property (such as `alloc_rand`

or `alloc_ef1`

). For published algorithms, the package uses a naming scheme based on the original publication.

The root of the function name is `alloc_`

, followed by a publication code:

- For a single-author paper, the first three letters of the author's last name are used;
- for multi-author papers, the first letter of the first four authors are concatenated.
- To this, the last two digits of the year are added.

For example, the 2/3-MMS algorithm of Garg, McGlaughlin and Taki (2018) is implemented by `alloc_gmt18`

.

If the same code applies to multiple publications, they are distinguished by a suffix

`a`

,`b`

, etc., after the year digits.If a single publication discusses multiple algorithms, a number such as

`_1`

,`_2`

, etc., is added. So, for example, the third algorithm described by Biswas and Barman (2018) is`alloc_bb18_3`

.

Some functions (such as `alloc_hh22_1`

) are given generic names as aliases (in this case, `alloc_half_mms`

).

These publication codes are similar to the authorship trigraphs used in some citation styles. Specifically, they follow the conventions of `alpha.bst`

, except that an "et al." character is not added when there are five or more authors.

**Accessors:** Using accessors such as `attr(obj)`

rather than `obj.attr`

comes with the cost of claiming names in the global namespace, so they are mainly used when they provide some value, and not as a general convention. Such added value may be, for example, that it makes the interface clearer or more consistent, or that it provides some modest level of encapsulation. In many cases, it may also be worthwhile to use a function to access elements of an internal collection (such as `foo(X, i)`

rather than `X.foo[i]`

).

If, however, an object is essentially a named tuple, attributes will tend to be used without accessors. This applies to thin wrapper (such as `Conflicts`

, for example), where the inner object is simply accessed directly.

Note that some such objects used accessors in earlier versions. These accessors are still available, but their use is deprecated. (Run `julia`

with `--depwarn=true`

to get the appropriate warnings.)

## Basic types

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

`Allocation`

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

`Allocations.Allocation`

— Type```
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 `Pair`

s 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 `Pair`

s:

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

`Allocations.Allocation`

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

.

`Allocations.Allocation`

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

`Allocations.Allocation`

— Method`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 => {}
```

`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 threshold is available through the `threshold`

attribute.

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

attribute.

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

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

`Allocations.Counts`

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

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

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

).

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

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

).

`Allocations.Profile`

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

`Allocations.Profile`

— Method`Profile(X::Matrix)`

Alias for `Additive(X)`

.

`Allocations.Reduction`

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

.

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

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

).

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

— Type```
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()`

.

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

— Function`na(X)`

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

.

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

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

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

.

`Base.copy`

— Method`copy(A::Allocation)`

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

.

## Checks and measures

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

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

Trivial check that `A`

satisfies a null-constraint. Always returns true.

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

.

## Allocation algorithms

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

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

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

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

.

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

### Reductions

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

.

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

.

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

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

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

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

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

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

.

## MIP-based allocation

`Allocations.alloc_ef1`

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

`Allocations.alloc_efx`

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

`Allocations.alloc_ggi`

— Function`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 *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$) 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.

`Allocations.alloc_lmm`

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

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

`Allocations.alloc_mm`

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

Most users will probably not need `ignored_agents`

. Its primary use is as part of `alloc_mms`

, for ignoring agents with an MMS of zero, whose α is unbounded.

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

`Allocations.alloc_mms`

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

.

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

In some cases, using asymmetric constraints might lead to a situation where a feasible allocation exists, but for some agent, an MMS partition does not. Then the agent's maximin share is undefined! One way around this is to relax the definition a bit, and to permit charity when finding the MMS partitions. The agent will still try to maximize the mininum value of any bundle in this partition, but is not required to allocate every object. This can be achieved as follows:

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

You should verify that the strategy makes sense for your application, however! In some cases, it might not be necessary, and would just needlessly inflate maximin shares. Also, it is only guaranteed to work for constraints where an empty bundle is feasible; it might fail for `Required`

, for example. Indeed, for some constraints, one could argue that it might not be advisable to use the MMS criterion to begin with.

`Allocations.alloc_mnw`

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

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

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

`Allocations.alloc_mnw_ef1`

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

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

`Allocations.mms`

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

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

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

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`

.

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

## Instance generation

`Allocations.rand_additive`

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

Note that the matrix samples should be the *transpose* of the ones used in the resulting profile. This is to maintain consistency with the multivariate distributions, which produce column vectors.

`rand_profile`

is an alias for `rand_additive`

.

`Allocations.rand_conflicts_ba02`

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

.

`Allocations.rand_conflicts_er59`

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

.

`Allocations.rand_conflicts_ws98`

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

## Configuration

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

.