additive_valuation
def
The additive valuation with item values u: a bundle is worth the sum of its items' values.
Statement
def additive_valuation {m : ℕ} (u : Fin m → ℝ) : 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 111
- 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…
- 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,…
- le_knapsack_optEvery budget-feasible subset S of C achieves value at most OPT(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…
- is_budget_feasibleAn allocation of m items to n agents is budget-feasible under item sizes s and agent budgets B if the allocated bundles are pairwise…
- 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…
- ido_chore_opposite_pairs_cost_boundsIn 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,…
- 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…
- 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…
- 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…
- knapsack_optFor an item subset C and budget b, OPT(C) is the maximum additive value v(S) over all subsets S ⊆ C with total size s(S) ≤ b.
- 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,…
- 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…
- is_consistent_algorithmAn online algorithm alg for n agents is consistent if for every m : ℕ and all nonnegative valuations v and predictions a_hat with exact…
- is_fractionally_pareto_optimal_scaleMultiplying each agent's additive valuation vector by a positive scale c_i > 0 preserves and reflects fractional Pareto optimality.
- 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…
- is_budget_feasible_emptyThe empty allocation giving no items to any agent is budget-feasible whenever all agent budgets are nonnegative.
- 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_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…
- guarantees_alpha_eefxAn algorithm alg guarantees alpha-EEFX for n agents under error factor ρ if for every m : ℕ, all nonnegative valuations v and all…
- 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…
- lxv_additive_valuationIn the instance, the additive value of a set is its integer value divided by 20.
- 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…
- exists_minimally_envied_source_extensionFor nonnegative additive values and any family of finite bundles A, suppose A(s) is unenvied by every agent relative to her own A(i), and…
- orientation_prop_shareThe proportional share of agent i in a multigraph orientation instance: half her value for her incident edges (each edge is relevant to…
- efx_of_bundle_card_le_oneAn allocation where each agent receives at most one good is unconditionally EFX for any nonnegative additive valuations.
- 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…
- 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 σ…
- balanced_high_count_chore_mms_boundFor n at least two, k at least two and n*k bivalued chores, a bundle of size k whose high-cost count times n is at most the total…
- 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.
- 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…
- 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…
- 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…
- envied_subset_contains_added_goodFor nonnegative additive item values, if every agent values a bundle S at most her threshold, any subset of S union a singleton g that…
- 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…
- 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_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…
- exists_minimally_envied_subsetGiven a real additive valuation profile, a real utility threshold for each agent, and a finite bundle envied by some agent relative to…
- 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…
- 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.
- 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…
- pmms3c_cost_nat_eqThe fold computing agent i's cost of the chores selected by P agrees with the additive cost of that set.
- 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…
- additive_valuation_erase_of_memRemoving a good belonging to a finite bundle subtracts exactly its item value from the additive value of that bundle.
- 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 ∪…
- 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…
- social_welfareThe utilitarian social welfare of an allocation X under a homogeneous additive valuation v is the sum of values v(X_i) over all agents i.
- 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.
- pareto_dominates_choresAn allocation of chores Pareto-dominates another if it costs every agent at most as much and some agent strictly less.
- 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.
- wpropx_gadget_avFor natural-number costs cast to the reals, the additive cost of a bundle is the cast of the natural-number cost.
- 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.
- 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…
- 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…
- 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…
- 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 additive valuation with item values `u`. -/ def additive_valuation {m : ℕ} (u : Fin m → ℝ) : Finset (Fin m) → ℝ := fun S => ∑ j ∈ S, u j