miner can sign a contract with user $i$, and switch user $i$’s and user $j$’s
positions in the bid vector. Since users $i$ and $j$ are bidding the same, the
miner’s revenue is unaffected if their positions are switched. On the other
hand, user $i$ and user $j$’s payments will be switched as a result. Thus,
user $i$’s utility has increased to $c_{i}-p_{j}({\mathbf{b}})$. This violates
$1$-weak-SCP.

Next, we analyze the second case. Without loss of generality, we assume
$b_{i}=p_{i}({\mathbf{b}})>b_{j}=p_{j}({\mathbf{b}})$. By Myerson’s lemma,
user $j$ can increase its bid without changing its payment. Thus, user $j$ can
increase its bid to $b_{i}$, and we have a bid vector
${\mathbf{b}}^{\prime}=({\mathbf{b}}_{-j},b_{i})$. By Lemma 6.3, miner’s
revenue should not change, so we have
$\mu({\mathbf{b}})=\mu({\mathbf{b}}^{\prime})$. If
$x_{i}({\mathbf{b}}^{\prime})=1$, it goes back to the first case, so we assume
$x_{i}({\mathbf{b}}^{\prime})=0$. Now, imagine that the real bid vector is
${\mathbf{b}}^{\prime}$. In this case, miner’s utility is
$\mu({\mathbf{b}}^{\prime})=\mu({\mathbf{b}})$, and user $i$’s utility is
zero. However, the miner can sign a contract with user $i$, and ask it to bid
$b_{j}$ instead. Consequently, the miner prepares a bid vector ${\mathbf{b}}$,
where $b_{j}$ comes from user $i$. In this case, miner’s utility is still
$\mu({\mathbf{b}}^{\prime})=\mu({\mathbf{b}})$, while user $i$’s utility
becomes $b_{i}-p_{j}({\mathbf{b}})>0$. This violates $1$-weak-SCP. ∎

######  Lemma 6.5.

Let $(\mathbf{x},{\mathbf{p}},\mu)$ be a deterministic mechanism that achieves
weak UIC and $2$-weak-SCP. Then, for all users $i,j$, if
$x_{i}({\mathbf{b}})=1$ and $x_{j}({\mathbf{b}})=0$, it must be $b_{i}\geq
b_{j}$. In other words, the confirmed bids must be the highest $k$ bids for
some $k\in\mathbb{N}$ where $k$ may be a function of the bid vector.

###### Proof.

For the sake of reaching a contradiction, suppose that there exist two users
$i,j$ such that $x_{i}({\mathbf{b}})=1$ and $x_{j}({\mathbf{b}})=0$, while
$b_{i}<b_{j}$. By Myerson’s lemma, user $i$ can increase its bid to $b_{j}$
without changing its confirmation and payment. Thus, we have a bid vector
${\mathbf{b}}^{\prime}=({\mathbf{b}}_{-i},b_{i}=b_{j})$ such that
$x_{i}({\mathbf{b}}^{\prime})=1$ and
$p_{i}({\mathbf{b}}^{\prime})=p_{i}({\mathbf{b}})$. There are two possible
cases: either $x_{j}({\mathbf{b}}^{\prime})=1$ or
$x_{j}({\mathbf{b}}^{\prime})=0$.

First, we assume $x_{j}({\mathbf{b}}^{\prime})=1$. Imagine the real bid vector
is ${\mathbf{b}}$ which also represents everyone’s true value. In this case,
miner’s utility is $\mu({\mathbf{b}})$, user $i$’s utility is
$b_{i}-p_{i}({\mathbf{b}})$, and user $j$’s utility is zero. However, the
miner can sign a contract with user $i$ and user $j$, and ask user $i$ to bid
$b_{j}$ instead. By Lemma 6.4, we have
$p_{i}({\mathbf{b}}^{\prime})=p_{j}({\mathbf{b}}^{\prime})$. Because
$p_{i}({\mathbf{b}}^{\prime})=p_{i}({\mathbf{b}})$ and
$p_{i}({\mathbf{b}})\leq b_{i}<b_{j}$, we have
$p_{j}({\mathbf{b}}^{\prime})<b_{j}$. Besides, by Lemma 6.3,
$\mu({\mathbf{b}})=\mu({\mathbf{b}}^{\prime})$. Therefore, after signing the
contract, miner’s utility is still $\mu({\mathbf{b}})$, user $i$’s utility is
still $b_{i}-p_{i}({\mathbf{b}})$, while user $j$’s utility becomes
$b_{j}-p_{j}({\mathbf{b}}^{\prime})>0$. This violates $2$-weak-SCP.

Next, we assume $x_{j}({\mathbf{b}}^{\prime})=0$. Imagine the real bid vector
is ${\mathbf{b}}^{\prime}$ which also represents everyone’s true value. Recall
that in ${\mathbf{b}}^{\prime}$, user $i$ and user $j$ are bidding the same;
however, user $i$ is confirmed but user $j$ is not. Furthermore, user $i$ is
bidding strictly higher than its payment as we have shown above. The coalition
of the miner and user $j$ can strictly benefit, if the miner switched user $i$
and user $j$’s positions in the bid vector; since this does not affect the
miner’s utility, but user $j$’s utility now becomes positive. This violates
$1$-weak-SCP.

∎

##### Notation for the universal payment.

According to Lemma 6.4, all confirmed users must pay the same price. Thus, we
may simplify the notation, and define $p({\mathbf{b}})$ to be the universal
payment price for all confirmed users under the bid vector ${\mathbf{b}}$. If
no one is confirmed under ${\mathbf{b}}$, then we define $p({\mathbf{b}})=0$.

######  Lemma 6.6.

Let $(\mathbf{x},{\mathbf{p}},\mu)$ be a deterministic mechanism that achieves
weak UIC and $2$-weak-SCP. Let ${\mathbf{b}}$ be a bid vector such that at
least one user is confirmed. Then, for any unconfirmed user $i$, it must be
$b_{i}\leq p({\mathbf{b}})$.

###### Proof.

For the sake of reaching a contradiction, suppose there exists an unconfirmed
user $i$ such that $b_{i}-p({\mathbf{b}})=\Delta$ for some $\Delta>0$. Let $j$
be a confirmed user in ${\mathbf{b}}$. By Lemma 6.5, we know that $b_{j}\geq
b_{i}$. Now, consider another bid vector
${\mathbf{b}}^{\prime}=({\mathbf{b}}_{-j},p({\mathbf{b}})+\Delta/2)$. By
Myerson’s Lemma, user $j$ is still confirmed and is still paying
$p({\mathbf{b}})$. However, notice that user $j$’s new bid
$p({\mathbf{b}})+\Delta/2<b_{i}$. By Lemma 6.5, user $i$ must be confirmed too
under the bid vector ${\mathbf{b}}^{\prime}$, and by Lemma 6.4, it would be
paying the same as user $j$, which is $p({\mathbf{b}})$. Now, imagine that
everyone’s true value is the vector ${\mathbf{b}}$. If everyone bids honestly,
the miner’s utility is $\mu({\mathbf{b}})$, user $j$’s utility is
$b_{j}-p({\mathbf{b}})$, and user $i$’s utility is zero. If the miner colludes
with users $i,j$, the coalition can benefit by having user $j$ bid
$p({\mathbf{b}})+\Delta/2$ instead. In this case, miner’s utility is still
$\mu({\mathbf{b}})$ due to Lemma 6.3, user $j$’s utility is still
$b_{j}-p({\mathbf{b}})$, while user $i$’s utility increases to $\Delta/2$.
This violates $2$-weak-SCP. ∎

######  Lemma 6.7.

Let $(\mathbf{x},{\mathbf{p}},\mu)$ be a deterministic, weak UIC, and
$1$-weak-SCP mechanism. Then, for any bid vector ${\mathbf{b}}$, any user $k$,
and any $0<\Delta\leq b_{k}$, it must be that
$\mu({\mathbf{b}})-\Delta\leq\mu({\mathbf{b}}_{-k},b_{k}-\Delta)\leq\mu({\mathbf{b}})$.

###### Proof.

We first prove the direction
$\mu({\mathbf{b}}_{-k},b_{k}-\Delta)\leq\mu({\mathbf{b}})$. We want to show
that if the users’ true value is ${\mathbf{b}}$, but now user $k$ bids
$b_{k}-\Delta$ instead of its true value $b_{k}$, then the miner revenue
should not increase. There are two cases.

  * •

First, if user $k$ is unconfirmed under ${\mathbf{b}}$ or confirmed but paying
its full bid $b_{k}$, then its utility is $0$ under ${\mathbf{b}}$. In this
case, obviously decreasing user $k$’s bid should not make the miner benefit;
since otherwise the coalition of user $k$ and the miner can benefit by having
user $k$ bid $b_{k}-\Delta$ instead, thus violating $1$-weak-SCP.

  * •

Second, suppose that user $k$ is initially confirmed under ${\mathbf{b}}$ and
moreover, $b_{k}>p({\mathbf{b}})$. We can first decrease user $k$’s bid to
exactly $\max(b_{k}-\Delta,p({\mathbf{b}}))$, and let
${\mathbf{b}}^{\prime}:=({\mathbf{b}}_{-k},\max(b_{k}-\Delta,p({\mathbf{b}})))$
be the resulting new bid vector. Due to Myerson’s Lemma, Lemma 6.3, and Lemma
6.4, $x_{k}({\mathbf{b}}^{\prime})=1$,
$\mu({\mathbf{b}}^{\prime})=\mu({\mathbf{b}})$, and
$p({\mathbf{b}}^{\prime})=p({\mathbf{b}})$. Then, we can decrease user $k$’s
bid from $\max(b_{k}-\Delta,p({\mathbf{b}}))$ to $b_{k}-\Delta$, and due to
the same argument as the first case, the miner’s revenue should not increase.

We next prove the other direction, that is,
$\mu({\mathbf{b}})-\Delta\leq\mu({\mathbf{b}}_{-k},b_{k}-\Delta)$. If no one
is confirmed under ${\mathbf{b}}$, the statement trivially holds. Henceforth,
we assume that at least one user is confirmed under ${\mathbf{b}}$. Again,
there are two cases.

  * •

First, suppose that user $k$ is not confirmed under ${\mathbf{b}}$ or
confirmed but paying its full bid $b_{k}$. Due to Lemma 6.6, we know that
$b_{k}\leq p({\mathbf{b}})$. By Myerson’s Lemma, user $k$ should be
unconfirmed or confirmed but paying full bid under
${\mathbf{b}}^{\prime}:=({\mathbf{b}}_{-k},b_{k}-\Delta)$. Now, suppose
everyone’s true value is actually ${\mathbf{b}}^{\prime}$, notice that user
$k$’s utility is $0$. We argue that if user $k$ bids $b_{k}$ instead of its
true value $b_{k}-\Delta$, it should not make the miner revenue increase by
more than $\Delta$. If so, the coalition of user $k$ and the miner can
strictly benefit by having user $k$ bid $b_{k}$ instead of its true value
$b_{k}-\Delta$, since the cost of such overbidding is at most $\Delta$ under
the new utility notion. This violates $1$-weak-SCP.

  * •

Second, suppose that user $k$ is confirmed under ${\mathbf{b}}$ and moreover
$b_{k}>p({\mathbf{b}})$. In this case, due to Myerson’s Lemma, Lemma 6.3, and
Lemma 6.4, the miner’s revenue should not be affected when we reduce user
$k$’s bid to $\max(p({\mathbf{b}}),b_{k}-\Delta)$. We now further decrease
user $k$’s bid from $\max(p({\mathbf{b}}),b_{k}-\Delta)$ to $b_{k}-\Delta$ —
due to the same analysis as the first case, the miner’s revenue should not
increase by more than $\Delta$ in this process.

∎

######  Lemma 6.8.

Let $(\mathbf{x},{\mathbf{p}},\mu)$ be a deterministic mechanism which is weak
UIC and $2$-weak-SCP. Let ${\mathbf{b}}=(b_{1},\ldots,b_{m})$ be an arbitrary
bid vector. Suppose that there exist three different users $i,j,k$ such that
$x_{i}({\mathbf{b}}_{-k},0)=x_{j}({\mathbf{b}}_{-k},0)=1$, and moreover,
$b_{i}-p({\mathbf{b}}_{-k},0)>b_{k}$ and $b_{j}-p({\mathbf{b}}_{-k},0)>b_{k}$.
Then, it must be that $x_{i}({\mathbf{b}})=x_{j}({\mathbf{b}})=1$ and
$p({\mathbf{b}})\leq p({\mathbf{b}}_{-k},0)+b_{k}/2$.

###### Proof.

We first prove that $x_{i}({\mathbf{b}})=x_{j}({\mathbf{b}})=1$. Suppose not,
without loss of generality, let us suppose $x_{i}({\mathbf{b}})=0$ since the
case $x_{j}({\mathbf{b}})=0$ has a symmetric proof. Imagine that the real bid
vector is ${\mathbf{b}}$ which also represents everyone’s true value. Suppose
the miner and user $i$ form a coalition, and they replace user $k$’s bid with
an injected $0$-bid. Due to Lemma 6.7, the miner’s utility decreases by at
most $b_{k}$ as a result. However, user $i$ now becomes confirmed and its
utility is $b_{i}-p({\mathbf{b}}_{-k},0)>b_{k}$. Therefore, the coalition
strictly gains which violates $1$-weak-SCP.

We next prove that $p({\mathbf{b}})\leq p({\mathbf{b}}_{-k},0)+b_{k}/2$. For
the sake of reaching a contradiction, suppose
$p({\mathbf{b}})>p({\mathbf{b}}^{\prime})+b_{i}/2$. Imagine the real bid
vector is ${\mathbf{b}}$ which is also everyone’s true value. In this case,
miner’s utility is $\mu({\mathbf{b}})$, user $i$’s utility is
$b_{i}-p({\mathbf{b}})$, and user $j$’s utility is $b_{j}-p({\mathbf{b}})$.
However, the miner can collude with user $i$ and user $j$, and miner replaces
$b_{k}$ with an injected $0$. Notice that injecting a $0$-bid costs nothing.
In this case, miner’s utility becomes
$\mu({\mathbf{b}}^{\prime})\geq\mu({\mathbf{b}})-b_{k}$, where the inequality
follows from Lemma 6.7. On the other hand, user $i$’s utility becomes
$b_{i}-p({\mathbf{b}}^{\prime})$, and user $j$’s utility becomes
$b_{j}-p({\mathbf{b}}^{\prime})$. Because
$p({\mathbf{b}})>p({\mathbf{b}}^{\prime})+b_{k}/2$, user $i$’s and user $j$’s
utilities each increases more than $b_{k}/2$. Consequently, the coalition’s
joint utility increases, which violates $2$-weak-SCP. ∎

######  Lemma 6.9.

Let $(\mathbf{x},{\mathbf{p}},\mu)$ be a deterministic mechanism which is weak
UIC and $1$-weak-SCP. Let ${\mathbf{b}}=(b_{1},\ldots,b_{m})$ be an arbitrary
bid vector. Let $i$ and $k$ be two different users, and suppose that
$x_{i}({\mathbf{b}})=1$ and $b_{i}-p({\mathbf{b}})>b_{k}$. Then,
$x_{i}({\mathbf{b}}_{-k},0)=1$ and $p({\mathbf{b}}_{-k},0)\leq
p({\mathbf{b}})+b_{k}$.

###### Proof.

For the sake of contradiction, suppose either $x_{i}({\mathbf{b}}_{-k},0)=0$
or $p({\mathbf{b}}_{-k},0)>p({\mathbf{b}})+b_{k}$. Imagine that the real bid
vector is ${\mathbf{b}}^{\prime}:=({\mathbf{b}}_{-k},0)$, which also
represents everyone’s true value. Now, the miner replaces user $k$’s $0$-bid
in ${\mathbf{b}}^{\prime}$ with an injected bid $b_{k}$. Injecting this bid
costs at most $b_{k}$. Due to Lemma 6.7, the miner’s utility cannot decrease,
i.e., $\mu({\mathbf{b}})\geq\mu({\mathbf{b}}^{\prime})$. However, consider
user $i$’s utility. If $x_{i}({\mathbf{b}}^{\prime})=0$ but
$x_{i}({\mathbf{b}})=1$, user $i$’s utility has increased from $0$ to
$b_{i}-p({\mathbf{b}})>b_{k}$. Else, if
$x_{i}({\mathbf{b}}^{\prime})=x_{i}({\mathbf{b}})=1$, but
$p({\mathbf{b}}^{\prime})>p({\mathbf{b}})+b_{k}$, then user $i$’s utility
increases by strictly more than $b_{k}$ too. In either case, the coalition of
the miner and user $i$ can strictly increase their joint utility by replacing
user $k$’s bid with the injected $b_{k}$ bid, which violates $1$-weak-SCP. ∎

######  Lemma 6.10.

Let $(\mathbf{x},{\mathbf{p}},\mu)$ be a deterministic mechanism which is
$2$-user-friendly, weak-UIC and $2$-weak-SCP. Then, there exists a bid vector
${\mathbf{b}}=(b_{1},\ldots,b_{m})$ where two different users $i,j$ are
confirmed, and moreover, $b_{i}>p_{i}({\mathbf{b}})$ and
$b_{j}>p_{j}({\mathbf{b}})$.

###### Proof.

Since $(\mathbf{x},{\mathbf{p}},\mu)$ is 2-user-friendly, there exists a bid
vector ${\mathbf{b}}$ such that at least two users’ bids are confirmed. There
are three possible cases:

  1. 1.

There are two users $i,j$ such that $b_{i}>p_{i}({\mathbf{b}})$ and
$b_{j}>p_{j}({\mathbf{b}})$.

  2. 2.

Only a single confirmed user bids strictly above its payment. Without loss of
generality, we may assume user $j$ is confirmed and
$b_{j}>p_{j}({\mathbf{b}})$; however, for any confirmed user $i\neq j$,
$b_{i}=p_{i}({\mathbf{b}})$, and there exists at least one such $i$.

  3. 3.

For any confirmed bid $b_{i}$, it holds that $b_{i}=p_{i}({\mathbf{b}})$.

The first case is exactly what we want. For the second case, we can raise
$i$’s bid by an arbitrary amount $\Delta>0$, and the new bid vector is
$({\mathbf{b}}_{-i},b_{i}+\Delta)$. By Myerson’s Lemma, $i$ should still be
confirmed and paying the same price. Due to Lemma 6.3, $j$ should still be
confirmed and paying the same price, too. Therefore, the bid vector
$({\mathbf{b}}_{-i},b_{i}+\Delta)$ satisfies the claim we want to prove.
Moreover, due to Lemma 6.3, it must be
$\mu({\mathbf{b}})=\mu({\mathbf{b}}_{-i},b_{i}+\Delta)$.333$\mu({\mathbf{b}})=\mu({\mathbf{b}}_{-i},b_{i}+\Delta)$
is not important for this proof, while this fact will be useful in the proof
of Lemma B.5.

We now focus on the third case which is the trickiest. Due to Lemma 6.4, it
must be that everyone confirmed has the same bid, and thus $b_{i}=b_{j}$. Fix
an arbitrary $\Delta>0$. Consider the bid vector ${\mathbf{b}}^{*}$ which is
the same as ${\mathbf{b}}$ except that user $i$ and user $j$’s bids are
replaced with $b_{i}+\Delta$. We claim that the bid vector ${\mathbf{b}}^{*}$
satisfies the claim we want to prove. In other words,
$x_{i}({\mathbf{b}}^{*})=x_{j}({\mathbf{b}}^{*})=1$ and
$b_{i}+\Delta>p({\mathbf{b}}^{*})$. Suppose this is not the case. There are
three cases:

  1. 1.

both $i$ and $j$ are not confirmed under ${\mathbf{b}}^{*}$;

  2. 2.

exactly one of them is not confirmed under ${\mathbf{b}}^{*}$ — without loss
of generality, we may assume that $j$ is not confirmed under
${\mathbf{b}}^{*}$. In this case, by Lemma 6.6, it must be that
$p_{i}({\mathbf{b}}^{*})=b_{i}+\Delta$;

  3. 3.

both $i$ and $j$ are confirmed under ${\mathbf{b}}^{*}$ but
$b_{i}+\Delta=p({\mathbf{b}}^{*})$.

In all of these cases, user $i$ and $j$ both have utility $0$ if the true
values are ${\mathbf{b}}^{*}$.

Let ${\mathbf{b}}^{\prime}:=({\mathbf{b}}_{-i},b_{i}+\Delta)$. By Lemma 6.7,
$\mu({\mathbf{b}}^{*})\geq\mu({\mathbf{b}}^{\prime})\geq\mu({\mathbf{b}}^{*})-\Delta$.
By Lemma 6.3, $\mu({\mathbf{b}}^{\prime})=\mu({\mathbf{b}})$. Thus,
$\mu({\mathbf{b}}^{*})\geq\mu({\mathbf{b}})\geq\mu({\mathbf{b}}^{*})-\Delta$.444$\mu({\mathbf{b}}^{*})\geq\mu({\mathbf{b}})$
is not important for this proof, while this fact will be useful in the proof
of Lemma B.5. Now, suppose the true values are ${\mathbf{b}}^{*}$. The miner
can collude with users $i$ and $j$, and have them bid $b_{i}=b_{j}$ instead.
Both users $i$ and $j$ are paying $b_{i}$ in this case. Therefore, each of
them has utilty $\Delta$ now. On the other hand, the miner’s utility decreases
by at most $\Delta$, and therefore the coalition’s utility increases. This
violates $2$-weak-SCP. ∎

##### Proof of Theorem 6.1.

By Lemmas 6.4 and 6.10, there exists a bid vector
${\mathbf{b}}=(b_{1},\ldots,b_{m})$ such that
$x_{1}({\mathbf{b}})=x_{2}({\mathbf{b}})=1$, $b_{1}>p({\mathbf{b}})$ and
$b_{2}>p({\mathbf{b}})$ — we can always relabel the bids to make any two
confirmed users with positive utility labeled as users $1$ and $2$.

Let $B$ denote the block size, and we define
$\Gamma=2^{B+8}\cdot|{\mathbf{b}}|_{1}\cdot\max(m,B+1)$ to be a sufficiently
large number. Now, we consider a bid vector
$\mathbf{c}=(c_{1},c_{2},\ldots,c_{m})$, where $c_{1}=c_{2}=\Gamma$ and
$c_{i}=0$ for all $i\geq 3$. We are going to show that
$x_{1}(\mathbf{c})=x_{2}(\mathbf{c})=1$. By the Myerson’s Lemma and Lemma 6.3,
from ${\mathbf{b}}$, we can increase $b_{1}$ without changing the confirmation
and the payment of $b_{1}$ and $b_{2}$, so
$x_{1}(\Gamma,b_{2},\ldots,b_{m})=1$ and $x_{2}(\Gamma,b_{2},\ldots,b_{m})=1$.
Similarly, we can then increase $b_{2}$ and we obtain
$x_{1}(\Gamma,\Gamma,b_{3},\ldots,b_{m})=1$,
$x_{2}(\Gamma,\Gamma,b_{3},\ldots,b_{m})=1$ and
$p(\Gamma,\Gamma,b_{3},\ldots,b_{m})=p({\mathbf{b}})$. Next, we reduce all
remaining bids to zero one by one. Repeatedly applying Lemma 6.9 and observing
that $\Gamma$ is sufficiently large, we have that
$x_{1}(\mathbf{c})=x_{2}(\mathbf{c})=1$, and the payment increases by
$\sum_{i=3}^{m}b_{i}$ at most, so $p(\mathbf{c})\leq
p({\mathbf{b}})+\sum_{i=3}^{m}b_{i}<|{\mathbf{b}}|_{1}$.

Without loss of generality, we may henceforth assume that $m>B$. If not, that
is, if $m<B$, we can always add $0$ bids one by one until there are at least
$B+1$ bids — we claim that this does not change the miner’s utility nor user
$1$ or $2$’s confirmation status and payment. To see this, notice that adding
or removing a $0$-bid is free of charge for the miner or a miner-user
coalition. Therefore, adding or removing a $0$-bid should not change the joint
utility of the miner and user $1$ by $1$-weak-SCP. This implies that user
$2$’s confirmation status and payment should not change, since otherwise, user
$2$’s utility would change, and thus the joint utility of the miner and users
$1$ and $2$ would change. This means that the coalition of the miner and users
$1$ and $2$ can cheat by adding or removing a $0$-bid to increase their joint
utility, thus violating $2$-weak-SCP. By a symmetric argument, user $1$’s
confirmation status or payment should not change either. Now, since the joint
utility of the miner and user $1$ should not change due to adding or removing
a $0$-bid, the miner’s utility should be unaffected too.

Now, we consider another bid vector $\mathbf{d}=(d_{1},d_{2},\ldots,d_{m})$,
where $d_{i}=\Gamma$ for all $i\in[B+1]$ and $d_{i}=0$ for $i>B+1$. We are
going to show that $x_{i}(\mathbf{d})=1$ for all $i\in[B+1]$ — note that this
is sufficient for reaching a contradiction since the block size is only $B$.
To see this, we start from $\mathbf{c}$, and increase the bids of each user
$j\in\\{3,\ldots,m\\}$ one by one. Intuitively, Lemma 6.8 guarantees that if
the payment grows at all during the process, it must grow slower than the
increase in a user’s bid, so at some point, user $j$’s bid will catch up with
the payment, as long as there is still a large enough gap left between
$\Gamma$ and the payment. Formally, since
$\Gamma-p(\mathbf{c})>2|{\mathbf{b}}|_{1}$, by Lemma 6.8, it must be that
$p(\Gamma,\Gamma,2|{\mathbf{b}}|_{1},0,\ldots,0)\leq
p(\mathbf{c})+|{\mathbf{b}}|_{1}<2|{\mathbf{b}}|_{1}$, and
$x_{3}(\Gamma,\Gamma,2|{\mathbf{b}}|_{1},0,\ldots,0)=1$. We now further
increase user $3$’s bid to $\Gamma$, and by Lemma 6.3, users $1$ to $3$ remain
confirmed and $p(\Gamma,\Gamma,\Gamma,0,\ldots,0)<2|{\mathbf{b}}|_{1}$. By the
same reasoning, since
$\Gamma-p(\Gamma,\Gamma,\Gamma,0,\ldots,0)>4|{\mathbf{b}}|_{1}$, by Lemma 6.8,
it must be that $p(\Gamma,\Gamma,\Gamma,4|{\mathbf{b}}|_{1},\ldots,0)\leq
p(\Gamma,\Gamma,\Gamma,0,\ldots,0)+2|{\mathbf{b}}|_{1}<4|{\mathbf{b}}|_{1}$,
and $x_{4}(\Gamma,\Gamma,\Gamma,4|{\mathbf{b}}|_{1},0,\ldots,0)=1$. Therefore,
$p(\Gamma,\Gamma,\Gamma,\Gamma,0,\ldots,0)<4|{\mathbf{b}}|_{1}$. We can now
repeat this process and raise the bid of each user $i\in[B+1]$ to $\Gamma$. It
is not hard to check that our choice of $\Gamma$ is sufficiently large for the
reasoning to go through in all steps.

##  7 Necessity for Blocks to Contain Unconfirmed Transactions

Observe that in our buring second-price auction, not all transactions in the
block are confirmed. In particular, only the top $k$ have a chance of being
confirmed, and remaining $B-k$ included bids are not confirmed. Instead, they
serve the role of setting the price, i.e., they are used by the blockchain to
compute the payment for each confirmed bid and the miner revenue. In the
cryptocurrency community, there is an ongoing debate whether including
unconfirmed transactions in a block is a good idea. The argument against this
approach is that “real estate” on the blockchain is a scarce resource, so we
ideally do not want to waste space including unconfirmed transactions in the
block.

We argue that having unconfirmed transactions in the block indeed can lead to
more versatile mechanisms. To show this, we argue that if “included” must be
equal to “confirmed”, then, even weakly incentive mechanisms are not possible.
More specifically, we prove the following corollary:

######  Corollary 7.1 (Impossibility for “included = confirmed”).

Assume that all transactions included in the block must be confirmed. Then, no
(possibly randomized) TFM $({\bf x},{\bf p},\mu)$ with non-trivial miner
revenue can satisfy weak UIC, weak MIC, and 1-weak-SCP at the same time — this
impossibility holds no matter whether the block size is finite or infinite.

Moreover, if the block size is finite, then the only (possibly randomized) TFM
that achieves weak UIC, weak MIC, and 1-weak-SCP is the trivial mechanism that
always confirms nothing and pays the miner nothing.

##### Myerson’s lemma still holds.

To prove this corollary, an important stepping stone is to prove that
Myerson’s lemma still holds for any weak UIC, weak MIC, and 1-weak-SCP
(randomized) mechanism where “included = confirmed”. It turns out that this is
somewhat non-trivial to prove.

Recall that in a randomized mechanism, the random coins come from two sources:
1) the miner can flip random coins to decide which transactions to include in
the block; 2) once the inclusion choices are made, the blockchain flips random
coins to determine which of the included transactions are confirmed, how much
each confirmed transaction pays, and how much the miner gets. In other words,
the randomness in the inclusion rule is chosen by the miner, whereas the
randomness in the confirmation, payment, and miner-revenue rules are chosen by
the blockchain. A strategic miner may choose its random coins arbitrarily and
not uniformly at random, to increase its expected gain. On the other hand, we
assume that the blockchain’s randomness is trusted. In other words, we assume
that the blockchain can toss fresh random coins that are revealed after the
miner commits to its inclusion decision — this makes our impossibility result
stronger, since if the blockchain’s randomness is revealed to the miner
earlier, it makes mechanism design even harder.

##### Terminology and notation.

Fix an arbitrary bid vector ${\mathbf{b}}=(b_{1},\ldots,b_{m})$. Let
$S\subseteq\\{b_{1},\ldots,b_{m}\\}$ denote a subset of these bids to include
in the block. We often call $S$ an inclusion outcome. Note that if “included =
confirmed”, the miner is essentially choosing which transactions are confirmed
directly, too. Whenever the miner picks an inclusion outcome
$S\subseteq\\{b_{1},\ldots,b_{m}\\}$, it can calculate its expected utility
denoted $\mathbb{E}(\mu|S)$ where the expectation is taken over the choice of
the blockchain’s random coins. We use the notation $\mathbb{E}(\mu)$ to denote
the miner’s expected utility under ${\mathbf{b}}$, had it executed the TFM
honestly.

Fix an arbitrary bid vector ${\mathbf{b}}=(b_{1},\ldots,b_{m})$. We say that
an inclusion outcome $S\subseteq\\{b_{1},\ldots,b_{m}\\}$ is possible (w.r.t.
${\mathbf{b}}$), if it is encountered with non-zero probability in an honest
execution of the TFM over ${\mathbf{b}}$.

######  Lemma 7.2.

Suppose that a randomized TFM satisfies weak MIC, and moreover, any
transaction included in the blockchain must be confirmed. Fix an arbitrary bid
vector ${\mathbf{b}}=(b_{1},\ldots,b_{m})$. For any possible inclusion outcome
$S\subseteq\\{b_{1},\ldots,b_{m}\\}$ it must be that
$\mathbb{E}(\mu|S)=\mathbb{E}(\mu)$.

As a direct corollary, for any possible inclusion outcomes
$S,S^{\prime}\subseteq\\{b_{1},\ldots,b_{m}\\}$ it must be that
$\mathbb{E}(\mu|S)=\mathbb{E}(\mu|S^{\prime})$.

###### Proof.

Suppose that there is a possible inclusion outcome $S$ where
$\mathbb{E}(\mu|S)\neq\mathbb{E}(\mu)$. It must be that there is a possible
inclusion outcome $S^{*}$ where $\mathbb{E}(\mu|S^{*})>\mathbb{E}(\mu)$. In
this case, instead of choosing the miner coins at random as prescribed by the
mechanism, it strictly benefits the miner to choose the specific inclusion
outcome $S^{*}$. This violates weak MIC. ∎

######  Lemma 7.3.

Suppose that a randomized TFM satisfies weak MIC and 1-weak-SCP, and moreover,
any transaction included in the blockchain must be confirmed. Suppose that
under some bid vector ${\mathbf{b}}=(b_{1},\ldots,b_{m})$, there is at least
one possible inclusion outcome that includes $b_{i}$, and at least one
possible inclusion outcome that does not include $b_{i}$. Then, consider any
possible inclusion outcome $S$ that includes $b_{i}$, it must be that
conditioned on $S$, user $i$ pays its full bid $b_{i}$ with probability $1$.

###### Proof.

Suppose that the claim does not hold, i.e., there is a possible inclusion
outcome that includes $b_{i}$, but user $i$ pays $p_{i}<b_{i}$; and moreover,
there is at least one possible inclusion outcome that does not include
$b_{i}$. Let $S^{*}$ be a possible inclusion outcome that includes $b_{i}$
that minimizes the payment of user $i$. In this case, the miner can form a
coalition with user $i$, and the miner can choose the inclusion outcome
$S^{*}$ with probability $1$. Due to weak MIC and Lemma 7.2, the miner’s
utility is still $\mathbb{E}(\mu)$ when it adopts this strategy, i.e., the
same as playing honestly. However, user $i$’s utility is positive and is
maximized under $S^{*}$. Furthermore, since there is at least one possible
inclusion outcome that does not include $b_{i}$ where user $i$’s utility is
$0$, it must be that user $i$’s expected utility is strictly greater under
this strategy than playing honestly. Therefore, the coalition strictly
benefits under this strategy, which violates $1$-weak-SCP. ∎

######  Lemma 7.4.

Suppose that a randomized TFM satisfies weak UIC, weak MIC, and 1-weak-SCP,
and moreover, any included transaction must be confirmed. Then, the TFM must
satisfy the constraints imposed by the Myerson’s Lemma.

###### Proof.

Recall that a mechanism disincentivizes an individual user from overbidding or
underbidding under the old utility notion, we say that it is user-DSIC (short
for dominant- strategy-incentive-compatible). Similarly, if a mechanism
disincentivizes an individual user from overbidding or underbidding under the
new utility notion, we say that it is weakly user-DSIC. Clearly, UIC implies
user-DSIC and weak UIC implies weakly user-DSIC, since in our definitions of
(weak) UIC, the user can misbehave in more ways besides over- or under-
bidding. Since Myerson’s lemma holds for user-DSIC, it suffices to show that
any (randomized) TFM where “included = confirmed” and satisfying weak user-
DSIC, weak MIC, and 1-weak-SCP must also satisfy user-DSIC.

Suppose that this is not true, i.e., there is some TFM where “included =
confirmed” and satisfying weak user-DSIC, weak MIC, and 1-weak-SCP, however,
the TFM does not satisfy user-DSIC. Notice that if a user underbids, its
utility is the same under the old and new utility notions. Therefore, there
must exist a bid vector ${\mathbf{b}}=(b_{1},\ldots,b_{m})$ some user
$j\in[m]$, and a bid $b^{\prime}_{j}>b_{j}$, such that the user $j$ is
incentivized to overbid under the old utility notion, but not incentivized to
overbid under the new utility notion. There are the following cases, and we
rule each one out, which allows us to reach a contradiction. Below we use the
terms “included” and “confirmed” interchangeably, and we define
${\mathbf{b}}^{\prime}:=({\mathbf{b}}_{-j},b^{\prime}_{j})$.

  * •

Case 1: user $j$ is confirmed with probability $1$ under
${\mathbf{b}}^{\prime}$. In this case, user $j$’s utility is the same under
the old and new utility definitions, and therefore, it is not possible that
user $j$ wants to deviate under the old utility but does not want to under the
new utility notion.

  * •

Case 2: user $j$ is unconfirmed with probability $1$ under
${\mathbf{b}}^{\prime}$. In this case, under the old utility, user $j$’s
utility is $0$ even when it bids $b^{\prime}_{j}$. Therefore, user $j$ does
not want to deviate under the old utility notion which contradicts our
assumption.

  * •

Case 3: user $j$ sometimes confirmed and sometimes unconfirmed under
${\mathbf{b}}^{\prime}$. Since the TFM is weak MIC and 1-weak-SCP, and
satisfies “included = confirmed”, by Lemma 7.3, whenever the user $j$ is
confirmed, it must pay its full bid. Therefore, under the old utility notion,
if user $j$ bids $b^{\prime}_{j}$ instead, its utility is always $0$. This
means that the user does not want to deviate under the old utility notion,
which contradicts our assumption.

∎

##### Proof of Corollary 7.1.

We now continue with the proof of Corollary 7.1. The proof of Lemma 4.8 also
makes use of the strategic deviation where a user colluding with the miner
overbids relative to its true value. Specifically, the proof of Lemma 4.8
relies on the fact that such overbidding comes for free if the offending
transaction is not confirmed. In general, this is not true under the new
utility function associated with weak incentive compatibility. However, we now
argue that if “included” must be equal to “confirmed”, then, the effect of
this deviation (where the overbid transaction is not confirmed) can
alternatively be realized in a way that is free of charge.

More concretely, instead of having the colluding user actually carry out the
overbidding, we instead exploit the miner’s ability to include an arbitrary
subset of the mempool in the block. Let ${\bf b}$ be the current mempool,
which includes the colluding user’s bid $b$. If in the proof of Lemma 4.8, the
miner wants the user to overbid $b^{\prime}>b$ instead, it can simply pretend
that the colluding user’s bid is $b^{\prime}$. In other words, the miner can
simulate running the mechanism on ${\bf
b}\backslash\\{b\\}\cup\\{b^{\prime}\\}$. As a result, the transaction
$b^{\prime}$ would not be confirmed, and thus $b^{\prime}$ would not be
included in the block, either. Therefore, the fact that the colluding user has
not authorized/signed the transaction $b^{\prime}$ does not matter in carrying
out this deviation555In other words, $b^{\prime}$ exists only in the
simulation in the miner’s head, but is not released to the public network..

It is easy to see that as long as Myerson’s Lemma holds and any overbid
transaction that is not confirmed in the present block comes for free, Lemma
4.8 still holds. Therefore, we conclude that Lemma 4.8 still holds even under
weak UIC and 1-weak-SCP, if we insist that “included” be equal to “confirmed”.
Now, as long as Lemma 4.8 and Myerson’s Lemma still hold, the proof of Theorem
4.7 follows in the same way as before, and so does the proof of Corollary 4.9.

If we restrict ourselves to deterministic mechanisms, we can actually prove a
counterpart of Corollary 7.1 without having to even rely on weak MIC. This is
formally stated in the following corollary:

######  Corollary 7.5.

Assume that all transactions included in the block must be confirmed. Then, no
deterministic TFM $({\bf x},{\bf p},\mu)$ with non-trivial miner revenue can
satisfy weak UIC and 1-weak-SCP at the same time — this impossibility holds no
matter whether the block size is finite or infinite. Moreover, if the block
size is finite, then the only deterministic TFM that achieves weak UIC and
1-weak-SCP is the trivial mechanism that always confirms nothing and pays the
miner nothing.

###### Proof.

Almost the same as the proof of Corollary 7.1, except that now, since the TFM
is promised to be deterministic, we can use Fact 6.2 instead of Lemma 7.4 to
establish the fact that Myerson’s lemma still holds. ∎

##  8 Conclusion and Open Questions

Mechanism design in decentralized settings (e.g., cryptocurrencies) departs
significantly from the classical literature in terms of modeling and
assumptions, and thus is relatively little understood. For example, our work
shows that even how to formally define incentive compatibility is subtle and
requires careful thought. Our work helps to unravel the mathematical
structures of incentive compatible TFMs, we hope that our definitional
contributions can serve as a basis for future work in this space. Our work
also raises more open questions than the ones we can answer. For example, are
there other reasonable relaxations in the modeling and in incentive compatible
notions that allow us to circumvent the impossibility results we showed? Can
we formally model and reason about the repeated nature of the TFM, and reason
about potential strategic behavior over a longer time scale? Can cryptography
help in the design of transaction fee mechanisms? For example, the elegant
work of Ferreira and Weinberg [FW20] showed that using cryptographic
commitments can help overcome some of the lower bound results shown by
Akbarpour and Li [AL20]. However, as mentioned in Section 2.5, the modeling
approach there is fundamentally incompatible with the setting for transaction
fee mechanisms. Besides these, Roughgarden [Rou20, Rou21b] also presented a
comprehensive list of open questions, most of which remain unanswered.

## Acknowledgments

We gratefully acknowledge helpful technical discussions with Kai-Min Chung
during an early phase of the project. We also thank T-H. Hubert Chan for
insightful technical discussions.

## References

  * [AL20] Mohammad Akbarpour and Shengwu Li.  Credible auctions: A trilemma.  Econometrica, Econometric Society, 2020.
  * [BEOS19] Soumya Basu, David A. Easley, Maureen O’Hara, and Emin Gün Sirer.  Towards a functional fee market for cryptocurrencies.  CoRR, abs/1901.06830, 2019.
  * [BSKN21] Adithya Bhat, Nibesh Shrestha, Aniket Kate, and Kartik Nayak.  Randpiper - reconfiguration-friendly random beacons with quadratic communication.  In ACM CCS, 2021.
  * [CKS00] Christian Cachin, Klaus Kursawe, and Victor Shoup.  Random oracles in constantinople: Practical asynchronous byzantine agreement using cryptography.  In in Proc. 19th ACM Symposium on Principles of Distributed Computing (PODC, pages 123–132, 2000.
  * [CM12] Jing Chen and Silvio Micali.  Collusive dominant-strategy truthfulness.  J. Econ. Theory, 147(3):1300–1312, 2012.
  * [DKIR21] Sourav Das, Vinith Krishnan, Irene Miriam Isaac, and Ling Ren.  Spurt: Scalable distributed randomness beacon with transparent setup.  Cryptology ePrint Archive, Report 2021/100, 2021.  https://ia.cr/2021/100.
  * [DM17] Alan Deckelbaum and Silvio Micali.  Collusion, efficiency, and dominant strategies.  Games Econ. Behav., 103:83–93, 2017.
  * [FMPS21] Matheus V. X. Ferreira, Daniel J. Moroz, David C. Parkes, and Mitchell Stern.  Dynamic posted-price mechanisms for the blockchain transaction-fee market.  CoRR, abs/2103.14144, 2021.
  * [FW20] Matheus V. X. Ferreira and S. Matthew Weinberg.  Credible, truthful, and two-round (optimal) auctions via cryptographic commitments.  In Proceedings of the 21st ACM Conference on Economics and Computation (EC), page 683–712, 2020.
  * [GH05] Andrew V. Goldberg and Jason D. Hartline.  Collusion-resistant mechanisms for single-parameter agents.  In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, January 23-25, 2005, pages 620–629. SIAM, 2005.
  * [GHK+06] Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin, Michael E. Saks, and Andrew Wright.  Competitive auctions.  Games Econ. Behav., 55(2):242–269, 2006.
  * [GL79] Jerry Green and Jean-Jacques Laffont.  On coalition incentive compatibility.  The Review of Economic Studies, 46(2):243–254, 04 1979.
  * [Har] Jason Hartline.  Lectures on optimal mechanism design.  http://users.eecs.northwestern.edu/~hartline/omd.pdf.
  * [kCK09] Yeon koo Che and Jinwoo Kim.  Optimal collusion-proof auctions.  Journal of Economic Theory, pages 565–603, 2009.
  * [LSZ19] Ron Lavi, Or Sattath, and Aviv Zohar.  Redesigning bitcoin’s fee market.  In The World Wide Web Conference, WWW 2019, San Francisco, CA, USA, May 13-17, 2019, pages 2950–2956. ACM, 2019.
  * [MM12] Robert C. Marshall and Leslie M. Marx.  The Economics of Collusion: Cartels and Bidding Rings.  The MIT Press, 2012.
  * [Mon20] Barnabe Monnot.  A transaction fee market proposal.  https://github.com/ethereum/rig/blob/master/eip1559/eip1559.ipynb, 2020\.
  * [Mye81] Roger B. Myerson.  Optimal auction design.  Math. Oper. Res., 6(1):58–73, February 1981.
  * [NRTV07] Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani.  Algorithmic Game Theory.  Cambridge University Press, USA, 2007.
  * [Rou20] Tim Roughgarden.  Transaction fee mechanism design for the Ethereum blockchain: An economic analysis of EIP-1559.  Manuscript, https://timroughgarden.org/papers/eip1559.pdf, 2020\.
  * [Rou21a] Private communication with Tim Roughgarden and Matt Weinberg, 2021.
  * [Rou21b] Tim Roughgarden.  Transaction fee mechanism design.  In EC, 2021.
  * [Vic61] William Vickrey.  Counterspeculation, auctions, and competitive sealed tenders.  Journal of finance, 1961.
  * [Yao18] Andrew Chi-Chih Yao.  An incentive analysis of some bitcoin fee designs.  CoRR, abs/1811.02351, 2018.

##  Appendix A Relations Between Incentive Compability Notions

The notions UIC, MIC, and $1$-SCP are incomparable as depicted in Figure 2.

UICMIC$1$-SCP$\backslash$second-pricd$\backslash$first-
price$\backslash$second-price$\backslash$first-price$\backslash$posted-price
(no burning)$\backslash$1st-price-or-free Figure 2: Relationship among
incentive compatibility notions. The same chart holds for UIC, MIC, and
$1$-SCP under $\gamma$-strict-utility for any $\gamma\in[0,1]$.

We explain Figure 2 in more detail below:

  * •

UIC $\not\Rightarrow$ MIC, UIC $\not\Rightarrow$ $1$-SCP: the second-price
auction satisfies UIC, but does not satisfy MIC or $1$-SCP. This was pointed
out in several earlier works [BEOS19, Rou20, Rou21b]. Recall that in the
second-price auction, the highest $B$ bids are included in the block, the top
$B-1$ are confirmed and they pay the $B$-th price, where $B$ is the block
size. The miner gets all payment.

  * •

MIC $\not\Rightarrow$ UIC, $1$-SCP $\not\Rightarrow$ UIC: the first-price
auction satisfies MIC and $c$-SCP for any $c\geq 1$, but is not UIC. This was
also pointed out in earlier works [BEOS19, Rou20, Rou21b]. Recall that in the
first-price auction, the top $B$ bids are included and confirmed, they each
pay their bid, and the miner gets all payment.

  * •

MIC $\not\Rightarrow$ $1$-SCP: the posted price auction satisfies MIC but not
$1$-SCP. Recall that in the posted-price auction, there is a fixed reserve
price $r$. Everyone bidding at least $r$ is included and confirmed and pays
exactly $r$. The miner gets all payment. It is easy to check that the
mechanism is indeed MIC. However, it is not $1$-SCP, since if a user’s true
value is $0<r^{\prime}<r$, the miner can collude with the user, have the user
bid $r$ instead, and the joint utility of the coalition strictly increases.

  * •

$1$-SCP $\not\Rightarrow$ MIC: this is the most subtle to see. We construct
the following “first-price-or-free” mechanism which is $c$-SCP for any $c\geq
1$, but not MIC. The mechanism is not MIC since if there is only one bid, it
makes sense for the miner to inject a fake bid to increase its utility. We
show that the mechanism satisfies $c$-SCP for any $c\geq 1$ below.

First-price-or-free mechanism • Choose all bids in the current bid vector to
include in the block. Let ${\mathbf{b}}=(b_{1},\ldots,b_{m})$ be the included
bids of the block, where $b_{1}\geq\cdots\geq b_{m}$. • Only the highest bid
($b_{1}$) is confirmed. Every other bid is unconfirmed. • If there is only one
bid in the block ($m=1$), the only confirmed user pays nothing. Otherwise, if
$m\geq 2$, the only confirmed user pays $b_{1}$. • The miner gets all the
payment.

######  Theorem A.1.

The first-price-or-free mechanism is $c$-SCP for all $c\geq 1$.

###### Proof.

Suppose there is only one user with true value $v^{*}$. The miner and that
user is the only possible coalition. If they play honestly, that user’s bid is
the only bid in the block, so it must be confirmed. Thus, in the honest case,
the joint utility is $v^{*}$. If the coalition now deviates, then the
confirmed bid is either a fake bid or the colluding user’s bid. In either
case, the coalition’s utility cannot exceed $v^{*}$.

Suppose the number of users is $m\geq 2$. There are two cases. First, suppose
the highest bid $b_{1}$ does not belong to the coalition if all colluding
users are bidding truthfully. In this case, the coalition’s utility is $b_{1}$
when it behaves honestly, and $b_{1}\geq v^{*}$ where $v^{*}$ denotes the
highest true value of any colluding user. Second, the highest bid $b_{1}$
belongs to the coalition if colluding users are bidding truthfully. In this
case, the coalition’s utility is $b_{1}=v^{*}$ if it behaves honestly. In
either case, we show that if the coalition deviates, it cannot gain. Suppose
$b^{\prime}_{1}$ is the new highest bid after deviating. If $b^{\prime}_{1}$
belongs to the coalition, then the miner revenue offsets the coalition’s
payment, and thus the coalition’s utility cannot exceed the highest true value
of any colluding user. If $b^{\prime}_{1}$ does not belong to the coalition,
it must be that $b^{\prime}_{1}\leq b_{1}$, and the coalition’s utility is
$b^{\prime}_{1}\leq b_{1}$.

∎

##### Relationship for incentive compatibility notions under $\gamma$-strict-
utility.

Note that in Figure 2, for each arrow $X\not\Rightarrow Y$ shown by some
example mechanism, it is easy to check that the same mechanism also shows that
$X\not\Rightarrow\text{weak }Y$. Thus, Figure 2 in fact also holds for UIC,
MIC, and $1$-SCP under $\gamma$-strict-utility, for any choice of
$\gamma\in[0,1]$.

##  Appendix B Additional Results for Weak Incentive Compatibility

In this section, we present some additional results that further unfold the
mathematical landscape of weakly incentive compatible mechanisms.

###  B.1 The Solitary Mechanism

Earlier in Section 6, we ruled out the existence of a deterministic, 2-user-
friendly mechanism that satisfies weak UIC and 2-weak-SCP simultaneously,
assuming finite block size. In this section, we show that the 2-user-friendly
restriction is necessary for this theorem to hold. In particular, we describe
a mechanism called the solitary mechanism, which always confirms a single
transaction, and satisfies weak UIC, weak MIC, and $c$-weak-SCP for all
$c\in\mathbb{N}$.

The solitary mechanism • Choose the highest two bids to include in the block.
• Only the highest bid is confirmed. Other bids are all unconfirmed. The
highest bid pays the second highest bid, and the miner is paid the second
highest bid.

######  Theorem B.1 (The solitary mechanism).

The solitary mechanism satisfies weak UIC, weak MIC, and $c$-weak-SCP for all
$c>0$. The theorem holds no matter the block size is infinite or finite.

###### Proof.

We prove the three properties one by one.

##### Weak UIC.

A user has two kinds of strategies to deviate from the honest behavior: to bid
strategically or to inject fake transactions. Since the payment is decided by
the second highest bid, injecting fake transactions can only increase the
payment, no matter whether the user is bidding truthfully or not. Moreover,
since this is exactly a classical second-price auction, bidding truthfully is
known to be DSIC for an individual user, even under the old utility notion
where overbidding is never penalized. Therefore, bidding untruthfully is not
incentive compatible under the new utility notion as well.

##### Weak MIC.

The miner has two kinds of strategies to deviate from honest behavior: not to
choose the highest two bids and to inject fake bids. Without loss of
generality, we assume that the miner chooses the included bids first, and
replaces some of them with fake bids then. We will show that both steps would
not increase the miner’s utility.

The miner’s revenue is decided by the second highest bid that is included, so
if miner does not choose the highest two bids to include, its revenue can only
decrease or remain the same. Next, suppose that the miner replaces one or both
of the included bids with fake ones. If after the replacement, the highest bid
is a fake one, then the miner has to pay the fee for the highest bid which is
equal to its revenue. Therefore, the miner’s utility cannot be greater than
$0$. If after the replacement, the highest bid is not a fake one but the
second highest bid is a fake one, and the bid amount is $b$. Then, the miner
revenue is $b$. However, the cost to inject the fake bid $b$ is also $b$.
Thus, the miner does not gain overall.

##### Weak $c$-SCP.

Consider an arbitrary coalition of the miner and a subset of the users.
Suppose the coalition plays honestly:

  * •

if the top confirmed bidder is in the coalition, the coalition’s utility is
top bidder’s true value denoted $v_{1}$;

  * •

if the top confirmed bidder is not in the coalition, then the coalition’s
utility is the true value of the 2nd bidder $v_{2}\leq v_{1}$.

Now, consider an arbitrary strategy where two bids are included and the higher
of the two gets confirmed. Each included bid can either come from some user,
or is a fake bid. Without loss of generality, we may equivalently assume that
a fake bid belongs to some imaginary user which belongs to the coalition, and
its true value is $0$. We may use the fake indices $0$ and $-1$ to refer to
the one or two imaginary users. There are the following cases:

  * •

Case 1: The confirmed user $i$ belongs to the coalition. In this case, the
coalition’s utility is upper bounded by (the possibly imaginary) user $i$’s
true value $v_{i}$. If $i$ has the highest true value, it means the
coalition’s utility is upper bounded by $v_{1}$; else if $i$ does not have the
highest true value, it means that the coalition’s utility is upper bounded by
$v_{2}$. Either way, the coalition’s utility cannot exceed the aforementioned
honest case.

  * •

Case 2: The confirmed user $i$ does not belong to the coalition. In this case,
suppose that the included but unconfirmed user is denoted $j$ where $j$ is
possibly an imaginary user. The coalition’s utility is
$b_{j}-\max(0,b_{j}-v_{j})\leq v_{j}$ where $b_{j}$ is user $j$’s bid, $v_{j}$
is its true value, and the part $\max(0,b_{j}-v_{j})$ is the penalty due to
overbidding. Since the confirmed user $i$ does not belong to the coalition, it
must be a real user and it must be bidding its truthful value, i.e.,
$b_{i}=v_{i}$. Note that the $b_{j}$ cannot be bidding higher than $b_{i}$
since $b_{j}$ is unconfirmed but $b_{i}$ is confirmed. Therefore, $v_{j}\leq
b_{j}\leq b_{i}=v_{i}$. This also implies that that $v_{j}\leq v_{2}$, and
thus the coalition’s utility is also upper bounded by $v_{2}$. Recall that the
coalition’s utility is at least $v_{2}$ had it played honestly; therefore, the
coalition does not gain anything in comparison with playing honestly.

∎

###  B.2 The Solitary-Or-Posted-Price Mechanism

Earlier in Section 6, we ruled out the existence of a deterministic, 2-user-
friendly mechanism that satisfies weak UIC and 2-weak-SCP simultaneously,
assuming finite block size. In this section, we show that the finite block
size restriction is necessary for this lower bound to hold, by showing a
deterministic, 2-user-friendly mechanism that satisfies weak UIC, weak MIC,
and 2-weak-SCP, but only under infinite block size.

The solitary-or-posted price mechanism

##### Parameters:

a reserve price $r$.

##### Mechanism:

• Choose the top two bids as well as every other bid that is at least $r$ to
include in the block. • Every bid at least $r$ is confirmed, and the highest
bid in the block is always confirmed (even if it is smaller than $r$). • Let
$b_{2}$ be the second highest bid in the block. Every confirmed bid pays
$\min(b_{2},r)$, and miner is paid $\min(b_{2},r)$. The remaining payment is
burnt.

######  Theorem B.2 (Solitary-or-posted-price mechanism).

Suppose the block size is infinite. The solitary-or-posted-price mechanism
satisfies weak UIC, weak MIC, and $c$-weak-SCP for all $c>0$.

###### Proof.

We prove the three properties one by one.

##### Weak UIC.

A user has two kinds of strategies to deviate from the honest behavior: to bid
strategically or to inject fake transactions. Since the payment is decided by
$\min(b_{2},r)$, injecting fake transactions can only increase the payment, no
matter whether the user is bidding truthfully or not.

Suppose the real bid vector is ${\mathbf{b}}=(b_{1},\ldots,b_{m})$, where
$b_{1}\geq\cdots\geq b_{m}$. Suppose user $i$ bids truthfully and other users
may bid arbitrarily. Let $v_{i}$ and $b^{\prime}_{i}$ be user $i$’s true value
and strategic bid, respectively.

  * •

Case 1: $b_{2}\geq r$. User $i$ is facing a posted-price auction such that it
if confirmed if and only if $b^{\prime}_{i}\geq r$. In this case, it is not
hard to see that no matter user $i$ overbids or underbids, its utility does
not increase.

  * •

Case 2: $b_{2}<r$. When $v_{i}=b_{1}$, then user $i$’t utility is
$v_{i}-b_{2}\geq 0$ in the honest case. If user $i$ overbids, it still pays
$b_{2}$ so the utility does not change. If user $i$ underbids, it is either
confirmed with the same payment, or becomes unconfirmed. In either case, the
utility does not increase.

##### Weak MIC.

The miner has two strategies to deviate: not to choose the highest two bids
and to inject fake bids. Without loss of generality, we assume that the miner
chooses the included bids first, and replaces some of them with fake bids
then. We will show that both steps would not increase the miner’s utility. The
miner’s revenue is decided by the second highest bid that is included, so if
miner does not choose the highest two bids to include, its revenue can only
decrease or remain the same.

Now, suppose the miner replaces some of the included bids with fake ones. If
any fake bid is confirmed, then the fake bid must be paying an amount equal to
the miner revenue, and thus the miner’s utility is at most $0$. If no fake bid
is confirmed, and some fake bid is unconfirmed and its bid amount is $b$.
Then, it must be that $b$ is the second highest bid and the highest bid is
smaller than $r$. In this case, the miner gets revenue $b$; however, it costs
$b$ to inject this fake bid. Thus, the miner does not gain overall.

##### Weak $c$-SCP.

Suppose there are $m$ users, and their true values are $(v_{1},\ldots,v_{m})$
where $v_{1}\geq\cdots\geq v_{m}$. Henceforth, we also call the user with the
highest true value $v_{1}$ the top user. There are two possible cases.

  * •

Case 1: $v_{2}<r$. When everyone behaves honestly, the miner’s revenue is
$v_{2}$, user $1$’s utility is $v_{1}-v_{2}$, and all other users are zero
since they are unconfirmed. Suppose the miner colludes with a subset of users,
and they prepare a bid vector $\mathbf{e}=(e_{1},\ldots,e_{m})$ where
$e_{1}\geq\cdots\geq e_{m}$. Each bid $e_{i}$ in $\mathbf{e}$ is either a non-
colluding bid coming from a non-coalition user in which case $e_{i}=v_{i}$, or
it is a colluding bid, i.e., one that comes from a colluding user or a fake
bid. If only one user $i$ is confirmed in $\mathbf{e}$, there are two
possibilities.

    * –

Suppose user $i$ is not in the coalition. The utility of the coalition is
miner’s revenue ($e_{2}$) minus potential extra cost if there are overbid or
fake bids that are unconfirmed. If $i$ is not the top user, then $e_{2}\leq
v_{i}\leq v_{2}$. This means the utility of the coalition cannot exceed
$v_{2}$, which can be achieved by playing honestly.

If $i$ is top user, to make the miner’s revenue larger than the honest case,
it must be that $e_{2}$ is a colluding bid and $e_{2}>v_{2}$. Let $v^{\prime}$
be the true value of this colluding user or $v^{\prime}=0$ if $e_{2}$ is fake.
Since $e_{2}$ is unconfirmed in $\mathbf{e}$, its utility becomes
$v^{\prime}-e_{2}$. Thus, the utility of the coalition cannot exceed
$v^{\prime}\leq v_{2}$, which can be achieved by playing honestly.

    * –

Suppose user $i$ is in the coalition. The utility of the coalition is $v_{i}$
minus potential extra cost. However, if top user is also in the coalition, the
utility of the coalition is $v_{1}$ in the honest case, and is at most
$v_{i}\leq v_{1}$ in the strategic case. If the top user is not in the
coalition, the utility of the coalition is $v_{2}$ in the honest case, and is
at most $v_{i}\leq v_{2}$ in the strategic case.

If there are two or more confirmed bids in $\mathbf{e}$, the miner’s revenue
becomes $r$, while each confirmed user needs to pay $r$. In this case, the
utility of the top user decreases by $r-v_{2}$. The utilities of all other
bids (including fake ones) are non-positive, since if they are confirmed, they
have to pay $r$ which is higher than their true values. Since $v_{2}<r$, there
must be a colluding user (that is not the top user) bidding $b^{\prime}\geq r$
or the miner injects a fake bid $b^{\prime}\geq r$. Let $v^{\prime}$ be the
true value of this colluding user or $v^{\prime}=0$ if the bid is fake. The
utility of this bid is $v^{\prime}-r$. The joint utility of this colluding or
fake bid and the miner is $v^{\prime}\leq v_{2}$, so the joint utility does
not increase.

  * •

Case 2: $v_{2}\geq r$. When everyone behaves honestly, the miner’s utility is
$r$, user $i$’s utility is $v_{i}-r$ for all confirmed user $i$, and all other
users are zero since they are unconfirmed. In this case, miner’s utility is
already maximized. Suppose the miner colludes with a subset of users, and they
prepare a bid vector $\mathbf{e}$. If there is only one confirmed bid in
$\mathbf{e}$, then only the confirmed user can benefit by the deviation since
its payment decreases. However, the amount that the confirmed user gains is
exactly what the miner loses, so the joint utility of any coalition does not
increase. If there are two or more confirmed bids in $\mathbf{e}$, then every
user’s utility is maximized when they bid truthfully, since the payment is
fixed at $r$ regardless of others’ bids.

∎

###  B.3 Necessity of Burning

Earlier in Section 6, we ruled out the existence of a deterministic, 2-user-
friendly mechanism that satisfies weak UIC and 2-weak-SCP simultaneously,
assuming finite block size. In this section, we show that if the mechanism is
not allowed to use a burning mechanism, i.e., if the miner’s payment must be
the sum of all users’ payment, then, the same lower bound would hold even
under infinite block size. This lower bound also shows that the burning in the
solitary-or-posted-price mechanism is necessary.

######  Theorem B.3.

Let $(\mathbf{x},{\mathbf{p}},\mu)$ be a deterministic mechanism without
burning. If $(\mathbf{x},{\mathbf{p}},\mu)$ is 2-user-friendly, then it cannot
achieve UIC and $2$-weak-SCP at the same time.

The remainder of this section will focus on proving Theorem B.3. We first
prove a useful lemma that says in a mechanism satisfying the desired
properties, if in some bid vector, all unconfirmed bids are bidding $0$, then
all confirmed bids must be paying $0$.

######  Lemma B.4.

Let $(\mathbf{x},{\mathbf{p}},\mu)$ be a deterministic mechanism without
burning that is weak UIC and $2$-weak-SCP. Suppose there exists a bid vector
${\mathbf{b}}=(b_{1},\ldots,b_{m})$ that confirms at least one bid, and
moreover, all unconfirmed bids are $0$. Then, all confirmed bids must pay $0$.

###### Proof.

Due to Lemma 6.4, let $p:=p({\mathbf{b}})$ denote the universal payment for
${\mathbf{b}}$. Let $\epsilon<p/2m$ be a sufficiently small positive number.
By Lemma 6.3 and Myerson’s Lemma, we can change all confirmed bids in
${\mathbf{b}}$ to $p+\epsilon$ such that all confirmed bids in ${\mathbf{b}}$
remain confirmed, and their payment unaffected. Let ${\mathbf{b}}^{\prime}$ be
the resulting bid vector, and let $u\in[m]$ be the number of confirmed users
in ${\mathbf{b}}^{\prime}$, and recall all unconfirmed users bid $0$. Since
there is no burning, $\mu({\mathbf{b}}^{\prime})=u\cdot p$. Let $i$ be a
confirmed user in ${\mathbf{b}}^{\prime}$. Now, suppose that the real bid
vector is actually
${\mathbf{b}}^{\prime\prime}:=({\mathbf{b}}^{\prime}_{-i},p-\epsilon)$, and
this also represents everyone’s true value. User $i$ becomes unconfirmed in
${\mathbf{b}}^{\prime\prime}$ by Myerson’s Lemma. Thus
$\mu({\mathbf{b}}^{\prime\prime})\leq(p+\epsilon)\cdot(u-1)$. In this case,
the miner can collude with user $i$ and ask it to bid $p+\epsilon$ instead. In
this case, user $i$’s utility is $-\epsilon$, however, the miner’s revenue is
$p\cdot u>\mu({\mathbf{b}}^{\prime\prime})+\epsilon$. Thus, the coalition can
strictly gain from this deviation, which violates $1$-weak-SCP.

∎

######  Lemma B.5.

Let $(\mathbf{x},{\mathbf{p}},\mu)$ be a deterministic mechanism without
burning which is $2$-user-friendly, weak-UIC, $2$-weak-SCP, and with non-
trivial miner revenue. Then, there exists a bid vector
${\mathbf{b}}=(b_{1},\ldots,b_{m})$ where two different users $i,j$ are
confirmed, and moreover, $\mu({\mathbf{b}})>0$, $b_{i}>p_{i}({\mathbf{b}})$
and $b_{j}>p_{j}({\mathbf{b}})$.

###### Proof.

It suffices to show that there exists a bid vector ${\mathbf{b}}$ such that
$\mu({\mathbf{b}})>0$ and at least two users’ bids are confirmed. If so, we
can use the same argument in the proof of Lemma 6.10 to show that there exists
a bid vector ${\mathbf{b}}^{\prime}$ such that $\mu({\mathbf{b}}^{\prime})>0$,
and moreover at least two users’ bids are confirmed, and they are both bidding
strictly higher than their payment. In particular, cases 1 and 2 follow just
like the proof of Lemma 6.10. For case 3, suppose that ${\mathbf{b}}$ is a bid
vector such that $\mu({\mathbf{b}})>0$ and two different users $i$ and $j$ are
confirmed, and both bid exactly their payment. In this case, the proof of
Lemma 6.10 constructed a new bid vector ${\mathbf{b}}^{\prime}$ which is
otherwise equal to ${\mathbf{b}}$ except that $b_{i}$ and $b_{j}$ now bid
$b_{i}+\Delta$ for an arbitrary $\Delta>0$, and showed that under
${\mathbf{b}}^{\prime}$, both $i$ and $j$ are confirmed and bidding strictly
above payment. Here, we only need to additionally argue that
$\mu({\mathbf{b}}^{\prime})>0$. This can be achieved by choosing $\Delta$ to
be sufficiently small, and then applying Lemma 6.7.

Therefore, below, we focus on proving that there exists a bid vector
${\mathbf{b}}$ such that $\mu({\mathbf{b}})>0$ and at least two users’ bids
are confirmed. Suppose this is not true. In other words, for any bid vector
${\mathbf{b}}$ satisfying $\mu({\mathbf{b}})>0$, only one user is confirmed.
We will show that this contradicts $2$-weak-SCP.

Since the mechanism is $2$-user-friendly, Lemma 6.10 guarantees that there
exists a bid vector $\mathbf{c}=(c_{1},\ldots,c_{m})$ such that
$x_{1}(\mathbf{c})=x_{2}(\mathbf{c})=1$ and $c_{1}>p(\mathbf{c})$ and
$c_{2}>p(\mathbf{c})$. By our assumption, it must be $\mu(\mathbf{c})=0$.
Because there is no burning, we have $p(\mathbf{c})=0$. By Lemma 6.3, we can
increase user $1$’s and user $2$’s bids arbitraily without changing their
confirmation and payment. As a result, we obtain
$\mathbf{c}^{\prime}=(\Gamma,\Gamma,c_{3},\ldots,c_{m})$, where
$\Gamma=|\mathbf{c}|_{1}$. By Lemma 6.9, we can now reduce each bid
$b_{3},\ldots,b_{m}$ down to zero one by one, without changing user $1$’s and
user $2$’s confirmation. Formally, we obtain a bid vector
$\mathbf{c}^{\prime\prime}=(\Gamma,\Gamma,0,\ldots,0)$ such that
$x_{1}(\mathbf{c}^{\prime\prime})=x_{2}(\mathbf{c}^{\prime\prime})=1$. By our
assumption, both confirmed users in $\mathbf{c}^{\prime\prime}$ are paying
$0$.

Since the mechanism has non-trivial miner revenue, there must exist a bid
vector ${\mathbf{b}}$ where $\mu({\mathbf{b}})>0$. By our assumption, only one
user denoted $i$ is confirmed in ${\mathbf{b}}$. By Lemma B.4, there must be
another user $j$ bidding non-zero. Suppose ${\mathbf{b}}$ also represents
everyone’s true value. In this case, miner’s utility is $\mu({\mathbf{b}})$,
user $i$’s utility is $b_{i}-\mu({\mathbf{b}})$, and user $j$’s utility is
zero. The miner can collude with user $i$ and user $j$, and ask them to bid
$\Gamma$ instead. Then, the coalition prepares a bid vector
$\mathbf{c}^{\prime\prime}=(\Gamma,\Gamma,0,\ldots,0)$ where the first two
bids are user $i$ and user $j$’s bids. In this case, the miner’s utility is
zero, while user $i$’s utility is $b_{i}$ and user $j$’s utility is $b_{j}$.
The joint utility increases by $b_{j}>0$, which violates $2$-weak-SCP. ∎

##### The proof of Theorem B.3.

By Lemma 6.4 and Lemma B.5, there exists a bid vector
${\mathbf{b}}^{(0)}=(b_{1},\ldots,b_{m})$ such that
$\mu({\mathbf{b}}^{(0)})>0$,
$x_{1}({\mathbf{b}}^{(0)})=x_{2}({\mathbf{b}}^{(0)})=1$,
$b_{1}>p({\mathbf{b}}^{(0)})$ and $b_{2}>p({\mathbf{b}}^{(0)})$ — note that we
can always relabel the bids to make the first two bids represent two confirmed
bids.

Now, one by one, we reduce every unconfirmed bid down to zero and increase
every confirmed bid to a sufficiently large value $\Gamma>|{\mathbf{b}}|_{1}$.
Formally, for $i=1,\ldots,m$, we define

${\mathbf{b}}^{(i)}=\left\\{\begin{matrix}({\mathbf{b}}^{(i-1)}_{-i},0),&\text{
if }x_{i}({\mathbf{b}}^{(i-1)})=0,\\\
({\mathbf{b}}^{(i-1)}_{-i},\Gamma),&\text{ if
}x_{i}({\mathbf{b}}^{(i-1)})=1.\end{matrix}\right.$

By Lemma 6.3, when increasing user $1$’s and user $2$’s bids, their
confirmation, payment, and miner revenue do not change. Later on, when
increasing any confirmed user $i$’s bid where $i>2$, any previous user bidding
$\Gamma$ would still remain confirmed and pay the same. When decreasing any
unconfirmed user $i$’s bid to $0$ where $i>2$, since $\Gamma$ is sufficiently
large, and by Lemma 6.9, any previous user bidding $\Gamma$ would remain
confirmed, and although their payment may change, change in the payment is
slow. Thus, at the end, users $1$ and $2$ are confirmed in the final vector
${\mathbf{b}}^{(m)}$.

By Lemma B.4 and the fact that there is no burning, it must be that
$\mu({\mathbf{b}}^{(m)})=0$. Let $i^{*}$ be the smallest integer
$i\in\\{1,\ldots,m\\}$ such that $\mu({\mathbf{b}}^{(i)})=0$. Then, we have
$\mu({\mathbf{b}}^{(i^{*}-1)})>0$ and $\mu({\mathbf{b}}^{(i^{*})})=0$. By
Lemma 6.3, increasing a confirmed user’s bid does not change miner revenue, so
user $i^{*}$ must be unconfirmed in ${\mathbf{b}}^{(i^{*}-1)}$. Imagine the
real bid vector is ${\mathbf{b}}^{(i^{*}-1)}$ which also represents everyone’s
true value. In this case, the miner’s revenue is
$\mu({\mathbf{b}}^{(i^{*}-1)})$, user $1$’s utility is
$\Gamma-p({\mathbf{b}}^{(i^{*}-1)})$, and user $i^{*}$’s utility is zero. The
miner can collude with user $1$ and user $i^{*}$, and ask user $i^{*}$ to bid
$\Gamma$ instead. The coalition now prepares a bid vector
$\mu({\mathbf{b}}^{(i^{*})})$ where the second coordinate $\Gamma$ actually
comes from user $i^{*}$ and $b_{i^{*}}=0$ is a fake bid injected by the miner.
Since there is no burning and $\mu({\mathbf{b}}^{(i^{*})})=0$, the payment
must be zero. Therefore, the miner’s revenue becomes zero, while user $1$’s
utility becomes $\Gamma$, and user $i^{*}$’s utility becomes $b_{i^{*}}$. By
Lemma 6.7, we have $b_{i^{*}}\geq\mu({\mathbf{b}}^{(i^{*}-1)})$, and thus the
coalition strictly gains from this deviation, which violates $2$-weak-SCP.


assume that families are irreducible. Observe that, for $H\in K[x,y,z]$ and
$\mathcal{F}:=\\{(f_{1}(t):f_{2}(t):f_{3}(t))\\}_{m(t)}$ irreducible,
$H(f_{1},f_{2},f_{3})\neq 0$ mod $m(t)$ iff $H$ does not vanish at any point
in the family $\mathcal{F}$. Moreover, if $\mathcal{F}$ is irreducible, then
$K_{m}:=K[t]/\\!<\\!m\\!>$ is an integral domain, and we can see
$(f_{1}(t):f_{2}(t):f_{3}(t))$ as a single point in the curve defined by
$G^{h}$ over $\overline{K_{m}}$. Let us denote this curve by
$\mathcal{C}(G^{h}_{\mathcal{F}})$. In that situation, by abuse of notation,
we will say that $\mathcal{F}$ is a point of
$\mathcal{C}(G^{h}_{\mathcal{F}})$ meaning that
$(f_{1}(t):f_{2}(t):f_{3}(t))\in\mathcal{C}(G^{h}_{\mathcal{F}})$.

In [30] it is proved that the singular locus of $\mathcal{C}(G^{h})$ can be
decomposed as a finite union of irreducible families of $K$-conjugate points
such that in each family the multiplicity and the singularity character (i.e.
whether the singularity is ordinary or non–ordinary) is preserved. The set of
all conjugate families appearing in the union above is called a $K$–standard
decomposition of the singular locus of $\mathcal{C}(G^{h})$, or of
$\mathcal{C}(G)$. In the following, we describe a process to determine a
$K$–standard decomposition of the singular locus; see also [30] page 83.
First, we introduce the notion of regular position:

######  Definition A.3.

We say that the affine plane curve $\mathcal{C}(G)$ is in regular position
w.r.t. $x$ if

  1. (1)

the coefficient of $y^{\deg(G)}$ in $G$ is a non-zero constant; and

  2. (2)

$G(a,b_{i})=G_{x}(a,b_{i})=0$ with $i\in\\{1,2\\}$ implies that $b_{1}=b_{2}$.

If $\mathcal{C}(G)$ is not in regular position, we may apply a linear change
of coordinates over $\mathbb{K}$ such that $G$ is transformed into regular
position (see e.g. Lemma 2 in [10]). More precisely, for this purpose, one may
perform a change of coordinates of the form
$\\{x=\bar{x}+q\bar{y},y=\bar{y}\\}$ where $q$ is taken in an open subset
defined by means of subresultants and by the homogeneous component of maximum
degree in $G$ (see e.g. Remark 3 in [10]).

Condition (1) in Definition (A.3) is easy to check. Let us now deal with the
second condition. Let us consider the ideal $\mathrm{J}$ generated by
$\\{G,G_{x}\\}$ in $K[x,y]$. Taking into account that $G$ is irreducible over
$\overline{K}$, one has that $\mathrm{J}$ is zero–dimensional. Therefore,
using the Shape lemma (see [39] page 194), the normed reduced Gröbner basis of
$\sqrt{\mathrm{J}}$, w.r.t. the lexicographic order $x<y$, is of the form

$\\{u(x),y-v(x)\\},$

with $u$ square-free and $\deg(v)<\deg(u)$, if and only if
$\sqrt{\mathrm{J}}$, or equivalently $\mathrm{J}$, satisfies condition (2) in
Definition (A.3). It remains to have a computational approach to determine
$\sqrt{\mathrm{J}}$. This can be achieved, for instance, using Seidenberg
lemma (see e.g. [22] or [15]). More precisely, if $\mathrm{J}\cap
K[x]=<\\!f(x)\\!>$ and $\mathrm{J}\cap K[y]=<\\!g(y)\\!>$, then

(A.1) $\sqrt{\mathrm{J}}=<\\!G,G_{x},\tilde{f},\tilde{g}\\!>,$

where $\tilde{f}=f/\gcd(f,f^{\prime})$ and $\tilde{g}=g/\gcd(g,g^{\prime})$
and where $f^{\prime}$ and $g^{\prime}$ denotes the derivatives of $f$ and $g$
w.r.t. $x$ and $y$, respectively.

Then, the process for computing a standard decomposition of the singular locus
of $\mathcal{C}(G^{h})$ is as follows.

Standard decomposition of the singular locus

Step 1: Regular position. If $\mathcal{C}(G)$ is not in regular position,
apply an affine linear change of coordinates over $\mathbb{K}$, say
$\mathcal{L}$, such that $\mathcal{C}(G)$ is transformed into regular position
(see comments above).

Step 2: Families of singularities at infinity. Factor $G^{h}(x,y,0)$ over $K$,

$G^{h}(x,y,0)=\prod_{i\in I}g_{i}(x,y)^{e_{i}}.$

Note that none of the polynomials $g_{i}$ is $x$ because $\mathcal{C}(G)$ is
in regular position w.r.t. $x$. Then, the set of points at infinity decomposes
in irreducible $K$–conjugate families as

$\bigcup_{i\in I}\\{(1:t:0)\\}_{g_{i}(1,t)}.$

Now, a family $\\{(1:t:0)\\}_{g_{i}(1,t)}$ is singular if and only if
$G^{h}_{x}(1,t,0)=G^{h}_{y}(1,t,0)=G^{h}_{z}(1,t,0)=0$ modulo $g_{i}(1,t)$.
Let $\mathcal{I}$ be the set containing all $g_{i}(1,t)$ defining
singularities. Then, the irreducible families of $K$–conjugate singularities
at infinity are

(A.2) $\bigcup_{m\in\mathcal{I}}\\{(1:t:0)\\}_{m(t)}.$

Step 3: Families of affine singularities. Let $\mathrm{I}$ be the ideal
generated by $\\{G,G_{x},G_{y}\\}$. Since $\sqrt{\mathrm{I}}$ is regular
w.r.t. $x$ because of condition (2) in Def. A.3, and zero–dimensional, by the
discussion above on the Shape lemma, the normed reduced Gröbner basis w.r.t.
the lexicographic order with $x<y$ of $\sqrt{\mathrm{I}}$ is of the form
$\\{A(x),y-B(x)\\}$ with $A$ square-free and $\deg(B)<\deg(A)$; recall that if
$\mathrm{I}\cap K[x]=<\\!f(x)\\!>$ and $\mathrm{I}\cap K[y]=<\\!g(y)\\!>$,
then

$\sqrt{\mathrm{I}}=<\\!G,G_{x},G_{y},\tilde{f},\tilde{g}\\!>,$

where $\tilde{f}=f/\gcd(f,f^{\prime})$, $\tilde{g}=g/\gcd(g,g^{\prime})$, and
$f^{\prime}$ and $g^{\prime}$ denote the derivatives of $f$ and $g$ w.r.t. $x$
and $y$, respectively. So, each irreducible factor $m(x)$ of $A(x)$ over $K$
generates the irreducible family $\\{(t:B(t):1)\\}_{m(t)}.$ Therefore, if
$\mathcal{A}$ denotes the set of all irreducible factors of $A$, the affine
singularities decompose in irreducible $K$–families as

(A.3) $\bigcup_{a\in\mathcal{A}}\\{(t:B(t):1)\\}_{m(t)}.$

Step 4: Standard decomposition. Applying $\mathcal{L}^{-1}$ to (A.2) and to
(A.3) we get an $K$–standard decomposition of the singular locus of
$\mathcal{C}(G^{h})$. We observe that the irreducible families of affine
singularities will be of the form $\\{(f_{1}(t):f_{2}(t):1)\\}_{m(t)}$ and the
singularities at infinity of the form $\\{(L_{1}(t):L_{2}(t):0)\\}_{m(t)}$
with $\deg_{t}(L_{i})\leq 1$ and $\gcd(L_{1},L_{2})=1$.

Let $\mathscr{F}$ be a $K$–standard decomposition of the singular locus of
$\mathcal{C}(G^{h})$ and let $\mathcal{F}\in\mathscr{F}$; note that by
construction, $\mathcal{F}$ is irreducible. Then, we denote by
$\mathrm{mult}(\mathcal{F})$ the multiplicity of the points in $\mathcal{F}$,
as points of $\mathcal{C}(G^{h})$. In addition, since the character of the
singularity is invariant within the family we will speak about ordinary and
non-ordinary families. The multiplicity of an irreducible family
$\mathcal{F}=\\{(f_{1}:f_{2}:f_{3})\\}_{m(t)}$ can be computed by determining
the greatest non-negative integer $r$ such that all partial derivatives of
$G^{h}$ of order less than $r$ vanish at $(f_{1}:f_{2}:f_{3})$ modulo $m(t)$.
The character of $\mathcal{F}$ can be decided by analyzing the squarefreeness,
modulo $m(t)$, of the polynomial defining the tangents to $\mathcal{C}(G^{h})$
at $(f_{1}:f_{2}:f_{3})$. Alternatively, one can work with the curve
$\mathcal{C}(G^{h}_{\mathcal{F}})$ (see Remark A.2 (3)). Now, the family
$\mathcal{F}$ in $\mathcal{C}(G^{h})$ turns to be one point in
$\mathcal{C}(G^{h}_{\mathcal{F}})$, namely $(f_{1}:f_{2}:f_{3})$. Then, the
character and multiplicity of $\mathcal{F}$ is the character and multiplicity
of $(f_{1}:f_{2}:f_{3})$ as a point in $\mathcal{C}(G^{h}_{\mathcal{F}})$.

Once the singularities have been detected, one proceeds to recursively, and
separately, blow up each non–ordinary singularity via the neighboring
singularities (see [37] or [30] for more details). Let us briefly recall how
the first iteration step works, first for a single point, and afterwards for
an irreducible family of conjugate points. In the following, let
$p\in\mathcal{C}(G^{h})$ be a non–ordinary singular point.

Blow up basic step

Step 1. Apply a linear change of coordinates $\mathcal{L}$ such that:
$p=\mathcal{L}(0:0:1)$, none of the tangent to
$\mathcal{C}(G^{h}(\mathcal{L}))$ at $(0:0:1)$ is one of the lines $x=0,$ and
$y=0$, and for $v\in\\{x,y,z\\}$ no point in
$\left(\mathcal{C}(G^{h}(\mathcal{L}))\setminus\mathcal{C}(v)\right)\setminus\\{(0:0:1)\\}$
is a singularity of $\mathcal{C}(G^{h})$.

Step 2. Apply the Cremona transformation $\mathcal{Q}:=(yz:xz:xy)$ to
$\mathcal{C}(G^{h}(\mathcal{L}))$. Then, $G^{h}(\mathcal{L}(\mathcal{Q}))$
factors as $G^{h}(\mathcal{Q}(\mathcal{L}))=x^{n_{1}}y^{n_{2}}z^{n_{3}}G^{*}$
for some natural numbers $n_{1},n_{2},n_{3}$. We call $G^{*}$ the quadratic
transform of $G^{h}$ w.r.t. $p$.

The first neighboring of $p$ is defined as

$\left(\mathcal{C}(G^{*})\cap\mathcal{C}(z)\right)\setminus\\{(1:0:0),(0:1:0)\\}.$

The points, and their multiplicities, in the neighborhood, are in one to one
correspondence with the tangents, and their multiplicities, to
$\mathcal{C}(G^{h})$ at $p$. The (first) neighboring singularities of $p$ are
the neighboring points being singularities of $\mathcal{C}(G^{*})$. The
process continues till no non-ordinary neighboring point appears in the
neighborhoods and until all non-ordinary singularities of $\mathcal{C}(G^{h})$
have been blowed up. We will refer to the set of all singularities and
neighboring singularities as the neighboring graph of $\mathcal{C}(G^{h})$. In
this situation, the genus can be computed as (recall that
$d=\deg(\mathcal{C}(G))$)

(A.4)
$\mathrm{genus}(\mathcal{C}(G))=\dfrac{(d-1)(d-2)}{2}-\dfrac{1}{2}\sum\mathrm{mult}(p)(\mathrm{mult}(p)-1)$

where the sum is taking over all the points in the neighboring graph of
$\mathcal{C}(G^{h})$.

If we work with families, say
$\mathcal{F}=\\{(f_{1}:f_{2}:f_{3})\\}_{m_{0}(t_{0})}$ is a non-ordinary
irreducible family of singularities, we may introduce the curve
$\mathcal{C}(G^{h}_{\mathcal{F}})$ (see above) and repeat the process with the
single point $p_{\mathcal{F}}:=(f_{1}:f_{2}:f_{3})$. In this way the first
neighboring of $p_{\mathcal{F}}$ is decomposed into irreducible
$K_{m_{0}}$–conjugate families; recall that $K_{m_{0}}$ is the quotient field
of $K[t_{0}]/\\!<\\!m_{0}(t_{0})\\!>$). These irreducible
$K_{m_{0}}$–conjugate families are of the form

(A.5) $\\{(t_{1}:1:0)\\}_{m_{1}(t_{0},t_{1})}$

where $t_{1}$ is a new variable and $m_{1}(t_{0},t_{1})\in
K_{m_{0}}[t_{1}]\setminus\\{t_{1}\\}$ is irreducible over $K_{m_{0}}$. In this
situation, the method continues by applying the same process to the
irreducible families of non-ordinary singularities in the first neighborhood.
The irreducible families in the second neighborhood will be of the form

(A.6) $\\{(t_{2}:1:0)\\}_{m_{2}(t_{0},t_{1},t_{2})}$

where $t_{2}$ is a new variable and $m_{2}\in
K_{m_{0},m_{1}}[t_{2}]\setminus\\{t_{2}\\}$ is irreducible over
$K_{m_{0},m_{1}}$, where $K_{m_{0},m_{1}}$ denotes the quotient field of
$K_{m_{0}}[t_{1}]/\\!<\\!m_{1}(t_{0},t_{1})\\!>$. In general, the irreducible
families in the $i$-th neighborhood will be of the form

(A.7) $\\{(t_{i}:1:0)\\}_{m_{i}(t_{0},\ldots,t_{i})}.$

By abuse of notation, we will say that the families of the form in (A.5),
(A.6), (A.7) are $K$–conjugate families. Applying this process till no non-
ordinary neighboring conjugate family appears in the neighborhoods and until
all non-ordinary families of $\mathcal{C}(G^{h})$ have been blown up, we get a
decomposition that we call a $K$–standard decomposition of the neighboring
graph of singularities. In this situation, the genus can be computed as

(A.8)
$\mathrm{genus}(\mathcal{C}(G))=\dfrac{(d-1)(d-2)}{2}-\dfrac{1}{2}\sum_{\mathcal{F}\in\mathscr{N}}\,\\#(\mathcal{F})\,\mathrm{mult}(\mathcal{F})(\mathrm{mult}(\mathcal{F})-1)$

where $\mathscr{N}$ is a standard decomposition of the neighboring graph of
$\mathcal{C}(G^{h})$.

###  A.2. Parametrization algorithm

Once the genus of $\mathcal{C}(G^{h})$ has been computed, if it is zero, we
may derive a rational parametrization of the curve. There are different
approaches to achieve a rational parametrization, see e.g. [13], [27], [28],
[30]. Here we will use a simplified version of the algebraically optimal
algorithm in [28] where Hilbert–Hurwitz theorem (see e.g. Theorem 5.8. in
[30]) is applied directly and recursively.

Let $\mathcal{N}$ be a $K$–standard decomposition of the neighboring graph of
singularities of $\mathcal{C}(G^{h})$. We consider the linear system
$\mathscr{A}_{d-2}(\mathcal{C}(G^{h}))$ of adjoint curves to
$\mathcal{C}(G^{h})$ of degree $d-2$ (recall that $d=\deg(\mathcal{C}(G))$);
that is, the linear system of all $(d-2)$–degree curves having each $r$-fold
point of $\mathcal{C}(G^{h})$, including the neighboring ones, as a point of
multiplicity at least $r-1$. In other words,
$\mathscr{A}_{d-2}(\mathcal{C}(G^{h}))$ is the linear system of curves of
degree $d-2$ defined by the effective divisor

$\sum_{\mathcal{F}\in\mathcal{N}}\sum_{p\in\mathcal{F}}(\mathrm{mult}(p)-1)\,p,$

where the multiplicity is w.r.t. the curve where $\mathcal{F}$ belongs to. In
practice, the linear conditions to construct the linear system can be derived
by working modulo the corresponding defining polynomials of the families. In
the following, we outline the process for computing
$\mathscr{A}_{d-2}(\mathcal{C}(G^{h}))$.

Adjoints computation

Step 1. We identify the set of all projective curves, including multiple
component curves, of fixed degree $d-2$, with the projective space

$\mathscr{V}_{d-2}:=\mathbb{P}^{\frac{(d-2)(d+1)}{2}}(\overline{K})$

via their coefficients, after fixing an order of the monomials. By abuse of
notation, we will refer to the elements in $\mathscr{V}_{d-2}$ by either their
tuple of coefficients, or by the associated $\\{x,y,z\\}$–form, or by the
corresponding curve. Let $H(\Lambda,x,y,z)$ denote the
$\\{x,y,z\\}$–homogeneous polynomial of degree $d-2$ defining a generic
element in $\mathscr{V}_{d-2}$, where $\Lambda$ is a tuple of undetermined
coefficients.

Step 2. For each irreducible $K$–family
$\mathcal{F}:=\\{(f_{1}:f_{2}:f_{3})\\}_{m_{0}(t_{0})}$, with
$r:=\mathrm{mult}(\mathcal{F})$, in the standard decomposition of the singular
locus of $\mathcal{C}(G^{h})$, and for each partial derivative $M$ of $H$ of
order $r-2$ w.r.t. the variables $\\{x,y,z\\}$, compute
$M(\Lambda,f_{1},f_{2},f_{3})$ mod $m_{0}(t_{0})$ and collect in a set
$\mathcal{S}$ of its non–zero coefficients w.r.t. $t$.

Step 3. For each neighborhood and for each irreducible $K$–family of
neighboring singularities
$\mathcal{F}:=\\{(t_{i}:1:0)\\}_{m_{i}(t_{0},\ldots,t_{i})}$, with
$r:=\mathrm{mult}(\mathcal{F})$, compute

(A.9) $(\cdots(N(\Lambda,t_{1},1,0)$ mod $m_{i})\cdots$) mod $m_{1}$

where $N$ is every partial derivative of order $r-2$ of $N^{*}$, being $N^{*}$
the form obtained applying to $H$ the same blow up process (linear changes of
coordinates, Cremona transformation and quadratic transformation, see
Subsection A.1) as the one to reach the curve where the neighboring family
$\mathcal{F}$ belongs to; in [27, Theorem 6] appears an alternative method to
derive (A.9). Include in $\mathcal{S}$ all non–zero coefficients w.r.t. $t$ of
the polynomials in (A.9).

Step 4. Solve the homogeneous linear system of equations
$\\{L(\Lambda)=0\\}_{L\in\mathcal{S}}$ and substitute the result in $H$. The
form resulting from this substitution defines
$\mathscr{A}_{d-2}(\mathcal{C}(G^{h}))$.

######  Remark A.4.

We observe that the defining polynomial of
$\mathscr{A}_{d-2}(\mathcal{C}(G^{h}))$ has coefficients in $K(\Lambda)$ and
hence the ground field is not extended.

Hilbert-Hurwitz theorem (see [9] or [30, Theorem 5.8]) ensures that for almost
all $(\phi_{1},\phi_{2},\phi_{3})\in\mathscr{A}_{d-2}(\mathcal{C}(G^{h}))^{3}$
the mapping

(A.10)
$\mathscr{H}\equiv(y_{1}:y_{2}:y_{3})=(\phi_{1}(x,y,z),\phi_{2}(x,y,z),\phi_{3}(x,y,z))$

transforms birationally $\mathcal{C}(G^{h})$ to an irreducible curve of degree
$d-2$. Note that, because of Remark A.4, the map in (A.10) is defined over
$K$. Furthermore, since the map is birational, the genus is preserved. Thus,
applying successively Hilbert–Hurwitz theorem one gets either a conic (if $d$
is even) or a line (if $d$ is odd) $K$–birationally equivalent to
$\mathcal{C}(G^{h})$.

After these considerations, we can outline the parametrization algorithm.

Parametrization computation

Step 1. Let $G$ be as above so that the genus of $\mathcal{C}(G^{h})$ is zero.

Step 2. Set $M:=G$, $\rho:=\deg(M)$, and $\mathcal{T}$ as the identity map in
$\mathbb{P}^{2}(K)$.

Step 3. While $\rho>2$ do

  1. (1)

Compute $\mathscr{A}_{\rho-2}(\mathcal{C}(M))$.

  2. (2)

Take
$(\phi_{1},\phi_{2},\phi_{3})\in\mathscr{A}_{d-2}(\mathcal{C}(G^{h}))^{3}$, so
that the mapping $\mathscr{H}$ in $\eqref{eq-HH}$ is birational over
$\mathcal{C}(M)$.

  3. (3)

Replace $M$ by $M(\mathscr{H}^{-1})$, $\rho$ by $\deg(M)$, and $\mathcal{T}$
by $\mathscr{H}\circ\mathcal{T}$.

Step 4. Parametrize birationally $\mathcal{C}(M)$. Let $\mathcal{Q}(t)$ be the
output parametrization.

Step 5. Return $\mathcal{T}^{-1}(\mathcal{Q}(t))$.

######  Remark A.5.

  1. (1)

If $d$ is odd one may stop the loop in Step 3 when $\rho=3$ since cubics can
be easily parametrize over the ground field. For parametrizing a conic or a
cubic see [30].

  2. (2)

The direct classical parametrization algorithm, see [37], [30], for
$\mathcal{C}(G^{h})$, in addition to the computation of the adjoints, needs
$d-2$ simple points of $\mathcal{C}(G^{h})$ (indeed, a more sophisticated
method in [27] shows that only one simple point is enough). Therefore, and
alternative to Step 5 is: compute $d-2$ simple points either on the conic, or
on the line, for instance, using $\mathcal{Q}(t)$; apply $\mathcal{T}$ to
these simple points; and now use the direct parametrization algorithm for
$\mathcal{C}(G^{h})$.