Explicitly simple near-tie auctions (Q6164504)

The paper is devoted to the problem of truthfully auctioning a single item, that can be either fractionally or probabilistically divided among several winners when their bids are sufficiently close to a tie. More precisely, the authors show that Myerson's payment rule is explicitly simple for two agents (regardless of the allocation rule), but become substantially more complex as the number of agents grows. The following is valid: Theorem. Every 2-agent partitioned single-item allocation (PSA) has a unique explicitly simple no positive transfers (NPT) implementation, which is the Myerson payment rule. For three agents or more, the authors characterize the near-tie allocation rules that admit such explicit payments, and provide an iterative algorithm to compute them. For the entire collection see [Zbl 1515.91014].