Dynamic mechanism design is a challenging extension to ordinary
mechanism design in which the mechanism designer
must make a sequence of decisions over time in the face of
possibly untruthful reports of participating agents. Optimizing
dynamic mechanisms for welfare is relatively well understood.
However, there has been less work on optimizing
for other goals (e.g. revenue), and without restrictive assumptions
on valuations, it is remarkably challenging to characterize
good mechanisms. Instead, we turn to automated mechanism
design to find mechanisms with good performance in
specific problem instances.We extend the class of affine maximizer
mechanisms to MDPs where agents may untruthfully
report their rewards. This extension results in a challenging
bilevel optimization problem in which the upper problem
involves choosing optimal mechanism parameters, and
the lower problem involves solving the resulting MDP. Our
approach can find truthful dynamic mechanisms that achieve
strong performance on goals other than welfare, and can be
applied to essentially any problem setting—without restrictions
on valuations—for which RL can learn optimal policies.
more »
« less
utomating Mechanism Design with Program Synthesis
This paper presents a new approach to the automated design of mechanisms that incentivize selfinterested agents to maximize a global objective (such as revenue or social welfare) in equilibrium. Prior work on automated design has either been restricted to relatively simple mechanisms, or represented mechanisms as neural networks that are hard to interpret and cannot easily incorporate prior knowledge. In this paper, we propose program synthesis as a way around these issues. Concretely, we formalize the problem of designing mechanisms in the form of multiagent environments whose transition and reward functions are programs in a domainspecific language (DSL), in order to maximize an outcome such as revenue or social welfare under given assumptions on how agents act in these environments. We present an initial algorithm, based on a combination of stochastic search over programs and Bayesian optimization, for this problem. We empirically evaluate the algorithm in two domains with different characteristics. Our experiments suggest that the approach can synthesize programmatic mechanisms that are humaninterpretable and also perform well.
more »
« less
 Award ID(s):
 1704883
 NSFPAR ID:
 10391908
 Date Published:
 Journal Name:
 Proc. Automated Learning Agents Workshop
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


The Nash social welfare problem asks for an allocation of indivisible items to agents in order to maximize the geometric mean of agents' valuations. We give an overview of the constantfactor approximation algorithm for the problem when agents have Rado valuations [Garg et al. 2021]. Rado valuations are a common generalization of the assignment (OXS) valuations and weighted matroid rank functions. Our approach also gives the first constantfactor approximation algorithm for the asymmetric Nash social welfare problem under the same valuations, provided that the maximum ratio between the weights is bounded by a constant.more » « less

We develop a versatile new methodology for multidimensional mechanism design that incorporates side information about agent types to generate high social welfare and high revenue simultaneously. Prominent sources of side information in practice include predictions from a machinelearning model trained on historical agent data, advice from domain experts, and even the mechanism designer’s own gut instinct. In this paper we adopt a priorfree perspective that makes no assumptions on the correctness, accuracy, or source of the side information. First, we design a metamechanism that integrates input side information with an improvement of the classical VCG mechanism. The welfare, revenue, and incentive properties of our metamechanism are characterized by novel constructions we introduce based on the notion of a weakest competitor, which is an agent that has the smallest impact on welfare. We show that our metamechanism, when carefully instantiated, simultaneously achieves strong welfare and revenue guarantees parameterized by errors in the side information. When the side information is highly informative and accurate, our mechanism achieves welfare and revenue competitive with the total social surplus, and its performance decays continuously and gradually as the quality of the side information decreases. Finally, we apply our metamechanism to a setting where each agent’s type is determined by a constant number of parameters. Specifically, agent types lie on constantdimensional subspaces (of the potentially highdimensional ambient type space) that are known to the mechanism designer. We use our metamechanism to obtain the first known welfare and revenue guarantees in this setting.more » « less

Coalition structure generation (CSG) is a critical problem in multiagent systems, involving the optimal partitioning of agents into disjoint coalitions to maximize social welfare. This paper introduces SALDAE, a novel multiagent path finding algorithm for CSG on a coalition structure graph. SALDAE employs various heuristics and strategies for efficient search, making it an anytime algorithm suitable for handling largescale problemsmore » « less

In an instance of the weighted Nash Social Welfare problem, we are given a set of m indivisible items, G,and n agents, A, where each agent i in A has a valuation v_ij for each item j in G. In addition, every agent i has a nonnegative weight w_i such that the weights collectively sum up to 1. The goal is to find an assignment that maximizes the weighted Nash Social welfare objective. When all the weights equal to 1/n , the problem reduces to the classical Nash Social Welfare problem, which has recently received much attention. In this work, we present a approximation algorithm for the weighted Nash Social Welfare problem that depends on the KLdivergence between the distribution w and the uniform distribution on [n]. We generalize the convex programming relaxations for the symmetric variant of Nash Social Welfare presented in [CDG+17, AGSS17] to two different mathematical programs. The first program is convex and is necessary for computational efficiency, while the second program is a nonconvex relaxation that can be rounded efficiently. The approximation factor derives from the difference in the objective values of the convex and nonconvex relaxation.more » « less