Lemma 2.2 — cancelability extends from a single good to any set disjoint from S ∪ T
ProvedRoundRobinEq.CancelableBluff.lemma_2_2cancelable-valuationsfair-divisionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be cancelable, and let with . Then
- ;
- ;
- .
Cancelability is defined by adding one good; the lemma says that adding a whole set of fresh goods to both sides never reverses a comparison. It is the tool behind Lemma 3.3 and the observation that, for cancelable valuations, a good of largest singleton value also has the largest marginal value.
Formalization Note The page reads "", which means ; it is stated as Disjoint R (S ∪ T). The page writes for inside the statement. The lemma assumes only cancelability: the page's codomain and the standing monotonicity are not used, so the Lean statement takes any real-valued cancelable (a statement at least as strong as the page's).
Preamble
import Mathlib import Definitions.Def_RoundRobinEq_CancelableBluff_Setting
Formal statement
namespace RoundRobinEq.CancelableBluff
theorem lemma_2_2 {M : Type*} [DecidableEq M] (v : Finset M → ℝ) (hv : IsCancelable v)
(S T R : Finset M) (hR : Disjoint R (S ∪ T)) :
(v (T ∪ R) < v (S ∪ R) → v T < v S) ∧
(v T ≤ v S → v (T ∪ R) ≤ v (S ∪ R)) ∧
(v S = v T → v (S ∪ R) = v (T ∪ R)) := by sorry
end RoundRobinEq.CancelableBluff
Source
Amanatidis et al., Round-Robin Beyond Additive Agents, arXiv:2301.13652v1, p. 5, Lemma 2.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.