Theorem 15.3: is bidder-submodular iff the core of every coalition is iff the VCG vector of every coalition lies in its core
ProvedSupplyChainTheory.vcg_core_characterizationTheorem 15.3. For a coalitional value function , the following three statements are equivalent:
(i) is bidder-submodular: for every bidder and coalitions , ;
(ii) for every coalition , , where ;
(iii) for every coalition , the VCG payoff vector lies in .
Bidder-submodularity is thus exactly the condition under which the VCG auction's payoff vector is a competitive outcome whatever the set of participating bidders, so that the revenue deficiency, non-monotonicity, collusion and false-name defects of Sect. 15.4.2 cannot occur. The book's proof shows (i) (ii) by telescoping the marginal contributions along a chain of coalitions, (ii) (iii) since , and (iii) (i) by exhibiting, from a failure of submodularity, a coalition that blocks its own VCG vector.
Formalization Note The statement is the conjunction (i) (ii) and (i) (iii); payoff vectors are functions on all players, and the conditions defining the core and involve only the players of .
import Definitions.Def_SupplyChainTheory_auctions
namespace SupplyChainTheory
theorem vcg_core_characterization {n : ℕ} (V : Finset (Fin (n + 1)) → ℝ)
(hV : IsCoalitionalValue V) :
(BidderSubmodular V ↔ ∀ S : Finset (Fin (n + 1)), (0 : Fin (n + 1)) ∈ S → ∀ π,
InCore V S π ↔ (∑ k ∈ S, π k = V S ∧ ∀ k ∈ S, k ≠ 0 → 0 ≤ π k ∧ π k ≤ vcgPayoff V S k))
∧ (BidderSubmodular V ↔ ∀ S : Finset (Fin (n + 1)), (0 : Fin (n + 1)) ∈ S →
InCore V S (vcgPayoff V S)) := by sorry
end SupplyChainTheory
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.