Ex-Post Max-Min Fairness of Generalized AGV Mechanisms

We generalize the standard Arrow-d'AspremontGerard- Varet (AGV) mechanism to balance the net payoffs received by all agents, while maintaining Bayesian incentive compatibility, ex-post efficiency, and ex-post budget balance of the standard AGV mechanism. In a private-value setting with independent agents' types and the principal's cost, we formulate a convex optimization problem to find the mechanism (that achieves ex-post max-min fairness) over a set of parameterized generalized AGV mechanisms, through maximizing the expected value of the minimum ex-post net payoff. We reformulate the convex program as a linear program that can be effectively solved when the number of agents is small. When the number of agents is large, we propose to solve the formulated convex program through the incremental subgradient method. Numerical results on two action models show that the proposed mechanism significantly outperforms the standard AGV mechanism in terms of the expected minimum ex-post payoff.