Monotonicity (mechanism design)
In mechanism design, monotonicity refers to a property of allocation rules or payment rules that ensures that a bidder's chances of winning an item or the payments they make do not decrease when they increase their bid. It is a crucial concept for ensuring incentive compatibility in mechanisms. Different types of monotonicity exist depending on the context and the specific requirements of the mechanism.
More formally, a mechanism is considered monotonic if, for any bidder i and any vector of bids from other bidders b-i:
-
Allocation Monotonicity: If bidder i wins the object with bid bi given b-i, then they must also win the object with any bid b'i > bi given b-i. In other words, raising one's bid cannot decrease the probability of winning. This type of monotonicity is sometimes called individual monotonicity.
-
Payment Monotonicity: If bidder i wins the object with bid bi given b-i, and their payment is pi, then their payment p'i with a higher bid b'i > bi given b-i must satisfy p'i >= pi. In many mechanism design settings, payment monotonicity is closely linked to allocation monotonicity.
Monotonicity is vital for incentive compatibility because it prevents bidders from strategically lowering their bids in order to increase their expected utility. If a mechanism is not monotonic, a bidder might be better off misreporting their value, violating the desired truthful revelation property of the mechanism.
Different mechanisms may require different types or strengths of monotonicity. For instance, the Vickrey-Clarke-Groves (VCG) mechanism, a well-known incentive-compatible mechanism, satisfies a strong form of monotonicity. Other mechanisms might satisfy weaker notions of monotonicity while still achieving incentive compatibility under certain conditions.
Violation of monotonicity can lead to undesirable outcomes such as collusion, reduced revenue, or inefficient allocations. Thus, ensuring monotonicity is a key consideration in the design and analysis of mechanisms.