Proof of Theorem 5.1 — the value-query algorithm is maximal in range

Consider the algorithm of §5.2 on report profiles $b=(b_1,\dots,b_n)$ of valuations on bundles of $M=\{1,\dots,m\}$: compute a maximum-weight matching $P$ between items and bidders with edge costs $b_i(\{j\})$, and a bidder $t$ maximizing $b_i(M)$; if $b_t(M)$ is strictly larger than the weight of $P$, give all items to $t$, otherwise give every item matched by $P$ to its matched bidder. Let $R$ be the set of allocations that give all of $M$ to a single bidder, together with the allocations (pairwise disjoint bundles) in which every bidder receives at most one item.

Then, for every choice of the maximum-weight matching and of the top bidder as functions of the reports, the algorithm is maximal in range with range $R$ on the normalized valuations: whenever $b_k(\emptyset)=0$ for every $k$, the output lies in $R$ and

Combined with the §5.1 observation on maximal-in-range rules, this is the incentive-compatibility half of Theorem 5.1.

Formalization Note The statement is over all normalized report profiles, a larger domain than the complement-free valuations of Theorem 5.1; normalization makes the welfare of "all items to $i$" equal to $b_i(M)$ and the welfare of a one-item-each allocation equal to the weight of the corresponding matching.