bundle_of
def
Under an allocation that gives each item x to agent s(x), agent i's bundle is the set of items given to i.
Statement
def bundle_of {m n : ℕ} (σ : Fin m → Fin n) (i : Fin n) : Finset (Fin m)- Defined in
- Exploring Relations among Fairness Notions in Discrete Fair Division, arXiv:2502.02815 v3, Defs. 5, 7, 8, 11; formalized by the operator (Claude), 2026-10-02
- Verified
- 02 Oct 2026
- Axioms
- none listed
- Used by 139
- eefx_bundle_imp_approx_efkLet n ≥ 3 and let σ be an allocation of m goods among n agents with nonnegative additive valuations u such that every agent's bundle is…
- complete_pmms_matroid_rank_sharp_mms_factorFor every integer n ≥ 2, every finite set of m indivisible goods, every profile of matroid-rank valuations v_1, ..., v_n on the goods, and…
- two_agent_common_bivalued_safe_partitionFor any ratio r with 1 ≤ r ≤ 2, any number of chores m, and any two-agent chore cost profile c satisfying is_scaled_bivalued_chores r c,…
- efx_exists_of_two_universal_small_goods_irLet m and n be natural numbers with n positive. There are m+2 goods with nonnegative real additive values for n agents. Each agent values…
- is_efx_goods_iff_bundle_totalsFor real additive valuations, EFX is equivalent to the following total-value inequalities: for every pair of distinct agents i,j and each…
- equal_marginal_balanced_high_count_allocationsFor at least two agents, k at least two, and n*k chores, each agent has an arbitrary set of high chores. There are n allocations such that…
- wpropx_gadget_to_natWeighted PROPX for natural-number costs cast to the reals with shares num_i/den implies its natural-number version multiplied through by…
- efx_intact_obstruction_no_coarseNo assignment of the four intact old bundles and new singleton in the explicit seven-good instance is EFX after casting its item values to…
- is_ef1_choresEF1 for chores with additive costs: whenever agent i envies agent j, removing some chore from i's own bundle removes the envy.
- two_agent_bivalued_equal_marginal_sharp_mmsFor two agents (n = 2), ratio r with 1 ≤ r and r ≤ 2, and m chores with a cost profile c : Fin 2 → Fin m → ℝ satisfying…
- is_alpha_eefx_allocationAn allocation is alpha-EEFX if each agent's bundle is alpha-EEFX for that agent.
- op_1004_two_type_efx_fpo_equal_ratioFor any real number a > 1, every two-agent instance on a finite set of goods where each good is valued at a by both agents or at 1 by both…
- is_efx_goods_exists_unenviedFor a positive number of agents, any EFX allocation of nonnegative additive goods can be changed to another EFX allocation that weakly…
- is_ex_ante_proportional_choresAn allocation lottery p over allocations of m chores among n agents is ex-ante proportional for chore cost functions c if each agent i's…
- efx_exists_of_positive_perturbationsFor any finite real additive valuation profile, if adding every strictly positive common real epsilon to every item value admits a…
- efx_allsource_three_pair_perturbed_strict_sanityThe perturbed partial state is strictly envy-free, and the explicit complete allocation remains EFX.
- op819_has_online_single_high_alpha_monoIf a deterministic online algorithm guarantees a beta-EFX allocation for n agents and m goods under single-high valuations with ratio R >=…
- goods_utilityThe utility vector of an allocation of goods under additive valuations: agent i's value for her own bundle.
- efx_allsource_pair_sanityThe old state is envy-free with all values positive and charity small for each owner; the explicit complete witness is EFX and IR.
- additive_valuation_bundle_last_casesAssigning the additional last good to agent s adds exactly its value to the old bundle value of s and leaves every other bundle value…
- is_efx_goodsAn allocation is EFX if for every pair of distinct agents i and j, and every good g in j's bundle, agent i values her own bundle at least…
- three_agent_seven_chores_equal_marginal_sharp_mmsFor three agents, seven chores, any ratio r in [1,2], and any scaled bivalued additive cost profile with common ratio r, there is a…
- mms_exists_monotoneEvery instance with n agents and m goods, in which every agent has a monotone valuation v_i with v_i(∅) = 0, has an MMS allocation: an…
- is_alpha_ef1_goodsAn allocation of m indivisible goods to n agents is alpha-EF1 under additive valuations u if for every pair of distinct agents i and j…
- ido_opposite_pair_cost_le_four_thirdsIn an identically ordered instance of m chores and n agents with 2 * n ≤ m and nonnegative costs c where every agent has maximin share 1,…
- mms_block_count_valuationThe valuation induced by a partition: a bundle is worth the number of its blocks that it entirely contains.
- eefx_imp_approx_efkLet n ≥ 3 and let σ be an allocation of m goods among n agents with nonnegative additive valuations u such that every agent's bundle is…
- uniform_bivalued_obstruction_no_equal_marginal_exact_mmsFor every integer t at least 2 and every real ratio r strictly between 1 + 1/t and 1 + 1/(t-1), the instance with 4t chores where agent 0…
- efx_three_bonus_distinct_sanityEvery value in the explicit matrix is positive and each bonus is no larger than every old good for each agent. The old allocation…
- efx_three_bonus_distinct_no_realFor the explicit positive four-agent seven-good instance, if an EFX allocation assigns its four old goods to distinct agents and its three…
- is_ef1_fairAn allocation is EF1-fair to agent i if, against every other agent j, i does not envy j, or removing some item from j's bundle ends the…
- is_efx_goods_insert_of_unenvied_of_minAdding a good to an unenvied agent preserves EFX if every other agent values the new good no more than every old good in that recipient's…
- has_bivalued_efx_sub_mms_instanceGiven natural numbers n, R, and d, there exists a finite additive instance with n agents where each item value is either 1 or the natural…
- is_alpha_efk_allocationAn allocation σ : Fin m → Fin n of m goods among n agents is α-EFk under valuations v : Fin n → Finset (Fin m) → ℝ if for all distinct…
- bundle_of_permute_agentsReassigning every good by the inverse of an agent permutation makes the bundle of agent i equal to the old bundle of the permuted agent.
- efx_exists_of_two_universal_small_goodsFor a positive number of agents with nonnegative real additive values, suppose each of the last two goods is weakly less valuable to every…
- is_efx_goods_nat_cast_iffFor natural-number item values, EFX after casting values to the reals is equivalent to all natural-number inequalities comparing each…
- balanced_high_counts_insufficient_for_sharp_mmsThere are seven chores, costs equal to 1 or 3/2, and a bundle S such that three times the number of chores in S is at most 9, three times…
- efx_pair_binary_partial_valueIn the explicit binary instance, restrict to the first eight goods and assign the adjacent pairs to the four agents in order. Every agent…
- is_wefx_goods_unit_weights_iff_is_efx_goodsWhen all agents have unit entitlements, weighted EFX is equivalent to standard unweighted EFX.
- op_1719_bivalued_efx_sub_mms_two_agents_two_ratioFor two agents and item values in {1, 2}, there exists an additive instance with a complete EFX allocation in which some agent obtains…
- is_ex_ante_proportional_of_equal_marginalEvery equal-marginal lottery over complete chore allocations is ex-ante proportional for any profile of chore costs.
- op819_single_high_efx_one_goodFor any number of agents $n \ge 1$, $m = 1$ good, and parameter $R \ge 0$, there exists a deterministic online algorithm that achieves a…
- scaled_common_ratio_bivalued_efx_fpo_envyfreeable_two_agents_core_of_efx_countsNormalized two-agent bivalued core from the EFX arithmetic: if both agents' values lie in {1, r} and for every choice of the four type…
- efx_of_bundle_card_le_oneAn allocation where each agent receives at most one good is unconditionally EFX for any nonnegative additive valuations.
- is_pmms_fairAn allocation is pairwise-MMS-fair to agent i if, for every other agent j, i's bundle is worth to i at least i's two-agent maximin share…
- lxv_is_ef1_iffIn the instance, real EF1 is equivalent to the Boolean integer check lxv_ef1.
- mms_exists_monotone_of_leWith n ≥ 1 agents and at most n goods, monotone valuations always admit an MMS allocation (give good j to agent j); so μ(n) ≥ n.
- pmms3c_verify_soundIf the certificate check accepts w for allocation σ, then σ is not PMMS for agent w mod 3.
- additive_valuation_bundle_sum_iteAn additive value of an allocated bundle equals the sum over all goods of the item value when that good has the specified owner, and zero…
- efx_equal_pairs_few_blockers_ir_completionIf some old pair p has at most one blocking agent, then some complete EFX allocation preserves all old utilities while leaving all four…
- efx_no_self_three_split_full_efxA complete EFX allocation of the matrix has owners (2,1,2,1,3,2,3,1,0,0,0,0,0).
- ido_remaining_chores_cost_le_one_thirdIn an identically ordered instance with nonnegative costs and maximin share 1 for each agent, every remaining chore g in V (with index at…
- is_alpha_mms_choresAn allocation σ of m chores among n agents is α-MMS for cost functions c if each agent i's total cost for her assigned bundle bundle_of σ…
- nash_welfareNash welfare of an allocation σ of m goods to n agents with additive valuations v_i: NW(σ) = ∏_i v_i(X_i), where X_i is the bundle of…
- efx_three_split_sanityAll values are positive. In the initial partial allocation (0,0,1,1,2,2,3,3), each agent values all four old bundles equally, values the…
- is_efx_goods_permute_of_utility_leA bundle permutation that weakly improves every agent's own additive value preserves EFX for nonnegative item values.
- wpropx_gadget_wpropx_natWeighted PROPX for natural-number costs and shares num_i/den, multiplied through by den.
- efx_anchor_lock_full_efxThe nondegenerate instance has a complete EFX allocation with owners (3,1,1,1,2,2,1,2,1,0,3,0).
- is_weighted_propx_choresWeighted PROPX for chores (zero-tolerant): for every agent i and every chore e in her bundle, her cost for the bundle without e is at most…
- wpropx_gadget_bcAgent i's cost for her own bundle under an allocation, for natural-number costs.
- relevant_min_valueAgent i's value for the least valuable of her relevant edges held by agent j, or 0 if j holds none.
- is_propm_orientationAn orientation is PROPm if every agent's value for her bundle plus her PROPm slack d_i is at least her proportional share.
- mnw2_lb_bundleIn the three-good instance, agent i's value for her bundle under σ is the sum of her values of the goods g ∈ {0, 1, 2} with σ(g) = i.
- two_agent_balanced_symmetric_swap_lotteryIf both bundles of a two-way partition cost at most alpha times the maximin share of each agent, the equal mixture of that allocation and…
- is_efx_goods_all_pairsFor nonnegative additive values, the EFX inequalities also hold when the observer and the target agent coincide.
- is_efx_goods_equiv_goodsRelabeling a finite set of goods through a bijection, both in the valuation profile and allocation, preserves and reflects EFX.
- propm_orientation_of_out_degree_twoIf the simple graph underlying a loopless multigraph has an orientation with every out-degree at most two, then for nonnegative additive…
- ex_post_one_mms_chore_lottery_single_agentFor a single agent (n = 1) and any m indivisible chores with nonnegative additive costs c, there exists an allocation lottery that is…
- fpo_of_itemwise_weighted_maxIf an allocation σ assigns each item g to an agent maximizing w_i * u_i(g) for positive weights w, then σ is fractionally Pareto optimal…
- social_costThe social cost of an allocation: the sum over agents of their cost for their own bundle.
- is_wefx_goodsAn allocation σ of m goods to n agents with positive entitlements w is weighted EFX (WEFX) if for every pair of distinct agents i and j,…
- not_has_online_alpha_ef1_four_of_gt_oneFor any alpha > 1, there is no deterministic online algorithm guaranteeing an alpha-EF1 allocation for four agents under exact frequency…
- lxv_sum_bundleThe integer value of a bundle equals the explicit six-term sum lxv_val.
- efx_min_cycle_full_efxThe instance has a complete EFX allocation with owners (0,0,0,0,1,3,2,2,2,3,2,1,1) that strictly improves all four original utilities; it…
- op913_randomized_mms_barrier_under_upgrade_recourseOpen problem OP-913 (arXiv:2611.00432, after Thm 4.1): for every number of agents n ≥ 2, has_randomized_online_mms_barrier_breaker n…
- efx_anchor_two_locks_preserve_threeIn the two-lock anchor family, a complete EFX allocation can preserve the original three agents’ starting utilities for every positive…
- chore_prop_share_le_maximin_shareFor any number of agents n >= 1, items m, and additive chore cost function u, the proportional share (sum of costs divided by n) is at…
- expected_chore_costThe expected cost of agent i : Fin n at horizon m : ℕ under a randomized online chore algorithm alg : RandomizedOnlineChoreAlgorithm n for…
- has_online_alpha_ef1_algorithm_zeroFor any positive number of agents n, there exists a deterministic online algorithm guaranteeing a 0-EF1 allocation under exact frequency…
- op562_not_consistent_eefx_of_ge_three_halvesFor any number of agents n at least 3 and any error factor rho at least 3/2, no consistent online algorithm can guarantee any positive…
- is_mxs_fairAn allocation is MXS-fair to agent i (minimum EFX share, arXiv:2502.02815, Def. 10) if i's bundle is worth to her at least her bundle in…
- is_alpha_ef1_goods_one_of_ef1_goodsIf an allocation is exactly EF1 (in the is_ef1_goods sense) for nonnegative additive valuations, then it is 1-EF1 in the…
- pmms_fair_not_imp_mms_fairOpen problem 4 of arXiv:2502.02815 has a negative answer: for submodular goods with binary marginals and equal entitlements, pairwise MMS…
- multigraph_orientation_subsidy_four_agentsThere is a four-agent multigraph with monotone graph valuations, normalised so the largest marginal is 1, in which every envy-free…
- efx_no_self_three_split_sanityThe matrix is positive; each agent values every old triple equally at her baseline, values every good in her own triple at least as much…
- is_alpha_efx_goodsAn allocation of m indivisible goods to n agents is alpha-EFX under additive valuations u if for every pair of distinct agents i and j,…
- mnw2_bundle_valueIf τ(g) = T(O g, N g) for a map T : {0,1}² → {0,1}, then the value u(X_k) of agent k's bundle under τ is the sum of the group sums…
- is_eef1_fairAn allocation is epistemic-EF1-fair to agent i if some allocation gives i the same bundle and is EF1-fair to her.
- mms_bad_coverA family of n partitions of the m goods into n (nonempty) blocks is a bad cover if no choice of one block per partition gives pairwise…
- is_connected_po_choresAn allocation of chores is Pareto optimal among connected allocations if no connected allocation costs every agent at most as much and…
- chore_maximin_shareThe maximin share (MMS) of an agent with additive chore costs u among n agents: the infimum over all partitions P : Fin m → Fin n of the…
- is_fractionally_pareto_optimal_zero_goodsWhen there are no goods, every complete allocation is fractionally Pareto optimal.
- op_1004_two_type_efx_fpo_single_typeFor two agents and any finite set of identical goods valued at c > 0 by agent 0 and d > 0 by agent 1, there exists an allocation that is…
- efx_three_small_goods_completion_loss_or_splitIn the explicit eleven-good instance cast to real values, every complete EFX allocation which keeps each of the four old adjacent pairs…
- efx_pareto_lock_sanityAll values are positive. The partial allocation (1,0,0,0,1,2,4,3), where 4 means unallocated, is EFX and meets the baseline utilities; the…
- ef1cost_social_cost_eqThe social cost of an allocation equals the sum over items of the cost of each item to its owner.
- efx_intact_obstruction_charity_strictEach agent strictly prefers her assigned bundle in the explicit six-good partial allocation to the unallocated seventh good.
- all_agent_bivalued_equal_marginal_divisible_choresFor every n at least two and k at least two, any common ratio r at least one, and any n-agent scaled bivalued additive cost profile on n*k…
- is_alpha_efx_choresAn allocation σ of m chores among n agents is α-EFX under additive costs c if for every pair of distinct agents i and j, and every chore e…
- multigraph_orientation_subsidy_three_halvesThere is a three-agent multigraph with monotone graph valuations, normalised so the largest marginal is 1, in which every envy-free…
- is_envy_free_with_subsidy_perm_leIf (σ, p) is envy-free with subsidies, then for every permutation π of agents, ∑_i v_i(A_{π(i)}) ≤ ∑_i v_i(A_i).
- scaled_common_ratio_bivalued_efx_fpo_envyfreeable_zero_goodsWhen m = 0, the empty allocation Fin.elim0 and zero subsidy vector 0 satisfy EFX, envy-freeness with subsidies, and fractional Pareto…
- is_connected_allocationAn allocation is connected if every agent's bundle is connected on the path.
- pmms_matroid_rank_mms_factor_two_agentsFor two agents with matroid-rank valuations, every complete pairwise maximin-share fair allocation gives each agent at least 1/(2-1) = 1…
- is_efx_fairAn allocation is EFX-fair to agent i (arXiv:2502.02815, Def. 3, equal entitlements) if, against every other agent j, either i does not…
- is_pmms_fair_choresPairwise maximin share (PMMS) for chores: allocation σ is PMMS for agent i if, for every other agent j and every way of splitting X_i ∪…
- efx_no_self_three_split_perturbed_fullThe nondegenerate perturbation admits a complete EFX allocation with owners (2,1,2,1,3,2,3,1,0,0,0,0,0).
- ef1_cost_gap_instance_specIn the instance (0, 1/2, 1/2), (1/3 - 2d, 1/3 + d, 1/3 + d) with 0 < d <= 1/6, the optimal social cost is 2/3 + 2d and the best EF1 social…
- ef1_implies_two_sub_one_div_n_mms_choresFor any n ≥ 2 agents with nonnegative additive costs over m indivisible chores, any EF1 allocation satisfies (2 - 1/n)-MMS.
- efx_three_small_goods_obstruction_sanityIn the explicit eleven-good instance all natural item values are strictly positive, and each of goods 8,9,10 is no more valuable than…
- efx_exists_of_common_pair_order_evenFor any positive number of agents and an even number 2k of goods with nonnegative additive values, suppose every agent weakly prefers…
- efx_source_two_full_efxThe explicit complete EFX allocation preserves the other three initial utilities.
- large_low_quota_sharp_mms_counterexampleWith eleven agents and sixty-five chores, there is a bivalued cost function with ratio 7/4 and a bundle of six chores that meets the…
- efx_allsource_three_pair_sanityThe partial allocation is envy-free; all values are positive and charity is owner-small; the explicit full EFX allocation preserves all…
- is_ef1_goodsEF1 for goods: every agent i either does not envy agent j, or stops envying j after some single good is removed from j's bundle.
- efx_nondeg_cycle_full_efxThe nondegenerate instance has a complete EFX allocation with owners (0,0,0,0,1,3,2,2,2,3,2,1,1).
- pareto_dominates_choresAn allocation of chores Pareto-dominates another if it costs every agent at most as much and some agent strictly less.
- mms_exists_monotone_of_partition_coverReduction to MMS partitions: if for every choice of one partition P_i of the m goods into n bundles per agent there is an allocation in…
- is_envy_free_with_subsidyAn allocation with nonnegative payments p is envy-free if v_i(A_i) + p_i ≥ v_i(A_j) + p_j for all agents i, j.
- is_efx_goods_scaleMultiplying each agent's additive valuation vector by a positive constant c_i > 0 preserves and reflects whether an allocation is EFX.
- mms_two_agents_four_goods_not_existsWith two agents, four goods and monotone valuations, an MMS allocation need not exist (both agents have MMS 2 in the Table 1 instance, but…
- efx_intact_obstruction_partial_efxIn the explicit seven-good instance restricted to the first six goods, assigning {5} to agent 0, {0,1} to agent 1, {2,3} to agent 2, and…
- wpropx_gadget_avFor natural-number costs cast to the reals, the additive cost of a bundle is the cast of the natural-number cost.
- mxs_fair_imp_prop1_fair_of_submodularOpen problem 3 of arXiv:2502.02815 has a positive answer: for submodular goods (monotone, v(empty) = 0) and equal entitlements, every…
- connected_ef1_po_chores_incompatibleFor chores on a path with additive, strictly positive costs, EF1 and Pareto optimality (among connected allocations) can be incompatible:…
- utilitarian_welfareUtilitarian social welfare of an allocation σ with additive valuations v_i: SW(σ) = ∑_i v_i(X_i), where X_i is the bundle of agent i under…
- efx_three_pair_anchor_sanityThe starting allocation is envy-free with r+2 goods per bundle and one charity good; the lifted complete witness is EFX.
- efx_pair_binary_full_efxFor the explicit binary nine-good valuation matrix cast to real values, the full allocation (3,3,1,2,0,2,1,1,0), listing the owner of each…
- op561_has_online_algorithm_monoIf there exists an online algorithm guaranteeing a beta-EF1 allocation for n agents under exact frequency predictions, then for any alpha…
- efx_pair_binary_no_one_splitFor the explicit binary nine-good matrix cast to real values, no allocation encoded by the one-split construction is EFX.
- weighted_efx_two_type_of_integer_ratioFor two agents with positive entitlements whose ratio max(w_0, w_1) / min(w_0, w_1) is a positive integer, every instance with two types…
- aps_fair_not_imp_prop1_fairOpen problem 2 of arXiv:2502.02815 has a negative answer: for additive goods with unequal entitlements, an allocation can give every agent…
- three_agent_critical_equal_weight_allocation_familyFor three agents and seven chores, suppose each agent designates four chores high. There exist three allocations such that every chore…
- ef1cost_bundle_iteFor two agents, the allocation giving the items of Y to p and the rest to q has bundles Y and its complement.
- efx_exists_of_universal_least_goodFor a positive number of agents and nonnegative additive values, if the last good is weakly least valuable for every agent, existence of…
- maximin_shareThe maximin share of a valuation among n agents: the maximum, over partitions of the items into n bundles, of the value of the worst bundle.
- mxs_fair_not_imp_eef1_fairOpen problem 1 of arXiv:2502.02815 has a negative answer: for additive goods and equal entitlements, MXS does not imply EEF1, already for…
- efx_three_small_goods_obstruction_no_current_irIn the explicit eleven-good instance cast to real values, every EFX coarse completion has some agent whose utility is strictly less than…
Lean source view module on GitHub
/-- The bundle of agent `i` under the allocation `σ` that gives item `x` to agent `σ x`. -/ def bundle_of {m n : ℕ} (σ : Fin m → Fin n) (i : Fin n) : Finset (Fin m) := Finset.univ.filter fun x => σ x = i