A matroid is a pair , where is a finite ground set and is its collection of matroid independent sets, satisfying the matroid independence axioms:
  • .
  • If and , then .
  • If and , some satisfies .
The last axiom is augmentation. In particular, every maximal matroid independent set within a given subset has maximum cardinality there: otherwise augmentation would enlarge it.
The monotone decomposition of a submodular set function subtracts each element's smallest possible marginal increment. For , define
The set function is a modular set function: the contributions of each element, and the constant , cancel in
Subtracting this equality from the submodularity inequality for proves that is a submodular set function. Also , so it is a normalised set function.
For , the inclusion and diminishing returns imply
Adding elements one at a time now proves that is a monotone set function. Since it starts at zero, it is also a nonnegative function. Thus has all the required properties.
Here modular set function means equality in the intersection–union identity; a constant term is allowed. If one imposed the additional convention , the claimed decomposition of an arbitrary would require . The displayed constant is essential for the problem as stated. For , take and .
Use the chain lower bound for a submodular set function. Order , set with , and put . For each , reveal its elements in this same order. Since , diminishing returns and the normalised set function property give
Apply this to each and interchange the finite sums. Every element occurs exactly times, so
This is the exact-cover inequality for submodular set functions. Some can be negative: exact multiplicity, rather than merely at least occurrences, is what makes the argument valid without monotonicity. In fact the nonnegative function hypothesis is unnecessary here. If , every is empty and both sides vanish.
The intersection–union definition of a submodular set function is
The diminishing returns characterization of submodularity says that its marginal increments decrease as the conditioning set grows:
To obtain diminishing returns from submodularity, apply the intersection–union inequality to and . Their intersection is and their union is , giving exactly the displayed comparison.
Conversely, assume diminishing returns, and enumerate . Put and . Since and , summing the marginal increment comparisons gives the telescoping sum
Rearrangement proves submodularity. When is empty, both sums are zero, so the proof includes that case.
For a set function , the four properties are:
Here monotone set function means nondecreasing under inclusion; it does not require strict increase.
The residual constraint graph is a tree, rooted conveniently at , with children and with a child of . Solve it by the tree-structured constraint satisfaction algorithm: enforce arc consistency from children toward their parents, then choose a surviving root value and select supported child values in the opposite direction.
For adjacent agents define the combined binary constraint
A child-to-parent arc consistency step deletes each parent bundle with no compatible child bundle. Process the edges in the order , , , .
First, needs a nonempty subset of . Supporting reduces 's constraint domain to
Indeed, leaves only for but gives value ; and leave no possible item for . Each of the four retained choices has a compatible choice for .
Next, supporting reduces 's constraint domain to all nonempty subsets of . To see why item cannot remain in 's bundle, a disjoint compatible bundle from would have to be , but then values its own bundle at and 's at least at . Conversely any nonempty subset of is compatible with .
Supporting next reduces 's constraint domain to
If held item , disjointness would force , whose value is below 's value for 's bundle. If holds but not , then , and needs value at least to avoid envying . If holds neither, supports every nonempty subset of .
Finally, supporting leaves
The removed choices contained both and , leaving no item for . Every displayed choice has a compatible choice for .
Choose , then supported child values, giving
Items remain unallocated, which this variant expressly permits. To check every envy-free allocation inequality, the matrix of agents' additive valuations of these bundles, with rows and columns both ordered , is
Each diagonal entry is at least every entry in its row. The bundles are nonempty, pairwise disjoint, and contain only positively valued items, so all remaining requirements hold.
Why does selecting supported children suffice? The residual constraint graph has no graph cycle, so different child subtrees have no constraints between them. Child-to-parent arc consistency has already ensured a compatible continuation below every retained parent value. Applying this observation recursively proves that the downward choices complete a solution without backtracking. With variables and maximum constraint domain size , the basic compatibility checks require time complexity in Big O notation, counting each binary constraint evaluation as one operation; evaluating bundle sums has its own input-dependent cost.
Restrict each agent to nonempty bundles of items that they value positively. Let the positive-value supports be
The residual constraint domains are , with sizes , respectively. The no-waste allocation and nonempty-bundle requirements are now built into these constraint domains.
If , every pair , is disjoint. Moreover, , so both envy-free allocation inequalities hold automatically because all values are nonnegative. Thus all three binary constraints disappear for the pairs
The only positive-support overlaps, and hence the remaining constraint graph edges, are
where parentheses list the shared items.
Each listed pair really retains restrictions. For , , , , respectively, let both endpoints choose , , , : this violates disjointness while belonging to both residual constraint domains. The directional envy-free allocation inequalities are also individually nontrivial. For example, for , choosing and makes envious, while choosing and makes envious. The analogous shared-item comparisons apply on the other three edges.
Figure 1.
The residual allocation constraint graph; labels show shared positive-value items
. Details.
Before using no-waste allocation to restrict the constraint domains, there is one constraint graph vertex for each of . Every distinct pair has a disjointness binary constraint, and also the two directional envy-free allocation constraints. Thus the constraint graph is the complete graph , with all ten edges.
The nonempty-bundle and no-waste allocation requirements are unary and add no edges. The original all-item coverage constraint has been removed because this variant permits unallocated items.
Figure 1.
The allocation constraint graph before restricting the constraint domains
. Details.
With agent variables, each constraint domain has cardinality . Their total number of listed domain values is , while the Cartesian product of the domains has
complete assignments before constraints.
With item variables, each constraint domain has cardinality . Their total number of listed domain values is , while their Cartesian product has
complete assignments. These are raw domain-space sizes. The larger agent-variable space includes overlaps and missing items; imposing the allocation constraints reduces it to the same actual complete allocations represented directly by item variables.
Use one variable per item, with constraint domain . Its value is the recipient agent. Every assignment automatically allocates each item exactly once, so separate coverage and disjointness constraints are unnecessary.
For every ordered pair , impose
Here is an indicator function. The constraint involves every with ; one may formally give it scope , since zero coefficients make the other variables irrelevant. These constraints state envy-free allocation using the comparing agent's additive valuation on both sides. In contrast to part (a), they generally involve more than two variables.
For fair division, let and let the additive valuation of agent be . Use one variable per agent, with constraint domain , the power set of the items. Empty bundles are permitted in this original formulation.
Require pairwise disjoint sets:
Each such binary constraint involves exactly . Require complete allocation by the single all-variable constraint
Finally impose the envy-free allocation binary constraints
each on . The two directions for a pair use different agents' additive valuations and must both hold. These conditions give precisely an ordered set partition of the items that is an envy-free allocation.
Write for the three item constants, for the banks, for the corrected load, unload and move actions, and for instantiated with the items' actual current locations. A fully executable plan in the STRIPS model of part (g) is
Thus the seven crossings carry rabbit west, nothing east, fox west, rabbit east, carrot west, nothing east, rabbit west.
Immediately before those crossings, the items left on the departure bank are respectively . None contains an incompatible pair, so each displayed has its safety preconditions. Each loaded crossing carries exactly one item, and all three finish west.

Pinned article: Introduction to the OurBigBook Project

Welcome to the OurBigBook Project! Our goal is to create the perfect publishing platform for STEM subjects, and get university-level students to write the best free STEM tutorials ever.
Everyone is welcome to create an account and play with the site: ourbigbook.com/go/register. We belive that students themselves can write amazing tutorials, but teachers are welcome too. You can write about anything you want, it doesn't have to be STEM or even educational. Silly test content is very welcome and you won't be penalized in any way. Just keep it legal!
We have two killer features:
  1. topics: topics group articles by different users with the same title, e.g. here is the topic for the "Fundamental Theorem of Calculus" ourbigbook.com/go/topic/fundamental-theorem-of-calculus
    Articles of different users are sorted by upvote within each article page. This feature is a bit like:
    • a Wikipedia where each user can have their own version of each article
    • a Q&A website like Stack Overflow, where multiple people can give their views on a given topic, and the best ones are sorted by upvote. Except you don't need to wait for someone to ask first, and any topic goes, no matter how narrow or broad
    This feature makes it possible for readers to find better explanations of any topic created by other writers. And it allows writers to create an explanation in a place that readers might actually find it.
    Figure 1.
    Screenshot of the "Derivative" topic page
    . View it live at: ourbigbook.com/go/topic/derivative
  2. local editing: you can store all your personal knowledge base content locally in a plaintext markup format that can be edited locally and published either:
    This way you can be sure that even if OurBigBook.com were to go down one day (which we have no plans to do as it is quite cheap to host!), your content will still be perfectly readable as a static site.
    Figure 5. . You can also edit articles on the Web editor without installing anything locally.
    Video 3.
    Edit locally and publish demo
    . Source. This shows editing OurBigBook Markup and publishing it using the Visual Studio Code extension.
  3. https://raw.githubusercontent.com/ourbigbook/ourbigbook-media/master/feature/x/hilbert-space-arrow.png
  4. Infinitely deep tables of contents:
    Figure 6.
    Dynamic article tree with infinitely deep table of contents
    .
    Descendant pages can also show up as toplevel e.g.: ourbigbook.com/cirosantilli/chordate-subclade
All our software is open source and hosted at: github.com/ourbigbook/ourbigbook
Further documentation can be found at: docs.ourbigbook.com
Feel free to reach our to us for any help or suggestions: docs.ourbigbook.com/#contact