To select a subset of samples or “winners” from a population of
candidates, order sampling <cit.> and the $k$-unit
Myerson auction <cit.> share a common scheme:
assign a (random) score to each candidate, then select the $k$
candidates with the highest scores.
We study a generalization of both order sampling and Myerson's allocation rule,
called winner-selecting dice.
The setting for winner-selecting dice is similar to auctions with
feasibility constraints: candidates have random types drawn from
independent prior distributions,
and the winner set must be feasible subject to certain constraints.
Dice (distributions over scores) are assigned to each type,
and winners are selected to maximize the sum of the dice rolls,
subject to the feasibility constraints.
We examine the existence of winner-selecting dice that implement
prescribed probabilities of winning (i.e., an interim rule) for all types.

Our first result shows that when the feasibility constraint is a matroid,
then for any feasible interim rule, there always exist
winner-selecting dice that implement it.
Unfortunately, our proof does not yield an efficient algorithm for
constructing the dice.
In the special case of a $1$-uniform matroid, i.e., only one winner
can be selected, we give an efficient algorithm that constructs
winner-selecting dice for any feasible interim rule.
Furthermore, when the types of the candidates are drawn in an
i.i.d. manner and the interim rule is symmetric across candidates,
unsurprisingly, an algorithm can efficiently construct symmetric dice that only
depend on the type but not the identity of the candidate.

One may ask whether we can extend our result to “second-order” interim rules,
which not only specify the winning probability of a type,
but also the winning probability conditioning on each other candidate's
We show that our result does not extend, by exhibiting an
instance of Bayesian persuasion whose optimal scheme is
equivalent to a second-order interim rule,
but which does not admit any dice-based implementation.

§ INTRODUCTION

Economic design often features scenarios in which choices must be made
based on stochastic inputs. In auction design, bidders drawn from a
population interact with an auction mechanism, and the mechanism must
then choose winners and losers of the auction. In information
structure design, a principal observes information pertinent to the
various actions available to one or more decision makers, and must use
this information to recommend actions to the decision makers.
In such settings, an important framing device is the notion of
an interim rule (also called a reduced form) of an (ex-post) winner
selection rule, summarizing the probability for each candidate to be selected.

We focus on the simplest and most natural class of such decision
making scenarios, one which includes auctions and Bayesian persuasion
<cit.> as special cases. In a winner selection
environment, there is a set of candidates $\C$,
each equipped with a random attribute known as its type.
A winner selection rule is a
randomized function (or algorithm) which maps each profile of types,
one per candidate, to a choice of winning candidates,
subject to the requirement that the set of winners must belong to a
specified family $\I\subseteq 2^\C$ of feasible sets.
The winner selection rule is also referred to as an ex-post rule since
it specifies the winning probabilities conditioned on every realized
type profile.
In auctions, candidates correspond to bidders, and a winner selection
rule is an allocation rule of the auction.
In Bayesian persuasion, candidates correspond to actions available to
a decision maker, and a winner selection rule corresponds to a
persuasion scheme used by a principal to recommend one of the actions
to the decision maker.
We restrict our attention to winner selection scenarios in which the
types of different candidates are independently distributed.

We distinguish two classes of interim rules: first-order and
second-order. The former is the traditional notion from auction
theory, while the latter is the notion better suited for persuasion.
A first-order interim rule specifies, for each candidate $i$ and
type $t$ of candidate $i$, the conditional probability of $i$ winning
given that his type is $t$. A second-order interim rule
specifies more information:

for each pair of candidates $i,j$ and type $t$ of candidate $j$,
it specifies the conditional probability of $i$
winning given that $j$ has type $t$.

First-order interim rules, when
combined with a payment rule, suffice for evaluating the welfare,
revenue, and incentive-compatibility of a single-item auction. For
Bayesian persuasion, second-order interim rules are needed for
evaluating the incentive constraints of a persuasion scheme.

Our motivation for studying winner selection at this level of
generality stems from the success of Myerson's <cit.>
famous and elegant characterization of revenue-optimal single-item
auctions when bidder type distributions are independent. In that
special case, Myerson showed that the optimal single-item auction
features a particularly structured winner-selection rule: each type is
associated with a virtual value, and given a profile of reported
types, the rule selects the bidder with the highest (non-negative)
virtual value as the winner.

Interestingly, order sampling <cit.> works in a
similar way as Myerson's auction, in the special case when the feasible
sets are sets of $k$ or fewer candidates,
and each candidate has only one type.
Order sampling assigns each candidate a random score variable (a die).
The winners are the candidates with the $k$ highest score variables.
In the language of order sampling, virtual value functions
define a single-sided die for each type.
Unlike Myerson's auction, there is no notion of “revenue” or
“incentive constraints” in order sampling.
The task

is simply to find dice that will induce a
prescribed first-order interim rule.

As a generalization of order sampling and Myerson's virtual-value approach, a dice-based winner-selection rule assigns each type a die, and selects the feasible set of winners maximizing the sum of the dice rolls.
We explore the extent to which dice-based rules are applicable
beyond single-parameter auctions or single-type environments, to
winner selection with independent type distributions
under more complex constraints.

In particular, we examine whether dice-based winner-selection rules
exist for winner selection subject to matroid constraints and for
Bayesian persuasion.

§.§ Our Results

As mentioned previously, all of our results are restricted to settings
in which the candidates' type distributions are independent.
It follows from Myerson's characterization that every first-order
interim rule corresponding to some optimal auction admits a
dice-based implementation.
[As we show in the appendixthe full version, there
are interim rules which are not optimal for any auction.]
Our main result (in Section <ref>)
is an existential proof showing that every
feasible first-order interim rule with respect to a matroid constraint
admits a dice-based implementation.
This illustrates that the structure revealed by Myerson's
characterization is more general, and applies to other settings
in which only first-order interim information is relevant.
For example, single-item auctions with (public or private) budgets are
such a setting (see, e.g., <cit.>).
Our result also provides a generalization of order sampling from the
$k$-winner setting to the general matroid, multi-type setting.

Beyond the existential proof of dice-based implementations,
we show (in Section <ref>)
that for single-winner environments,
an algorithm can construct the dice-based rule efficiently.
When the types are identically distributed, we also constructively
show (in Section <ref>the full version)
that every first-order interim rule
which is symmetric across candidates admits a symmetric dice implementation;
i.e., different candidates have the same die for the same type.
This is consistent with Myerson's symmetric characterization of
optimal single-item auctions with i.i.d. bidders, and generalizes it
to any other first-order single-winner selection setting in which
candidates are identical.
Single-item auctions with identically distributed budgeted bidders are
such a setting, and a symmetric dice-based implementation of the
optimal allocation rule was already known from <cit.>.

For single-winner cases, we also show the converse direction:
how to efficiently compute the first-order
interim rule of a given dice-based winner selection rule.
In effect, these results show that collections of dice are a
computationally equivalent description of single-winner first-order
interim information.
This implies a kind of equivalence between the two dominant approaches
for mechanism design: the Myersonian approach based on virtual values
(i.e., dice), and the Borderian approach based on optimization over interim rules.

In an attempt to leverage the same kinds of insights for
Bayesian persuasion, we examine
(in Sections <ref> and <ref>)
the dice implementability of second-order interim rules.
When the candidate type distributions are non-identical,
we show an impossibility result.
We construct an instance of Bayesian persuasion with independently
distributed non-identical actions,
and show that no optimal persuasion scheme for this instance can be
implemented by dice.
Since second-order interim rules are sufficient for evaluating the
objective and constraints of Bayesian persuasion,
this implies that there exist second-order interim rules which are not
This rules out the Myersonian approach for characterizing and
computing optimal schemes for Bayesian persuasion
with independent non-identical actions, complementing the negative
result of <cit.> which rules out the Borderian
approach for the same problem.

Our impossibility result disappears when the actions are i.i.d.,
since second-order interim rules collapse to first-order interim rules in
symmetric settings.
In particular, as we show in Section <ref>,
our results for first-order interim rules,
combined with those of <cit.>,
imply that Bayesian persuasion with i.i.d. actions admits an optimal
dice-based scheme, which can be computed efficiently.

§.§ Additional Discussion of Related Work

<cit.> was the first to characterize revenue-optimal single-item auctions; this characterization extends to single-parameter mechanism design settings more generally (see, e.g., <cit.>).
The (first-order) interim rule of an auction, also known as its reduced form, was first studied by <cit.> and <cit.>. The inequalities characterizing the space of feasible interim rules were described by <cit.>. Border's analytically tractable characterization of feasible interim rules has served as a fruitful framework for mechanism design, since an optimal auction can be viewed as the solution of a linear program over the space of interim rules. Moreover, this characterization has enabled the design of efficient algorithms for recognizing interim rules and optimizing over them, by <cit.> and <cit.>. This line of work has served as a foundation for much of the recent literature on Bayesian algorithmic mechanism design in multi-parameter settings.

It is important to contrast our dice-based rule with the characterization of <cit.>. In particular, the results of <cit.> imply that every first-order interim rule can be efficiently implemented as a distribution over virtual value maximizers. In our language, this implies the existence of an efficiently computable dice-based implementation in which the dice may be arbitrarily correlated. Our result, in contrast, efficiently computes a family of independent dice implementing any given first-order interim rule in single-winner settings, and shows the existence of a dice-based rule in matroid settings. This is consistent with Myerson's characterization, in which virtual values are drawn independently.

<cit.> also studied winner-selection environments, under the
different name “service based environments.” For single-winner
settings, they proposed a mechanism called stochastic sequential
allocation (SSA). The mechanism also implements any feasible
first-order interim rule, by creating a token of winning and
transferring the token sequentially from one candidate to another,
with probabilities defined by an efficiently computed transition
Dice can be considered as the special case of SSA in which the
transition probabilities are independent of the current owner of the token.

As another motivation for our focus on dice-based rules,
order sampling studies how to sample $k$ winners from $n$ candidates
with given inclusion probabilities (i.e., implement an interim rule),
by assigning a random score variable (die) to each candidate.
<cit.> showed that parameterized Pareto
distributions can be used to implement a given interim rule asymptotically.
<cit.> proved the existence of an order sampling
scheme that exactly implements any feasible interim rule.
Our existential proof is a generalization of the proof of <cit.> to settings with multiple types and matroid constraints.

The Bayesian persuasion model is due to <cit.>, and is the most influential model in the general space of information structure design (see the survey by <cit.> for references). Bayesian persuasion was examined algorithmically by <cit.>, who observed its connection to auction theory and interim rules, and examined the computational complexity of optimal schemes through the lens of optimization over interim rules.

Of particular relevance to our work is the negative result of <cit.> for Bayesian persuasion with independent non-identical actions: it is #P-hard to compute the interim rule (first- or second-order) of the optimal scheme, or more simply even the sender's optimal utility. Most notable about this result is what it does not rule out: an algorithm implementing the optimal persuasion scheme “on the fly,” in the sense that it efficiently samples the optimal scheme's (randomized) recommendation when given as input the profile of action types. Stated differently, the negative result of <cit.> merely rules out the Borderian approach for this problem, leaving other approaches — such as the Myersonian one — viable as a means of obtaining an efficient “on the fly” implementation.  This would not be unprecedented: <cit.> exhibit a simple single-parameter auction setting for which the optimal interim rule is #P hard to compute, yet Myerson's virtual values can be sampled efficiently and used to efficiently implement the optimal auction. Our negative result in Section <ref> rules out such good fortune for Bayesian persuasion with independent non-identical actions: there does not exist a (Myersonian) dice-based implementation of the optimal persuasion scheme in general.

§ PRELIMINARIES

§.§ Winner Selection

Consider choosing a set of winners from among candidates.

Each candidate $i$ has a type $\type{i} \in T_i$,
drawn independently from a distribution [i].
A winner-selection rule maps each type profile
$\TP = (\type{1}, \ldots, \type{\NUMC})$, possibly randomly,
to one of a prescribed family of feasible sets $\I\subseteq 2^{[n]}$.
When $i\in \ALGO(\TP)$, we refer to $i$ as a
winning candidate, and to $t_i$ as his winning type.
Writing $\PMF = \PMF[1] \times \cdots \times \PMF[n]$ for the
(independent) joint type distribution,
we also refer to $(\PMF, \I)$ as the winner-selection environment.
When $\I$ is the family of singletons, as in the setting of the single
item auction,
we call $(\PMF,\I)$ a single-winner environment.

This general setup captures the allocation rules of general
auctions with independent unit-demand buyers,
albeit without specifying payment rules or imposing incentive constraints.
Moreover, it captures Bayesian persuasion with independent action
payoffs, albeit without enforcing persuasiveness (also called obedience)

§.§ Matroids

In this paper, we focus on settings in which the feasible sets $\I$ are
the independent sets of a matroid.
We use the standard definition of a matroid $\M$ as a pair $(E, \I)$,
where $E$ is the ground set and $\I\subseteq 2^E$ is a family
of so-called independent sets, satisfying the three matroid axioms.
We also use the standard definitions of a circuit and
rank function $r_\M : 2^E \to \NN$.
The restriction $\M|S$ of $\M=(E,\I)$ to some $S \sse E$ is the
matroid $(E, \I \intersect 2^S)$.[Note that we deviate
slightly from the standard definition in that we do not restrict the
ground set.]
For details on matroids, we refer the reader to <cit.>.

A matroid $\M = (E, \I)$ is separable if it is a direct sum
of two matroids $\M_1=(E_1, \I_1)$ and $\M_2=(E_2, \I_2)$.
Namely, $E = E_1\uplus E_2$, $\I = \Set{A\cup B}{A\in \I_1, B\in \I_2}$.
Note that if $\M$ is non-separable, then $r_\M(E) < |E|$;
otherwise $\M$ is the direct sum of singleton matroids.
We use the following theorem.

(1) When $\M=(E, \I)$ is a non-separable matroid, for every $a,b\in E$, there is a circuit containing both $a$ and $b$.
(2) Any separable matroid $\M$ is a direct sum of two or more
non-separable matroids called the components of $\M$.

In most of the remainder of the paper, we focus on winner selection
environments $(\PMF,\I)$ where $\I$ is the family of independent sets of
a matroid $\M$.
We therefore also use $(\PMF,\M)$ to denote the environment.

§.§ Interim Rules and Border's Theorem

A (first-order) interim rule specifies the winning probability
$\interim[i]{t} \in [0,1]$ for all $i \in [\NUMC], t \in T_i$ in an
environment $(\PMF, \I)$.
More precisely, we say that a winner-selection rule implements the interim rule for a prior if it
satisfies the following:
if the type profile $\TP = (\type{1}, \ldots, \type{n})$
is drawn from the prior distribution
$\PMF = \PMF[1] \cross \cdots \cross \PMF[\NUMC]$,
then $\ProbC{i\in \ALGO[\TP] }{\type{i} = t} = \interim[i]{t}$.

An interim rule is feasible (or implementable) within an
environment $(\PMF, \I)$
if there is a winner-selection rule implementing it that always
outputs an independent set of $\I$.

§.§.§ Border's theorem and implications for  single-winner environments

The following theorem characterizes the space
of feasible interim rules for single-winner settings.

An interim rule is feasible for a single-winner setting if and only if for all possible type
$S_1\subseteq T_1, S_2\subseteq T_2, \ldots,
S_n\subseteq T_{\NUMC}$,

\begin{equation}
\sum_{i=1}^\NUMC \sum_{t \in S_i} \pmf[i]{t} \interim[i]{t}
\le 1 - \prod_{i=1}^\NUMC \left( 1 - \sum_{t\in S_i} \pmf[i]{t} \right).
\label{eqn:border-constraint}
\end{equation}

The following result leverages Theorem <ref> to show that
efficient algorithms exist for checking the feasibility of an interim
rule, and for implementing a feasible interim rule.

Given explicitly represented priors $\PMF[1], \ldots, \PMF[\NUMC]$ and
an interim rule in a single-winner setting, the feasibility of can be checked
in time polynomial in the number of candidates and types.
Moreover, given a feasible interim rule ,
an algorithm can find a winner-selection rule implementing in time
polynomial in the number of candidates and types.

In our efficient construction for single-winner settings, we utilize a structural result
which shows that checking only a subset of Border's
constraints suffices <cit.>.
This subset of constraints can be identified efficiently.

An interim rule is feasible for a single-winner setting if and only if for all possible
$\alpha \in [0,1]$, the sets
$S_i(\alpha) = \Set{t \in T_i}{\interim[i]{t} > \alpha}$
satisfy the following Border's constraint:

\[
\sum_{i=1}^{\NUMC} \sum_{t\in S_i(\alpha)} \pmf[i]{t} \interim[i]{t}
\leq 1 - \prod_{i=1}^{\NUMC} \left(1 - \sum_{t\in S_i(\alpha) } \pmf[i]{t}\right).
\]

When the candidates' type distributions are i.i.d., i.e.,
$T_i$ and [i] are the same for all candidates $i$,
it is typically sufficient to restrict attention to symmetric
interim rules.
For such rules, [i]t is equal for all candidates $i$.
In the i.i.d. setting, we therefore notationally omit the dependence on
the candidate and let $T$ refer to the common type set of all candidates,
to the candidates' (common) type distribution,
and t to the probability that a particular candidate wins
conditioned on having type $t$.
In the i.i.d. setting, only the symmetric constraints from
Theorem <ref> suffice to characterize feasibility
<cit.>; namely,

\begin{equation}
\NUMC \cdot \sum_{t\in S} \pmf{t} \interim{t}
\; \le \; 1 - \left( 1-\sum_{t \in S} \pmf{t} \right)^{\NUMC} ,
\label{eqn:symmetric-border}
\end{equation}

for all $S \sse T$.
Theorem <ref> then implies that it suffices to check
Inequality (<ref>) for sets of the form
$S(\alpha) = \set{ t \in T : \interim{t} > \alpha}$ with $\alpha \in [0,1]$.

§.§.§ Border's Theorem for matroid environments

For general settings with matroid constraints, <cit.>
established the following generalized “Border's Theorem.”

Let $\candidate$ map each type $t$ to the (unique) candidate $i$ with
$t \in T_i$.
An interim rule is feasible within an environment $(\PMF, \M)$
if and only if for all possible type subsets
$S_1\subseteq T_1, S_2\subseteq T_2, \ldots, S_n\subseteq T_{\NUMC}$,

\[
\sum_{i=1}^n \sum_{t\in S_i}\pmf[i]{t} \interim[i]{t}
\le \Expect[\vc{t} \sim \PMF]{r_{\M}(\candidate(\vc{t}\cap S))},
\]

\sum_{i=1}^n \sum_{t\in S_i}\pmf[i]{t} \interim[i]{t}
\le \Expect[\vc{t} \sim \PMF]{r_{\M}(\candidate(\vc{t}\cap S))},
where $S=\bigcup_{i=1}^n S_i$.

In later sections, we omit the function $\candidate$,
and for any type set $S$ just write $r_\M(S)$ instead of $r_\M(\candidate(S))$.

§.§ Winner-Selecting Dice

We study winner-selection rules based on dice, as a generalization of order sampling to multiple types and
general constraints.
A dice-based rule fixes, for each type $t\in T_i$,
a distribution [i]t over real numbers, which we call a die.
Given as input the type profile $\TP = (\type{1}, \ldots, \type{\NUMC})$,
the rule independently draws a score
$v_i \sim \die[i]{\type{i}}$ for each candidate $i$ by “rolling
his die;” it then selects the feasible set of candidates maximizing
the sum of scores as the winner set, breaking ties with a predefined rule.
In this paper, we will mainly discuss matroid feasibility constraints,
for which a feasible set maximizing the sum of scores can be found by
a simple greedy algorithm:
candidates are added to the winner set in decreasing order of their
scores, breaking ties uniformly at random, as long as the new winner
set is still an independent set of the matroid and their scores are
When candidates have the same type sets,
we call a dice-based rule symmetric if [i]t is the same
for all $i$.

Myerson's optimal auction is a dice-based winner-selection rule.
In Myerson's nomenclature, i is candidate $i$'s virtual value,
and [i]t is a single-sided die with the virtual value.

Let $T$ be the set of all types of all candidates and
$\DIESET = (\DIE[t])_{t \in T}$ be a vector of dice, one per type.
Given an interim rule , and a winner-selection environment
$(\PMF, \I)$, we say that implements ,
or describes winner-selecting dice for in
$(\PMF, \I)$, if the dice-based rule given by implements
within the environment $(\PMF, \I)$.

§.§ Second-order Interim Rules

A (first-order) interim rule, as defined in Section <ref>,
specifies, for each candidate $i$, the conditional type distribution
of $i$ in the event that $i$ is chosen as the winner.
We define a second-order interim rule
[Our notion of second-order interim rules is
different from the notion defined in <cit.>.
Because <cit.> consider correlation in types,
their notion of second-order interim rules is aimed at capturing the
allocation dependencies arising through such type
correlation, rather than solely through the mechanism's choice.]
which maintains strictly more information,
as needed for describing the incentive constraints of Bayesian persuasion.
Such a rule specifies, for each pair of candidates $i$ and $i'$
(where $i'$ may or may not be equal to $i$),
the conditional type distribution of $i'$ in the event that $i$
is chosen as the winner.
Formally, a second-order interim rule specifies
$\sinte{i}{i'}{t} \in [0,1]$ for each pair of candidates
$i, i' \in [\NUMC]$, and type $t \in T_{i'}$.
We say that a winner-selection rule implements for a prior if it satisfies the following:
if the type profile $\TP = (\type{1}, \ldots, \type{\NUMC})$
is drawn from the prior distribution
$\PMF=\PMF[1] \cross \cdots \cross \PMF[\NUMC]$,
then $\ProbC{i\in\ALGO(\TP) }{\type{i'} = t} = \sinte{i}{i'}{t}$.

A second-order interim rule is feasible if there is a winner
selection rule implementing it.

§ EXISTENCE OF DICE IMPLEMENTATION FOR MATROIDS

In this section, we prove our first theorem:In this section,
we outline the proof of our first theorem:

Let $(\PMF, \M)$ be a matroid winner selection-environment
with a total of $m$ types,

and let be an interim rule that is feasible within $(\PMF, \M)$.
There exist winner-selecting dice $\D$, each of which has at
most $m+1$ faces, which implement .

The proof consists of two parts.
First, we generalize the result of <cit.>,
which showed the existence of continuous winner-selecting dice for feasible
interim rules for a $k$-uniform matroid with fixed types, to general
matroids and multiple types.
Second, we convert the continuous dice to dice with at most $m+1$
faces each, while keeping the interim probabilities unchanged.

§.§ Continuous Winner-Selecting Dice

Let $\M$ be a matroid, and $\INTE$ a feasible interim rule within the
winner-selection environment $(\PMF, \M)$.
There exist winner-selecting dice $\D$ over $\mathbb{R}$
that implement $\INTE$ in $(\PMF, \M)$.

We assume without loss of generality that the candidates' type sets
are disjoint,
and use $T =\biguplus_{i=1}^{\NUMC} T_i$ to denote the set of all types.
We use t and t as shorthand for [i]t and [i]t,
where $i = \candidate(t)$ is the candidate for whom $t \in T_i$.
Moreover, given a set of types $S \sse T$,
we write $S_i = S \intersect T_i$.
Recall the Border constraints

\begin{equation}
\label{eq:border-matroid}
\sum_{i=1}^n \sum_{t\in S_i}\pmf[i]{t} \interim[i]{t} \le R(S),
\end{equation}

where $R(S)=\Expect[\vc{t}\sim \PMF]{r_{\M}(\vc{t}\cap S)}$ is the
expected rank of types in $S$ which show up,
a submodular function over the type set $T$.
The Border constraints can therefore be interpreted as follows:
An interim rule $\INTE: T \to [0,1]$ is feasible for and $\M$
if and only if $\tilde{\INTE}$ is in the polymatroid given by
$R(S)$, where $\tilde{x}(t) := \pmf{t} \interim{t}$.
Equivalently, is feasible if and only if the submodular
slack function
$\slack(S) = R(S) - \sum_{t \in S} \pmf{t} \interim{t}$
is non-negative everywhere.

When is feasible, we call a set $S \sse T$ tight
for $(f, \INTE, \M)$ if the Border constraint (<ref>) corresponding to $S$ is tight at $\INTE$,
i.e., $\sum_{i=1}^n \sum_{t\in S_i}\pmf{t} \interim{t} = R(S)$.
By definition, $S=\emptyset$ is always tight.
The family of tight sets, being the family of minimizers of the
submodular slack function, forms a lattice:
the intersection and the union of two tight sets is a tight set.

The tightness of a set $S$
means that the expected number of winners from $S$ equals the expected
rank of  types in $S$ which show up. In other words, $S$ is tight if
and only if a maximum independent subset of $\vc{t}\cap S$
is always selected as winners.

By Remark <ref>the preceding remark,
the types in minimal non-empty tight sets need to be treated preferentially,
i.e., assigned higher faces on their dice, compared to types outside them.
Because they play such an important role, we define them as barrier sets.
Formally, we define the set of active types
$T^+= \set{ t \in T: \pmf{t} \interim{t} > 0}$
to be the types who win with positive probability.
Barrier sets are subsets of $T^+$.
If there is at least one non-empty tight set of active types,
we define the barrier sets as the (inclusion-wise) minimal such sets.
Otherwise, we designate the entire set $T^+$ of active types as the
unique barrier set.

To prove Theorem <ref>, we first assume that the matroid $\M$ is non-separable. Separable matroids will be handled in the proof of Theorem <ref> by combining the dice of their non-separable components. Because barrier sets get precedence, we first show how to construct dice for barrier sets with Lemma <ref>. Once we have dice for barrier sets, we can repeatedly “peel off” the tight sets and combine their dice, which is captured in Lemma <ref>. We start with the existence of dice for barrier sets:

Let $\M$ be a non-separable matroid, and
$\INTE > \vc{0}$ a feasible interim rule within the
winner-selection environment $(\PMF, \mathcal{M})$.
Let $S$ be a barrier set for $(\PMF, \INTE, \M)$, and define
$\INTE_S$ to be  $(\interim{t})_{t\in S}$.
There exists a vector of
distributions $\D=(\DIE[t])_{t\in S}$ over $\mathbb{R}$,
such that $\D$ implements $\INTE_S$ in $(\PMF, \M|S)$.

Without loss of generality, assume that the barrier set $S$ contains
types, and number them by $1, 2, \dots, \BT$.

When $|\candidate(S)|=1$ and $S$ is tight, all types in $S$ belong
to the same candidate, so there is no competition
between candidates. Because of the tightness of $S$, we can simply
assign a single-sided die with face value $1$ to each type in $S$. Thus in the
proof, we assume that either there is more than one candidate with a
type in $S$ or that $S$ is not tight.
[Recall that $S$ could be the (possibly non-tight) barrier
set of all active types, if no non-empty set is tight.]
In both cases, this implies that $\interim{t} < 1$ for all $t\in S$.
For if $\interim{t} = 1$, the singleton $\SET{t}$ would
be a proper tight subset of $S$,
which contradicts the assumption that $S$ is a barrier set.

We create [t] from any continuous distribution
[For example, one can use an exponential distribution.]
$D$ with support $[0, \infty)$.
For each type $t$, we assign a parameter $\theta_t > 0$.
Also, we choose a global parameter $\tau$.
To sample from [t],
we draw a primitive roll $v_t\sim D$ and output
$\theta_tv_t - \tau$.

We define $g_t(\tau, \theta_1, \dots, \theta_\BT)$ to be the
interim probability of type $t$ winning in the environment $(\PMF,
\M|S)$ when the winner-selecting dice [t] with parameters
$\theta_t$ and $\tau$ are used for $t\in S$.
Each $g_t$ is continuous in all of its parameters.
Using $\vc{\theta}_S = (\theta_t)_{t\in S}$ for short,
consider the following system of equations with variables $\vc{\theta}_S$:

\begin{align}
\sum_{t\in S} \interim{t} g_t(\tau, \vc{\theta}_S)
&= \sum_{t\in S} \pmf{t} \interim{t}\label{eq:interim-system-sum}\\
g_t(\tau, \vc{\theta}_S)
&= \interim{t}, \quad \mbox{ for all } t\in [\BT]. \label{eq:interim-system}
\end{align}

The objective of the proof is to show that the system of equations
(<ref>) admits a solution.
This solution will directly induce a dice system that implements
$\INTE$ for types in $S$.
Notice that the system is redundant:
Equation (<ref>) is implied by the Equations (<ref>).
Throughout the proof, we use $\pre_i$ to denote the prefix
$(\tau, \theta_{1},\dots, \theta_{i})$ and $\suf_i$ to denote the suffix
of parameters $(\theta_{i}, \theta_{i+1}, \dots, \theta_{n})$. In particular, $\pre_0 = \tau$.
We prove the following inductively for $k=1,\dots, \BT$:

For any
positive suffix $\suf_k > \vc{0}$, there is a prefix $\pre_{k-1}$ so
that $(\pre_{k-1}(\suf_k), \suf_k)$ satisfies the first $k$ equations
in the system

Applying the claim with $k=\BT$, for every positive $\theta_\BT$, there is a
solution that satisfies the first equations.
Because of the redundancy of the system, satisfying the first equations
guarantees that the last equation is also satisfied.

For the base case $k=1$,
consider an arbitrary positive $\suf_1 = \vc{\theta}_S$.
We need to prove the existence of a $\tau$ such that
$\sum_{t\in S} \pmf{t} g_t(\tau, \vc{\theta}_S)
= \sum_{t\in S} \pmf{t} \interim{t}$.
When $\tau = 0$, all types get non-negative die rolls.
Therefore, a maximum independent subset of $\vc{t}\cap S$ is always
Thus, $S$ is tight at $(g_t(0, \vc{\theta}_S))_{t\in S}$, i.e.,
$\sum_{t\in S} \pmf{t} g_t(0, \vc{\theta}_S) = R(S)
\ge \sum_{t\in S} \pmf{t} \interim{t}$.
On the other hand, as $\tau$ increases,
the probability that all die rolls are negative goes to 1,
meaning that in the limit, no agent wins.
Thus, $\lim_{\tau\to \infty} g_t(\tau, \vc{\theta}_S) = 0$.
Furthermore, each $g_t(\tau, \vc{\theta}_S)$
strictly and continuously decreases with $\tau$.
Because $0 < \sum_{t\in S} \pmf{t} \interim{t} \leq R(S)$,
by the Intermediate Value Theorem,
for every  $\vc{\theta}_S$, there is a unique $\tau$ such that
$\sum_{t\in S} \pmf{t} g_t(\tau, \vc{\theta}_S)
= \sum_{t\in S} \pmf{t} \interim{t}$.
We denote this unique $\tau$ by $h_0(\vc{\theta}_S)$;
notice that $h_0(\vc{\theta}_S)$ is a continuous function of $\vc{\theta}_S$.
When $S$ is a tight barrier set, i.e., $R(S) = \sum_t f(t) x(t)$,
the equation is satisfied for $\tau = 0$, so $h_0(\vc{\theta}_S) = 0$.
This establishes the base case $k=1$ of the induction hypothesis.

For the inductive step, fix an arbitrary $k \ge 1$,
and let $\suf_{k+1} > \vc{0}$ be arbitrary.
For any fixed $\theta_k > 0$, by induction hypothesis,
there is a unique $\pre_{k-1} (\theta_k, \suf_{k+1})$ such that
$(\pre_{k-1} (\theta_k, \suf_{k+1}), \theta_k, \suf_{k+1})$
satisfies the first $k$ equations
of (<ref>)–(<ref>).
Lemma <ref>
below shows that there is a unique $\theta_{k} = h_k(\suf_{k+1})$
such that
$(\pre_k (h_k(\suf_{k+1}), \suf_{k+1}), h_k(\suf_{k+1}), \suf_{k+1})$
satisfies the first $k+1$ equations of
The inductive claim now follows by defining
$\pre_{k+1}(\suf_{k+1}) = (\pre_k(h_k(\suf_{k+1}),\suf_{k+1}), h_k(\suf_{k+1})).$

Fix any feasible .
For every $k$ and suffix $\suf_{k+1}$,
there is a unique $\theta_k\in (0, \infty)$ such that
$g_k(\pre_{k-1}(\theta_k, \suf_{k+1}), \theta_k, \suf_{k+1}) = \interim{k}$.

The proof of Lemma <ref> is based on large part on the
following monotonicity properties:

Assume that $S$ contains types of more than one candidate or is not
For any $t \ge k$, consider
$g_t(\pre_{k-1}(\theta_k, \suf_{k+1}), \theta_k, \suf_{k+1})$
as a function of $\theta_i$, for $i \ge k$.
The function $g_t$ satisfies the following properties:

* It is weakly decreasing in $\theta_{i}$,
for all $i \ne t, i \ge k$.

* It is strictly increasing in $\theta_t$.

If $\candidate(t) \ne \candidate(i)$, then $g_t(\vc{\theta}_S)$ is
strictly decreasing in $\theta_{i}$.
If in addition $i \geq k$ and $t \geq k$, then
$g_t(\pre_{k-1}(\suf_{k}), \suf_{k})$
is also strictly decreasing in $\theta_{i}$.

For notational convenience, we define the shorthand
$g_t(\inductionpoint) :=
g_t(\pre_{k-1}(\theta_k, \suf_{k+1}), \theta_k, \suf_{k+1})$.
Furthermore, for fixed $\suf_{k+1}$ (which will be clear from the context),
we define
$h_t(\theta_k)$ to be the t
component of $\pre_{k-1}(\theta_k, \suf_{k+1})_t$, for any $t < k$.

Lemma <ref>
As we did in the proof of Lemma <ref> for the base
case of the induction claim,
we will examine the limits of $g_k(\inductionpoint)$ as
$\theta_k \to 0$ and $\theta_k \to \infty$.
By doing so, we will establish that $\interim{k}$
lies between the two limits.
Then, using the continuity and strict monotonicity
(by Lemma <ref>) of $g_k(\inductionpoint)$,
the Intermediate Value Theorem implies that there is a unique $\theta_k$
satisfying $g_k(\inductionpoint) = \interim{k}$.

* To compute $\lim_{\theta_k\to \infty} g_k(\inductionpoint)$,
consider the set of types
$A = \Set{t < k}{\lim_{\theta_k\to \infty} h_t(\theta_k)=\infty}$.
As $\theta_k \to \infty$,
with probability approaching $1$,
$A\cup\SET{k}$ will dominate all other types.
We distinguish two cases, based on whether
$\lim_{\theta_k \to \infty} h_0(\vc{\theta}_S)$ is finite or not.

* If $\lim_{\theta_k\to \infty}h_0(\theta_{k}) \neq \infty$,
the parameter $\tau$ will be finite in the limit. Therefore,
a maximum independent subset of $A \cup \SET{k}$ will be selected as
winners,  implying that $A \cup \SET{k}$ is tight in the limit.
Because $\pre_{k-1}(\theta_k, \suf_{k+1})$ ensures that the first
$k$ equations of
(<ref>)–(<ref>) are satisfied,
each type $t \in A$ wins with probability $\pmf{t} \interim{t}$.
Because $A \cup \SET{k}$ is tight,
$\lim_{\theta_k \to \infty} \pmf{k} g_k(\inductionpoint)
= R (A\cup \SET{k}) - \sum_{t\in A} \pmf{t} \interim{t}$.
From the Border constraint for the set $A\cup \SET{k}$,
$\pmf{k} \interim{k} + \sum_{t\in A} \pmf{t} \interim{t} < R(A\cup\SET{k})$;
otherwise $A \cup \SET{k}\subsetneq S$ would be a tight set,
contradicting that $S$ is a barrier set.
Rearranging, we have shown that
$\lim_{\theta_k \to \infty} \pmf{k} g_k(\inductionpoint) > \pmf{k} \interim{k}$.

* If $\lim_{\theta_k \to \infty} h_0(\theta_{k}) = \infty$,
then all types $t > k$ will get negative die rolls with probability
approaching 1, so $\lim_{\theta_k\to\infty} g_t(\inductionpoint) = 0$
for all types $t > k$.
$\lim_{\theta_k\to\infty} \pmf{k} g_k(\inductionpoint)
+ \sum_{t<k} \pmf{t} \interim{t} = \sum_{t\in S} \pmf{t} \interim{t}$,
$\lim_{\theta_k\to\infty}\pmf{k} g_k(\inductionpoint)
= \sum_{t\ge k} \pmf{t} \interim{t} > \pmf{k} \interim{k}$,
because all types in a barrier set are active by definition.

* To compute $\lim_{\theta_k \to 0}g_k(\inductionpoint)$, define
the type set
$A = \Set{1 \le t < k}{\lim_{\theta_k\to 0} h_t(\theta_k) > 0}
\cup \SET{k+1, \dots, \BT}$.
As $\theta_k\to 0$, with probability approaching $1$,
$A$ will dominate all other types because for
$t \notin A$, $h_t(\theta_k)$ goes to $0$.
Again, we distinguish two cases,
based on whether $\lim_{\theta_k \to \infty} h_0(\theta_k) = 0$ or not.

* If $\lim_{\theta_k \to \infty} h_0(\theta_k) = 0$,
then in the limit, a maximum independent subset of $A$ must always be
chosen as winners, so $A$ approaches tightness.
Again, $\pre_{k-1}(\theta_k, \suf_{k+1})$ ensures that
$g_{t}(\inductionpoint) = \interim{t}$ for $t < k$, so we have
$\lim_{\theta_k \to 0}\sum_{t > k} \pmf{t} g_t(\inductionpoint)
= R(A) - \sum_{t\in A, t < k} \pmf{t} \interim{t}$.
Combined with
$\sum_{t\ge k} \pmf{t} g_t(\inductionpoint)
= \sum_{t\ge k} \pmf{t} \interim{t}$,
which is also ensured by $\pre_{k-1}(\theta_k, \suf_k)$,
we obtain that

\[\lim_{\theta_k\to 0} \pmf{k} g_k(\inductionpoint)
= \sum_{t\ge k} \pmf{t} \interim{t} -
\left( R(A) - \sum_{t\in A, t<k} \pmf{t} \interim{t} \right). \]

Rearranging the Border constraint corresponding to
$A\subseteq S \setminus \SET{k}$ gives us that
$0 > \sum_{t > k} \pmf{t} \interim{t} -
\left( R(A)-\sum_{t\in A, t < k} \pmf{t} \interim{t} \right)$
because $A \subsetneq S$ is not tight.
Adding $\pmf{k} \interim{k}$ on both sides,
we get $\pmf{k} \interim{k} > \sum_{t \ge k} \pmf{t} \interim{t} -
\left( R(A) - \sum_{t\in A, t < k}\pmf{t} \interim{t}\right)$.
Finally, canceling out $\pmf{k}$, we obtain that
$\interim{k} > \lim_{\theta_k \to 0} g_k(\inductionpoint)$.

* If $\lim_{\theta_k\to 0} h_0(\theta_k) > 0$, as $\theta_k \to 0$,
type $k$ will get a negative roll with probability
approaching $1$,
so $\lim_{\theta_k\to 0} g_k(\inductionpoint) = 0 < \interim{k}$.

In summary, we have shown that
$\lim_{\theta_k \to 0}g_k(\inductionpoint) < \interim{k}
< \lim_{\theta_k\to \infty} g_k(\inductionpoint)$.
Because  $g_k(\suf_k)$ is continuous and monotone in $\theta_k$,
by the Intermediate Value Theorem,
there exists a unique $\theta_k$ such that $g_k(\suf_k) = \interim{k}$.

In the proofs for Lemmas <ref> and
we will often want to analyze the effect of
keeping $\theta_{i}$ for all $i \ne t$ unchanged,
while changing $\theta_t$ to $\theta'_t$.
Thereto, we always consider the following coupling of dice rolls in
the two scenarios, which we call primitive-roll coupling for $t$:
all dice will obtain the same primitive rolls $\vc{v}$ under the two
scenarios, but scale them differently.
More precisely, we consider the rolls
$(\theta_i v_i - \tau)_{i\in S}$ and $(\theta'_i v_i - \tau')_{i \in S}$,
for any given primitive rolls $\vc{v}$,
where $\theta'_i = \theta_i$ for $i \ne t, i \ge k$.
Recall that all $\theta_i$ for $i < k$ are functions of $\suf_k$.

Part 1 of Lemma <ref>
To show that $g_t(\theta_k, \suf_{k+1})$ is weakly decreasing
in $\theta_i$ for all $i \ge k, i \ne t$,
we again use induction on $k$.
The induction hypothesis is the following:

* Each entry of $\pre_{k}(\suf_{k+1})$ is weakly increasing
in $\theta_i$ for $i > k$.

* $g_t(\suf_{k+1})$ is weakly decreasing in $\theta_i$
for $i \ne t, i > k$.

We begin with the base case $k=0$.
The first part of the base case — that $\pre_0(\vc{\theta}_S)$ is
weakly increasing in $\theta_i$ — has been shown in the proof of
Lemma <ref>.
To prove the second part of the base case,
we use primitive-roll coupling for $i$ with $\theta_i< \theta'_{i}$.
For every scenario with primitive rolls $\vc{v}$ in which $t$ is not
a winner with $\vc{\theta}_S$,
we show that $t$ cannot become a winner with $\vc{\theta'}_S$.

* Increasing $\theta_i$ to $\theta'_i$ can only (weakly)
increase the threshold $\tau = \pre_0(\vc{\theta}_S)$,
by the first part of the base case.

* Let $A$ be the set of types with rolls higher than the roll
of type $t$ when the rolls are derived from $\vc{v}$ using $\vc{\theta}_S$.
Since $t$ is not winning, we have

\[ 0 \; = \; r_\M(A\cup\SET{t}) - r_\M(A)
\; \ge \; r_\M(A\cup\SET{t, i}) - r_M(A\cup\SET{i}). \]

The inequality is due to the submodularity of the matroid rank
function, and shows formally that (potentially) adding $i$ to the set
of types with higher rolls than $t$ cannot help $t$ become a winner.

For the induction step, consider some $k \geq 1$ and fix a $\suf_{k+1}$.
By the induction hypothesis,
each entry of $\pre_{k-1}(\theta_k, \suf_{k+1})$ is weakly increasing
in $\theta_i$ for $i \ge k$,
and $g_t(\theta_k, \suf_{k+1})$ is weakly decreasing in $\theta_i$
for $i \ne t, i \ge k$.

* We first show that each entry of $\pre_k(\suf_{k+1})$
is weakly increasing in $\theta_i$ for $i > k$.
The key is component $k$ of $\pre_k(\suf_{k+1})$.
By the second part of the induction hypothesis, applied with $t=k$,
$g_k(\pre_{k-1}(\theta_k,\suf_{k+1}), \theta_k, \suf_{k+1})$
is weakly decreasing in $\theta_i$.
Since $g_k(\pre_{k-1}(\theta_k,\suf_{k+1}), \theta_k, \suf_{k+1})$
is defined as the winning probability of $k$ with the given
parameters, when $\theta_i$ is raised to $\theta'_i > \theta_i$,
in order to keep
$g_k(\pre_{k-1}(\theta'_k,\suf'_{k+1}), \theta'_k, \suf'_{k+1})
= \interim{k} =
g_k(\pre_{k-1}(\theta_k,\suf_{k+1}), \theta_k, \suf_{k+1})$,
we require $\theta'_k \geq \theta_k$.
By applying the induction hypothesis twice, once for $\theta_i$ and
once for $\theta_k$,
all entries of $\pre_{k-1}(\theta_k, \suf_{k+1})$ weakly increase.
Therefore, all entries of $\pre_{k}(\suf_{k+1})$ are
weakly increasing in all $\theta_i$ for $i > k$.

* To prove the second part of the inductive step,
recall that
$g_t(\suf_{k+1}) = g_t(\pre_k(\suf_{k+1}), \suf_{k+1})
= g_t(h_{k}(\suf_{k+1}), \suf_{k+1})$.
For $t\le k$, $g_t(\suf_{k+1})=\interim{t}$ is a constant,
and in particular weakly decreasing in $\theta_i$.
Consider some $t > k, i > k, t \ne i$.
First, $h_k(\suf_{k+1})$ is weakly increasing in $\theta_i$
by the first part of the induction hypothesis.
By the second part of the induction hypothesis,
$g_t(\theta_k, \suf_{k+1})$ is weakly decreasing in all of
its variables except $\theta_t$,
so substituting $\theta_k = h_k(\suf_{k+1})$ shows that
$g_t(h_k(\suf_{k+1}),\suf_{k+1})$ is weakly decreasing in $\theta_i$.

Part 2 of Lemma <ref>
Recall that $t \geq k$.
To show that $g_t(\suf_k)$ is strictly increasing in $\theta_t$,
we will show that at least one type $i \ge k$ has $g_{i}(\suf_k)$
strictly decreasing in $\theta_t$.
By Part 1 of the lemma, each $g_{i}(\suf_k)$ for $i \ge k $ is weakly
decreasing in $\theta_{t}$.
By definition, $\pre_{k-1}(\suf_{k})$ ensures that the first $k$
equations of the system
(<ref>)-(<ref>) are satisfied;
this implies that
$\sum_{j\ge k} \pmf{j} g_j(\suf_k) = \sum_{j\ge k} \pmf{j} \interim{j}$.
Thus, if at least one of the $g_{i}(\suf_k)$ is strictly decreasing
in $\theta_t$,
to keep the summation $\sum_{j\ge k}\pmf{j} g_j(\suf_k)$ unchanged,
$g_{t}(\suf_k)$ must increase strictly in $\theta_t$.
We consider two possible cases for $S$,
as permitted by the assumption of the lemma:

* $S$ is not tight.
In this case, we first show that $h_0(\vc{\theta}_S)$ is a strictly
increasing function of $\theta_t$.
Consider the primitive-roll coupling for $\theta'_t > \theta_t$.
For any primitive rolls $\vc{v}$, the number of winners will not
decrease when $\theta_t$ increases to $\theta'_t$.
Thus, we can bound the summation
$\sum_{i\in S} \pmf{i} g_i(\tau, \vc{\theta}_S)
\le \sum_{i\in S} \pmf{i} g_i(\tau, \vc{\theta'}_S)$.
Because $S$ is not tight, with non-zero probability,
$\vc{v}$ is such that $v_i\theta_i - \tau < 0$ for all $i$.
And because $\vc{v}$ is drawn from a continuous distribution,
with positive probability, $v_t \theta'_t - \tau > 0$ as well.
In that case, $t$ is the only candidate with a positive die roll.
This implies that
$\sum_{i\in S} \pmf{i} g_i(\tau, \vc{\theta}_S)
< \sum_{i\in S} \pmf{i} g_i(\tau, \vc{\theta'}_S)$.
Because $h_0(\vc{\theta'}_S)$  is defined as the unique $\tau$
satisfying the equation
$\sum_{i\in S} \pmf{i} g_i(\tau, \vc{\theta'}_S)
= \sum_{i\in S} \pmf{i} \interim{i}$,
we obtain that $h_0(\vc{\theta'}_S) > h_0(\vc{\theta}_S)$.

Now consider any primitive rolls $\vc{v}$ under which a type $i\ne
t$ wins, and $\vc{v}$ is such that
$v_{i}\theta_{i} - h_0(\vc{\theta}_S) > 0$ but
$v_{i}\theta_{i} - h_0(\vc{\theta'}_S) < 0$.
Such rolls $\vc{v}$ must occur with positive
probability, because all the dice are fully supported over
$(0, \infty)$.
In that case, $i$ is no longer a winning type under $\vc{\theta'}_S$.
Thus $g_{i}(\vc{\theta}_S)$  is strictly decreasing in $\theta_t$.

* There is more than one candidate, i.e.,
there is a type $i$ with $\candidate(i) \ne \candidate(t)$.

* If there is such a type $i \ge k$
with $\candidate(i) \ne \candidate(t)$,
then $g_{i}(\suf_k)$ is strictly decreasing in $\theta_t$
by the second part of Lemma <ref>.

* Otherwise, all types $t' \ge k$ have
$\candidate(t') = \candidate(t)$.
Define $\suf'_{k} = \suf_{k}$ for all entries except type $t$,
where it equals $\theta'_t > \theta_t$.
Consider a type $i < k$ with $\candidate(i) \ne \candidate(t)$.

By definition of $\pre_{k-1}(\cdot)$, we get that
$g_{i}(\suf'_k) = \interim{i} = g_{i}(\suf_k)$.
And by the first part of Lemma <ref>,
$g_{i}(\pre_{k-1}(\suf_k), \suf_k) > g_{i}(\pre_{k-1}(\suf_k), \suf'_k)$.
So $i$ wins with strictly higher probability under
the parameters $(\pre_{k-1}(\suf'_k), \suf'_k)$ than under
the parameters $(\pre_{k-1}(\suf_k), \suf'_k)$.
As shown in Part 1 of Lemma <ref>,
$g_i(\theta_S)$ is weakly decreasing in all of its variable except $\theta_i$.

Thus, the only way that the winning probability of agent $i$ can
increase is for the i component of $\pre_{k-1}(\suf'_k)$
to be strictly greater than the i component of

Finally, consider some type $t' \geq k, t' \ne t$ with
$\candidate(t') = \candidate(t) \ne \candidate(i)$.
Because all components of $\pre_{k-1}(\cdot_k)$ weakly increase
going from $\suf_k$ to $\suf'_k$, and the i component
strictly increases, we get that $g_{t'}(\suf_k) < g_{t'}(\suf'_k)$.
Thus, we have shown that there is a $t' \ne t$ such that
$g_{t'}(\suf_k)$ is strictly decreasing in $\theta_t$.

Lemma <ref>
We prove both statements using primitive-roll coupling.
For the second part of the lemma, notice that when
$\theta_i$ is increased to $\theta'_i$ for $i \geq k$,
all components of $\pre_{k-1}(\suf_k)$ weakly increase.
Thus, all components of $(\pre_{k-1}(\suf_k), \suf_k)$
are weakly larger than those of $(\pre_{k-1}(\suf'_k), \suf'_k)$,
and $\theta'_i > \theta_i$, while $\theta'_t = \theta_t$.
Thus, we can apply primitive-roll coupling in both cases.

Since the matroid is non-separable,
there is a circuit $C$ that contains
$\candidate(t)$ and $\candidate(i)$.
Under the parameter vector $\vc{\theta}_S$,
with non-zero probability (over primitive rolls $\vc{v}$),
the candidates in $C$ get the highest rolls,
$\candidate(t)$ (barely) wins with the second-lowest roll,
and $\candidate(i)$ gets the lowest roll among all candidates in $C$
and does not win.
When $\theta_i$ increases to $\theta'_{i}$,
with non-zero probability, the scaled roll for type $t$ becomes the
lowest so that $t$ ceases to be a winner.
Combining this with Part 1 of Lemma <ref>
(which states that $g_t(\vc{\theta}_S)$ is weakly decreasing in $\theta_i$),
we have that $g_t(\vc{\theta}_S)$ is strictly decreasing in $\theta_{i}$.

The proof is quite technically involved, and due to space
constraints, it is entirely deferred to the full version.
The high-level idea is to base the dice upon
any full-support continuous distribution for the dice.
This distribution is scaled by different parameters $\theta_i$ for
different types $i$, and shifted by a constant $\tau$.
Matching the prescribed interim winning probabilities i
imposes a system of non-linear equations on the $\theta_i$.
We establish that the winning probabilities of different types
satisfy certain key monotonicity properties in the parameters $\theta_i$;
these monotonicity properties are proved using the fact that the
feasible sets form a matroid.
Then, we apply the Intermediate Value Theorem inductively for all
types $i$ to non-constructively prove the existence of the desired $\theta_i$.

To generalize Lemma <ref> to arbitrary sets of
types, we will need a construction that allows us to “scale”
the faces of some dice such that they will always be above/below the faces
of another set of newly introduced dice;
such a construction will allow us to give dice for types in barrier
sets higher faces than other dice.
For the types of full-support distributions over $[0, \infty)$ we have
been using so far, this would be impossible.
There is a simple mapping that guarantees our desired properties:
we map faces from $(0,\infty)$ to the set $(1, 2)$
by mapping all positive $s \mapsto 2 - \frac{1}{1+s}$,
and mapping all negative $s$ to $-1$.
Notice that the new dice implement the same interim rule as the old ones:
in matroid environments, the set maximizing the sum of die rolls is
determined by the greedy algorithm, and hence, only the relative order
between die faces matters.

With the help of this mapping, we prove the following lemma,
similar to Lemma <ref>.
The proof is again only given in the full version.

Let $\INTE > \vc{0}$ be a feasible interim rule within a
winner-selection environment $(\PMF, \M)$,
where $\M$ is a non-separable matroid.
Fix a tight set $S$, and let $\hat{S}$ be a minimal tight
set that includes $S$ as a proper subset, if such a set exists;
otherwise let $\hat{S} = T$.
Given dice $\D =(D_t)_{t\in S}$ that implement $\INTE_S$
in $(\PMF,\M|S)$,
there are dice $\D' = (D'_t)_{t \in \hat{S}}$
which implement
$\INTE_{\hat{S}}$ in $(\PMF,\M|\hat{S})$.

First, we define the dice $D'_t$ for types $t \in S$:
they are obtained by applying the transformation described
previously to the corresponding dice $D_t$.
Thus, the range of positive faces is $(1,2)$ for these $D'_t$.

For types $t \in \hat{S} \setminus S$,
we construct new dice $D'_t$ in a similar way to the proof of
Lemma <ref>.
The construction is essentially identical, but all positive die
faces $s$ are mapped to $1-\frac{1}{1+s}$.
Notice that this mapping ensures that all die faces are strictly
less than 1, and hence, these types $t$ will always lose to types
$t' \in S$.
The main other change in the proof is to change the definition of
$g_t(\tau, \vc{\theta}_{\hat{S} \setminus S})$:
it is now the interim winning probability of the type $t\in S'$ when
winners are selected with the die rolls $\D'$,
assuming all types outside $\hat{S}$ always get negative die rolls.

None of the monotonicity properties of the functions $g_t(\cdot)$
will be affected under this new definition;
thus, the same proof will go through,
with only a slight change in the limits of $\pmf{k}g_k(\theta_k, \suf_{k+1})$:

\begin{align*}
\lim_{\theta_k \to \infty} \pmf{k} g_k(\theta_k, \suf_{k+1})
& \in \{ \sum_{t \ge k} \pmf{t} \interim{t},
R(A\cup \SET{k})-\sum_{t\in A} \pmf{t} \interim{t}\}\\
\lim_{\theta_k\to 0} \pmf{k} g_k(\theta_k, \suf_{k+1})
& \in \{ 0, \sum_{t \ge k} \pmf{t} \interim{t} -
\left(R(A) - \sum_{t\in A \setminus B} \pmf{t} \interim{t} \right)
\}. \QED
\end{align*}

Theorem <ref>
First consider the case when $\M$ is non-separable.
Let $T$ be the type set with $m$ types.
We define the dice system as follows:
First, for all types $t$ with $\interim{t} = 1$,
assign them a point distribution (single-sided die) at $2$, so they
always win.
Next, for all types $t$ with $\interim{t} = 0$,
assign them a point distribution at $-1$, so they never win.
Next, we create dice for barrier sets $S$ according to
Lemma <ref>.
Then, starting from the barrier sets,
we repeatedly apply Lemma <ref> to construct dice
for larger tight sets $\hat{S} \supsetneq S$ (or all of $T$)
implementing $\INTE_{\hat{S}}$.

If $\M$ is separable, let $\M_1, \dots, \M_k$ be the components of

Using the construction from the previous paragraph for each $\M_j$,
let $\D_j$ be the dice set constructed for $\M_j$.
Since there is no circuit containing two candidates from
different components,
the winner set of one component has no effect on the winner set of any
other component.
Thus, the union $\bigcup_{j=1}^k \D_j$ of dice implements the desired
interim rule.

§.§ Winner-Selecting Dice with polynomially many faces

The proof is based on the following generalization of the fundamental
theorem of linear programming to uncountable dimensions.

Let $f_1, \dots, f_m : \mathbb{X} \to \mathbb{R}$ be Borel measurable
on a measurable space $\mathbb{X}$,
and let $\mu$ be a probability measure on $\mathbb{X}$ such that $f_i$
is integrable with respect to $\mu$ for each $i=1,\dots, m$.
Then, there exists a probability measure $\varphi$ on $\mathbb{X}$
with finite support, such that

\[
\int_{\mathbb{X}} f_id\varphi = \int_{\mathbb{X}} f_id\mu
\]

\int_{\mathbb{X}} f_id\varphi = \int_{\mathbb{X}} f_id\mu
for all $i$.
Moreover, there is such a $\varphi$ whose support consists of at most
$m+1$ points.

Theorem <ref>
Theorem <ref> establishes that there is a vector of probability
measures $\D=(D_t)_{t\in T}$ over $V = (1, 2) \cup \SET{-1}$,
satisfying the following for all $i$ and $t_i \in T_i$:

\begin{equation}\label{eq:integral}
\int_{V} \sum_{\vc{t}\in T_{-i}}\prod_{j\ne i}
\pmf{t_j} \idotsint_{V^{n-1}} w_{t_i}(s_1, \dots, s_n)
dD_{t_1}(s_1)\cdots  dD_{t_n}(s_n)dD_{t_i}(s_i)
= \interim{t_i}.
\end{equation}

where $w_{t_i}(s_1, \dots, s_n)$ equals $1$ if type $t_i$ is a winning type
with dice rolls $s_1, \dots, s_n$, and equals $0$ otherwise.

For a fixed type $t^\ast\in T_i$ and an equation corresponding to $(j, t'_j)$,
we can change the order of integration to make $dD_{t^\ast}$
the outermost integral,
and isolate the terms that do not involve $dD_{t^\ast}$.
Specifically, we define

\[
q_{j, t'_j}(s_i) =
\sum_{\substack{\vc{t}\in T\\ t_j=t'_j , t_i=t^\ast}}\prod_{k\ne j}
\pmf{t_k} \idotsint_{V^{n-1}} w_{t_j}(s_1, \dots, s_n)
dD_{t_1}(s_1)\cdots  dD_{t_n}(s_n)
\]

to be the inner integral over distributions of $t\ne t^\ast$,
as a function of $s_i$, and

\[
c_{j, t'_j} =
\begin{cases}
0, \text{ for } t'_j=t^\ast\\
\begin{aligned}
\int_{V} \sum_{\vc{t}\in T_{-j}, t_i\ne t^\ast} \prod_{k\ne j}
\pmf{t_k} \idotsint_{V^{n-1}} &w_{t_j}(s_1, \dots, s_n)\\
&dD_{t_1}(s_1)\cdots  dD_{t_n}(s_n)dD_{t_j}(s_j), \text{ for }  t'_j\ne t^\ast
\end{aligned}
\end{cases}
\]

as the component of the integral that does not have $dD_{t^*}$ involved.
Thus, Equation (<ref>) can be rewritten as

\[
\int_{V} q_{j, t'_j}(s_i) d D_{t^\ast}(s_i) + c_{j, t'_j}
= \interim{t'_j}.
\]

\int_{V} q_{j, t'_j}(s_i) d D_{t^\ast}(s_i) + c_{j, t'_j}
= \interim{t'_j}.
By Theorem <ref>,
$D_{t^\ast}$ can be changed to a measure $D'_{t^\ast}$ with support of
size $m+1$, such that for all $j$ and $t_j \in T_j$,

\[
\int_V q_{j, t_j} (s_i) d D_{t^\ast}(s_i)
= \int_V q_{j, t_j}(s_i)d D'_{t^\ast}(s_i).
\]

\int_V q_{j, t_j} (s_i) d D_{t^\ast}(s_i)
= \int_V q_{j, t_j}(s_i)d D'_{t^\ast}(s_i).
In other words, we can replace $D_{t^*}$ with $D'_{t^*}$,
which has at most $m+1$ faces.
Applying the same procedure to each type $t^*$ in turn,
all dice can be replaced by dice with at most $m+1$ faces.

§ EFFICIENT CONSTRUCTION OF DICE FOR
SINGLE-WINNER ENVIRONMENTS

In the preceding section, we proved the existence of winner-selecting
dice by a “construction.”
However, the construction involves repeated appeals to the
Intermediate Value Theorem, and is thus inherently
It is certainly not clear how to implement it efficiently.
In this section, we show that when the matroid $\M$ is $1$-uniform,
i.e., at most one winner can be selected,
winner-selecting dice can be computed efficiently.
We prove the following.

Consider a winner-selection environment with candidates,
where each candidate $i$'s type is drawn independently from a prior
[i] supported on $T_i$, and at most one winner can be selected.
If is a feasible interim rule for
$\PMF = \PMF[1] \times \cdots\times \PMF[n]$,
an explicit representation of the associated dice can be
computed in time polynomial in and $\NUMT = \sum_i |T_i|$.

We use the same notation t and t as in
Section <ref>.
In the single-winner setting, the function
$R(S) = \Expect[\vc{t}\sim \PMF]{r_\M(\vc{t}\cap S)}$
can be treated as a natural extension of to subsets of $T$:
given  $S \sse T$, we let
$R(S) = \pmf{S} = 1- \prod_{i=1}^{\NUMC} (1- \sum_{t \in S_i} \pmf{t})$,
which is the probability that at least one type in $S$ shows up.
Border's constraints can then be written as follows:

\sum_{t \in S} \pmf{t} \interim{t}
\; \leq \; \pmf{S} \mbox{ for all } S \subseteq T.

The slack function becomes
$\slack_{f,\INTE}(S) = \pmf{S} - \sum_{t \in S} \pmf{t} \interim{t}$
and is nonnegative everywhere when $\INTE$ is feasible.

Tight sets and barrier sets are defined as the special case of the
definition for general matroids in  Section <ref>.
The algorithm , given as Algorithm <ref>,
simply implements the definition of barrier sets as minimal non-empty
tight sets, and therefore correctly computes a barrier set.

$T^+ \gets \set{t \in T: f(t) \interim{t} > 0}$.
Define $g(S) = f(S) - \sum_{t \in S} f(t) \interim{t}$ for $S \sse T^+$.
$\min\set{g(S) : \emptyset \subsetneq S \subseteq T^+} \neq 0$

$T^* \gets T^+$.
while there is a type $t \in T^*$ such that $\min\set{g(S): \emptyset \subsetneq S \subseteq T^* \sm \set{t}} = 0$

do $T^* \gets T^* \sm \set{t}$.
$\FindBarrierSet (f,\INTE)$

The following lemma characterizes the key useful structure of barrier sets for the single-winner setting.

Let $\PMF$ and be such that is feasible for $f$.
If there are multiple barrier sets for $(f,\INTE)$,
then there is a candidate $i^*$ such that
each barrier set is a singleton $\set{t}$ with $t \in T_{i^*}$.

In other words, either there is a unique barrier set, or all
barrier sets are singletons of types from a single candidate.

Let $A, B$ be any two barrier sets.
Because $A$ and $B$ are both tight,
the lattice property of tight sets implies that $A \cap B = \emptyset$.

We first show that there is a candidate $i^*$
with $A \subseteq T_{i^*}$ and $B \subseteq T_{i^*}$.
Suppose not for contradiction; then, there exist $i \neq j$
and types $t_i \in A \cap T_i$ and $t_j \in B \cap T_j$.
With non-zero probability, the types $t_i$ and $t_j$ show up at the
same time.
However, according to the definition of a tight set,
when a type in $A$ shows up,
the winner must be a candidate with type in $A$,
and the same must hold for $B$.
Then, the winner's type would have to be in $A \intersect B$ with
non-zero probability.
This contradicts the disjointness of $A$ and $B$.

It remains to show that all barrier sets are singletons.
Since $A$ is tight and all types in $A$ belong to the same candidate,
$\sum_{t \in A} f(t) \interim{t} = f(A) = \sum_{t \in A} f(t)$.
Hence, $\interim{t} = 1$ for all $t \in A$,
and because barrier sets are minimally tight, $A$ must be a singleton.

§.§ Description of the Algorithm

Given a prior $f$ and a feasible interim rule ,
the recursive procedure ,
shown in Algorithm <ref>,
returns a family of dice implementing for $f$.
It operates as follows.
There are two simple base cases:
when no candidate ever wins,
and when a single type of a single candidate always wins.
In the recursive case, the algorithm carefully selects a type
$t^*$ and awards its die the highest-valued face $M'$.
It assigns this new face a probability as large as possible,
subject to still permitting implementation of .
We choose $t^*$ as a member of a barrier set; this is important in
order to guarantee that the algorithm makes significant progress.

The subroutine , shown as Algorithm <ref>,
essentially conditions both $f$ and on the face $M'$ not
Specifically, computes the conditional type distribution $f'$,
and an interim rule , such that if there were a dice
implementation of for $f'$,
then adding $M'$ to the die of $t^*$ would yield a set of dice
implementing for $f$.

PDFs $f_1, \ldots, f_{\NUMC}$ supported on disjoint type sets $T_1,\ldots,T_{\NUMC}$.
Interim rule feasible for $f$.
Vector of dice $(\DIE[t])_{ t \in \biguplus_{i=1}^{\NUMC} T_i}$.
Let $T= \biguplus_i T_i$.
Let $T^+_i = \set{t \in T_i : f_i(t) \interim[i]{t} > 0}$,
and let $T^+ = \biguplus_{i=1}^{\NUMC} T^+_i$.
for all types $t \in T$, let [t] be a single-sided die with a $-1$ face.

there is a type $t^* \in T^+$ with $f(t^*) \interim{t^*} = 1$

Let [t^*] be a single-sided die with a $+1$ face.
for all other types $t \in T \sm \set{t^*}$,
let [t] be a single-sided die with a $-1$ face.

Let $T^* = \FindBarrierSet(f,\INTE)$.
Let $t^* \in T^*$ be a type chosen arbitrarily.
Let $(f',\INTEP)=\Decrement(f, \INTE, t^*, q^*)$,
for the largest value of $q^* \in [0, f(t^*) \interim{t^*}]$
such that is feasible for $f'$.
*[r]Note that $f(t^*) \interim{t^*} < 1$.

Let $(\DIEP[t])_{ t \in T} \gets \ConstructDice(f', \INTEP)$.
Let $M$ be the maximum possible face of any die [t], and $M' := \max(M,0)+1$.
Let $\DIE[t] = \DIEP[t]$ for all types $t \neq t^*$.
Let [t^*] be the die which rolls $M'$ with probability $\frac{q^*}{f(t^*)}$,
and [t^*] with probability $1-\frac{q^*}{f(t^*)}$.
$(\DIE[t])_{t \in T}$.

*[l]$q \geq 0$ is the probability allocated to the highest face.
Because it is a contribution to the unconditional winning
probability $f(t^*) \interim{t^*}$ of type $t^*$,
and we separated out the case that a single type has unconditional
winning probability 1,
$q$ satisfies $q \leq f(t^*) \interim{t^*} < 1$.
if $q=f(t^*)$, then
let $f'(t^*) \gets 0$
and $\interimp{t^*} \gets 0$
let $f'(t^*) \gets \frac{f(t^*) - q}{1-q}$
and $\interimp{t^*} \gets \frac{f(t^*) \interim{t^*} - q}{f(t^*) - q}$.
Let $i^*$ be such that $t^* \in T_{i^*}$.
for all $t \in T_{i^*}, t \ne t^*$,
let $f'(t) \gets\frac{f(t)}{1-q}$ and $\interimp{t} \gets \interim{t}$.
for all $t \in T \sm T_{i^*}$,
let $f'(t) \gets f(t)$ and $\interimp{t} \gets\frac{\interim{t}}{1-q}$.
$\Decrement (f, \INTE, t^*, q)$

We now provide a formal analysis of our algorithm.
Theorem <ref> follows from
Lemmas <ref>–<ref>.

If terminates, it outputs dice implementing
for $f$.

terminates after at most $\NUMT^2$ recursive calls.
(Recall that $\NUMT = \sum_i |T_i|$.)

Excluding the recursive call, each invocation of can
be implemented in time polynomial in and .

§.§ Proof of Lemma <ref> (Correctness)

We prove the lemma by induction over the algorithm's calls.
Correctness is obvious for the two base cases:
when $T^+ = \emptyset$ (no type should win),
and when there exists a type $t^*$ with $f(t^*) \interim{t^*}=1$
($t^*$ always shows up and should always win).
For the inductive step, suppose that the recursive call in
step <ref> returns dice
$\DIESETP = (\DIEP[t])_{ t \in T}$, correctly implementing for $f'$,
and let $\DIESET = (\DIE[t])_{ t \in T}$ be the new dice defined in
steps <ref> and <ref>.

We analyze the interim winning probability of each type when using the
dice-based winner selection rule given by .
For each type $t$, let $\bar{v}_t \sim \DIE[t]$ be a roll of the die for
type $t$, and for each $i$, let $t_i \sim f_i$ be a draw of a type;
all $\bar{v}_t$ and $t_i$ are mutually independent.
In other words, we may assume that the die of every type is
rolled (including types that do not show up),
then the type profile is drawn independently.
The winning type is then the type $t_i$ with largest positive
if all $\bar{v}_{t_i}$ are negative, then no type wins.

Let $t^* \in T_{i^*}$ be as defined in step <ref>.
Let $\E$ be the event that $i^*$ has type $t^*$ and that $\bar{v}_{t^*} = M'$,
and let $\bar{\E}$ be its complement.
By independence of the random choices, the probability of $\E$ is
$f(t^*) \cdot \frac{q^*}{f(t^*)} = q^*$.
Type $t^*$ always wins under the event $\E$.
Conditioned on $\bar{\E}$, each $\bar{v}_t$ (including $\bar{v}_{t^*}$)
is distributed as a draw from [t],
the type vector is distributed as a draw from
$f'_1 \cross \cdots \cross f'_{\NUMC}$,
and the $\bar{v}_t$'s and are mutually independent.
By the inductive hypothesis, conditioned on $\bar{\E}$,
each type $t$ wins with probability $f'(t) \interimp{t}$.
Using the definition of $f'$ and from the subroutine,
the total winning probability for $t^*$ is
$q^* \cdot 1 + (1-q^*) \cdot f'(t^*) \interimp{t^*}
= q^* + (1-q^*) \cdot \frac{f(t^*) \interim{t^*} - q^*}{1-q^*}
= f(t^*) \interim{t^*}$.
For $t \neq t^*$, the total winning probability is
$q^* \cdot 0  + (1-q^*) f'(t) \interimp{t}
= (1-q^*) \cdot \frac{f(t) \interim{t}}{1-q^*}
= f(t) \interim{t}$.
Therefore, the interim winning probability for each type $t$ is t,
and the dice implement for $f$.

§.§ Proof of Lemma <ref> (Number of Recursive Calls)

The following lemma is essential in that it shows that invoking
maintains feasibility and tightness of sets.

Let $f$, , $t^*$ and $q$ be valid inputs for ,
and $f'$, the output of the call to $\Decrement (f, \INTE, t^*, q)$.
Let $S$ be any set of types with $t^* \in S$. Then,

* The Border constraint for $S$ is satisfied for $(f', \INTEP)$
if and only if it is satisfied for $(f, \INTE)$.

* The Border constraint for $S$ is tight for $(f', \INTEP)$
if and only if it is tight for $(f,\INTE)$.

We will show that the slack for every $S \ni t^*$ satisfies
$\slack_{f',\INTEP}(S) = \frac{\slack_{f,\INTE}(S)}{1-q}$,
which implies both claims.
Let $i^*$ be such that $t^* \in T_{i^*}$.
Using the definitions of $f'$ and ,

\begin{align*}
\slack_{f',\INTEP}(S)
& = f'(S) - \sum_{t\in S} f'(t) \interimp{t} \\
& = 1 - \left( 1 - \frac{f(S_{i^*})-q}{1-q} \right)
\cdot \prod_{i \neq i^*} (1-f(S_i))
- \frac{(\sum_{t\in S}f(t)  \interim{t}) - q}{1-q} \\
& = \frac{1}{1-q} \cdot \left( 1- (1-f(S_{i^*}))
\cdot \prod_{i \neq i^*} (1-f(S_i))
- \sum_{t\in S} f(t) \interim{t} \right)\;=\; \frac{\slack_{f,\INTE}(S)}{1-q}.\QED
\end{align*}

We are now ready to prove Lemma <ref>.
We will show that with each recursive invocation of (step <ref>), at least one of the following happens:
(1) The number of active types $|T^+|$ decreases;
(2) The size of the barrier set $|T^*|$ decreases.

Notice that the number of active types or the size of a barrier set
never increase.
Because the size of the barrier set can only decrease at most times, the number of active types must decrease at least every recursive invocations.
It, too, can decrease at most times, implying the claim of the lemma.

Let $T^*$, $t^*$, and $(q^*, f', \INTEP)$ be as chosen in
steps <ref>, <ref>, and <ref>, respectively.
Let candidate $i^*$ be such that $t^* \in T_{i^*}$.
If $q^*= f(t^*) \interim{t^*}$,
then the type $t^*$ will be inactive in $(f',\INTEP)$,
and there will be one fewer active type in the subsequent invocation
of (step <ref>).
We distinguish the cases $|T^*|=1$ and $|T^*| > 1$.

If $|T^*|=1$, then $T^*= \set{t^*}$.
By definition of a barrier set, $T^*$ is tight,
implying (for a singleton set) that $\interim{t^*}=1$.
We claim that $q^*$ is set to $f(t^*) = f(t^*) \interim{t^*}$ in
step <ref>,
implying that the number of active types decreases.
To prove that $q^* = f(t^*)$, we will show that this choice of $q^*$
is feasible in the invocation of $\Decrement(f, \INTE, t^*, f(t^*))$.
Consider the $\hat{f}, \INTEH$ resulting from such an
invocation of .
Lemma <ref> implies that the feasibility of each Border
constraint corresponding to a set $S \ni t^*$ is preserved for
$(\hat{f}, \INTEH)$.
For type sets $S$ excluding $t^*$,

\begin{align*}
\slack_{\hat{f}, \INTEH}(S)
& = \hspace{-5pt}\hat{f}(S) - \sum_{t\in S} \hat{f}(t) \interimh{t} \;=\; 1 - \left(1-\frac{f(S_{i^*})}{1-f(t^*)} \right)
\cdot \prod_{i \neq i^*} (1-f(S_i))
- \frac{\sum_{t\in S}f(t) \interim{t} }{1-f(t^*)} \\
& =  \begin{aligned}[t]
\frac{1}{1-f(t^*)} \cdot \Biggl( 1 &- (1-f(S_{i^*}) + f(t^*)) \cdot
\prod_{i \neq i^*} (1-f(S_i))  \\
&-  \left( \sum_{t\in S}f(t) \interim{t} + f(t^*)\interim{t^*} \right) \Biggr)
\end{aligned}\\
& = \frac{\slack_{f,\INTE}(S\cup\SET{t^*})}{1-f(t^*)},
\end{align*}

which is nonnegative because is feasible for $f$.
Therefore, step <ref> indeed chooses $q^* = f(t^*)$.

Next, we consider the case $|T^*| > 1$,
and assume that $q^* < f(t^*) \interim{t^*}$
(since otherwise, we are done).
Then, the set of active types $T^+$ is the same for both
$(f,\INTE)$ and $(f',\INTEP)$.

If the instance $(f', \INTEP)$ for the recursive call has multiple
barrier sets, then by Lemma <ref>,
they are all singletons, and indeed the size of the barrier set in the
next recursive call (which is 1) is strictly smaller than $|T^*|$.
So we assume that $(f', \INTEP)$ has a unique barrier set $T'$.

Because $|T^*| > 1$, Lemma <ref> implies that
$T^*$ is the unique barrier set for $(f,\INTE)$.
Therefore, by the definition of barrier sets,
$T^*$ (and hence also $t^*$) is contained in every tight set of active
types for $(f,\INTE)$ (if any).
Because $t^*$ is contained in all tight sets, Lemma <ref>
implies that for every $q \in [0, f(t^*) \interim{t^*}]$,
the result of $\Decrement(f,\INTE,t^*,q)$
does not violate any constraints which are already tight for
$(f,\INTE)$, and in fact preserves their tightness.

Because all other constraints have slack,
the optimal $q^*$ is strictly positive.
By assumption, we also have that  $q^* < f(t^*) \interim{t^*}$;
therefore, a non-empty set $S'$ which was not tight for $(f,\INTE)$
must have become tight for
$(f',\INTEP) = \Decrement (f,\INTE,t^*,q^*)$.
By Lemma <ref>, this set $S'$ does not include $t^*$.
Because discarding inactive types preserves tightness,
we may assume without loss of generality that $S' \subseteq T^+$.

We have shown the existence of a non-empty tight set
$S' \subseteq T^+ \sm \set{t^*}$ for $(f',\INTEP)$.
By definition, the barrier set $T'$ is the (unique, in our case)
minimal tight set for $(f',\INTEP)$, so $T' \subseteq S'$.
We distinguish two cases, based on the possible definitions of
barrier sets:

* If $T^* = T^+$, then because $S' \subsetneq T^+ = T^*$,
the barrier set $T'$ is strictly smaller than $T^*$.

* If $T^*$ is tight for $(f,\INTE)$, then it is also tight for
$(f',\INTEP)$ by Lemma <ref>;
since both $S'$ and $T^*$ are tight for $(f',\INTEP)$,
we get that $T' \subseteq T^* \cap S' \subseteq T^* \setminus \set{t^*}$
is strictly smaller than $T^*$.

§.§ Proof of Lemma <ref> (Runtime per Call)

There are only two steps for which polynomial runtime is not
the computation of $q^*$ in step (<ref>) of ,
and finding a non-empty minimizer of a submodular function in
steps (<ref>) and (<ref>) of .
We prove polynomial-time implementability of both steps in the
following lemmas.

In step <ref> of ,
$q^*$ can be computed in $\poly(\NUMT)$ time.

Let $f$, , and $t^*$ be as in step <ref>,
and let the candidate $i^*$ be such that $t^* \in T_{i^*}$.
For each $q \in [0,f(t^*) \interim{t^*}] \sse [0,1)$,
let $(f_q, \INTE_q) = \Decrement(f, \INTE, t^*, q)$
be the result of running $\Decrement(f, \INTE, t^*, q)$ with parameter $q$.
Lemma <ref> implies that all Border constraints
for $S \ni t^*$ remain feasible for $(f_q, \INTE_q)$.
For type sets $S \not\ni t^*$, we can write the slack in the
corresponding Border constraint as a function of $q$ as follows:

\begin{align*}
\slack_{f_q,\INTE_q}(S)
& = f_q(S) - \sum_{t\in S} f_q(t) x_q(t) \\
& = 1 - \left(1-\frac{f(S_{i^*})}{1-q} \right)
\cdot \prod_{i \neq i^*} \left(1-f(S_i) \right)
- \frac{\sum_{t\in S}f(t) \interim{t} }{1-q} \\
& = \frac{1}{1-q} \cdot \left( 1- (1 - f(S_{i^*}) - q)
\cdot \prod_{i \neq {i^*}} (1-f(S_{i}))
- \sum_{t\in S}f(t)\interim{t} - q \right)\\
& = \frac{1}{1-q} \left( \slack_{f,\INTE}(S) - q f(S \sm S_{i^*})\right).
\end{align*}

The preceding expression is nonnegative if and only if
$q \leq h(S) := \frac{\slack_{f,\INTE}(S)}{f(S \sm S_{i^*})}$.
Therefore, $q^*$ is the minimum of $f(t^*) \interim{t^*}$ and
$\min_{ S \sse T \sm \set{t^*}} h(S)$.
The function $h(S)$ does not appear to be submodular,
and hence efficient minimization is not immediate.
We utilize Theorem <ref> to reduce the search
space and compute $q^*$ efficiently.

For an interim rule $\INTE: T \to [0,1]$,
we call $S \sse T$ a level set of if there exists
an $\alpha \in [0,1]$ such that $S = \set{ t \in T : \interim{t} > \alpha}$.
If $q^*= \min_{S \not\ni t^*} h(S)$,
then at least one Border constraint just becomes tight at $q=q^*$.
Theorem <ref> implies that at least one level set of
$\INTE_{q^*}$ corresponds to one of these newly tightened constraints,
and $h$ is minimized by such a level set.
It follows that, in order to compute $q^*$,
it suffices to minimize $h$ over all those sets $S \not\ni t^*$
which could possibly arise as level sets of some
$\INTE_q$ for $q \in [0, f(t^*) \interim{t^*}]$.

Let $t_1, \ldots, t_K$ be the types in $T_{i^*} \sm \set{t^*}$,
ordered by non-increasing t;
similarly, let $t'_1, \ldots, t'_L$ be the types in $T \sm T_{i^*}$,
ordered by non-increasing t.
The relative order of types in $T_{i^*} \sm \set{t^*}$ is the same
under $x_q(t)$ as under t, because $x_q(t) = \interim{t}$;
similarly, the relative order of types in $T \sm T_{i^*}$ is the same
under $x_q(t)$ as under t, because $x_q(t) = \frac{\interim{t}}{1-q}$.
Therefore, the family
$\left\{\set{t_1, \ldots, t_k, t'_1, \ldots, t'_\ell} : k \leq K, \ell \leq L\right\}$
includes all level sets of every $\INTE_q$ excluding $t^*$.
There are at most $\NUMT^2$ type sets in this family,
and those sets can be enumerated efficiently to minimize $h$.

There is an algorithm for computing a non-empty minimizer of a
submodular function in the value oracle model,
with runtime polynomial in the size of the ground set.

For a submodular function $g: 2^T \to \mathbb{R}$,
let $g_t(S) = g (S\cup \SET{t})$, for $t\in T$.
$g_t$ is also submodular,
and can be minimized in time polynomial in $|T|$ <cit.>.
Let $S_t$ be a minimizer of $g_t$ and  $t^* \in \arg\min_{t\in T}
g_t(S_t)$. $S_{t^*} \cup \SET{t^*}$ is a non-empty minimizer of $g$.

§ SYMMETRIC DICE FOR I.I.D. CANDIDATES IN SINGLE-WINNER SETTINGS

Even when the candidates are identical and the interim rule is symmetric,
Algorithm <ref> typically produces different
dice for different candidates.
In this section, we design an algorithm specifically for the case of
$\NUMC \geq 2$ i.i.d. candidates that guarantees symmetry across
candidates in the dice-based implementation.

Consider a winner-selection environment with candidates,
where each candidate has types $T$, each candidate's type is drawn independently from the prior
on $T$, and at most one candidate is selected as winner.
If $\INTE: T \to [0,1]$ is a feasible symmetric interim rule,
then it admits a symmetric dice-based implementation.
An explicit representation of the associated dice can be
computed in time polynomial in and $\NUMT=|T|$.

Algorithm <ref>,
which is similar to Algorithm <ref>,
recursively constructs a dice-based implementation for the
symmetric interim rule .

Number of candidates $\NUMC\geq 2$.
PDF $f$ supported on $T$.
Symmetric interim rule $\INTE: T \to [0,1]$ feasible for $f^\NUMC$.
Set of dice $(\DIE[t])_{ t \in T}$.
Let $T^+\gets \Set{t}{f(t)\interim{t}> 0}$ be the set of active types.
$|T^+|\le 1$
for all $t \in T\backslash T^+$, let [t] be a
single-sided die with a $-1$ face.
for all $t \in T^+$ (if any), let [t] be a
die with two sides -1, 1 and probability
$\frac{1-\sqrt[\NUMC]{1 - \NUMC f(t) \interim{t}}}{f(t)}$
of coming up 1.

Let $T^* = \FindBarrierSetIID(\NUMC,f,\INTE)$ .
Let $t^* \in T^*$ be arbitrary.
Let $(f',\INTEP) \gets \DecrementSymmetricDice(\NUMC,f,\INTE,t^*, q^*)$,
for the largest value $q^*\in [0, f(t^*)]$
such that is feasible for $f'$.
$(\DIEP[t])_{t\in T} \gets \ConstructSymmetricDice (\NUMC,\PMFP,\INTEP)$.
Let $M$ be the maximum possible face of any [t], and $M':=\max(M,0)+1$.
Let $\DIE[t] = \DIEP[t]$ for $t\ne t^*$.
Let [t^*] be the die which rolls $M'$ with probability $\frac{q^*}{f(t^*)}$, and rolls [t^*] with probability $1-\frac{q^*}{f(t^*)}$.
$(\DIE[t])_{ t\in T}$.

*[l]As in the algorithm , $q$ is the probability
assigned to the highest face.
Unlike in the algorithm , due to symmetry, for any one
candidate, the probability of winning thanks to this highest face is only
$(1-(1-q)^\NUMC)/\NUMC $.
if $\pmf{t^*} = q$, then let $\pmfp{t^*} \gets 0, \interimp{t^*} \gets 0$.
else let $\pmfp{t^*} \gets \frac{\pmf{t^*}-q}{1-q}$ and
$\interimp{t^*} \gets \frac{f(t^*)\interim{t^*} -
*[r]$q < 1$ because $|T^+| \geq 2$.
for all $t \ne t^*$ do
let $\pmfp{t} \gets \frac{\pmf{t}}{1-q}$
and $\interimp{t} \gets \frac{\interim{t}}{(1-q)^{\NUMC-1}}$.
$\DecrementSymmetricDice (\NUMC, \PMF, \INTE, t^*, q)$

Interim rule feasibility is characterized by the symmetric Border
constraints (Inequality (<ref>)).

We let $\slack_{\NUMC,f,\INTE}(S)$ denote the slack in the
symmetric Border constraint for $S \sse T$.
Similarly to Section <ref>,
when is feasible for $(\NUMC,f)$,
we call a set $S \sse T$ tight for $(\NUMC,f,\INTE)$
if $\slack_{\NUMC,f,\INTE}(S) = 0$.
Also similar to Section <ref>,
we let $T^+= \set{t \in T: f(t) \interim{t} > 0}$ be the set of
active types,
and we define the barrier sets to be the minimal non-empty
tight sets of active types if any non-empty tight sets exist;
otherwise, $T^+$ is the unique barrier set.
The algorithm is essentially
identical to from Section <ref>;
hence, we omit it here.
The following lemma shows that the barrier set is unique in the
i.i.d. setting, and that therefore, every tight set contains it.

In the i.i.d. setting, there is a unique barrier set.

The uniqueness of the barrier set can be shown by a proof very similar
to the proof of Lemma <ref>.
Assume for contradiction that there are two barrier sets $A$ and $B$.
Minimality implies that $A$ and $B$ are disjoint.
Since there are at least 2 candidates, with positive probability,
at least one candidate has a type in $A$ and at least one candidate
has a type in $B$.
In this event, tightness implies that the winner's type must lie in
both $A$ and $B$, contradicting their disjointness.

We now sketch the proof of Theorem <ref>,
which is very similar to that of Theorem <ref>.

Theorem <ref>
First, we show correctness.
Assuming that the algorithm terminates,
we show that it outputs a set of dice implementing the symmetric rule
for $f^\NUMC$.

In the base case $|T^+| \leq 1$, our choice of dice for types
$t \notin T^+$ ensures that they are never chosen as winner.
If there is a (unique) type $t \in T^+$, then the probability of its
die rolling 1 is
$\frac{1 - \sqrt[\NUMC]{1 - \NUMC f(t) \interim{t}}}{f(t)}$.
The probability that a particular candidate has type $t$ and rolls 1
is therefore $1 - \sqrt[\NUMC]{1 - \NUMC f(t) \interim{t}}$,
and the probability that at least one candidate has type $t$
and rolls 1 is $\NUMC f(t) \interim{t}$.
Thus, the probability that some candidate has type $t$
and wins is $\NUMC f(t) \interim{t}$;
by symmetry and the uniform tie breaking rule, the probability that
a specific candidate has type $t$ and wins is
$f(t) \interim{t}$.

For the inductive step, consider a recursive call to .
Assume by induction hypothesis that the dice collection
$(\DIEP[t])_{ t \in T}$ implements for $(f')^\NUMC$,
and consider the winner selection rule implemented by the dice
$(\DIE[t])_{ t \in T}$ for the joint type distribution $f^\NUMC$.

The probability of at least one candidate rolling the highest face $M'$
is $1 - (1-q^*)^\NUMC$.
Conditioned on no candidate rolling the highest face $M'$,
the conditional type distribution of each candidate is $f'$,
the conditional distribution of type $t$'s die is [t],
and all these distributions are independent.
The probability of a specific candidate winning with type
$t \neq t^*$ is $(1-q^*)^\NUMC f'(t) \interimp{t} = f(t) \interim{t}$.

Next consider the winning probability for type $t^*$.
There are two ways in which a candidate with type $t^*$ could win:
by rolling the highest face $M'$ and winning the uniformly random tie
breaking if necessary,
or by having the highest face when no candidate rolls the face $M'$.
Similar to the argument in the base case,
the probability that some candidate wins by rolling $M'$
is $(1-(1-q^*)^\NUMC)$, so the probability that a specific
candidate wins by rolling $M'$ is $\frac{1}{\NUMC}(1-(1-q^*)^\NUMC)$.
The probability of winning without rolling the highest face is
$(1-q^*)^\NUMC f'(t^*) \interimp{t^*}$.
In total, the probability of a specific candidate winning with type $t^*$ is
$\frac{1}{\NUMC}(1-(1-q^*)^\NUMC) + (1-q^*)^\NUMC f'(t^*) \interimp{t^*}
= f(t^*) \interim{t^*}$,
so for all types $t$,
the interim winning probability of each type $t$ is t, as claimed.

Next, we bound the number of iterations by $\NUMT^2$.
As before, we show that with each recursive call,
either the size of the unique barrier set decreases,
or the number of active types decreases.
The following equation captures the key part of the analogue of
Lemma <ref>,
showing that invoking $\DecrementSymmetricDice(\NUMC,f,\INTE,t^*,q)$
preserves slackness and tightness of every set $S \ni t^*$.

\begin{align*}
\slack_{\NUMC,f', \INTEP}(S)
& = 1 - \left( 1- \sum_{t \in S} f'(t) \right)^\NUMC
- \NUMC \sum_{t\in S} f'(t)\interimp{t}\\
& = 1- \left( 1 - \frac{\sum_{t \in S} f(t)-q}{1-q}\right)^\NUMC
- \NUMC \cdot \frac{\sum_{t \in S} f(t)\interim{t} - (1-(1-q)^\NUMC)/\NUMC}{(1-q)^\NUMC}\\
& = \frac{1}{(1-q)^\NUMC} \cdot
\left( (1-q)^\NUMC - \left( 1 - \sum_{t \in S} f(t) \right)^\NUMC
- \NUMC \sum_{t\in S} f(t)\interim{t} + (1-(1-q^\NUMC)) \right) \\
& = \frac{\slack_{\NUMC,f,\INTE}(S)}{(1-q)^\NUMC}.
\end{align*}

Now consider a call to .
There are again two cases,
based on the cardinality of the barrier set $T^*$.
If $|T^*| > 1$, then either $q^*= f(t^*)$,
and the number of active types obviously decreases,
or $q^* < f(t^*)$,
and a new tight set is created in step (<ref>).
In the latter case, the size of the barrier set decreases in the next
recursive call;
as in the proof of Lemma <ref>,
this follows from the uniqueness of the barrier set
(Lemma <ref>),
the fact that preserves tightness and
slackness of sets containing the type $t^*$
(including, in particular, the tight set $T^*$),
and the fact that tight sets are closed under intersection.

If $T^*=\set{t^*}$ is a singleton, then tightness implies that
$\NUMC f(t^*) \interim{t^*} = 1-(1-f(t^*))^\NUMC$.
The following calculation then shows that invoking
$\DecrementSymmetricDice(\NUMC,f,\INTE,t^*,q)$ with $q = f(t^*)$
does not violate the feasibility of any set $S \not\ni t^*$.

\begin{align*}
\slack_{\NUMC,f', \INTEP}(S)
& = 1 - \left( 1 - \sum_{t \in S} f'(t) \right)^\NUMC
- \NUMC \sum_{t\in S} f'(t)\interimp{t}\\
& = 1 - \left( 1 -\frac{\sum_{t \in S} f(t)}{1-q}\right)^\NUMC
- \NUMC\sum_{t\in S} \frac{f(t)\interim{t}}{(1-q)^\NUMC}\\
& = \frac{1}{(1-q)^\NUMC} \cdot
\left( (1-q)^\NUMC - \left( 1-q-\sum_{t \in S} f(t) \right)^\NUMC
- \NUMC\sum_{t\in S} f(t)\interim{t} \right) \\
& = \frac{1}{(1-q)^\NUMC}
\left( 1 - \left( 1-f(t^*)-\sum_{t \in S} f(t) \right)^\NUMC
- \NUMC \sum_{t\in S} f(t)\interim{t}
- \left(1- \left( 1-f(t^*) \right)^\NUMC \right) \right) \\
& = \frac{\slack_{\NUMC,f,\INTE}(S\cup\SET{t^*})}{(1-q)^\NUMC}
\; \ge \; 0.
\end{align*}

Because feasibility is also preserved for sets $S \ni t^*$ (as
mentioned above),
this implies that $q^*=f(t^*)$;
as a result, the number of active types decreases.

Finally, it remains to show that each recursive call can be
implemented in time polynomial in and .
For step (<ref>),
the proof is essentially identical to the analogous claim in
Section <ref> and is therefore omitted.
For computing $q^*$ in Step (<ref>),
the proof is similar to the analogous claim in Section <ref>.
Let $(f_q,\INTE_q) = \DecrementSymmetricDice(\NUMC,f,\INTE,t^*,q)$;
as shown above, this operation preserves the feasibility of every
constraint corresponding to  $S \ni t^*$.
For sets $S \not\ni t^*$, there exists a threshold $h(S)$ for the
maximum value of $q \leq f(t^*) \interim{t^*}$ such that
$\slack_{\NUMC,f_q,\INTE_q}(S) \geq 0$,
and this threshold can be computed numerically.
As in the proof of Lemma <ref>,
Theorem <ref> implies that it suffices to restrict
attention to level sets of the form
$S(\alpha) = \set{ t  \neq t^* : x_q(t) > \alpha}$
for some $q \in [0, f(t^*)]$ and $\alpha \in [0,1]$.

In the i.i.d. setting, there are at most $\NUMT-1$ such level sets,
since the relative order of types $t \neq t^*$ by  $x_q(t)$ does not
depend on $q$ (and hence, can be computed from ).
As in the proof of Lemma <ref>,
computing $q^*$ then reduces to minimizing $h(S)$
over these $\NUMT-1$ level sets.

§ FROM WINNER-SELECTING DICE TO INTERIM RULES FOR SINGLE-WINNER SETTINGS

Having shown how to compute winner-selecting dice implementing a given interim rule,
we next show the easier converse direction:
how to compute the interim rule given winner-selecting dice
$\SET{\die[i]{t}}$ in single-winner environments.
As before, we denote the type set of candidate $i$ by $T_i$, and
assume without loss of generality that the type sets of different
candidates are disjoint.
For simplicity of exposition,
we assume that each die has a given finite support
[Our approach extends easily to the case of continuously
supported dice, so long as we can perform integration with respect
to the  distributions of the various dice.],
and we write $U_i := \bigcup_{t \in T_i} \supp(\die[i]{t})$
for the combined support of candidate $i$'s dice.
We also assume that we can evaluate the probability
$\Prob{\die[i]{t} = u}$ of the face labeled with $u$,
for all candidates $i$, types $t$, and faces $u \in U_i$.

Consider a single-winner selection environment with candidates
and independent priors $\PMF[1], \ldots, \PMF[\NUMC]$,
where [i] is supported on $T_i$.
Given dice $\Set{\die[i]{t}}{i \in [\NUMC], t \in T_i}$
represented explicitly,
the interim rule of the corresponding dice-based winner selection rule
can be computed in time polynomial in , $\NUMT = \sum_i |T_i|$,
and the total support size $\SetCard{\bigcup_i U_i}$ of all the dice.

First, we can compute the probability mass function of each candidate
$i$'s (random) score i.
Given $u \in U_i$, we have $\Prob{\score{i} = u} = \sum_{t \in T_i} \pmf[i]{t} \cdot \Prob{\die[i]{t} = u}.$

From this probability mass function, we easily compute

$\Prob{\score{i} \leq u}$
for each $u \in U_i$ by the appropriate summation.
When all dice faces are distinct, this is all we need;
since $\Prob{\score{i'} < u} = \Prob{\score{i'} \leq u}$
for $i' \neq i$ and $u \in U_i$,
the interim rule is given by the following simple equation:

\[
\interim[i]{t}
= \sum_{u \in \supp(\die[i]{t})} \Prob{\die[i]{t} = u}
\cdot \prod_{i' \neq i} \Prob{\score{i'} \leq u}.
\]

When the dice's faces are not distinct,
recall that we break ties uniformly at random.
To account for the contribution of this tie-breaking rule,
we need the distribution of the number of other candidates that tie
candidate $i$'s score of $u$;
this is a Poisson Binomial distribution.
More, precisely, we need the Poisson Binomial distribution
with the $\NUMC-1$ parameters
$\left(\frac{\Prob{\score{i'} = u}}{\Prob{\score{i'} \leq u}} \right)_{i' \neq i}$;
we denote its probability mass function by $B_{i,u}$.
It is well known, and easy to verify, that a simple dynamic program
computes the probability mass function of a Poisson Binomial
distribution in time polynomial in its number of parameters.
Therefore, we can compute $B_{i,u}(k)$ for each
$i \in [\NUMC], u \in U_i$
and $k \in \SET{1, \ldots, \NUMC-1}$.
The interim rule is then given by the following equation:

\[
\interim[i]{t}
= \sum_{u \in \supp(\die[i]{t})} \Prob{\die[i]{t} = u} \cdot
% \left( \prod_{i' \neq i}\Prob{\score{i'} < u} \right)
\left( \prod_{i' \neq i}\Prob{\score{i'} \leq u} \right)
\cdot \sum_{k=0}^{\NUMC-1} \frac{B_{i,u}(k)}{k+1}.
\]

It is easy to verify that all the above computations satisfy the
claimed runtime.

§ WINNER-SELECTING DICE AND PERSUASION

In this section, we investigate the existence of winner-selecting dice
for instances of Bayesian persuasion.
Our main result (Theorem <ref>) is to exhibit an instance
with independent non-identical actions for which there is no optimal
signaling scheme that can be implemented using winner-selecting dice.
This result is contrasted with Theorem <ref>,
which shows that when the actions' types are not just independent,
but identically distributed as well,
a dice-based implementation always does exist.

There is an instance of Bayesian persuasion (given in
Table <ref>) with independent actions
which does not admit a dice-based implementation of any
optimal signaling scheme.
Consequently, there exists a second-order interim rule which does not
admit a dice-based implementation.

Every Bayesian persuasion instance with i.i.d. actions admits an
optimal dice-based signaling scheme.
Moreover, when the prior type distribution is given explicitly,
the corresponding dice can be computed in time polynomial in the
number of actions and types.

The negative result of Theorem <ref> has
interesting implications.
Since second-order interim rules summarize all the attributes of a
winner selection rule relevant to persuasion,
second-order interim rules, unlike their first-order brethren,
can in general not be implemented by dice.
Most importantly, this result draws a sharp contrast between
persuasion and single-item auctions,
despite their superficial similarity:
it rules out a Myerson-like virtual-value characterization of optimal
persuasion schemes, and it joins the #P-hardness result of
<cit.> as
evidence of the intractability of optimal persuasion.

§.§ Basics of Bayesian Persuasion

In Bayesian persuasion,
the candidates are actions which a receiver can
Each action $i$ has a type i, drawn independently
[The draws are independent in this paper. In more general
Bayesian persuasion models, they can be correlated.]
from the set $T_i$, according to a commonly known distribution [i].
Each type $t_i$ has associated payoffs
$s (i, \type{i})$ and $r (i, \type{i})$ for the sender and receiver,
The sender (or principal) also has access to the
actual draws $\TP = (\type{1}, \ldots, \type{\NUMC})$
of the types, and would like to use this leverage to persuade the
receiver to take an action favorable to him
[To avoid ambiguities, we always
use male pronouns for the sender and female ones for the receiver.].

Thereto, the sender can commit to a (typically randomized) policy
— called a signaling scheme —
of revealing some of this information to the receiver.
It was shown by <cit.> that the sender can restrict
attention, without loss, to direct schemes:
randomized functions mapping type profiles to recommended
Naturally, the function must be persuasive:
if action $i$ is recommended,
the receiver's posterior expected utility from action $i$ must be no
less than her posterior expected utility from any other action $i'$.
In this sense, direct schemes can be viewed as winner selection rules
in which the actions are the candidates,
and persuasiveness constraints must be obeyed.

§.§ Proof of Theorems

Theorem <ref>
The persuasion instance, shown in Table <ref>,
features three actions $\SET{A,B,C}$, each of which has two types $\SET{1,2}$.
The types of the different actions are distributed independently.
In the instance, the sender's utility from any particular action is a
constant, independent of the action's type.

actiontype    1     2

$A$      $0.5\times (100, 2)$     $0.5\times (100, -\infty)$

$B$      $0.99\times (1,3)$     $0.01\times(1, -\infty)$

$C$     $0.5\times (0,0)$     $0.5\times (0, 6)$

A Persuasion instance with no dice-based implementation.
The notation $p \times (s, r)$ denotes that the type $(s,r)$
(in which the sender and receiver payoffs are $s$ and $r$, respectively)
has probability $p$.

One (optimal, as we will show implicitly)
signaling scheme is the following.
(In writing a type vector, here and below,
we use $*$ to denote that the type of an action is irrelevant.)

* If the type vector is $(1,*,1)$, then recommend action $A$.

* If the type vector is $(1,*,2)$, then recommend each of $A, C$
with equal probability .

* If the type vector is $(2,1,*)$, then recommend action $B$.

* If the type vector is $(2,2,*)$, then recommend action $C$.

While this is not the unique optimal scheme,
we next prove that none of the optimal persuasion schemes admit a
dice-based implementation.

The given signaling scheme recommends action $A$
with probability $3/8$ overall,
action $B$ with probability $\frac{99}{200}$ overall,
and action $C$ with the remaining probability.
No persuasive signaling scheme can recommend $A$ with
probability strictly more than $3/8$, because conditioned on
receiving the recommendation $A$, action $C$ must be at least twice as
likely to be of type $1$ as of type $2$, in addition to action $A$ being of type $1$ with probability $1$.
Similarly, no persuasive scheme can recommend $B$ with probability
strictly more than $\frac{99}{200}$, because action $C$ must be at
least as likely to be of type $1$ as of type $2$ when $C$ is
recommended, in addition to action $B$ being of type $1$ with probability $1$.
Hence, any optimal signaling scheme must recommend $A$ with
probability $3/8$ and $B$ with probability
$\frac{99}{200}$, and the given scheme is in fact optimal.

Suppose for a contradiction that there exist dice
$(\die[i]{j})_{i \in \SET{A,B,C}, j \in \SET{1,2}}$
implementing an optimal signaling scheme.
We gradually derive properties of these optimal signaling schemes,
eventually leading to a contradiction.

* Since action $A$ can never be recommended when it has type 2
(the receiver would never follow the recommendation),
it must be recommended with probability $\frac{3}{4}$
conditioned on having type 1.

* In particular, whenever the type profile is $(1,*,1)$, action
$A$ must be recommended, regardless of the type of action $B$.
This is because action $C$ must be at least twice as likely
of type 1 as of type 2 for a recommendation of $A$ to be

* Therefore, all faces on [A]1 must be larger than all faces
on [B]1 and on [B]2.

* Because of this, action $B$ can never be recommended when the
type profile is $(1,*,2)$.

* Thus, when the type profile is $(1,*,2)$, the signaling scheme
has to recommend each of $A$ and $C$ with probability .
(The recommendation could of course follow different distributions
based on the type of $B$; such a correlation is immaterial for our

* Given that action $B$ cannot be recommended when action $A$ has
type 1, or when action $B$ has type 2, it must always be
recommended for type vectors $(2,1,*)$.

* This implies that all faces of [B]1 must be larger than
all faces on [C]1 and on [C]2.

* This is a contradiction to Step <ref>,
which states that with positive probability,
[C]2 beats [B]1.

Thus, we have proved that there is no dice-based implementation of any
optimal signaling scheme for the given instance.

Theorem <ref>
When the actions' (or more generally: candidates')
type distributions are i.i.d., i.e.,
$T_i$ and [i] are the same for all candidates $i$,
<cit.> have shown that there is an optimal
symmetric signaling scheme,
or more generally a symmetric second-order interim rule .
We show that any symmetric second-order interim rule is
uniquely determined by its first-order component,
a fact implicit in <cit.>.

For symmetric rules, ii't depends only on whether $i=i'$
or $i \neq i'$,
but not on the identities of the candidates $i$ and $i'$.
Therefore, can be equivalently described by two type-indexed vectors
$\vc{y}$ and $\vc{z}$,
where $y_t= \sinte{i}{i}{t}$ for all candidates $i$,
and $z_t= \sinte{i}{i'}{t}$ for all candidates $i$ and $i'$ with $i \neq i'$.
The vector $\vc{y}$ is a first-order interim rule,
and we refer to it as the first-order component of .
If is feasible and implemented by ,
then $y_t = \sinte{i}{i}{t} = \ProbC{\ALGO(\TP) = i}{\type{i} = t}$
for all candidates $i$,
so $\vc{y}$ is the first-order interim rule implemented by .
For every candidate $i$ and type $t$, we have

\[
1 \; = \; \sum_{i'=1}^\NUMC \ProbC{\ALGO(\TP) = i'}{\type{i} = t}
\; = \; (\NUMC-1) z_t + y_t.
\]

Therefore, $\vc{z} = \frac{\vc{1}-\vc{y}}{\NUMC-1}$,
and the first-order component of a symmetric second-order interim rule
suffices to fully describe it.
The second-order rule is also, by the preceding argument,
efficiently computable from its first-order component,
and is feasible if and only if its first-order component is a feasible
symmetric interim rule.
Moreover, by <cit.>,
feasibility of symmetric second-order interim rules can be checked in
time polynomial in the number of types and candidates,
and given a feasible symmetric second-order interim rule ,
a winner selection rule implementing can be evaluated in
time polynomial in the number of types and candidates.
polynomial time.

§ DIRECTIONS FOR FUTURE WORK

We have begun an investigation of dice-based winner selection rules,
in which each of several candidates independently draws a “score”
from a distribution (rolling a “die”),
and a candidate set is selected to maximize the sum of scores,
subject to a feasibility constraint.
We have shown that dice-based winner selection rules can implement all
first-order interim rules with matroid constraints,
but not all second-order interim rules;
in particular, there are instances of Bayesian persuasion in which no
optimal signaling scheme can be implemented using dice.

A natural direction for future work is to understand the limits of
dice-based winner selection rules.
While our existence proof uses matroid properties,

matroid constraints are not the limit of implementability by dice:
in the appendixthe full version,
we show an example in which the feasible sets do not form a matroid,
yet every feasible interim rule within the environment is
implementable with dice.
This rules out a characterization of the form
“a feasibility constraint $\I$ has all feasible $(\INTE, \PMF)$
implementable by dice if and only if $\I$ is a matroid.”
In fact, we do not know of any feasibility constraint and
corresponding first-order feasible interim rule for which a dice-based
implementation can be ruled out,
though we strongly suspect that such examples exist.
A difficulty in verifying our conjecture is that we are not
aware of a useful general technique for proving the
non-existence of a dice-based implementation for a given
interim rule.

Another direction is to find an efficient algorithm for matroid
To derive an efficient algorithm from our existential proof,
the functions $g_t$ and $h_t$ would have to be evaluated efficiently.
Furthermore, even if a set of continuous dice is given,
it is still unclear how to convert them to dice with finitely many
faces in polynomial time.

§ AN INTERIM RULE NOT CORRESPONDING TO ANY OPTIMAL AUCTION

According to <cit.>, the linear program
which solves for the revenue-maximizing interim rule
is equivalent to the following LP:

∑_i=1^∑_t∈T_i [i]t [i]t v̅_i(t)

is a feasible interim rule.

Here $\bar{v}_i$ is the (ironed) virtual value function.
When no type has virtual value 0, every optimal solution is at the
boundary of the polytope of feasible interim rules.
When some types have virtual value 0,
and we employ the convention of never awarding those types an item,
again we get an interim rule at the boundary.
Therefore, any interior point of this polytope cannot
arise as the interim rule of any optimal auction.
In particular, we have shown that there exist feasible interim
rules not arising as allocation rules of optimal auctions.

§ A NON-MATROID EXAMPLE IMPLEMENTABLE BY DICE

In this section, we show a non-matroid example for which all
feasible first-order interim rules are implementable by dice.
Notice that finding one interim rule that is implementable by
dice within a given environment is easy:
one can calculate the interim winning probability of a collection of
trivial winner-selecting dice.
What we want is to show that dice exist for all feasible interim
rules of a non-matroid environment.

Consider a winner-selection environment with $4$ candidates, numbered
$1, 2, 3, 4$.
The feasible winner sets are $\SET{1, 2}, \SET{3,4}$ and
their subsets, i.e., all singletons and the empty set.
Each candidate has a single type, so the type distribution is trivial.
We denote the unique type of candidate $i$ by $i$.

Consider any ex-post rule, i.e., a distribution over the feasible sets
$\SET{1, 2}, \SET{3, 4}, \SET{1}, \SET{2}, \SET{3}, \SET{4}, \emptyset$.
Denote the ex-post rule's probability of selecting the winner set $S$ by $y_S$.
We have

\begin{equation}\label{eq:expost-interim}
\begin{aligned}
x(1) &= y_{\SET{1, 2}} + y_{\SET{1}}\\
x(2) &= y_{\SET{1, 2}} + y_{\SET{2}}\\
x(3) &= y_{\SET{3, 4}} + y_{\SET{3}}\\
x(4) &=y_{\SET{3, 4}} + y_{\SET{4}}
\end{aligned}
\end{equation}

Notice that any feasible interim rule can be implemented by a
distribution $\vc{y}$ in this way.

Without loss of generality, assume that $x(1) \le x(2)$ and $x(3)\le x(4)$.
Whenever is feasible, we define the following set of dice.
Each die has $-\infty$ on one side; the other side's value and
probability are given by Table <ref>.

Type $t$     1     2     3     4

positive face     100     2     10     1

probability of
positive face     $x(1)$     $\frac{x(2)-x(1)}{1-x(1) -x(3)}$     $\frac{x(3)}{1-x(1)}$     $\frac{x(4)-x(3)}{1-x(2)-x(3)}$

Dice for

One can easily verify that these dice implement the desired interim rule,
if the given probabilities for the positive face fall in the interval $[0, 1]$.
Thus, we only need to verify that they do.
Substituting (<ref>) into the probabilities from
Table <ref>, we have

Type $t$     1     2     3     4

probability of
positive face      $y_{\SET{1, 2}} + y_{\SET{1}}$     $\frac{y_{\SET{2}}-y_{\SET{1}}}{1-y_{\SET{1, 2}} - y_{\SET{1}} -y_{\SET{3, 4}}-y_{\SET{3}}}$     $\frac{y_{\SET{3, 4}}+y_{\SET{3}}}{1-y_{\SET{1,2}}-y_{\SET{1}}}$     $\frac{y_{\SET{4}}-y_{\SET{3}}}{1-y_{\SET{1,2}}-y_{\SET{2}}-y_{\SET{3, 4}}-y_{\SET{3}}}$

Since $\sum_{S \subseteq \SET{1,2,3,4}} y_S =  1$ and
$x(1)\le x(2), x(3)\le x(4)$, all the probabilities indeed fall in the
interval $[0, 1]$.
Thus for any feasible interim rule in this winner-selection environment,
there is a collection of dice implementing .

The theorem is a generalization of the fundamental theorem of linear programming to uncountable dimensions.

Let $f_1, \dots, f_m : \mathbb{X} \to \mathbb{R}$ be Borel measurable on a measurable space $\mathbb{X}$ and let $\mu$ be a probability measure on $\mathbb{X}$ such that $f_i$ is integrable with respect to $\mu$ for each $i=1,\dots, m$.  Then there exists a probability measure $\varphi$ with finite support on $\mathbb{X}$, such that:

\[\int_{\mathbb{X}} f_id\varphi = \int_{\mathbb{X}} f_id\mu, \quad \forall i=1, \dots, m. \]

Moreover, the support of $\varphi$ may consist of at most $m+1$ points.