Stanford CS329H: Machine Learning from Human Preferences | Autumn 2024 | Mechanism Design

Key Concepts

Mechanism Design, Rule Making, Strategic Behavior, Social Choice, Game Theory, Auctions, Pricing, Incentive Compatibility (IC), Individual Rationality (IR), Revenue Maximization, Bidders, Items, Allocation, Payments, Buyer Type, Virtual Values, Second Price Auction (Vickrey Auction), Reserve Price, Distributional Analysis (Ex-ante IC, Ex-interim IC, Ex-post IC), Generalized Second Price Auction, Learning in Mechanisms, Regret, Pairwise Preferences, Information Asymmetry, Digital Goods.

Mechanism Design: The Science of Rule Making

• Definition: Mechanism design is the science of designing rules for interactions such that desirable outcomes are achieved even when participants act strategically (e.g., adversarially, self-interestedly).
• Goal: To design rules that lead to a socially desirable outcome, even with strategic actors. The designer defines what constitutes a "desirable outcome."
• Connections: Combines social choice theory, voting theory, and game theory.
• Applications: Traditionally studied in economics, but increasingly relevant in computing, especially with the rise of large internet companies. Used in auctions, pricing, and collective decision-making.
• Examples:
  • Auction design for radio wave spectrum allocation.
  • Pricing and ordering of items on Amazon.
  • Ad buying process in web search (Google, Facebook).
• Impact: Has had a significant impact on society due to its application in pricing, auctions, and collective decision-making.
• Key Question: Can we infer bias and true economic preferences to design effective mechanisms?

Core Components of a Mechanism

• Buyers and Items: Involves buyers with different valuations for items (e.g., coffee, cupcake).
• Mechanism's Task: To decide which buyers receive which items and how much they pay.
• Goal: To align payments with the value of items for individuals and ensure that those who value the item the most win the bid.
• Strategic Behavior: Buyers have an incentive to be strategic, aiming to pay as little as possible while still acquiring the desired items.

Examples of Mechanisms

• Posted Price: The designer sets a fixed price for each item, and buyers decide whether to purchase based on their individual utility.
  • Utility: The difference between the buyer's value for the item and the posted price.
  • Limitation: Provides limited information about individual preferences, only revealing that the buyer's value is higher than the stated price.
• Standard Auction: Buyers bid on items, and the highest bidder wins.
  • Strategic Bidding: Buyers may bid strategically, not necessarily reflecting their true value.
  • Potential Issue: May not maximize social welfare or reveal true utilities.
• Second Price Auction (Vickrey Auction): Buyers bid, but the winner pays the second-highest bid.
  • Mitigation of Strategic Bidding: Partially mitigates strategic bidding by incentivizing bidders to bid closer to their true value.
  • Potential Issue: Vulnerable to adversarial bidding and value mismatch between seller and buyers.
• Second Price Auction with Reserve Price: A minimum price is set by the seller. The highest bidder wins if their bid exceeds the reserve price, and they pay the maximum of the reserve price and the second-highest bid.
  • Mitigation of Value Mismatch: Addresses the issue of value mismatch between buyers and the seller.
  • Mitigation of Adversarial Behavior: Partially mitigates adversarial behavior by guaranteeing the seller a minimum price.

Formal Setup

• m Items, n Buyers: Each buyer has a value for every possible bundle of items.
• Buyer Type: The list of values for all possible bundles of items for a buyer.
• Mechanism Functions:
  • Allocation: Decides which buyers get which items.
  • Payments: Defines how much each buyer pays.
• Revenue: The sum of payments across all buyers.
• Strategic Bidding: Buyers may bid strategically, not necessarily their true value.

Properties of Mechanisms

• Incentive Compatibility (IC): Incentivizing agents to bid their true value.
  • Goal: To elicit true preferences and maximize revenue.
  • Second Price Auction Claim: The second price auction is incentive compatible, meaning bidders maximize their utility by bidding truthfully.
  • Proof (Informal):
    • Bidding higher than true value: No benefit if already the winner; negative utility if it leads to overpaying.
    • Bidding lower than true value: May lose the auction and get zero utility.
  • Levels of Information:
    • Ex-ante IC: Truthfulness in expectation, given knowledge of the distribution of values.
    • Ex-interim IC: Truthfulness, given knowledge of own value and distributions over others' values.
    • Ex-post IC: Truthfulness, given knowledge of everyone's actual values.
• Individual Rationality (IR): Ensuring that buyers are no worse off participating in the mechanism than not.
  • Second Price Auction Claim: The second price auction is individually rational.
  • Proof (Informal): Bidders pay nothing or less than their true value by participating.

Revenue Maximization

• Meerson's Auction: A revenue-maximizing single-item auction that is also incentive compatible.
• Virtual Values: Defined as the difference between the value and a normalized notion of the distribution of values.
• Procedure:
  1. Compute virtual values for all bidders.
  2. If all virtual values are less than zero, do not allocate the item.
  3. Otherwise, allocate the item to the buyer with the highest virtual value.
  4. The winner pays a thresholded bid based on the inverse of the virtual value function.
• Connection to Second Price Auction: Can be converted into a standard second price auction with a reserve price.
• Limitations: Optimal mechanisms for even two items are unknown.

Learning in Mechanisms

• Integration of Machine Learning: Incorporating learning models into mechanisms to predict prices or placement.
• Online Learning: Using online learning to address questions about revenue and bidding.
• Regret: The difference between the cumulative revenue for the seller versus the best price they could have gotten in hindsight.
• Learning to Bid: Mechanisms where buyers learn how to bid over time based on interactions and signals.
• Profit Inequality and Sector Problems: Analyzing mechanisms with adversarial or random buyer arrival orders and valuations.
• Learning with Revealed Preferences: Using observed buyer actions to predict future behavior and inform pricing mechanisms.

Pairwise Feedback Options for Digital Goods

• Motivation: Addressing the challenge of pricing digital goods (e.g., prompt completions) where the value is unknown until after the item is created.
• Information Asymmetry: The seller doesn't know the value of the completion until it's done, creating a cycle problem.
• Proposed Mechanism: Based on pairwise preferences and partial preferences to learn the potential value of items.
• Loop:
  1. Learn the potential value of items.
  2. Use a second price auction mechanism with predicted prices.
• Goal: To achieve high revenue and incentive compatibility in information-asymmetric settings.
• Reverse Auction Application: Applying the mechanism to compensation for hazardous labeling tasks, treating harm as a negative value.
• Results: Shows that using pairwise feedback reduces the amount of signal needed and improves overall regret compared to uniform allocation.

Conclusion

Mechanism design is a powerful tool for designing interactions that achieve desirable outcomes even with strategic participants. Key concepts include incentive compatibility, individual rationality, and revenue maximization. While optimal mechanisms are known for single-item auctions, challenges remain in more complex settings, such as multi-item auctions and digital goods. Integrating learning models into mechanisms is an active area of research, with applications in pricing, ad placement, and even compensation for hazardous tasks. The field offers valuable lessons for preference elicitation and optimization in AI.