Automated Dynamic Mechanism Design
Authors: Hanrui Zhang
Vincent Conitzer
Venue: NeurIPS 2021 Poster (2021)
Keywords: mechanism design
dynamic mechanism design
automated mechanism design

Abstract: We study Bayesian automated mechanism design in unstructured dynamic environments, where a principal repeatedly interacts with an agent, and takes actions based on the strategic agent's report of the current state of the world.  Both the principal and the agent can have arbitrary and potentially different valuations for the actions taken, possibly also depending on the actual state of the world.  Moreover, at any time, the state of the world may evolve arbitrarily depending on the action taken by the principal.  The goal is to compute an optimal mechanism which maximizes the principal's utility in the face of the self-interested strategic agent.

We give an efficient algorithm for computing optimal mechanisms, with or without payments, under different individual-rationality constraints, when the time horizon is constant.  Our algorithm is based on a sophisticated linear program formulation, which can be customized in various ways to accommodate richer constraints.  For environments with large time horizons, we show that the principal's optimal utility is hard to approximate within a certain constant factor, complementing our algorithmic result.  These results paint a relatively complete picture for automated dynamic mechanism design in unstructured environments.  We further consider a special case of the problem where the agent is myopic, and give a refined efficient algorithm whose time complexity scales linearly in the time horizon.
    
In the full version of the paper, we show that memoryless mechanisms, which are without loss of generality optimal in Markov decision processes without strategic behavior, do not provide a good solution for our problem, in terms of both optimality and computational tractability.  Moreover, we present experimental results where our algorithms are applied to synthetic dynamic environments with different characteristics, which not only serve as a proof of concept for our algorithms, but also exhibit intriguing phenomena in dynamic mechanism design.

Automated Dynamic Mechanism Design
Hanrui Zhang
Vincent Conitzer
Duke University
Duke University conitzer duke. .dd
hrzhang@cs. duke. edu
Abstract
We study Bayesian automated mechanism design in unstructured dynamic environ- ments, where principal repeatedly interacts with an agent, and takes actions based on the strategic agent's 's report of the current state of the world, Both the principal and the agent can have arbitrary and potentially different valuations for the actions taken, possibly also depending time, the state of the world may evolve arbitrarily depending on the action taken by the principal. The goal is to compute an optimal mechanism which maximizes the principal's 's utility in the face of the self-interested strategic agent.
the actual state of the world. Moreover, at any
We give an efficient algorithm for computing optimal mechanisms, with or without payments, under different andividual-rationalii constraints, when the time horizon is constant. Our algorithm is based on a sophisticated linear program formulation, which be customized in various ways to accommodate richer constraints. For environments with large time horizons, we show that the principal's 's optimal utility is hard approximate within certain constant factor, complementing our algorithmic result. These results paint a relatively complete picture for automated dynamic mechanism design in unstructured environments. We further consider a special case of the problem where the agent is myopic, and give a refined efficient algorithm whose time complexity scales linearly in the time horizon.
In the full version of the paper, we show that memoryless mechanisms, which are without loss of generality optimal in Markov decision processes without strategic behavior, do not provide a good solution for our problem, terms of both opti- mality and computational tractability. Moreover, we present experimental results where our algorithms are applied to synthetic dynamic environments with different characteristics, which not only serve as proof of concept for our algorithms, but also exhibit intriguing phenomena in dynamic mechanism design.
1 Introduction
Consider the following scenario. A company assembles an internal research group to develop key technologies to be used in the company's next-generation product in 5 years. The more progress the group makes, the more successful the product likely to be. Since research progress is hard to monitor, the company manages the group based on its annual reports. At the beginning of each year, the group submits a report, summarizing its progress in the preceding year, as well as its needs for the current year. Taking into consideration this report (and possibly also reports from previous years), the company then decides the compensation level and the headcount of the group in the current year. Moreover, after the product launches, the company may also pay a bonus members of the group, depending on how successful the product is.
For simplicity, suppose annual report consists of two items: research progress (satisfac- tory/unsatisfactoryy, and need to expand (no request/request for an intern/request for a full-time employee). The company's 's goal is to encourage and facilitate research progress while keeping the expenses reasonable. So, natural managing strategy is to increase (resp. decrease) the compensation
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

level when the reported research progress is satisfactory (resp. unsatisfactory), and to allow the group to expand only when necessary, i.c., when the reported research progress is unsatisfactory. However, the research group may have different goal than the company's. s. Suppose members of the group do not care about the success of the product per se. Instead, their primary goal is to maximize the total compensation received from the company, and for this reason, they may be incentivized to misreport the situation. In other words, the company faces a dynamic mechanism design problem. where the principal (i.e., the company) needs to implement (and commit to) a mechanism (i.e., a managing strategy) that achieves its goal through repeated interactions, in the presence of strategic behavior of the agent (i.e., the research group).
Indeed this problem is nontrivial. For example. if the company implements the above strategy, then the group will report satisfactory progress regardless of the actual situation, which maximizes the group's total compensation over the years, but also causes greater expenses for the company and jeopardizes the success of the product. To counter this, the company may additionally promise significant bonus contingent on the success of the product. This creates incentives for the group to make more progress, and discourages overreporting the progress, because the group is not allowed to expand when the reported progress is satisfactory. That is, actual progress is unsatisfactory, this introduces an incentive to report this truthfully so that the group may expand. However, this also runs the risk of encouraging the group to report unsatisfactory progress in order to expand even if actual progress is satisfactory, because more members always make more progress, which leads to higher (chance of) bonus, whereas the cost of expanding is paid by the company and therefore irrelevant to the group.
One may try to fix this by introducing more rules, possibly replacing existing ones. For example, the company may allow the group to recruit an intern, but not a full-time employee, when the reported progress is unsatisfactory. Then, in the next year, if the reported progress improves, the company allows the group to make return offer to the intern as full-time employee. Or alternatively, the company may unconditionally allow the group to recruit interns (which are less costly), but never full-time employees. In addition to the above, the company could also temporarily decrease the compensation level when a new member joins, and later adjust the compensation based on how the reported progress improves. While all these ad hoc rules make intuitive sense, it is not immediately clear which (combinations of) rules are better, how to optimize parameters of these rules (c.g.. the number of new members allowed per year and the amount by which the compensation is adjusted), or whether there is a better set of rules that look totally different.
As demonstrated by the foregoing discussion, in general, the problem of finding an optimal mechanism in unstructured dynamic environments, such as the above example, turns out to be extremely rich and challenging. In such environments, the actions of the principal may go beyond the allocation of items to the agent, and affect the state of the world in arbitrary ways. Moreover, both the principal and the agent may have arbitrary valuations for these actions, which also depend on the current state of the world. In economic theory, the characterize-ane aarriii--nd--ooeeeeeeee approach [25] 13 30 to mechanism design has achieved spectacular success in both static and dynamic environments, by exploiting structure of the environment to construct a characterization of optimal mechanisms, often leading to closed-fom form or computationally tractable solutions. However, since the environments under consideration here loosely structured at best, the classical sharacterizz-and-Seee suited. When disregarding the agent's incentives, one could treat the problem of finding an optimal strategy as a planning problem, which is known to be solvable efficiently (6] 21 (1), However, as discussed above, the agent's strategic behavior can ruin the performance of such strategy. From a computational perspective, while numerous methods for automated mechanism design which efficiently compute optimal mechanisms without heavily exploiting structures of the environment, have been proposed [10) [1] all existing methods work only for static environments with one- one-time interactions, and it is not immediately clear how generalize these methods to dynamic environments. All this brings us to the following question:
approach does not seem particularly
Can we efficiently compute optimal mechanisms in unstructured dynamic environments?
2

---

1.1
Our Results
In this paper, we study the problem of computing optimal mechanisms single-agent. discrete-time dynamic environments with finite time horizon, without any further structural assumptions. Our main results (presented in Section
3 can be summarized as follows:
Efficient algorithm:
when the time horizon is fixed, there is polynomial-time algorithm for computing optimal mechanisms, with or without payments, that maximize the principal's 's utility
facing strategic agent.
Inapproximability: when the time horizon can be large, it is NP-hard to approximate the principal's 's optimal utility within factor of (7/8 + E) for any E >> O.
To the best of our knowledge, our algorithm for constant time horizons is the first that efficiently computes optimal mechanisms in unstructured dynamic environments. The fact that our algorithm cannot scale beyond constant time horizons is by no means surprising: optimal dynamic mechanisms generally depend on the entire history, and as result, the straightforward description of such mechanism is exponentially large in the time horizon. Our inapproximability result further rules out the possibility of computing succinet representations of approximately optimal mechanisms that can be efficiently evaluated. These results together paint a complete picture of the computational complexity of dynamic mechanism design in unstructured environments.
1.2 Further Related Work
Dynamic mechanism design. The problem we study can be situated in the broad area of dynamic mechanism design, and below discuss some representative related work. For a more comprchensive exposition, sec, c.g., the survey by Pavan [29] and the one by Bergemann and Välimäki [8) In the context of efficient (i.e., dynamic pivot mechanism, which generalizes the VCG mechanism in static environments, and Athey and Segal [2] propose the team mechanism, which focuses budget- baagget--alacednesss. As for optimal (i.e.. Levenue-maximinn
mechanisms, Bergemann and Välimäki (7) propose the
mechanisms, which are more closely related to our results, following earlier work (5 R 17I. Pavan al. (30] generalize the classical characterization by Myerson (25) into dynamic environments, unifying previous results with continuous type spaces. Ashlagi al. 1 study ex-post individual-rational dynamic mechanisms for repeated auctions, and give an efficient (1 E) aapproximmaionn to the optimal revenue for single agent with independent valuations across items. Mirrokni et al. (24) study non-clairvoyant dynamic mechanism design, where future distributional knowledge is unavailable to the principal. All these results for optimal mechanisms follow the characterize-ame wwwpeterizze-nd-sollll solve approach, which is quite different from the computational approach that we take.
Particularly related to our results is the work by Papadimitriou et al. [28 who study setting where one item is sold at each time, and agents' valuations can be correlated across items. They show that designing an optimal deterministic mechanism is computationally hard even when there is only one agent and two items (thereby ruling out the possibility of efficiently computing optimal deterministic mechanisms in our model, which is more general). And moreover, they give polynomial-size linear program formulation for optimal randomized mechanisms for independent agents when the number of agents and the time horizon are both constant. Restricted to a single agent, their LP formulation can be viewed as special case of our main result: they focus on revenue maximization with single item to be allocated at each time, in a model where the principal's 's actions cannot affect the future valuations of the agent; on the other hand, we allow the principal to care about actions as well as revenue, with actions being general and unstructured (as opposed to allocation/no allocation). where the future state of the world can depend arbitrarily on the principal's 's actions as well as the current state.
Automated Mechanism Design. There is a rich body of research regarding automated mechanism design (AMD) in (essentially) static environments. Conitzer and Sandholm [10 [I] initiated the study of automated mechanism design. They consider various specific static setups, and show that computing optimal deterministic mechanisms, even with single agent, is often NP-hard (which also rules out the possibility of efficiently computing optimal deterministic mechanisms in our model, since the 1-period case a special case), while computing optimal randomized mechanisms is often tractable. Conceptually related to our model, Hajiaghayi et al. [20] consider model where agents
3

---

enter and leave the mechanism online (but still have one-time interactions with the mechanism), and provide an algorithm for computing mechanisms that are competitive against the optimal allocation from hindsight. Sandholm et al. (35 study automated design of multistage mechanisms, but these are not for dynamic settings; instead, the motivation is to implement static mechanisms using multiple rounds of queries in order to minimize the communication cost. Sandholm and Likhodedov [44] study automated design of combinatorial auction mechanisms, and Balcan et al. 13] 4 study the sample complexity thereof. Kephart and Conitzer [22] 23 and Zhang et al. (37] study AMD with partial verification and/or reporting costs. More recently, various methods have been proposed for automated mechanism design via machine learning [4 27 and in particular, deep learning [TS] 18] 36, 32)
All these results are essentially for static environments, whereas in this paper, we focus solely on AMD in dynamic environments. Another emerging research direction is Bayesian persuasion in dynamic environments [16 33]. In particular, Celli et al. [9] study an algorithmic persuasion problem in extensive-form games, where single signal is sent at the very beginning. and Gan et al. [9 study an algorithmic persuasion problem in anfinit-hhorizn
discounted MDPs, where a new signal is sent at every time. These persuasion problems can be viewed the principal has the commitment power, and tries to encourage the agent to truthfully report their private information, whereas in (dynamic) Bayesian persuasion, the agent has the commitment power, and tries to induce the principal to act in favor of the agent by selectively revealing their private information.
dual problem of ours: in our problem,
2 Preliminaries
Dynamic environments. Throughout this paper, consider single-agent, discrete-time environ- ments with a finite time horizon. Below, we give a general definition of such a dynamic environment. Let T be the time horizon, S be the state space, and A be the action space. The agent observes the state, but the principal controls the action that is taken. For each 1 E [7]. let of" S x A - IR be the principal's valuation function, where for each state s E S and action the principal when playing action a in state 8, at time i; similarly, let uz4 : S x A + R be the agent's s value function. Let Po (S)) be the initial distribution over states, and for each E S, denote by Po(s) the probability that the initial state is s. Moreover, for each E [7]. let P: S x A - (SS) be the transition operator, which maps a state-action pair (s, a) time to the distribution of the next state at time L + 1, (r(s, a) E A (SS). We denote by Pr(s, a, 8') the probability that the next state is 8 when playing action in state s at time E [T]. For notational simplicity, let Po a, s') Po(s") for all s, s E S and E A. (Note that the first actual action is taken at t = 1 not = 0 possibly based on the state at 1.)
A, 1 (s, a) is the value of
Histories. A t-step history is sequence of states and actions (s1, a1, .2..... Q $t, at), where for each i E [t]. it the case that s; E and a, E A. For each [T], let He be the set of all possible (-step histories, i.e.,
H, {(11, ai....,..................... St, at) s; E S,,a, E A for all E [t]]
For each h = ($1, a1..... S2, ar) E H. let [h| = t, and moreover, for any Si+1 E S, 0++1 E A. let h + ($141, 11+1 (s1, a...............................
................................ St+1 d(+1). ). Let Ho = (0). where @ corresponds to the empty history with [0] = 0. Let H = Ho U Uterr-a He be the set of all possible histories of length at most T 1 in the dynamic environment. Note that H does not contain histories of length T.
Dynamic mechanisms. Dynamic mechanisms are more powerful than static ones, in that they may depend on the entire history, rather than only the current state. A (randomized) dynamic mechanism M- (TT,P p) consists of an action policy π and a payment function p. The action policy T:: H. x S + (AA) maps each history h E H. extended with the reported current state s E S, to distribution over actions T Th,, s) A(A). We denote by T(h, s, a) the probability that the action taken by the mechanism is a for (h, s). The payment function p: H x S - IR maps the extended history (h, s) to real number, i.e., the payment, made from the agent the principal (but it can be negative). We remark that in principle, one can absorb payments into the action space. However, doing so would make the action space uncountable, introducing subtleties into the computational problem (which is the main focus of this paper). Here, we keep payments separate and explicit to avoid such issues. Also, our algorithm allows linear constraints on feasible payments, including but not limited to: nonnegative payments, payments, etc. See Section 3.2 for more details.

---

Utilities. Fixing mechanism M = (T.. we can then define the onward utility of the principal and the agent. Let up H S - be the principal's onward utility function under mechanism M, defined inductively such that
(1htn + Σ Pintt((,,,,8) up u (1++ (o, ())a))))) + p(h, 8), s'
M up (h, 8) = -- (h,
with the boundary condition that uit (h, = O for all h E Hr and & S. Here, all summations are over the entire state/action space. Let up (0) be the overall utility of the principal, i.e.,
up Σ Po(s) up (0. s).
Similarly, let u² ; x S be the agent's onward utility function under mechanism M, defined such that
" (h, 8) = Σ &)), (VAHHal Pil++ w (h- (s)))),6) p(h, 8),
where u s) = for all h E Hr and E S. And let u (0) be the overall utility of the agent, i.e.,
A (0) = Σ Po(s) a 8)
We remark that while the above definition assumes that the principal cares about payments as much the agent does, in fact, our algorithm allows for the principal to care about payments in arbitrary linear way (including possibly not at all). See Section 3.2 for detailed discussion.
Incentive-compatiby mechanisms. We say a mechanism M is incentive-compatille (IC) if the agent can never achieve higher overall utility by misreporting the state, even in sophisticated ways. Formally, reporting strategy r H x S S maps each history / extended with the current state to a reported state s', which is possibly different from s. Note that the agent only (mis)reports the current state, since the principal can memorize all historical reports. This reporting strategy induces reported history r(h) = (81, al,..., Sy, ae) for each actual history h = ($1 .i,..., at), where for each E [t].
$f r ($1, a1. : 01-1,;
Note that we abuse notation here: in particular, r(h, s) denotes a reported state, whereas r(h) denotes a reported history. And without loss of generality, we only consider deterministic reporting strategies. Given a mechanism M and a reporting strategy r, we can define the agent's utility function uA under M and r inductively such that
M,r
(1h4)1(8.0++ E (p)tti(s,,,s)) u u. (h+ (s, s')
M.r (h, U.A (rr s) Σ
p(r(h)) r(h,,)
where u i...
Mrr sh = 0 for all h E Hr and s E S. And let u Mrr (0) be the overall utility of the agent,
u M-r(0) = Σ Po(s) M (0, 8).
Ad.r is the utility function of the agent applying the reporting strategy r in response to the In words, U.A. mechanism M. The mechanism M is IC iff for any such reporting strategy r,
(0)
2 A Mar (0).
Since the revelation principle holds in dynamic environments (see, e.g., (26)). we focus on IC mechanisms in the rest of the paper!]
'Of course, the revelation principle will not hold in our dynamic setting if we allow it to generalize static setting in which the revelation principle does not hold. For example, in the case of partial verification every type being able misreport every other type or costly misreporting, the revelation principle is known to hold only under certain conditions [23). this paper, we only consider the standard mechanism design setting in which every type can freely misreport any other type, but our techniques can be generalized to the other settings well.
5

---

andividually-rationi: mechanisms. When payments are allowed, it is standard to impose individuullraaiionalltt (IR) (also known as which roughly say that the agent should never be made worse off by participating in the mechanism. In this paper, we consider two versions of constraints:
constraints on the mechanism.
A mechanism M is overall IR if the overall utility of the agent nonnegative, i.c., ux This ensures that the agent is willing to participate in the overall mechanism.
A mechanism M is dynamic IR if the onward utility of the agent is nonnegative for every history h and current state 8, i.e., A (h, s) 2 O for all h E 7 and s E S. This stronger notion of IR further ensures that the agent has no incentive to leave the mechanism at any time.
As discussed in later sections, our algorithms work for all 3 cases regarding IR constraints: IR (which results in an unbounded objective value if payments are allowed and valued by the principal), overall IR, and dynamic IR.
3 Computation of Optimal Mechanism
In this section, we investigate the computational problem finding an optimal dynamic mechanism, which maximizes the principal's overall utility. For concreteness, we assume that all components of the dynamic environment, including the time horizon T, state and action spaces S and A, valuation functions of and v and transition operator P, are given explicitly input.
3.1 Hardness Result for Long-Horizon Environments
First we show that the problem with an arbitrarily large time horizon intractable. In general, takes exponentially many parameters in 7 to describe dynamic mechanism, which immediately rules out the possibility of computing a flat representation of an optimal mechanism polynomial time. However, this leaves the possibility of computing succinct representations, e.g., oracle which maps extended histories to distributions over actions. Our hardness result shows that it is hard to approximate the principal's maximum utility within a constant factor, which rules out the possibility of such succinet representations that can be efficiently evaluated, assuming 7 NP. The proof of the theorem, well all other proofs, are deferred to the appendices.
Theorem 1. When the time horizon T be arbitrarily large, it is NP-hard to approximate the principal's 's maximum utility within a factor 7/8 + foror any & > 0.
3.2 Algorithm for Short-Horizon Environments
Now we give polynomial-timg timeilllltmmmeeeee algorithm for computing optimal mechanism when T is constant. Our algorithm based on delicate linear program (LP) formulation, which relies on the following notation and concepts.
Feasible history-state pairs. A history-state pair (h, where h = (81, 01.,01...... 8t,00) 0e). is i- feasible if (sj, 85+1) > for every j E (i,i + 1,..., 1). and (st, 0t, 8) > 0. In other words, starting from 8; and taking the actions specified in h, there is positive probability that the rest of the history and the state are generated from the transition operator. We say a pair (h, 8) is feasible if it is l-feasible.
Feasible extensions. For two history- pairs (h, and (h', where h (s), a1.... St. az) and R = (s/, di,,,,,,,,, sy,, ),),, we say that (h',')) feasibly extends (h, s), i.e., (h, s) C (h's8) (h, s) (h/, s'), or the following conditions hold simultaneously:
|h| < |n' = t'.
For any E [t). (st, az) (s/, at) (this holds automatically when h and therefore |h| 0).
8 = 8/411
(h', s') is (16) + 1e-feisible (note that this does not require h itself to be feasible).

---

objective:
max
Σ
Σ NeEA
uf (1 s(), + y(h,s) +((+,,
(1)
(h),) is feasible
flow constraints:
z(h, = Σ x(h,,,,0
WEE,
(2)
aEA
=(0, 5) = (s)
VsES
(3)
z(h + (s, a), 5') = Pii a, x(h, s,s, ES
(4)
utility: u(h,8)=
E W
Σ LaEA
a (0)))l((sa)-<((h,6 v(K,'')
wh H. E
(5)
IC constraints:
s
Σ asA
e - -0,,))
PIN+1(0,,,88))
u(h + (s',
th H, ES
aEA 1h|+1 (s', as'
(6)
PE
[h] (Ops up: 8)
u(h, s) 2
-uh, 8, 5'), where (p) last(h)
4h E H. s, s' E
PE Up: ap: 8
M (8ps
(7)
IR constraints: u(h, 8) 2
4h H, E (8)
feasible actions:
s(h,8,a) 0
Yh E HH, (9)
feasible payments: y(h, s)
th 8 (10)
Figure 1: Linear program for computing an optimal dynamic mechanism.
Extended transition operator.
For notational simplicity we define the following extended transi- tion operator P. :S x A ASS) for all t {0) U [T'], such that
{ (P((s a,) P(s,,,,, 00 {1,
(s
otherwise
In words, the extended transition operator assigns phantom probability to each way of transitioning that happens with probability (so P. (s., a) does not always normalize to 1). As a shorthand, let (f()s Pf(s,, a, s') for some s S and a A (the specific choice does not matter). The extended transition operator helps in constructing the flow and IC constraints below and simplifies the formulation. In particular, always have P. (s, a, 8') > 0.
Last state-action pair. For history h H. where h (S1, 01. St, at), use last(h) shorthand for the last state-action pair, i.e., last(h) = (st, az). In particular, when 6. last(h) can be any state-action pair (the choice does not affect results it is merely simplifying shorthand).
Now we are ready to describe the IP formulation. The complete formulation is given in Figure T The formulation is for nonnegative payments and dynamic IR constraints will discuss later

---

how the formulation can be modified to allow other types of constraints, Below, we describe each of its components.
Variables, flow constraints, and the corresponding mechanism. There are 5 classes of variables in the LP:
rth, 8, a): the absolute, unconditional probability that the mechanism reaches state via history h, and takes action a.
y(h s): the payment for history-state pair (h, s), scaled by the probability that the mechanism reaches via h (i.e., 2(h, s)).
=(h, s): the probability that the mechanism reaches state a via history h, which by definition satisfies
=hh 8)
Σ x ah,,, 8, aEA
u(h, s): the onward utility of the agent state with history h assuming truthful reporting, scaled by the probability that the mechanism reaches s via & (i.c., 2h,,
u(h, s, s'): the onward utility of the agent at state s with history h if the agent misreports s', assuming truthful reporting in the future, scaled by the probability that the mechanism reaches s via h (i.e., 2hh, s))).
The flow constraints (Eq. (2)((4) enforce roughly the above interpretation of variables to ærh, 8, a) and =(h,,), except for ways of transition that have probability 0. For each way of transition with probability 0, the extended transition operator assigns phantom probability 1. This phantom probability is not counted in the objective function (because only feasible history-state pairs are counted) or in the utility variables u(h, s) (because only feasible extensions are counted), So, the phantom probability does not affect the principal's the agent's ' utility assuming truthful reporting. Instead, together with other constraints, it guarantees that the mechanism behaves well even for history-state pairs that appear with probability O under truthful reporting, which is necessary for the mechanism to be IC (see later paragraphs). Under the above interpretation, the LP variables (and in particular, at,,, 8, a), y(h, 8) and z(h, naturally correspond to mechanism M (TT, p). Formally, for each h E H, 8 E S:
If (hh,s) s) > 0, then
p(h, 5) = v(h, s))
and for each a E A.
(h, 8, a) = =xh, 8, 2(h,
. If (h, = 0, then let (h,, s) be an arbitrary distribution over A, and p(h, s) = 0.
The feasibility of the mechanism (i.e., every s), is distribution over A and every p(h, s) is nonnegative) is guaranteed by constraints ( (9) and (TO). We remark that while the mechanism constructed from the LP variables may not be unique, effectively this makes no difference, since the parts of the mechanism that are chosen arbitrarily can never be accessed when executing the mechanism. This because =(h,s) s)
only if at some point in the history h. there is an action that the mechanism would never play given the reported states and actions before that, In particular, the above does not simply apply to all history-state pairs (h, s) that are reached with probability 0 under truthful reporting, in which case 2(h, s) may still be positive due to the extended transition operator. Moreover, given any mechanism. one can construct LP variables in similar way, such that the mechanism constructed from these variables is the same as the original mechanism (modulo the unreachable parts). In other words, the above correspondence effectively bijective.
The objective. The objective function of the LP (Eq. ( is precisely the overall utility of the principal under the mechanism constructed above, assuming truthful reporting. This is captured by the following lemma.
Lemma 1.
Let M (π,p) be the mechanism constructed from variables æ(h, 8, a). v(h, and =(,, 8) which satisfy the flow constraints. Then
M (0) =
Σ
Σ lasd
P (s, x(h, a) + v(h,8) 8)
(EH, is feasible
8

---

From this lemma, it is clear that the objective of the LP is the natural quantity to maximize.
Utility. The utility constraints (Eq. 5 collect the agent's s onward utility, where u(h, s) is equal to the agent's s onward utility in state s from history h, assuming truthful reporting, scaled by 2(h, s). This is captured by the following lemma.
Lemma 2. Let M (T. p) be the mechanism constructed from variables x(h, s, a), y(h, s) and z(h, 8) which satisfy the flow and utility constraints. For all h E H. s E E,
u(h, s) z(h, s) uA (h, s).
The proof of Lemma 2 is essentially the same as that of Lemma [ Given the correspondence to the agent's utility w (h, 8), the utility variables u(h, s) act as auxiliary variables in IC constraints.
IC constraints. IC constraints are a key component of the LP formulation. There are two families
of IC constraints: collecting the agent's scaled utility from single-step misreporting (Eq. (6). and subsequently restricting the mechanism such that there is no incentive for misreporting (Eq. 7 In Eq. ( we build variables u(h, s, s'), which is supposed be the onward utility of the agent state 8 from history misreporting 8', assuming truthful reporting in the future, scaled by z(h, s') (rather than zh, s)). This is captured by the following lemma.
Lemma 3. Let M (x, p) be the mechanism constructed from variables 2h,, s, a). y(h, s), and z(h, 8) which satisfy the flow constraints, the utility constraints, and Eq. (6). Then the following statement holds: for all h H. 8, 8,8 E S, let reporting strategy This,s be such that
[s's
if h1' and s =
The (N, 8""
(s",
otherwise
That is, sh misreports s' only in state s from history h and reports truthfully otherwise. Then for all E H. 8,8' E ES,
u(h, s, =(hhs') U
M.r..sof (h, s).
Given Lemma 3 Eq. 7 then guarantees that the mechanism M is robust against single-step misre- porting for all reachable history-state pairs.
Lemma 4. Let M (z, be the mechanism constructed from variahles a(h, 8, a). y(h,s), and 2h,, s) which satisfy the flow constraints, the utility constraints, and Eq. (6). The following is true if
and only if the LP variables also satisfy Eq. (7): for all h E H. s, S where (h, s) reachable by the mechanism M,
u (h, 8) 2 UA
Miria (h, 8)-
We then show that mechanism is IC if and only if there is no incentive for single-step misreporting, which directly implics that the mechanism M constructed from the LP variables is IC. This is captured by the following lemma.
Lemma 5. Let M = (ι,p) be the mechanism constructed from variables x(h, 8, a), y(h, s), and =(,, 8) which satisfy the flow constraints, the utility constraints, and Eq. (6). Then M is IC if and only if the LP variables also satisfy Eq. (7)
IR constraints, feasible actions, and feasible payments. These constraints are straightforward given the correspondence between the IP variables and the mechanism that we have discussed above. Note that while Eq. 8 is for dynamic IR (i.c., the agent has no incentive to leave the mechanism at any point) and Eq. (10) is for nonnegative payments, it is easy to replace them with similar constraints that correspond to overall IR or no payments. See Appendix C for more details.
Optimality of LP solution. Given the above facts, of the paper.
ready to state and prove the main result
Theorem 2. There is an algorithm which computes an optimal IC and (optionally) IR dynamic mechunism, with or without payments, in time Oppoly(SS |A L)), where L is the number of bits required encode each of the imput parameters. purticular, when T is constant, the algorithm runs in polynomial time.

---

The Case of Myopic Agents: Characterization and Faster Algorithm
In this section, briefly discuss special case of the problem of computing optimal dynamic mechanisms, namely the case where the agent is myopic, or, equivalently, the agent has a discount factor of O. While our LP-based algorithm still applies, as we will see below, optimal mechanisms for myopic agents enjoy succinct representation in this case, which also enables a faster algorithm that scales only linearly in the time horizon T. See Appendix D for more details, including the formal definition of myopic agents and the complete description of the algorithm.
4.1
Characterization of Optimal Mechanisms
We first show that when the agent is myopic, without loss of generality, the actions and payments specified by an optimal mechanism depend only on the time, the previous state, the previous action and the current state (we call such mechanism succinct mechanism), instead of the entire history-state pair.
Lemma 6. Fix a dynamic environment. When the agent myopic, for any IC mechanism M (sT, p). there is another IC mechanism M' = =T'' .p) (which is IR whenever M is) such that
M M' (0) (0) 2 up (0), and up
for all h E H. E S, n' and p' depend only on [h], Sp. Op and s, where (sp. Up) = last(h).
Moreover, the above is regardless of whether payments are allowed, or which IR constraints required.
4.2 Faster Algorithm for Myopic Agents
Based on the above characterization, we present faster algorithm for computing optimal mecha- nism the face of a myopic agent. particular, the time complexity of this algorithm depends only linearly the time horizon T. making it feasible for dynamic environments with long time horizon. This is in contrast with the case patient agents, for which, as we have seen, the long-horizon problem is hard to approximate. The algorithm computes an optimal IC (and optionally IR) mechanism static environments, with or without payments. It is known that such algorithm can be implemented using linear programming, and in some cases in more efficient ways 10 37).
subroutine blackbox algorithm that
Theorem 3. When the agent is myopic, Algorithm ?? computes an optimal IC and (optionally) IR dynamic mechanism, with or without payments, in time
OTTSS|AA T (|S), [A], L)) O(T (oly(
where Tstas is the time complexity of the blackbox algorithm used for computing an optimal IC (and optionally IR) mechanism in static environments, and L is the number of bits required to encode each of the input parameters.
Conclusion
We studied automated dynamic mechanism design and showed that, while it is computationally hard to find (even approximately) optimal mechanisms when (I) facing a patient agent and (2) the horizon is long, when either of these two conditions is dropped, an optimal mechanism can be found efficiently. An interesting future direction is to generalize our results to related problems with stronger learning flavor, e.g., reinforcement learning with IC and/or IR constraints.
Besides using our algorithms directly for appropriate applications, the experimental results that they enable (including those that we presented in Appendix F) can guide new theory. For example, can we rigorously prove the benefit of facing a patient agent when the setting is not all too adversarial, and perhaps even characterize the transition point at which facing patient agent becomes better than facing a myopic one? Analytically derived mechanisms can also be compared to these experimental results to see how close to optimal in performance they are. Finally, close inspection of the actual mechanisms generated by our algorithms may reveal insights that can be used to analytically design new mechanisms.
10

---

Funding Transparency Statement
Funding in direct support of this work: NSF grant 181-1814056.
References
[1] Itai Ashlagi, Constantinos Daskalakis, and Nima Haghpanah. Sequential mechanisms with ex-post participation guarantees. In Proceedings of the 2016 ACM Conference on Economics and Computation, pages 213-214, 2016.
[2] Susan Athey and Iya Segal. An efficient dynamic mechanism. Econometrica, 8166):243322485 2013.
[3] Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik. Sample complexity of automated mechanism design. In Proceedings of the 30th International Conference on Neural Information Processing Systems, pages 2091-2099, 2016.
[4] Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik. A general theory of sample complexity for multi-item profit maximization. In Proceedings of the 2018 ACM Conference on Economics and Computation, pages 173-174, 2018.
[5] David P Baron and David Besanko. Regulation and information in continuing relationship. Information Economics and policy, 13):2677-30, 1984.
[6] Richard Bellman. A markovian decision process. Journal of mathematics and mechanics, 6(5): 679-684, 1957.
[7] Dirk Bergemann and Juuso Välimäki. The dynamic pivot mechanism. Econometrica, 78(2): 771-789, 2010.
[8] Dirk Bergemann and Juuso Välimäki. Dynamic mechanism design: An introduction. Journal of Economic Literature, 57(2):235-74 2019.
(9] Andrea Celli, Stefano Coniglio, and Nicola Gatti. Private bayesian persuasion with sequential games. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 1886-1893, 2020.
[10] Vincent Conitzer and Tuomas Sandholm. Complexity of mechanism design. arXiv preprint cs/0205075, 2002.
[11] Vincent Conitzer and Tuomas Sandholm. Self-interested automated mechanism design and implications for optimal combinatorial auctions. In Proceedings of the 5th ACM Conference on Electronic Commerce, pages
2004.
[12] Vincent Conitzer and Tuomas Sandholm. Computing the optimal strategy to commit to. In Proceedings of the 7th ACM conference on Electronic commerce, pages 82-90, 2006.
[13] Pascal Courty and Li Hao. Sequential screening. The Review of Economic Studies, 67(4): 697-717, 2000.
[14] Dütting, F Fischer, Jirapinyo, Lai, Lubin, and DC Parkes. Payment rules through discriminant-based classifiers. ACM Transactions Economics and Computation, 2015.
[15] Paul Dütting, Zhe Feng, Harikrishna Narasimhan, David Parkes, and Sai Srivatsa Ravindranath. Optimal auctions through deep learning. In International Conference on Machine Learning. pages 7706-1715 PMLR, 2019.
[16] Jeffrey C Ely. Beeps. American Economic Review, 107(1):31-53, 2017.
[17] Péter Esö and Balazs Szentes. Optimal information disclosure in auctions and the handicap auction. The Review of Economic Studies, 74(3):705-733 2007.
[18] Zhe Feng, Harikrishna Narasimhan, and David C Parkes. Deep learning for revenue-optimal auctions with budgets. Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems, pages 354-362,2225 2018.

---

[19] Jiarui Gan, Rupak Majumdar, Goran Radanovic, and Adish Singla. Bayesian persuasion in sequential mecision-making.. arXiv preprint arXiv:2106.05137, 2021.
[20] Mohammad Taghi Hajiaghayi, Robert Kleinberg, and Tuomas Sandholm. Automated online mechanism design and prophet inequalities. In AAAI, volume 7, pages 58-65, 2007.
[21] Ronald A Howard. Dynamic programming and markov processes. 1960.
[22] Andrew Kephart and Vincent Conitzer. Complexity of mechanism design with signaling costs. In AAMAS, pages 357-365. Citeseer, 2015.
[23] Andrew Kephart and Vincent Conitzer. The revelation principle for mechanism design with reporting costs. In Proceedings of the 2016 ACM Conference Economics and Computation, pages 85-102, 2016.
[24] Vahab Mirrokni, Renato Paes Leme, Pingzhong Tang, and Song Zuo. Non-clairvoyant dynamic mechanism design. Econometrica, 1835):193-1196, 2020.
[25] Roger B Myerson. Optimal auction design. Mathematics of operations research, 6(1):58-73, 1981.
[26] Roger B Myerson. Multistage games with communication. Econometrica: Journal of the Econometric Society, pages 323-358, 1986.
[27] Harikrishna Narasimhan, Shivani Brinda Agarwal, and David C Parkes. Automated mechanism design without money via machine learning. In Proceedings of the 25th International Joint Conference on Artificial Intelligence, 2016.
[28] Christos Papadimitriou, George Pierrakos, Christos-Alexandee Psomas, and Aviad Rubinstein. On the complexity of dynamic mechanism design. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pages 1475-1475 SIAM, 2016.
[29] Alessandro Pavan. Dynamic mechanism design: Robustness and endogenous types. In Advances in Economics and Econometrics: Eleventh World Congress, pages 1-62, 2017.
[30] Alessandro Pavan, Ilya Segal, and Juuso Toikka. Dynamic mechanism design: A myersonian approach. Econometrica, 82(2)x601-633, 2014.
[31] Martin L Puterman and Moon Chirl Shin. Modified policy iteration algorithms for discounted markov decision problems. Management Science, 1221131127711137 1978.
[32] Jad Rahme, Samy Jelassi, Joan Bruna, and S Matthew Weinherg. A permutatiooneqquiarriatt neural network architecture for auction design. arXiv preprint arXiv:2003.01977,00 2020.
[33] Jérôme Renault, Eilon Solan, and Nicolas Vieille. Optimal dynamic information provision. Games and Economic Behavior, 104:329-349, 2017.
[34] Tuomas Sandholm and Anton Likhodedov. Automated design of revenue- maximizing combina- torial auctions. Operations Research, 63(5):1000-1025 2015.
[35] Tuomas Sandholm, Vincent Conitzer, and Craig Boutilier. Automated design of multistage mechanisms. IJCAI, volume 7, pages 1500-1506, 2007.
[36] Weiran Shen, Pingzhong Tang, and Song Zuo. Automated mechanism design via neural networks. In Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems, pages 215-223, 2019.
[37] Hanrui Zhang, Yu Cheng, and Vincent Conitzer. Automated mechanism design for classification with partial verification. In Proceedings of the AAAI Conference on Artificial Intelligence, 2021.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them?
[Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] See appendices.
3. If you experiments...
(a) Did you include the code, data, and instructions needed reproduce the main experimental results (either in the supplemental material or as a URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experiments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're
using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable?
[N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "t5nonynWlJc", "reviewer": "Reviewer_AaYK", "summary": "This paper presents and proves a linear program for unstructured dynamic mechanism design. The LP supports payments and different individual-rationality constraints. The key contributions are:\n1) Presenting an LP that provably yields an optimal mechanism for an unstructured dynamic environment with a finite time horizon.\n2) From this LP formulation and standard LP complexity results follows a polynomial runtime guarantee for finding an optimal mechanism.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1. This work addresses a novel task of computing optimal mechanisms in unstructured dynamic environments. Previous works have explored automated mechanism design for static environments, where agents make a memoryless single decision rather than repeated interactions with the same mechanism. This makes the paper the first such result for dynamic environments, which is of interest to the broader Economics and Computation community.\n2. The paper is well written and organized. The build up of the linear program (Figure 1) through lemmas 1-5 was very clear. However, it may be helpful to leave additional space for discussion of the main result (Theorem 2). As someone unfamiliar with the analogous results for non-dynamic settings, it is not immediately clear how to interpret the upper bound: were we expecting the complexity to potentially be non-polynomial? is there potential to improve on this bound (e.g. weaken the exponential dependence on T)?\n3. As the paper is purely theoretical, it is not clear how practical solving the LP is in experimental settings. The theoretical results are significant in that they’re the first such result for dynamic environments. The hardness result (Theorem 1) is not surprising but still an important justification for the paper’s focus on constant horizons. The main result (Theorem 2) is important as it shows the LP can be solved in polynomial time, although the complexity bound does feel a bit loose given the exponential dependence on T which could pose a practical issue. The proof technique of setting up an LP is not novel/significant/unique in itself, but it is clean and does the job of showing a loose polynomial complexity bound.\n4. Although I only skimmed the proof for Theorem 1 in the Appendix, the MAX-SAT reduction looks sound and the result seems reasonable. The LP construction is correct and Theorem 2 follows straightforwardly from the usual LP guarantees.\n\n*My review is based on the main PDF, and not the full version that is mentioned in the abstract and placed in the supplementary files.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors did not discuss potential negative societal impact, but the research is very fundamental so I do not think it is necessary. The limitations are also discussed (e.g. constant horizon).", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "ogCdH756QA", "reviewer": "Reviewer_bSJY", "summary": "The authors formulate and study dynamic mechanism design in an MDP-like setting. The motivation is principal-agent problems. The principal commits to a policy to choose actions given observations of states; the environment evolves according to some transitions dynamics based on these actions; the agent does not act but is free to misreport states to the principal. Agent and principal receive utility; the principal’s goal is to choose a policy that is incentive compatible and individually rational (standard goals of mechanism design) while maximizing its own expected total utility.\n\nIn general, from a full description of the environment and dynamics, the “planning” type problem to find an optimal mechanism is NP-hard (shown via reduction from MAXSAT). If the time horizon of the problem is treated as a constant, then it is possible to formulate a linear program to find the optimal mechanism in polynomial time, and doing so is a major portion of the paper.\n", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Longer summary\n\nThe motivation is a principal-agent problem. The principal is going to commit to some policy mapping world states to (distributions over) actions; then the agent can choose to lie about the state of the world; based on this possibly false state, the principal’s policy acts, and the agent and the principal both receive some utility based on states and actions. In the single-step case, this is a fairly general description of mechanism design with a single agent. Then the standard goals of the principal are to maximize its own utility, subject to the incentive compatibility (IC) constraint that agents should not gain utility from lying, and the individual rationality (IR) constraint that agents should be assured they will never have negative utility.\n\nTo generalize to the multi-step case, the authors define an MDP-like environment which transitions from state to state over multiple time horizons. The dynamics of this environment are Markovian, in that transitions only depend on the current state and action; however both principal and agent are aware of their full histories. Both principal and agent receive immediate utility based on the current state and action, and their goal is to maximize total expected utility over future time steps. The definition of IC is generalized to the dynamic setting to allow for misreporting strategies that depend on the whole history of states. Likewise the notion of IR is generalized in two ways: either guaranteeing that expected utility at the start is positive, or guaranteeing that expected forward-looking utility never goes negative (so the agent will never leave the mechanism).\n\nThis formalization of dynamic mechanism design is carefully and clearly done. A major part of the paper is then a linear program which, given a description of the environment, maximizes principal utility subject to constraints enforcing IR and IC for the agent. It’s natural to notice that this program has constraints for each possible state-action history, which grows exponentially with the length of the episode, so it’s only really poly-time if the time horizon is treated as a constant. The authors address this point and show via a reduction from MAXSAT that this is unavoidable — for arbitrarily long time horizons the problem is inevitably NP hard even to approximate.\n\nOther points worth mentioning:\n\n- Markovian policies, which in regular MDPs are optimal, may be arbitrarily far from optimal. Furthermore, in this setting restricting to Markovian policies doesn’t even make things easier to compute (the MAXSAT reduction still works). This is an interesting result.\n- The general problem is NP hard. By treating time horizon as a constant one can avoid this (and formulate the LP). It’s also possible to avoid this if the agent is restricted to be myopic. In this case, optimal policies only require the current state and 1 step of history, which allows the authors to implement a dynamic-programming-style algorithm which is faster than solving the general LP.\n\nThere are also some experiments in which the authors actually implement their LPs for a simple setting.\n\n## Evaluation\n\n### Originality\n\nThe paper carefully extends existing settings for mechanism design to a dynamic setting, and considers many special cases and design goals. The results all tend to come out as expected, and the techniques seem fairly familiar, but I wouldn’t call it unoriginal.\n\n### Quality\n\nThe paper is high-quality with a lot of attention to detail.\n\n### Clarity\n\nThe paper is clearly written and easy to understand. Due to the unfortunate space limitations, a lot has been moved to the appendix, which fragments the paper a little. I liked the introduction but I think it could have been condensed a lot in order to squeeze more appendix material into the main body, and this would have helped the paper.\n\n### Significance\n\nThe paper provides a useful framework for thinking about dynamic mechanism design, and the results about computational hardness are relevant, especially in comparison to single-agent MDPs. I think the formalization here could end up being a very useful starting point for people who want to study new techniques for this type of mechanism design problem, including e.g. extending reinforcement learning techniques to work in this setting.\n\n## Questions for authors\n\n### Misreporting strategies\n\nCan the agent be inconsistent in their misreports? In other words, can they misreport s_t as s_t’ one round, and then s_t’’ the next round? It seems like the answer is no due to the definition of the misreporting strategy. But perhaps spelling this out explicitly might be useful.\n\n### Myopic agents and memoryless mechanisms\n\nTheorem 3 says that computing an optimal general mechanism for myopic agents can be done in polynomial time (because a “succinct” two-step-history mechanism will be optimal). Theorem 5 says that computing an optimal memoryless mechanism, including for myopic agents, is hard to approximate. Is there some intuition of how just going from general (actually succinct) mechanisms, to memoryless mechanisms, makes the problem computationally harder? It’s possible I’ve misunderstood some assumptions of these two theorems.\n\n\nFinal update: the authors helpfully answered my questions and my opinion of the paper is still quite positive.\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is a highly theoretical paper and any negative social impacts would be very remote. As for limitations, the authors do discuss them when relevant (e.g. the results require assuming that principal utility must depend linearly on payments, if the revelation principle doesn't hold in a static setting then it won't hold for dynamic). Moreover a lot of the paper is about computational hardness results which represent a kind of limitation.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "gpZZPtpC8PP", "reviewer": "Reviewer_D9VS", "summary": "This paper studies automated mechanism design in dynamic unstructured dynamic environments. In the setting of interest, a principal and agent repeatedly interact for a finite number of time steps (finite time horizon); at each time step, the agent reports the current state of the environment, the principal takes action, and the environment transitions to the new state. Importantly, the agent's and the principal's utilities are not necessarily the same, implying that the agent might misreport which further implies the need for a mechanism.  The paper considers a randomized dynamic mechanisms that consists of the policy of the principal and the mechanism's payment function. The main results are: a) an LP for finding optimal mechanisms (constant time horizon), b) a computational complexity result which shows that the principal's utility is hard to approximate within a certain factor for environments with large time horizons.  The paper has additional results, as mentioned in the abstract, but these are not presented in the main text.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I enjoyed reading the paper and, to my knowledge, its contributions to the work on automated mechanisms design are novel and significant. My main concerns are related to its structure, quite a few interesting results are in the appendix without actually being presented in the main text. Below I highlight some of the pros and cons of the paper.\n\nPros:\n- This paper is well written and easy to follow, and it clearly explains the setting of interest. The introduction motivates the setting of interest well. That said, the motivating example is more relevant for EconCS than ML.\n- The results seem novel, they extend prior work on automated mechanism design to a setting that, to my knowledge, hasn't been studied by prior work. \n- The paper provides a relatively complete computational complexity characterization of automated mechanism design for the setting of interest (dynamic unstructured environments, single-agent). \n- The most important references (those related to (automated) mechanism design) are adequately presented. Given that the paper studies a principal-agent problem in dynamic environments, a discussion related to stochastic Stackelberg games or environment design could be added. \n\nCons:\n- The paper primarily focuses on the computational complexity aspects of the problem at hand. The learning aspects, which could be more interesting for the NeurIPS community, are not discussed. \n- The main algorithmic result, the LP for computing optimal mechanisms, might not be very practical. It assumes that the the transitions probabilities are known and does not scale well with time horizon $T$. While the latter is not surprising (given the hardness result), it might be useful to have some discussion on the former. \n- The structure of the paper could be considerably improved. For example, the abstract extensively talks about the results that are not in the main text, including simulation-based experiments, which appear to be quite interesting. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The checklist indicates that the limitations are discussed, but it is not clear where. The discussion on the limitations could include a discussion on the modeling assumptions (e.g., as those discussed in the main review). Potential negative societal impacts are not discussed, however, in my opinion, this is not needed given the topic of the paper.  ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 or 5 hours"}, "extra_text": {}}, {"review_id": "5p055jRYErj", "reviewer": "Reviewer_KjrC", "summary": "The authors study the problem of computing optimal mechanisms in a dynamic unstructured environment. Unlike a static environment, the principal is allowed to repeatedly interact with a strategic agent and take actions based on the agent's reports of the current state of the world. The authors show that when the time horizon of such a dynamic environment is not finite, the problem is intractable. When the time horizon is small, they show that an efficient mechanism can be computed using an LP", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "- The contribution is significantly novel - much work in the AMD literature has been on the static environment. Additionally, since the environment that the authors consider is also only loosely structured, their method differs from the typical characterize-and-solve approach to mechanism design.\n\n- The claims seem to be technically sound however I didn't check the proofs in detail.\n\n- The paper is well written/ clear\n\n- The authors provide a compelling example in the introduction as to why studying dynamic mechanism design for unstructured environments is significant. I believe it's a problem of interest to people in both the ML and the mechanism design community. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: SUMMARY

The authors consider a dynamic mechanism design problem. In this problem a single agent interacts with a single principal over a time horizon of T rounds. The problem is as follows: There is a distribution over initial states. A start state is drawn from this distribution. In each round, the agent observes the state s and reports a state s'. The principal takes an action a based on the history of states and actions and the reported current state s'. For each state and action pair there is a distribution over next round states, from which the next state is drawn. Both principal and agent have possibly distinct valuation functions that operate on state-action pairs, and quasi-linear utility for money that can flow in either way. 

The goal is to design a (possibly randomized) dynamic mechanism that maximizes the principal's utility subject to dynamic IC plus overall or dynamic IR.

The two main results are: 

(1) When T is non-constant, it is NP hard to approximate the principal's maximum utility to within a factor of 7/8+eps (Theorem 1).

(2) There is a LP that finds the optimal principal's utility in time O(|S|^T,|A|^T,L) where S is the state space, A is the action space, and L is the number of bits needed to encode each input parameter (LP in Figure 1, Theorem 2).

The paper mentions a couple of other theoretical results including experiments, but all of these are deferred to the appendix. 

The theoretical results include an algorithm that scales linearly in T for a myopic agent. A result that shows that memoryless mechanisms, which are optimal for MDPs, do not provide a good solution to the problem in the presence of strategic decisions. The experiments amongst others show that taking incentives into account matters and that optimal designs are remarkably robust against misaligned preferences.

Related work:

The main point of comparison for this paper is a paper by Papadimitriou et al. (SODA 2016 [24]), which considers a closely related mechanism design problem in which the principal's decision in each round is to allocate an item. They show that it is strongly NP hard to complete the optimal deterministic mechanism for a single bidder and two days; and give a LP based algorithm for computing the optimal randomized mechanism when the number of agents and types are both constant (See third comment below).

RECOMMENDATION:

All reviewers liked the motivating story and the and the theoretical results. Although somewhat related, the extension over Papadimitriou et al. seems significant enough to warrant publication in NeurIPS. 

For the camera ready:

** I would strongly encourage to cut most of the space used for the LP-based approach (just mention the LP and the theorem with some discussion what the key ingredients are); then use the additional space to state the additional theoretical results and describe some of the experiments

** Also: I think it would be nice to compare in more detail where and why your results are different from Papadimitriou et al., both qualitatively and technically

** Discussion of [24]: You write that [24] give a poly-time LP-based algorithm "when the number of agents and the time horizon are both constant" - I couldn't parse their theorem (Theorem 8 in Section 5 of the arXiv version of that paper). It says "For any number of days D, and a constant number of independent bidders k, the optimal adaptive randomized auction can be found in time polynomial in the number of types and in the number of days." 
(please double check that you cite it correctly)

** Related work: The deep learning approach to AMD should be credited to [13].

** Related work: For work on AMD through ML, please also cite:
Payment Rules through Discriminant Based Classifiers
P. Dutting, F. Fischer, P. Jirapinyo, J. K. Lai, B Lubin, D. C. Parkes
ACM EC'12
Decision: Accept (Poster)