# Optimal Coordination in Generalized Principal-Agent Problems:
A Revisit and Extensions

Jiarui Gan
University of Oxford
<EMAIL_ADDRESS>Minbiao Han
University of Chicago
<EMAIL_ADDRESS>Jibang Wu
University of Chicago
<EMAIL_ADDRESS>Haifeng Xu
University of Chicago
<EMAIL_ADDRESS>
###### Abstract

In the principal-agent problem formulated by Myerson [13], agents have private
information (type) and make private decisions (action), both of which are
unobservable to the principal. Myerson pointed out an elegant solution that
relies on the revelation principle, which states that without loss of
generality optimal coordination mechanisms of this problem can be assumed to
be truthful and direct. Consequently, the problem can be solved by a linear
program when the support sets of the action and type spaces are finite. In
this paper, we extend Myerson’s results to the setting where the principal’s
action space might be infinite and subject to additional design constraints.
This generalized principal-agent model unifies several important design
problems —including contract design, information design, and Bayesian
Stackelberg games—and encompasses them as special cases. We present a
revelation principle for this general model, based on which a polynomial-time
algorithm is derived for computing the optimal coordination mechanism. This
algorithm not only implies new efficient algorithms simultaneously for all the
aforementioned special cases but also significantly simplifies previous
approaches in the literature.

##  1 Introduction

The generalized principal-agent problem [13] involves two important economic
concepts, _adverse selection_ and _moral hazard_ [2, 9, 3, 8].111Notably, the
two conceptual findings are key contributions highlighted in the Nobel Prize
in Economic Sciences 2001 and 2016. On the one hand, these two factors are the
major challenges in designing coordination mechanisms for the principal: the
agents may have private information which the principal cannot directly
observe; and the agents may have private decision domains which the principal
cannot directly control. On the other hand, the two factors of the generalized
principal-agent problem enable it to capture economic problems of various
kinds. Somewhat unexpectedly, the paper [13] and its generalized model
receives limited attention from the community, as most work have been only
focused on either one of the constraining factors. Therefore, our work plans
to revisit the general model [13] and extend its mechanism design insights to
a wider class of sequential games.

##### Our Contributions

We start by presenting a slightly more generalized principal-agent problem
that unifies several important sequential game models including contract
design, Bayesian Stackelberg games, and information design. Our key
contribution is to show that the optimal coordination mechanism can be
efficiently computed in this generalized model, beyond the setting of [13]
over finite state and action spaces. In Theorem 1, building upon the results
of Myerson [13], we present a generalized revelation principle confirming the
existence of an optimal coordination mechanism that is succinct, truthful, and
direct. Specifically, we introduce the _succinctness constraint_ as a
refinement of the coordination policy which uses at most one principal
strategy to induce a specific agent type to take a specific action. Under such
succinctness constraints, the optimal coordination policy can be formulated as
convex program and solved efficiently in general. We also identify the
irregular cases where the exact optimal mechanism does not exist and
accordingly provides an efficient algorithmic approach to determine the
$\epsilon$-optimal solution. Finally, we survey the existing literature and
fill several gaps on the hardness of computing the optimal coordination
mechanism under various restrictions, including settings where type
elicitation or further randomization of the principal’s strategies is
prohibited.

##### Related Work

The contract theory has been a crucial branch of economics [9, 14, 12]. Driven
by an accelerating trend of contract-based markets deployed to Internet-based
applications, the contract design problem recently started to receive a
surging interest especially from the computer science community [6, 7, 10, 1,
4, 5]. As pointed out by [1], this includes online markets for crowdsourcing,
sponsored content creation, affiliate marketing, freelancing and etc. The
economic value of these markets is substantial and the role of data and
computation is pivotal. Hence, to accommodate the growing need for data
elicitation and personalization, the aspect of private agent information in
the principal-agent problems are studied by several recent works. [10] modeled
the hidden type of the agent which determines the outcome distribution and
present hardness results on solving the optimal menu of single contract. [1]
modeled the hidden type of the agent which determines the agent’s cost per
unit-of-effort and showed its tractability under constant number of action.
[5] presented a “surprisingly” positive result on the efficient computation of
the optimal menu of randomized contracts while showing that the exact optimal
solution does not always exist. Our work presents a simplified and unified
characterization of the optimal coordination mechanism in the more generalized
model of the principal-agent problem. Notably, our algorithm 1 solves for the
optimal (or $\epsilon$-optimal) mechanism in explicitly constructed convex
programs, saving us from the (practically inefficient) ellipsoid method in
[5].

##  2 Mechanisms for the General Principal-Agent Problem

###  2.1 Problem Setting

We consider the generalized principal-agent problem [13], as a sequential game
between two players, namely the principal and the agent.222While our model and
results can be extended to the case with multiple agents, this work focus on
the single agent setting for the simplicity of notation. The agent has a
private type $\theta$ that is sampled from a probability distribution $f$. The
distribution $f$ is known to the principal but the realization $\theta$ is
unknown. The agent also makes a private decision $a$, which the principal
cannot control directly. We denote the type and action spaces of the agent as
$\Theta$ and $\mathcal{A}$, respective. The utility function of the principal
and agent are denoted as $U$ and $V$, respectively, where
$U,V:\mathcal{X}\times\mathcal{A}\times\Theta\to\mathbb{R}$ and $\mathcal{X}$
denotes the strategy space of principal. Throughout this paper, we assume the
function $V$ is linear w.r.t. principal strategy $x$, therefore, we will
explicitly write $V(\bm{x},a;\theta)=k^{a,\theta}\bm{x}+c^{a,\theta}$.

In this problem, a direct coordination mechanism is given by a coordination
policy $\pi:\mathcal{X}\times\mathcal{A}\times\Theta\to[0,1]$ such that
$\sum_{\bm{x}\in\mathcal{X},a\in\mathcal{A}}\pi(\bm{x},a;\theta)=1$ for all
$\theta\in\Theta$. Using $\pi$, if the agent reports a type $\theta$, then
with probability $\pi(\bm{x},a;\theta)$ the principal plays strategy $\bm{x}$
and recommends the agent to take action $a$. A direct coordination mechanism
is incentive compatible (IC), or truthful, if and only if the honest-obedient
participation strategy—i.e., reporting his type truthfully and taking the
recommended action—is optimal for the agent [13]. Mathematically, a truthful
and direct coordination mechanism satisfies the following constraints:

$\sum_{\bm{x}\in\mathcal{X}}\sum_{a\in\mathcal{A}}\pi(\bm{x},a;\theta)\cdot
V(\bm{x},a;\theta)\geq\sum_{\bm{x}\in\mathcal{X}}\sum_{a\in\mathcal{A}}\big{[}\pi(\bm{x},a;\theta^{\prime})\cdot\mathop{max}_{a^{\prime}\in\mathcal{A}}V(\bm{x},a^{\prime};\theta)\big{]},\quad\forall\theta,\theta^{\prime}\in\Theta.$

Consequently, given a truthful and direct coordination mechanism, the
principal’s utility can be written as

$\sum_{\theta\in\Theta}f(\theta)\sum_{\bm{x}\in\mathcal{X}}\sum_{a\in\mathcal{A}}\pi(\bm{x},a;\theta)\cdot
U(\bm{x},a;\theta).$

In summary, the sequence of the interactions is as follows,

  1. 1.

The principal announces a coordination mechanism $\pi$ to the agent.

  2. 2.

An agent type $\theta$ is drawn from $f$ and the agent reports a type
$\theta^{\prime}$ to the principal.

  3. 3.

A strategy $\bm{x}$ of the principal and an action $a$ of the agent are drawn
from $\pi(\cdot,\cdot;\theta)$. The principal plays $\bm{x}$ (and recommends
the agent to take action $a$).

  4. 4.

The agent plays an action $a^{\prime}$ in response to $\bm{x}$
($a^{\prime}\in\mathop{argmax}_{b\in\mathcal{A}}V(\bm{x},a;\theta)$).

  5. 5.

The principal and the agent receive utilities $U(\bm{x},a^{\prime};\theta)$
and $V(\bm{x},a^{\prime};\theta)$, respectively.

##### Supplemental Constraints

Based on the model in [13], we consider a set of supplemental constraints on
the coordination policy $\pi$. That is, for each $\theta\in\Theta$,

$\sum_{x\in\mathcal{X}}\sum_{a\in\mathcal{A}}\pi(\bm{x},a;\theta)\cdot\bm{x}\in\mathcal{C}$
(2.1)

for some convex set $\mathcal{C}$. In Theorems 1 and 2, we will show that even
with such supplemental constraints, our results still hold. In Section 4.3,
these constraints will be particularly useful. We can use these constraints to
cast the information design problem as a special case of the generalized
principal-agent problem. That is, if the constraint
$\sum_{x\in\mathcal{X}}\sum_{a\in\mathcal{A}}\pi(\bm{x},a;\theta)\cdot\bm{x}=\mu$
is imposed for some prior distribution $\mu$ of the states, the coordination
policy forms a menu of signaling scheme, where each $\bm{x}$ is a posterior
distribution of some signal.

###  2.2 Myerson’s Optimal Mechanisms for Finite Games

We first introduce the two useful results due to [13] on the optimal
coordination mechanism. The results help restrict the space of mechanisms to
be considered to truthful and direct coordination mechanisms without loss of
optimality.

######  Proposition 1 ([13]).

When the agent type set $\Theta$ and the players’ action sets $\mathcal{X}$
and $\mathcal{A}$ are finite, the optimal truthful and direct coordination
mechanism can be computed by the following linear program:

$\begin{array}[]{l>{\displaystyle}l>{\displaystyle}l}\mbox{maximize}&{\sum_{\theta\in\Theta}f(\theta)\sum_{x\in\mathcal{X}}\sum_{a\in\mathcal{A}}\pi(\bm{x},a;\theta)\cdot
U(\bm{x},a;\theta)}&\\\ \mbox{subject
to}\displaystyle&\sum_{\bm{x}\in\mathcal{X}}\sum_{a\in\mathcal{A}}\pi(\bm{x},a;\theta)\cdot
V(\bm{x},a;\theta)\geq\sum_{\bm{x}\in\mathcal{X}}\sum_{a\in\mathcal{A}}\big{[}\pi(\bm{x},a;\theta^{\prime})\cdot\mathop{max}_{a^{\prime}\in\mathcal{A}}V(\bm{x},a^{\prime};\theta)\big{]}&\mbox{for
}\theta,\theta^{\prime}\in\Theta\\\
\displaystyle&\sum_{\bm{x}\in\mathcal{X}}\sum_{a\in\mathcal{A}}\pi(\bm{x},a;\theta)=1&\mbox{for
}\theta\in\Theta\\\ \end{array}$

######  Proposition 2 (Revelation Principle [13]).

There always exists an optimal coordination mechanism that is truthful and
direct.

Note that the revelation principle presented in Proposition 2 is a general
result that applies even in the setting where $\Theta$, $\mathcal{X}$, and
$\mathcal{A}$ are infinite, while the arguments in Proposition 1 only holds
for finite action and type spaces. Moreover, despite that Myerson did not
consider the supplemental constraints on $\pi$ as we defined above, it can be
easily verified that Proposition 2 still holds even with these additional
constraints imposed: if the given (non-truthful) coordination mechanism $M$
satisfies these additional constraints, the constructed truthful coordination
mechanism (simulated on $M$) only uses the agent’s non-truthful participation
strategy to change its coordination policy w.r.t. $\theta$ and thus has no
effect on constraints w.r.t. the part of policy conditioned on $\theta$. For a
non-direct coordination mechanism, we define $\Sigma$ as the set of all
messages which agent might receive, $\mathcal{R}$ as the set of possible
reports that might be sent by the agent. As a result, we have
$\rho:\Theta\rightarrow\mathcal{R}$ as agent’s reporting strategy, and
$\delta:\Sigma\times\Theta\rightarrow\mathcal{A}$ as the agent’s choice of
decision. Therefore, for a non-direct coordination mechanism, we have the
coordination policy $\pi:\mathcal{X}\times\Sigma\times\mathcal{R}\to[0,1]$ and
$\sum_{\bm{x}\in\mathcal{X},m\in\Sigma}\pi\big{(}\bm{x},m;\rho(\theta)\big{)}=1$
for all $\theta\in\Theta$. The supplemental constraint is defined as follows:

$\sum_{\bm{x}\in\mathcal{X}}\sum_{m\in\Sigma}\pi(\bm{x},m,\rho(\theta))\cdot\bm{x}\in\mathcal{C}.$

To construct a direct mechanism, define
$\delta^{-1}(a,\theta)=\big{\\{}m|\delta(m,\theta)=a\big{\\}}$. Then, define
$\pi^{*}:\mathcal{X}\times\mathcal{A}\times\Theta\rightarrow[0,1]$ so that:
$\pi^{*}(\bm{x},a;\theta)=\sum_{m\in\delta^{-1}(a,\theta)}\pi\big{(}\bm{x},m,\rho(\theta)\big{)}$.
As a result, for the direct coordination mechanism, we have

$\begin{split}\sum_{\bm{x}\in\mathcal{X}}\sum_{a\in\mathcal{A}}\pi^{*}(\bm{x},a;\theta)\cdot\bm{x}=\sum_{\bm{x}\in\mathcal{X}}\sum_{a\in\mathcal{A}}\,\sum_{m\in\delta^{-1}(a,\theta)}\pi\big{(}\bm{x},m,\rho(\theta)\big{)}\cdot\bm{x}=\sum_{\bm{x}\in\mathcal{X}}\sum_{m\in\Sigma}\pi(\bm{x},m,\rho(\theta))\cdot\bm{x}\in\mathcal{C}.\end{split}$

##  3 Main Result: Optimal Mechanism Design Beyond Finite Games

In this work, we consider the more general and practical setting where the
principal’s strategy space may be any closed convex set and size of which may
be infinite. Despite the intractable mechanism design space, we start by
showing that considering only the _succinct coordination mechanisms_ is
without loss of generality: under mild assumptions, an optimal succinct,
truthful and direct coordination mechanism offers the principal at least as
much utility as any other mechanism does.

Specifically, we define _succinct coordination mechanisms_ as the direct
coordination mechanisms that satisfy the following _succinct constraint_ :

$\big{|}\mathop{\mathbf{supp}}(\pi(\cdot,a;\theta))\big{|}\leq
1,\quad\forall\theta\in\Theta,a\in\mathcal{A},$

where $\mathop{\mathbf{supp}}(\cdot)$ denotes the support of a distribution.
In other words, a succinct mechanism prescribes deterministically a single
strategy $\bm{x}$ for each type $\theta$ reported and action $a$ chosen by the
agent. Under this definition, a succinct mechanism admits the following
simplified representation. Denote by $\bm{x}^{a,\theta}$ the strategy
prescribed for a reported type $\theta$ and action $a$ (namely, the strategy
$\bm{x}$ with $\pi(\bm{x},a;\theta)=1$ as in the original representation). The
coordination policy of the succinct mechanism is then given as
$\pi:\mathcal{A}\times\Theta\to[0,1]$ with
$\sum_{a\in\mathcal{A}}\pi(a;\theta)=1$ for all $\theta\in\Theta$; when the
agent reports a type $\theta$, with probability $\pi(a;\theta)$ the principal
plays $\bm{x}^{a,\theta}$ and recommends the agent to take action $a$. The
policy $\pi$ now has a finite support irrespective of the size of
$\mathcal{X}$. And similarly to Proposition 1, we can represent the optimal
succinct, truthful and direct coordination mechanism as the solution of the
following optimization problem (OP), in which the variables
$\\{(\pi(a;\theta),\bm{x}^{a,\theta}):\theta\in\Theta,a\in\mathcal{A}\\}$
forms the succinct coordination mechanism.

$\begin{array}[]{l>{\displaystyle}l>{\displaystyle}l}\mbox{maximize}&{\sum_{\theta\in\Theta}f(\theta)\sum_{a\in\mathcal{A}}\pi(a;\theta)\cdot
U(\bm{x}^{a,\theta},a;\theta)}&\\\ \mbox{subject
to}\displaystyle&\sum_{a\in\mathcal{A}}\pi(a;\theta)\cdot(k^{a,\theta}\bm{x}^{a,\theta}+c^{a,\theta})\geq\sum_{a\in\mathcal{A}}\big{[}\pi(a;\theta^{\prime})\cdot\mathop{max}_{a^{\prime}\in\mathcal{A}}\\{k^{a^{\prime},\theta}\bm{x}^{a,\theta^{\prime}}+c^{a^{\prime},\theta}\\}\big{]}&\mbox{for
}\theta,\theta^{\prime}\in\Theta\\\
\displaystyle&\bm{x}^{a,\theta}\in\mathcal{X},\pi(a;\theta)\in[0,1]&\mbox{for
}a\in\mathcal{A},\theta\in\Theta\\\
\displaystyle&\sum_{a\in\mathcal{A}}\pi(a;\theta)=1&\mbox{for
}\theta\in\Theta\\\
\displaystyle&\sum_{a\in\mathcal{A}}\pi(\bm{x}^{a,\theta},a;\theta)\cdot\bm{x}^{a,\theta}\in\mathcal{C}&\mbox{for
}\theta\in\Theta\\\ \end{array}$ (3.1)

We now formally extend the Proposition 2 to show the revelation principle
holds under succinctness constraints and therefore we can restrict our
optimization space to only the set of all succinct coordination mechanisms.

######  Theorem 1 (Succinct Revelation Principle).

Suppose that the agent’s utility is linear and the principal’s utility is
concave with respect to the principal’s strategy, and the principal’s strategy
set $\mathcal{X}$ is convex. Then there always exists an optimal coordination
mechanism that is succinct, truthful and direct.

###### Proof.

Given Proposition 2, it suffices to show that for any truthful and direct
coordination mechanism, there exists a succinct, truthful and direct
coordination mechanism that achieves at least as much utility.

Pick an arbitrary coordination mechanism $\pi$ that is truthful and direct. We
construct a new coordination mechanism $\overline{\pi}$ as follows. For every
$a\in\mathcal{A}$ and $\theta\in\Theta$, let the $\mathcal{X}^{a,\theta}$ be
the set of principal strategies against which action $a$ is a best response of
a type-$\theta$ agent. Moreover, define the following strategy
$\overline{\bm{x}}^{a,\theta}\coloneqq\frac{\sum_{\bm{x}\in\mathcal{X}^{a,\theta}}\pi(\bm{x},a;\theta)\cdot\bm{x}}{\sum_{\bm{x}\in\mathcal{X}^{a,\theta}}\pi(\bm{x},a;\theta)}$,
and let the new coordination mechanism choose this strategy with probability
$\overline{\pi}(a;\theta)=\sum_{\bm{x}\in\mathcal{X}^{a,\theta}}\pi(\bm{x},a;\theta)$.333Throughout
this proof, if $\mathcal{X}^{a,\theta}$ is an infinite set we can replace the
summation operation to integration.

It is easy to see that $\overline{\bm{x}}^{a,\theta}\in\mathcal{X}$ as it is a
convex combination of the strategies in $\mathcal{X}^{a,\theta}$. Moreover,
for every $\theta\in\Theta$, we have
$\sum_{x\in\mathcal{X}}\sum_{a\in\mathcal{A}}\overline{\pi}(\bm{x},a;\theta)=1$,
so $\overline{\pi}(\cdot,\cdot;\theta)$ is a valid probability distribution.
We next show the following facts about $\overline{\pi}$ to complete the proof.

  1. 1.

First, $\overline{\pi}$ remains feasible. In particular, it satisfies the
supplemental constraints defined in (2.1): for all $\theta\in\Theta$, we have

$\displaystyle\overline{\pi}(\overline{\bm{x}}^{a,\theta},a;\theta)\cdot\overline{\bm{x}}^{a,\theta}+\sum_{\widetilde{a}\in\mathcal{A},a\neq\widetilde{a}}\overline{\pi}(\bm{x},\widetilde{a};\theta)\cdot\bm{x}$
$\displaystyle=\sum_{\bm{x}\in\mathcal{X}^{a,\theta}}\pi(\bm{x},a;\theta)\cdot\bm{x}+\sum_{\widetilde{a}\in\mathcal{A},a\neq\widetilde{a}}\overline{\pi}(\bm{x},\widetilde{a};\theta)\cdot\bm{x}$
$\displaystyle=\sum_{a\in\mathcal{A}}\pi(\bm{x},a;\theta)\cdot\bm{x},$

which is still inside the convex set $\mathcal{C}$.

  2. 2.

Second, $\overline{\pi}$ is incentive compatible: for any
$\theta^{\prime}\in\Theta$, we have

$\displaystyle\quad\overline{\pi}(\overline{\bm{x}}^{a,\theta},a;\theta)\cdot
V(\overline{\bm{x}}^{a,\theta},a;\theta)+\sum_{\bm{x}\in\mathcal{X}}\sum_{\widetilde{a}\in\mathcal{A},a\neq\widetilde{a}}\overline{\pi}(\bm{x},\widetilde{a};\theta)\cdot
V(\bm{x},\widetilde{a};\theta)$
$\displaystyle=\sum_{\bm{x}\in\mathcal{X}^{a,\theta}}\pi(\bm{x},a;\theta)\cdot
V(\bm{x},a;\theta)+\sum_{\bm{x}\in\mathcal{X}}\sum_{\widetilde{a}\in\mathcal{A},a\neq\widetilde{a}}\pi(\bm{x},\widetilde{a};\theta)\cdot
V(\bm{x},\widetilde{a};\theta)$
$\displaystyle=\sum_{\bm{x}\in\mathcal{X}}\sum_{\widetilde{a}\in\mathcal{A}}\pi(\bm{x},\widetilde{a};\theta)\cdot
V(\bm{x},\widetilde{a};\theta)$
$\displaystyle\geq\sum_{\bm{x}\in\mathcal{X}}\sum_{\widetilde{a}\in\mathcal{A}}\big{[}\pi(\bm{x},\widetilde{a};\theta^{\prime})\cdot\mathop{max}_{a^{\prime}\in\mathcal{A}}V(\bm{x},a^{\prime};\theta)\big{]}$
$\displaystyle=\sum_{\bm{x}\in\mathcal{X}^{a,\theta}}\big{[}\pi(\bm{x},a;\theta^{\prime})\cdot\mathop{max}_{a^{\prime}\in\mathcal{A}}V(\bm{x},a^{\prime};\theta)\big{]}+\sum_{\bm{x}\in\mathcal{X}}\sum_{\widetilde{a}\in\mathcal{A},a\neq\widetilde{a}}\big{[}\pi(\bm{x},\widetilde{a};\theta^{\prime})\cdot\mathop{max}_{a^{\prime}\in\mathcal{A}}V(\bm{x},a^{\prime};\theta)\big{]}$
$\displaystyle\geq\overline{\pi}(\overline{\bm{x}}^{a,\theta},a;\theta^{\prime})\cdot\mathop{max}_{a^{\prime}\in\mathcal{A}}V(\overline{\bm{x}}^{a,\theta},a^{\prime};\theta)\big{]}+\sum_{\bm{x}\in\mathcal{X}}\sum_{\widetilde{a}\in\mathcal{A},a\neq\widetilde{a}}\big{[}\pi(\bm{x},\widetilde{a};\theta^{\prime})\cdot\mathop{max}_{a^{\prime}\in\mathcal{A}}V(\bm{x},a^{\prime};\theta)\big{]}.$

Here the first transition follows by the definition of
$\overline{\bm{x}}^{a,\theta}$ and the linearity of $V$ with respect to
$\bm{x}$. For the simplicity of notation, above we use $V(\bm{x},a;\theta)$
for its explicit linear form $k^{a,\theta}\bm{x}+c^{a,\theta}$. The second
follows by merging the strategies $\bm{x}\in\mathcal{X}^{a,\theta}$ into the
summation terms. The third follows by the truthfulness constraint of the
original coordination mechanism. The fourth follows by separating the
strategies $\bm{x}\in\mathcal{X}^{a,\theta}$ from the summation terms. The
last transition uses Jensen’s inequality and the convexity of point-wise
maximization.

  3. 3.

Finally, merging the strategies in $\mathcal{X}^{a,\theta}$ will not cause the
principal’s utility to decrease. Specifically, for all $a\in\mathcal{A}$ and
$\theta\in\Theta$, using Jensen’s inequality and the concavity of $U$ with
respect to $\bm{x}$, we get that

$\displaystyle\overline{\pi}(\overline{\bm{x}}^{a,\theta},a;\theta)\cdot
U(\overline{\bm{x}}^{a,\theta},a;\theta)$
$\displaystyle\geq\sum_{\bm{x}\in\mathcal{X}^{a,\theta}}\pi(\bm{x},a;\theta)\cdot
U(\bm{x},a;\theta)$
$\displaystyle=\sum_{\bm{x}\in\mathcal{X}}\pi(\bm{x},a;\theta)\cdot
U(\bm{x},a;\theta),$

where the equality is due to the incentive compatibility of $\overline{\pi}$.
Now that $\overline{\pi}$ is also incentive compatible as we argued above, the
principal’s overall expected utility can be written as
$\sum_{\theta\in\Theta}f(\theta)\sum_{a\in\mathcal{A}}\overline{\pi}(\overline{\bm{x}}^{a,\theta},a;\theta)\cdot
U(\overline{\bm{x}}^{a,\theta},a;\theta)$. Hence,

$\displaystyle\sum_{\theta\in\Theta}f(\theta)\sum_{a\in\mathcal{A}}\overline{\pi}(\overline{\bm{x}}^{a,\theta},a;\theta)\cdot
U(\overline{\bm{x}}^{a,\theta},a;\theta)\geq\sum_{\theta\in\Theta}f(\theta)\sum_{a\in\mathcal{A}}\sum_{\bm{x}\in\mathcal{X}}\pi(\bm{x},a;\theta)\cdot
U(\bm{x},a;\theta),$

which means that the principal’s utility for $\overline{\pi}$ is at least as
large as that for $\pi$. ∎

We now extend Proposition 1 to succinct mechanisms by showing that OP (3.1)
can be solved efficiently. Specifically, we show that for typical cases —
i.e., when $\mathcal{X}$ is bounded or when the instance is not irregular — OP
(3.1) reduces to an explicitly constructed convex program (CP) and thus admits
practically efficient algorithms. Key challenge in proving Theorem 2 is to
address unbounded $\mathcal{X}$ with irregular game structure (e.g., the
special case of contract design with possibly infinite payments [5]). In this
case, we have to first identify the irregularity and then adjust the mechanism
to output a finite solution that is arbitrarily close to the optimal. Our
analysis here is more involved, but our algorithm still only needs to solve at
most $|A||\Theta|$ many explicitly constructed polynomial-size convex programs
and thus avoids the (practically inefficient) ellipsoid method used in
previous literature [5].

######  Theorem 2.

Suppose that both the agent’s and the principal’s utilities are linear with
respect to the principal’s strategy, the agent’s type set $\Theta$ and action
set $\mathcal{A}$ are finite, and the principal’s strategy set $\mathcal{X}$
is a convex and closed set. Then an optimal succinct, truthful and direct
coordination mechanism can be computed in polynomial time.

###  3.1 Proof of Theorem 2

At a high level, we will convert OP (3.1) into a convex optimization problem,
which is efficiently solvable. For this purpose, define the variable
$\bm{z}^{a,\theta}\coloneqq\pi(a;\theta)\cdot\bm{x}^{a,\theta}$ and the
following joint space of $\pi(a;\theta)$ and $\bm{z}^{a,\theta}$:

$\mathcal{P}\coloneqq\big{\\{}(\lambda,\lambda\bm{x}):\bm{x}\in\mathcal{X},\lambda\in[0,1]\big{\\}}.$

As shown in Lemma 2.1 below, a useful property of $\mathcal{P}$ is that it is
convex whenever $\mathcal{X}$ is convex. Nevertheless, $\mathcal{P}$ may not
be a closed set even when $\mathcal{X}$ is closed. For instance, if
$\mathcal{X}=\mathbb{R}_{\geq 0}$, then
$\mathcal{P}=\\{(\lambda,z):\lambda\in(0,1],z\geq 0\\}\cup\\{(0,0)\\}$ which
is convex but not closed. This may cause irregularity issues in our
optimization and a large part of our proof is devoted to addressing these
issues.

######  Lemma 2.1.

If $\mathcal{X}$ is a convex set, then
$\mathcal{P}:=\\{(\lambda,\lambda\bm{x}):\bm{x}\in\mathcal{X},\lambda\in[0,1]\\}$
is a convex set.

###### Proof.

To prove that $\mathcal{P}$ is a convex set, pick any two element
$(\lambda_{1},\lambda_{1}\bm{x}_{1}),(\lambda_{2},\lambda_{2}\bm{x}_{2})$ and
we show that for any $\alpha\in[0,1]$, the element as the convex combination
$(\alpha\lambda_{1}+(1-\alpha)\lambda_{2},\alpha\lambda_{1}\bm{x}_{1}+(1-\alpha)\lambda_{2}\bm{x}_{2})$
is still in $\mathcal{P}$.

It suffices to consider two cases and show in both cases that the constructed
element can be written as $(\lambda_{3},\lambda_{3}\bm{x}_{3})$ where
$\lambda_{3}\in[0,1]$ and $\lambda_{3}\in\mathcal{X}$.

  1. 1.

Any of $\lambda_{1},\lambda_{2}$ is $0$: Without loss of generality, suppose
$\lambda_{1}=0$, then we have $\lambda_{1}\bm{x}_{1}={\bm{0}}$ and the new
element must be in the form of
$((1-\alpha)\lambda_{2},(1-\alpha)\lambda_{2}\bm{x}_{2})$. Then, we can let
$\lambda_{3}=(1-\alpha)\lambda_{2}\in[0,1]$ and
$\bm{x}_{3}=\bm{x}_{2}\in\mathcal{X}$.

  2. 2.

None of $\lambda_{1},\lambda_{2}$ is $0$: First, we can easily see that
$\lambda_{3}=\alpha\lambda_{1}+(1-\alpha)\lambda_{2}\in[0,1]$.

Second, we have
$\bm{x}_{3}=\frac{\alpha\lambda_{1}\bm{x}_{1}+(1-\alpha)\lambda_{2}\bm{x}_{2}}{\alpha\lambda_{1}+(1-\alpha)\lambda_{2}}=\frac{\alpha\lambda_{1}}{\alpha\lambda_{1}+(1-\alpha)\lambda_{2}}\bm{x}_{1}+\frac{(1-\alpha)\lambda_{2}}{\alpha\lambda_{1}+(1-\alpha)\lambda_{2}}\bm{x}_{2}\in\mathcal{X}$,
since
$\frac{\alpha\lambda_{1}}{\alpha\lambda_{1}+(1-\alpha)\lambda_{2}}\in[0,1]$
and
$\frac{\alpha\lambda_{1}}{\alpha\lambda_{1}+(1-\alpha)\lambda_{2}}+\frac{(1-\alpha)\lambda_{2}}{\alpha\lambda_{1}+(1-\alpha)\lambda_{2}}=1$.
∎

Now we convert OP (3.1) to a convex optimization problem, possibly one with a
feasible region that is not closed. We introduce a new function,
$\widehat{U}$, such that $\widehat{U}(c\cdot\bm{x},c,a;\theta)\coloneqq c\cdot
U(\bm{x},a;\theta)$. Since the principal’s utility is linear w.r.t. $\bm{x}$,
the new function $\widehat{U}$ is also linear w.r.t. $c\cdot\bm{x}$ and $c$.
We can then obtain the following convex optimization with variables
$\\{(\pi(a;\theta),\bm{z}^{a,\theta}):\theta\in\Theta,a\in\mathcal{A}\\}$. For
ease of description, we will also refer to the solution of this optimization
problem as a mechanism $M$.

$\begin{array}[]{l>{\displaystyle}l>{\displaystyle}l}\mbox{maximize}&{\sum_{\theta\in\Theta}f(\theta)\sum_{a\in\mathcal{A}}\widehat{U}(\bm{z}^{a,\theta^{\prime}},\pi(a;\theta),a;\theta)}&\\\
\mbox{subject
to}\displaystyle&\sum_{a\in\mathcal{A}}k^{a,\theta}\bm{z}^{a,\theta}+c^{a,\theta}\pi(a;\theta)\geq\sum_{a\in\mathcal{A}}\mathop{max}_{a^{\prime}\in\mathcal{A}}\\{k^{a^{\prime},\theta}\bm{z}^{a,\theta^{\prime}}+c^{a^{\prime},\theta}\pi(a;\theta^{\prime})\\}&\mbox{for
}\theta,\theta^{\prime}\in\Theta\\\
\displaystyle&(\pi(a;\theta),\bm{z}^{a,\theta})\in\mathcal{P}&\mbox{for
}a\in\mathcal{A},\theta\in\Theta\\\
\displaystyle&\sum_{a\in\mathcal{A}}\pi(a;\theta)=1&\mbox{for
}\theta\in\Theta\\\
\displaystyle&\sum_{a\in\mathcal{A}}\bm{z}^{a,\theta}\in\mathcal{C}&\mbox{for
}\theta\in\Theta\\\ \end{array}$ (3.2)

In CP (3.2), the first set of constraints is convex with respect to the
variables
$\\{(\pi(a;\theta),\bm{z}^{a,\theta}):\theta\in\Theta,a\in\mathcal{A}\\}$. The
third set of constraints is linear. In Lemma 2.1, we show that the second set
of constraint is convex. The last set of constraints is convex as
$\mathcal{C}$ is convex. In Lemma 2.2, we show this program admits the same
supremum as OP (3.1) and their solutions can be converted into one another by
construction.

######  Lemma 2.2.

$\sup(\text{CP}\eqref{lp:transformed})=\sup(\text{OP}\eqref{lp:original})$.
That is, any mechanism
$\\{(\pi(a;\theta),\bm{z}^{a,\theta}):\theta\in\Theta,a\in\mathcal{A}\\}$ in
CP (3.2) achieves the same amount of utility as some mechanism
$\\{(\pi(a;\theta),\bm{x}^{a,\theta}):\theta\in\Theta,a\in\mathcal{A}\\}$ in
OP (3.1), where
$\bm{x}^{a,\theta}=\begin{cases}\bm{z}^{a,\theta}/\pi(a;\theta)&\pi(a;\theta)\neq
0\\\ 0&\pi(a;\theta)=0\end{cases}$, for each $(a,\theta)$.

###### Proof.

For
$\sup(\text{CP}\eqref{lp:transformed})=\sup(\text{OP}\eqref{lp:original})$, we
need to show both directions holds:

  1. 1.

$\sup(\text{CP}\eqref{lp:transformed})\geq\sup(\text{OP}\eqref{lp:original})$.
That is, for any
$\\{(\pi(a;\theta),\bm{x}^{a,\theta}):\theta\in\Theta,a\in\mathcal{A}\\}$ in
OP (3.1), we can construct the mechanism
$\\{(\pi(a;\theta),\bm{x}^{a,\theta}):\theta\in\Theta,a\in\mathcal{A}\\}$ in
CP (3.2) that achieves the same utility. The construction is done by setting
$\bm{z}^{a,\theta}=\pi(a;\theta)\cdot\bm{x}^{a,\theta}$ and keeping
$\pi(a;\theta)$ the same as before for each $(a,\theta)$. It is immediately
clear according to this construction that
$\\{(\pi(a;\theta),\bm{x}^{a,\theta}):\theta\in\Theta,a\in\mathcal{A}\\}$
satisfies all constraints in CP (3.2) and has exactly the same objective as
the original mechanism.

  2. 2.

$\sup(\text{CP}\eqref{lp:transformed})\leq\sup(\text{OP}\eqref{lp:original})$.
That is, for any
$\\{(\pi(a;\theta),\bm{z}^{a,\theta}):\theta\in\Theta,a\in\mathcal{A}\\}$ in
CP (3.2), we can construct a mechanism
$\\{(\pi(a;\theta),\bm{x}^{a,\theta}):\theta\in\Theta,a\in\mathcal{A}\\}$ in
OP (3.1) that achieves the same utility. The construction is done by setting
$\bm{x}^{a,\theta}=\begin{cases}\bm{z}^{a,\theta}/\pi(a;\theta)&\pi(a;\theta)\neq
0\\\ 0&\pi(a;\theta)=0\end{cases}$ and keeping $\pi(a;\theta)$ the same as
before for each $(a,\theta)$. Observe that for any $(a,\theta)$, if
$(\pi(a;\theta),\bm{z}^{a,\theta})=(0,{\bm{0}})$, both the principal’s and
agent’s utilities for action $a$ and type $\theta$ must be zero in CP (3.2);
Similarly, both utilities are zero in OP (3.1) when
$(\pi(a;\theta),\bm{x}^{a,\theta})=(0,{\bm{0}})$ . It remains to verify that
$\\{(\pi(a;\theta),\bm{x}^{a,\theta}):\theta\in\Theta,a\in\mathcal{A}\\}$
satisfies all the constraints in OP (3.1) and has the exact same objective as
the original mechanism, which is straightforward. ∎

By Lemma 2.2, the optimal mechanism can be recovered from the optimal solution
to the convex program (CP) (3.2), except for a technical caveat — the feasible
region CP (3.2) may not be a closed set. Thus when the optimal solution of CP
(3.2) lies on the boundary not contained in the feasible region, the exact
optimal coordination mechanism may not exist. This makes it difficult to apply
an off-the-shelf convex program solver. We address this issue through a
careful analysis below.

#### The Case with Bounded Action Set

For simplicity, we start by assuming that the set $\mathcal{X}$ is bounded. In
this case, we show via Lemmas 2.1 and the following Lemma 2.3 that the set
$\mathcal{P}$ in the second set of constraints is convex and closed, and
therefore the solution to CP (3.2) is the optimal coordination mechanism.
Moreover, we can convert the optimal solution from CP (3.2) to the original
mechanism according to Lemma 2.2.

######  Lemma 2.3.

If $\mathcal{X}$ is a compact set, then
$\mathcal{P}:=\\{(\lambda,\lambda\bm{x}):\bm{x}\in\mathcal{X},\lambda\in[0,1]\\}$
is a compact set.

###### Proof.

Clearly,
$\mathcal{P}^{\prime}=\\{(\lambda,\bm{x}):\bm{x}\in\mathcal{X},\lambda\in[0,1]\\}=[0,1]\times\mathcal{X}$
is a compact set. The set $\mathcal{P}$ is the image of $\mathcal{P}^{\prime}$
under the continuous mapping $f(\lambda,\bm{x})=(\lambda,\lambda\bm{x})$.
Since compactness is preserved under a continuous mapping, it follows
immediately that $\mathcal{P}$ is compact. ∎

#### The Case with Unbounded Action Set under Regularity Assumption

We now consider the case when $\mathcal{X}$ is unbounded (but closed). The set
$\mathcal{P}$ is not a closed set and we cannot directly solve CP (3.2). We
say that the problem instance is _regular_ if CP (3.2) admits a maximum, and
it is _irregular_ otherwise.

For a regular game instance, instead of solving CP (3.2), we can without loss
of generality solve its “closure” CP (3.3), which is simply CP (3.2) with its
second constraint relaxed to the closure $\overline{\mathcal{P}}$ of the
original (possibly not closed) $\mathcal{P}$. Note that
$\overline{\mathcal{P}}$ is convex by the fact that the closure of a convex
set must be convex. According to the definition of regularity above, the
solution to CP (3.3) is exactly the maximum of CP (3.2). Hence, we can again
convert this solution to the original mechanism according to Lemma 2.2.

$\begin{array}[]{l>{\displaystyle}l>{\displaystyle}l}\mbox{maximize}&{\sum_{\theta\in\Theta}f(\theta)\sum_{a\in\mathcal{A}}\widehat{U}(\bm{z}^{a,\theta^{\prime}},\pi(a;\theta),a;\theta)}&\\\
\mbox{subject
to}\displaystyle&\sum_{a\in\mathcal{A}}k^{a,\theta}\bm{z}^{a,\theta}+c^{a,\theta}\pi(a;\theta)\geq\sum_{a\in\mathcal{A}}\mathop{max}_{a^{\prime}\in\mathcal{A}}\\{k^{a^{\prime},\theta}\bm{z}^{a,\theta^{\prime}}+c^{a^{\prime},\theta}\pi(a;\theta^{\prime})\\}&\mbox{for
}\theta,\theta^{\prime}\in\Theta\\\
\displaystyle&(\pi(a;\theta),\bm{z}^{a,\theta})\in\overline{\mathcal{P}}&\mbox{for
}a\in\mathcal{A},\theta\in\Theta\\\
\displaystyle&\sum_{a\in\mathcal{A}}\pi(a;\theta)=1&\mbox{for
}\theta\in\Theta\\\
\displaystyle&\sum_{a\in\mathcal{A}}\bm{z}^{a,\theta}\in\mathcal{C}&\mbox{for
}\theta\in\Theta\\\ \end{array}$ (3.3)

#### Addressing the Irregular Situations

However, not all problem instances are regular. A concrete example is provided
in [5], where the optimal menu of randomized contracts has to use an
infinitely large payment. This is precisely an irregular problem instance
under our definition. We denote $\mathcal{M}$ as the feasible region of CP
(3.2), $\overline{\mathcal{M}}$ as the feasible region of CP (3.3) and recall
our definition above: if the solution to CP (3.3) $M\not\in\mathcal{M}$, the
problem instance is irregular. For the sake of convenience, we will also say
that a pair $(a,\theta)$ is _irregular_ in a mechanism if $\pi(a;\theta)=0$
but $z^{a,\theta}\neq 0$; and it is _regular_ otherwise. In Lemma 2.4, we
provide a characterization of the unattainable boundary of $\mathcal{P}$, with
which we can identify irregular cases and efficiently resolve them through an
algorithmic approach.

######  Lemma 2.4.

Suppose that $M$ is a feasible mechanism in CP (3.3). Then $M$ is feasible in
CP (3.2) if and only if $(a,\theta)$ is regular in $M$ for all
$a\in\mathcal{A},\theta\in\Theta$.

###### Proof.

Let $\widehat{\mathcal{P}}=\\{(0,\bm{z}):\bm{z}\neq{\bm{0}}\\}$. We will argue
that for all $p\in\overline{\mathcal{P}}$, it holds that $p\in\mathcal{P}$ if
and only if $p\notin\widehat{\mathcal{P}}$. This easily generalizes to the
stated result in the lemma as CPs (3.3) and (3.2) differ only in the second
sets of constraints.

Pick arbitrary $p=(\lambda,\bm{z})\in\overline{\mathcal{P}}$. Since
$p\in\overline{\mathcal{P}}$, by definition, there exists a convergent
sequence $p^{1},p^{2},\dots$, such that $p^{\ell}\in\mathcal{P}$ for all
$\ell=1,2,\dots$, and $\lim_{\ell\to\infty}p^{\ell}=p$. Let
$p^{\ell}=(\lambda^{\ell},\bm{z}^{\ell})$. Hence,
$\lim_{\ell\to\infty}\lambda^{\ell}=\lambda$ and
$\lim_{\ell\to\infty}\bm{z}^{\ell}=\bm{z}$. The fact that
$p^{\ell}\in\mathcal{P}$ implies that $\lambda^{\ell}\in[0,1]$, so it must be
that $\lambda\in[0,1]$. Consider the following two cases:

  * •

If $\lambda=0$, then either $\bm{z}={\bm{0}}$, in which case
$p=(0,{\bm{0}})\in\mathcal{P}$, or $\bm{z}\neq{\bm{0}}$, in which case
$p\in\widehat{\mathcal{P}}$. Hence, $p\in\mathcal{P}$ if and only if
$p\notin\widehat{\mathcal{P}}$.

  * •

If $\lambda\in(0,1]$, we have
$\lim_{\ell\to\infty}\bm{z}^{\ell}/\lambda^{\ell}=\bm{z}/\lambda$. The fact
that $p^{\ell}\in\mathcal{P}$ implies that
$\bm{z}^{\ell}/\lambda^{\ell}\in\mathcal{X}$ according to the definition of
$\mathcal{P}$. Recall that $\mathcal{X}$ is a closed set, which means
$\bm{z}/\lambda\in\mathcal{X}$. As a result,
$p=(\lambda,\bm{z})\in\mathcal{P}$. Moreover, since $\lambda\neq 0$, we also
have $p\notin\overline{\mathcal{P}}$ in this case.

Hence, $p\in\mathcal{P}$ if and only if $p\notin\widehat{\mathcal{P}}$. ∎

To solve irregular instances, we now show that, for any arbitrarily small
$\epsilon>0$, we can obtain an (additively) $\epsilon$-optimal mechanism in
polynomial time using Algorithm 1, when the problem’s optimal objective value
is bounded (for situations with unbounded optimal utility, our constructed
mechanism will also have unbounded utility).444Typical problems, such as
contract design, are guaranteed to have bounded optimal utility even when the
principal strategy is unbounded (due to the individual rationality
constraint).  The high level idea is to solve CP (3.3) first and then add a
slight perturbation to the optimal solution if it is on the unattainable
boundary $\overline{\mathcal{P}}\setminus\mathcal{P}$. This is based on two
established facts: (1) the Lipschitz continuity of the linear objective in CP
(3.3); (2) the convexity of constraints in CP (3.3). Consequently, we can
construct a new mechanism $\overline{M}=(1-\epsilon)M^{*}+\epsilon M^{\prime}$
for any arbitrarily small $\epsilon>0$, which is a convex combination of the
optimal mechanism $M^{*}$ to CP (3.3) and a coordination mechanism
$M^{\prime}$ that lies within $\mathcal{P}$ of CP (3.2). $\overline{M}$
attains utility at least $(1-\epsilon)$ fraction of $M^{*}$ and lies within
$\mathcal{P}$ of CP (3.2) by convexity. Since $\overline{M}$ is feasible in CP
(3.2), we can convert it to a solution to OP (3.1) according to Lemma 2.2.

Hence, the remaining challenge is to find the mechanism $M^{\prime}$, which
lies within $\mathcal{P}$. The task is akin to finding a relative interior
point in the feasible region of CP (3.3) (but not exactly the same as a
feasible mechanism in CP (3.3) might be on the boundary $\pi(a;\theta)=0$ and
$\bm{z}^{a,\theta}=0$, e.g., when the action $a$ of type $\theta$ is strictly
dominated by other actions). Our approach relies on the observation of Lemma
2.4 and proceeds by enforcing a margin on the constraints $\pi(a,\theta)\geq
0$ to nudge solutions on the boundary
$\overline{\mathcal{P}}\setminus\mathcal{P}$ towards $\mathcal{P}$.
Specifically, we will use CP (3.4) to find out the maximum enforceable margin
for each action-type pair $\pi(a;\theta)$. More efficiently, leveraging the
special problem structure, we can avoid having to always solve CP (3.4) for
all the action-type pairs; the approach is presented in Algorithm 1.

$\begin{array}[]{l>{\displaystyle}l>{\displaystyle}l}\mbox{maximize}&{\pi(\widetilde{a};\widetilde{\theta})}&\\\
\mbox{subject to}&\text{the same constraints as CP~{}\eqref{lp:transformed-
closure}}&\\\ \end{array}$ (3.4)

1: Solve for the optimal mechanism $M^{*}$ in CP (3.3);

2: ${\mathcal{S}}\leftarrow\emptyset$ and $\overline{M}\leftarrow{M}^{*}$;

13: while exists $(\widetilde{a},\widetilde{\theta})$ irregular in
$\overline{M}$ do // i.e., $\pi(\widetilde{a};\widetilde{\theta})=0$ and
$\bm{z}^{\widetilde{a},\widetilde{\theta}}\neq{\bm{0}}$

24: $M^{\widetilde{a},\widetilde{\theta}}\leftarrow$ an optimal mechanism in
CP (3.4);

35:
${\mathcal{S}}\leftarrow{\mathcal{S}}\cup\\{(\widetilde{a},\widetilde{\theta})\\}$;

6:
$\overline{M}\leftarrow(1-\epsilon){M}^{*}+\frac{\epsilon}{|{\mathcal{S}}|}\sum_{(a,\theta)\in{\mathcal{S}}}M^{a,\theta}$;

7: end while

8: return $\overline{M}$.

Algorithm 1 Computing an $\epsilon$-optimal solution for CP (3.2)

##### Correctness and Time Complexity of Algorithm 1

Clearly, if Algorithm 1 terminates, the solution must be a feasible
$(1-\epsilon)$-approximate solution, as desired; indeed, the termination
condition, that the output mechanism $\overline{M}$ contains no irregular pair
$(\theta,a)$, implies that $\overline{M}$ is feasible in CP (3.2) by Lemma
2.4. The fact that the iterative process of Algorithm 1 always terminates can
be verified by the fact that each action-type pair appears at most once in the
iterations, which we demonstrate next. This observation also implies that
Algorithm 1 terminates in at most $|\mathcal{A}||\Theta|$ many iterations.

Suppose that $(\widetilde{a},\widetilde{\theta})$ appears in some iteration,
and consider the following cases with respect to the optimal mechanism
$M^{\widetilde{a},\widetilde{\theta}}$ at Line 4:

  * 1.

$\pi(\widetilde{a};\widetilde{\theta})>0$ in
$M^{\widetilde{a},\widetilde{\theta}}$. In this case, we will have
$\pi(\widetilde{a};\widetilde{\theta})>0$ in $\overline{M}$ in the remainder
of the process as $M^{\widetilde{a},\widetilde{\theta}}$ always gets a
positive weight at Line 6. Hence, $(\widetilde{a},\widetilde{\theta})$ remains
regular and will not appear again in the subsequent iterations.

  * 2.

$\pi(\widetilde{a};\widetilde{\theta})=0$ in
$M^{\widetilde{a},\widetilde{\theta}}$. In this case, we argue that it must be
$\bm{z}^{\widetilde{a},\widetilde{\theta}}={\bm{0}}$, so
$(\widetilde{a},\widetilde{\theta})$ should actually not be selected in the
previous iterations, meaning that this case is not possible. To see that
$\bm{z}^{\widetilde{a},\widetilde{\theta}}={\bm{0}}$, suppose for the sake of
contradiction that $\bm{z}^{\widetilde{a},\widetilde{\theta}}\neq{\bm{0}}$.
Since $M^{\widetilde{a},\widetilde{\theta}}$ is a feasible solution to CP
(3.4), we have
$p=\left(\pi(\widetilde{a};\widetilde{\theta}),\bm{z}^{\widetilde{a},\widetilde{\theta}}\right)\in\overline{\mathcal{P}}$,
so according to the definition of a closure there exists a point
$p^{\prime}=(\lambda,\bm{z})\in\mathcal{P}$ in every neighbourhood of $p$. Now
that $\bm{z}^{\widetilde{a},\widetilde{\theta}}\neq{\bm{0}}$, there must be
some neighbourhood of $p$ that does not contain $(0,{\bm{0}})$, which then
implies the existence of
$p^{\prime}=(\lambda,\bm{z})\in\mathcal{P}\setminus\\{(0,{\bm{0}})\\}$.
According to the definition of $\mathcal{P}$, we have $\lambda>0$, which
contradicts the assumption that $\pi(\widetilde{a};\widetilde{\theta})=0$ in
the optimal solution to CP (3.4).

#### Final Remark

While the proof of Theorem 2 is involved, the main challenge in the analysis
lies at handling the irregular situations in which the exact optimal solution
may not be attainable. While this is important for theoretical guarantee, we
expect such corner situations not to happen often. For typical regular
instances, a practical implementation of our algorithm could be very efficient
as it suffices to solve CP (3.3). If there is no irregular $(a,\theta)$ pair
in the solution, such that $\pi(a;\theta)=0$ and $\bm{z}^{a,\theta}\neq 0$,
then one can directly convert the solution into a feasible coordination
mechanism according to Lemma (2.2). Otherwise, to find the $\epsilon$-optimal
mechanism, our algorithm would just solve a few more convex programs unless
the instance is extremely degenerated.

##  4 Special Cases of Generalized Principal-Agent Problems

In this section, we discuss several special cases covered by the generalized
model we presented above.

###  4.1 Contract Design with Bayesian Agents

One special case of the generalized principal-agent problem is known as the
contract design problem. The agent has $n$ actions that the principal cannot
directly observe or control. Instead, the principal observes the $m$ different
possible outcomes and receives the reward $r_{i}\in\mathbb{R}$ associated with
each outcome $i\in[m]$. We denote $\bm{r}$ as the reward vector over each
outcome. Each agent action induces a certain outcome distribution. And the
principal must design a contract $\bm{x}\in\mathbb{R}^{m}$ that specifies the
transfer based on each possible outcome to incentivize the agent to take
certain action.

In addition, the agent has a private type $\theta$ sampled from a probability
distribution $f$, and the realization is unknown to the principal. For each
agent type $\theta$, we denote $P^{\theta}_{j}\in\Delta_{m}$,
$c^{\theta}_{j}\in\mathbb{R}$ respectively as the outcome distribution and
action cost of agent action $j$. Without loss of generality, we can restrict
the agent’s response to pure strategies that picks a deterministic action
$j\in[N]$ to play. In cases where there is more than one action that maximizes
the follower’s utility, it is assumed that the agent breaks ties in favor of
the principal. Thus, we use
$U,V:\mathbb{R}^{m}\times[n]\times\Theta\to\mathbb{R}$ to denote the utility
function of the principal and agent such that given agent type $\theta$,
principal using contract $\bm{x}$ and agent taking action $j$, the principal
and agent utility are respectively
$U(\bm{x},j;\theta)=P^{\theta}_{j}(\bm{r}-\bm{x})$ and
$V(\bm{x},j;\theta)=P^{\theta}_{j}\bm{x}-c^{\theta}_{j}$.

In this problem, the principal first commits to a menu of randomized contracts
as coordination policy $\pi:\mathbb{R}^{m}\times[n]\times\Theta\to[0,1]$ with
$\sum_{\bm{x}\in\mathcal{X},j\in[m]}\pi(\bm{x},j;\theta)=1,\forall\theta\in\Theta$
such that given that the agent reports his type $\theta$, with probability
$\pi(\bm{x},j,\theta)$, the principal will use the contract $\bm{x}$ and
recommend the agent to take action $j$. The agent then responds to the
principal’s coordination policy by first reporting a type $\theta^{\prime}$
and then choose an action $j^{\prime}$ that maximizes his expected utility
after observing the realization of principal’s contract.

######  Corollary 4.1.

The optimal menu of randomized contract can be computed in polynomial time.

The result is directly implied by Theorem 1 and 2. We can easily verify that,
in this problem, the principal strategy space is convex; the agent action and
type space are finite; the principal and agent utility are both linear w.r.t.
the principal strategy.

######  Remark 4.1.

This positive result is also observed and proved in [5] via a different
approach using the ellipsoid method. However, our algorithm only requires
solving an explicitly constructed convex program for typical instances, and at
most $|\Theta||A|$ many convex programs in the worst case.

###  4.2 Stackelberg Game with Bayesian Followers

Another special case of the generalized principal-agent problem is the
celebrated model of Stackelberg game. In a two-players Stackelberg game, we
commonly refer to the first mover as the leader and the second mover as the
follower. The follower has $n$ actions that the leader cannot directly
control. The leader has $m$ different action and can use certain mixed
strategy from the simplex $\Delta_{m}$ to induce the follower to best respond
with certain action.

In addition, the follower has a private type $\theta$ sampled from a
probability distribution $f$, and the realization is unknown to the leader.
For each follower type $\theta$, we denote $u^{\theta}\in\mathbb{R}^{m\times
n}$ (resp. $v^{\theta}\in\mathbb{R}^{m\times n}$ ) as the utility matrix of
the leader (resp. follower), and each entry $u_{i,j}^{\theta}$ (resp.
$v_{i,j}^{\theta}$) denotes the leader’s (resp. follower’s ) utility when
leader plays action $i$ and follower plays action $j$. Without loss of
generality, we can restrict the follower’s response to pure strategies that
picks a deterministic action $j\in[N]$ to play. In cases where there is more
than one action that maximizes the follower’s utility, it is assumed that the
follower breaks ties in favor of the leader. Thus, we denote the leader’s
(resp. follower’s) utility function as
$U,V:\Delta_{m}\times[n]\times\Theta\to\mathbb{R}$ such that given follower
type $\theta$, leader using strategy $\bm{x}$ and agent taking action $j$, the
leader and follower utility are respectively
$U(\bm{x},j;\theta)=\bm{x}^{\top}u^{\theta}e_{j}$ and
$V(\bm{x},j;\theta)=\bm{x}^{\top}v^{\theta}e_{j}$.555$e_{j}$ denotes the one-
hot vector with only $j$th entry as $1$.

In the game, the leader moves first by committing to a menu of randomized
strategies as coordination policy
$\pi:\Delta_{m}\times[n]\times\Theta\to[0,1]$ with
$\sum_{\bm{x}\in\mathcal{X},j\in[m]}\pi(\bm{x},j;\theta)=1,\forall\theta\in\Theta$
such that given that the follower reports his type $\theta$, with probability
$\pi(\bm{x},j,\theta)$, the leader will take the strategy $\bm{x}$ and
recommend the follower to take action $j$. The follower then responds to the
leader’s coordination policy by first reporting a type $\theta^{\prime}$ and
then choose an action $j^{\prime}$ that maximizes his expected utility after
observing the realization of leader’s strategy.

######  Corollary 4.2.

The optimal menu of randomized leader strategy can be computed in polynomial
time.

The proof is straightforward based on Theorem 1 and 2. The role of leader and
follower corresponds to the principal and agent in the general setting of
Section 2. We only need to verify that, in this problem, the leader strategy
space is a simplex and thus convex; the follower action and type space are
finite; the leader and follower utility are both linear w.r.t. the leader
strategy.

###  4.3 Information Design with Bayesian Receivers

We also consider the information design problem with Bayesian receivers as a
special case of the generalized principal-agent problem. In such problem, we
commonly refer to the information designer as the sender and the decision
maker as the receiver. The decision maker has $n$ actions that the information
designer cannot directly control. The information source has a prior
$\mu\in\Delta_{m}$ that is supported on $m$ different outcomes. The
information designer is able to observe the realization of the outcome, and
strategically reveal to the decision maker in order to influence the
receiver’s decision.

To model the sender’s strategic revelation of information, it is standard to
use a _signaling scheme_ , which essentially specifies the conditional
distribution of a random variable (namely the _signal_), given the outcome.
Before the realization of the outcome, the sender commits to such a signaling
scheme. Given the realized outcome, the sender samples a _signal_ from the
conditional distribution according to the _signaling scheme_ and reveals it to
the receiver. Upon receiving this _signal_ , the receiver infers a posterior
belief about the outcome via Bayes’ theorem (based on the correlation between
the signal and outcome $i\in[n]$ as promised by the signaling scheme) and then
chooses an action $j\in[n]$ that maximizes the expected utility. For
notational convenience, we denote the signal by $\bm{x}\in\Delta_{m}$ as the
posterior inferred from the signal. The signaling scheme is valid if
$\sigma(\bm{x})\bm{x}=\mu$, where $\sigma(\bm{x})$ is the probability the
signal is sampled.

In addition, the receiver has a private type $\theta$ sampled from a
probability distribution $f$, and the realization is unknown to the sender.
For each receiver type $\theta$, we denote $u^{\theta}\in\mathbb{R}^{m\times
n}$ (resp. $v^{\theta}\in\mathbb{R}^{m\times n}$ ) as the utility matrix of
the sender (resp. receiver), and each entry $u_{i,j}^{\theta}$ (resp.
$v_{i,j}^{\theta}$) denotes the sender’s (resp. receiver’s ) utility when
receiver takes action $j$ at the realized outcome $i$. Without loss of
generality, we can restrict the receiver’s response to pure strategies that
picks a deterministic action $j\in[N]$ to play. In cases where there is more
than one action that maximizes the receiver’s utility, it is assumed that the
receiver breaks ties in favor of the sender. Thus, we denote the sender’s
(resp. receiver’s) utility function as
$U,V:\Delta_{m}\times[n]\times\Theta\to\mathbb{R}$ such that given follower
type $\theta$, sender using signal $\bm{x}$ and follower taking action $j$,
the sender and receiver utility (taking expectation over outcomes conditioned
on the signal) are respectively
$U(\bm{x},j;\theta)=\bm{x}^{\top}u^{\theta}e_{j}$ and
$V(\bm{x},j;\theta)=\bm{x}^{\top}v^{\theta}e_{j}$.

In this problem, the sender first commits to a menu of signaling scheme as
coordination policy $\pi:\Delta_{m}\times[n]\times\Theta\to[0,1]$ with
$\sum_{\bm{x}\in\mathcal{X},j\in[m]}\pi(\bm{x},j;\theta)=1,\forall\theta\in\Theta$
and
$\sum_{\bm{x}\in\mathcal{X},j\in[m]}\pi(\bm{x},j;\theta)\bm{x}=\mu,\forall\theta\in\Theta$
in order for the signaling scheme to be valid. Hence, given that the receiver
reports his type $\theta$, with probability $\pi(\bm{x},j,\theta)$, the sender
will use the signal $\bm{x}$ and recommend the receiver to take action $j$.
The receiver then responds to the sender’s coordination policy by first
reporting a type $\theta^{\prime}$ and then choose an action $j^{\prime}$ that
maximizes his expected utility after observing the realization of sender’s
signal.

######  Corollary 4.3.

The optimal signaling mechanism for Bayesian receiver type can be computed in
polynomial time.

The result is directly implied by Theorem 1 and 2. The role of leader and
follower corresponds to the principal and agent in the general setting of
Section 2. Similar to the Stackelberg game, we can also verify that, in this
problem, the principal strategy space is convex; the agent action and type
space are finite; the principal and agent utility are both linear w.r.t. the
principal strategy. In addition, in the information design problem, we need to
account for the additional constraint specific to the signaling scheme, i.e.,
$\sum_{\bm{x}\in\mathcal{X},j\in[m]}\pi(\bm{x},j;\theta)\bm{x}=\mu,\forall\theta\in\Theta$.
And this can be model by the supplemental constraint, as $\mu$ is a single
point in $\Delta_{m}$ that gives a convex set.

######  Remark 4.2.

In such information design problems, we treat the signal, instead of the
signaling scheme, as a strategy of the receiver (principal). Thus, it suffices
to consider the coordination policy as a menu of single schemes, as oppose to
a menu of randomized schemes that one might expect. Alternatively, any set of
randomized schemes can be merged into a single scheme by reweighing signals of
each scheme in the set by the probability of choosing such schemes. However,
the information design problem is different from the Stackelberg game problem
in that the signals, compared to the leader strategies, must satisfy the
additional constraint in order for the signaling scheme to be valid.

##  5 Computing Optimal Coordination Mechanisms under Restrictions

In this section, we study the complexity of computing the optimal coordination
mechanisms for each specific principal-agent game under different
restrictions. Specifically, we consider two restrictions that can be imposed
on the coordination mechanism. The first restriction requires that the
principal must use the same strategy for all agent types. In other words,
there is no type reporting or information elicitation under this restriction.
Without this restriction, the principal can use a menu that specifies type-
dependent strategies. In this case, the second restriction we consider
requires the menu to be deterministic. In the most general case without both
restrictions, the principal uses a menu which specifies a randomized strategy
for each reported agent type. Note that the randomized strategy is more
general than the concept of mixed strategy—we can devise a randomized strategy
that is a distribution over a set of mixed strategies. Optimal coordination
mechanisms under these two restrictions has been studied in a number of
applications [16, 10, 5]. We summarize previous results in the literature and
fill in several blanks that were left open. The results on contract design,
Stackelberg game, and Bayesian persuasion are summarized in Tables 1, 2 and 3,
respectively.

|  Single Contract | Menu of | Menu of
---|---|---|---
| Deterministic Contracts | Randomized Contracts
Hidden Agent Type (Action Cost) | NP-Hard | NP-Hard | Polynomial
[16] | [16, 5] |  [5], [Corollary 4.1]
Hidden Agent Type (Outcome Distribution) | NP-Hard | NP-Hard | Polynomial
[10] | [10, 5] |  [5], [Corollary 4.1]
Table 1: Computation complexity of optimal contract design for hidden agent types. Hidden agent type with action cost means all the agent types have the same outcome distribution but different costs for every action, and vice versa for the hidden agent type with outcome distribution. | Single Strategy | Menu of Single Strategies | Menu of Randomized Strategies
---|---|---|---
Hidden Follower Type | NP-Hard | NP-Hard | Polynomial
[11] | [Theorem 3] | [Corollary 4.2]
Table 2: Computation complexity of optimal leader strategy for hidden followers types. | Single Scheme | Menu of Single Schemes $\equiv$ Menu of Randomized Schemes
---|---|---
Hidden Receiver Type | NP-Hard [15] | Polynomial [Corollary 4.3]
Table 3: Computation complexity of optimal signaling scheme for unknown
receivers types.

######  Theorem 3.

For any constant $\epsilon>0$, it is NP-Hard to compute
$\frac{1}{|\Theta|^{1-\epsilon}}$-approximation incentive compatible leader
strategy in a Stackelberg game with Bayesian followers.

###### Proof.

We show a reduction from the Max Independent Set (MIS) problem. It is known
that no polynomial-time $\frac{1}{|\Theta|^{1-\epsilon}}$-approximation
algorithm exists for MIS, unless P=NP. An MIS instance is given by a graph
$G=(V,E)$, we construct a game with $K=|V|=|\Theta|$ follower types
$\Theta=\\{\theta_{v}:v\in V\\}$; each follower $\theta_{v}$ corresponds to a
node $v$ and appears with probability $\frac{1}{k}$. The leader has $2|V|$
actions $\\{a_{v}:v\in V\\}\cup\\{b_{v}:v\in V\\}$; the follower has $3$
actions $\\{1^{F},2^{F},3^{F}\\}$. The follower’s utility is given by Table 4.

Type $\theta_{v}$ | $1^{F}$ | $2^{F}$ | $3^{F}$
---|---|---|---
$a_{v}$ | 0.1 | 0.1 | 0.1
$b_{v}$ |  | 1 | 1
$\\{a_{v^{\prime}}:v^{\prime}\in\mathcal{N}(v)\\}$ | 0.5 |  | 1
otherwise |  |  | 0.1
Table 4: Utility information of the follower with type $\theta_{v}$.
$\mathcal{N}(v)$ denotes the neighbour nodes of $v$ in the graph $G$. All
empty elements are 0.

Irrespective of the strategy the leader plays, the leader always gets utility
$1$ when the follower responds with action $1^{F}$, and utility $0$ when the
follower responds with $2^{F}$ or $3^{F}$.

Given an independent set $V^{*}$ of size $k$, consider the following leader
mechanism:

$\bm{x}^{*}(\theta^{v})=\begin{cases}a_{v},\quad\text{if }v\in V^{*}\\\
b_{v},\quad\text{otherwise}\end{cases}$

We claim the above leader mechanism $\bm{x}^{*}(\theta^{v})$ is an incentive
compatible leader mechanism and gives the expect leader utility $\frac{k}{K}$
because: (1) for any follower type $\theta^{v}\in V^{*}$, misreporting
$\theta^{\overline{v}}$ leads to the leader playing strategy
$a_{\overline{v}}$ if $\overline{v}\in V^{*}$ (which means
$\overline{v}\notin\mathcal{N}(v)$ as $V^{*}$ is an independent set), or
strategy $b_{\overline{v}}$ if $\overline{v}\notin V^{*}$. Neither strategy
makes the follower better off than reporting truthfully. (2) for any follower
type $\theta^{v}\notin V^{*}$, the follower can already get the maximum
possible utility $1$ if they report truthfully. So no follower type has any
incentive to misreport in this case. As a result, among the $K$ follower
types, the $k$ types in the independent set will respond with $1^{F}$ which
offers the leader a utility of $\frac{k}{K}$.

On the other hand, given any incentive compatible mechanism, we claim that the
follower types who respond with $1^{F}$ must form an MIS. For the sake of
contradiction, assume $(v_{1},v_{2})\in E$ and both follower types
$\theta^{v_{1}}$ and $\theta^{v_{2}}$ best respond with $1^{F}$. Note that
$1^{F}$ is strictly dominated by $3^{F}$ for the follower unless the leader
plays $a_{v}$. Therefore, in order to make follower type
$\theta^{v_{1}}(\theta^{v_{2}})$ best respond with $1^{F}$, we must have
$\bm{x}(\theta^{v_{1}})=a_{v_{1}}(\bm{x}(\theta^{v_{2}})=a_{v_{2}})$. However,
note that $(v_{1},v_{2})\in E$. Consequently, the follower of type
$\theta^{v_{1}}(\theta^{v_{2}})$ is incentivized to misreport
$\theta^{v_{2}}(\theta^{v_{1}})$, which gives them a higher utility,
contradicting the incentive compatibility.

As a result, under the optimal incentive compatible leader strategy, the
number of follower types who respond with $1^{F}$ equals to the size of the
MIS. In addition, the number of follower types who respond with $1^{F}$ is
also proportional to the leader’s overall utility since the leader only gets
utility when the follower responds with $1^{F}$. Therefore, any
$\frac{1}{|\Theta|^{1-\epsilon}}$-approximation algorithm for the optimal
incentive compatible leader strategy would also give
$\frac{1}{|\Theta|^{1-\epsilon}}$-approximation to the MIS problem. ∎

## References

  * ADTC [21] Tal Alon, Paul Dütting, and Inbal Talgam-Cohen.  Contracts with private cost per unit-of-effort.  In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 52–69, 2021.
  * Ake [78] George A Akerlof.  The market for “lemons”: Quality uncertainty and the market mechanism.  In Uncertainty in economics, pages 235–251. Elsevier, 1978.
  * Ant [81] Ricky Lee Antle.  Moral hazard and auditor contracts: an approach to auditors’legal liability and independence.  Stanford University, 1981.
  * [4] Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti.  Bayesian agency: Linear versus tractable contracts.  Artificial Intelligence, 307:103684, 2022.
  * [5] Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti.  Designing menus of contracts efficiently: The power of randomization.  arXiv preprint arXiv:2202.10966, 2022.
  * DRTC [19] Paul Dütting, Tim Roughgarden, and Inbal Talgam-Cohen.  Simple versus optimal contracts.  In Proceedings of the 2019 ACM Conference on Economics and Computation, pages 369–387, 2019.
  * DRTC [21] Paul Dutting, Tim Roughgarden, and Inbal Talgam-Cohen.  The complexity of contracts.  SIAM Journal on Computing, 50(1):211–254, 2021.
  * EFR+ [13] Liran Einav, Amy Finkelstein, Stephen P Ryan, Paul Schrimpf, and Mark R Cullen.  Selection on moral hazard in health insurance.  American Economic Review, 103(1):178–219, 2013.
  * GH [92] Sanford J Grossman and Oliver D Hart.  An analysis of the principal-agent problem.  In Foundations of insurance economics, pages 302–340. Springer, 1992.
  * GSW [21] Guru Guruganesh, Jon Schneider, and Joshua R Wang.  Contracts under moral hazard and adverse selection.  In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 563–582, 2021.
  * LCM [09] Joshua Letchford, Vincent Conitzer, and Kamesh Munagala.  Learning and approximating the optimal strategy to commit to.  In International symposium on algorithmic game theory, pages 250–262. Springer, 2009.
  * LM [09] Jean-Jacques Laffont and David Martimort.  The theory of incentives.  In The Theory of Incentives. Princeton university press, 2009.
  * Mye [82] Roger B Myerson.  Optimal coordination mechanisms in generalized principal–agent problems.  Journal of mathematical economics, 10(1):67–81, 1982.
  * Smi [04] Stephen A Smith.  Contract theory.  OUP Oxford, 2004.
  * Xu [20] Haifeng Xu.  On the tractability of public persuasion with no externalities.  In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2708–2727. SIAM, 2020.
  * XWC+ [20] Shenke Xiao, Zihe Wang, Mengjing Chen, Pingzhong Tang, and Xiwang Yang.  Optimal common contract with heterogeneous agents.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 7309–7316, 2020.