Knaster's Procedure of Sealed Bids

N Players Discrete Items Auction O(N) Rounds

Overview

Knaster's sealed bid procedure enables fair division of indivisible goods through a truthful auction mechanism combined with monetary transfers to ensure proportional outcomes.

Fairness Properties

Proportional with Monetary Transfer

Formal Statement: Each player receives utility ≥ $\frac{1}{n}$ of their total valuation when bidding truthfully.

Proof Sketch: If player $i$ bids truthfully ($b_i^j = v_i^j$), their final utility is:

$$U_i = \sum_{j \in S_i} v_i^j - \sum_{j \in S_i} b_i^j + \frac{\sum_k payment_k}{n}$$

The redistribution mechanism ensures this equals at least $\frac{1}{n} \sum_j v_i^j$.

Strategy-Proof

Intuition: Bidding true valuations is a dominant strategy because overbidding risks overpaying, while underbidding risks losing valuable items.