Summary
This paper studies the incorporation of fairness constraints into revenue-optimal single-item auctions. Specifically, it focuses on a scenario with two groups bidders. Within each group, bidders' private valuations are sampled i.i.d. from a distribution, with the two groups having different valuation distributions. The fairness constraint is defined by two numbers, $\alpha_1$ and $\alpha_2$, requiring the mechanism to ensure that the expected allocation to group $i$ is at least $\alpha_i$. The objective is to identify the revenue-optimal EPIC and IR mechanism that meets this fairness criterion.
The submission first investigates the static case where only one round of the auction is conducted and characterizes the optimal mechanism. The authors demonstrate that, compared to the optimal auction without fairness constraints, the optimal mechanism with fairness constraints subsidizes all bidders in the virtual value space to enhance their chances of allocation. Additionally, the paper observes that the optimal mechanism provides subsidies to the disadvantaged group. From a technical perspective, the argument extends Myerson’s original proof of optimal auctions without fairness considerations in a relatively straightforward manner.
Next, the authors extend their analysis to a dynamic auction setting where the auction is conducted over $T$ rounds, with an item being auctioned in each round. Valuations can vary across rounds. In this dynamic setting, the fairness constraint imposes a lower bound on the expected number of allocated items in future rounds based on the allocation history of previous rounds. Bidder incentives become more complex, as they might underbid in the current round to gain an advantage in future rounds with higher-valued items due to the fairness constraints. The authors characterize the optimal mechanism using backward induction, noting that the optimal mechanism starting from round $t$ depends only on the remaining fairness quota for each group. With this insight, the optimal mechanism starting from round $t$ can be determined by implementing Myerson’s auction after adjusting the bidder's value by the externality (the decrease in future revenue from awarding the item to the bidder in the current round). With a discounting factor, finding the exact optimal mechanism requires exponential time. The authors propose methods to efficiently approximate it through early stopping and discretization.
The paper concludes with a numerical experiment illustrating how different fairness constraints impact revenue and bidders’ utilities in each group.
Minor comments:
- There is an extra symbol in equation (6).
- It would be much clearer to add a description of the allocation for each region in Figure 1.
Strengths
- The problem is well-motivated. I believe studying fairness notions in dynamic auction settings has its potential. In addition, the specific model considered in the paper feels reasonable.
- The paper fully characterizes the optimal mechanism and provides some high-level interpretations.
- The paper is well-written. Technical parts are easy to follow.
Weaknesses
- Experiments seem too simple, it would be better if the authors conducted a more extensive experiment.
- Though the authors claim that results should extend to more than 2 groups, it would better to include some formal statements.