ifaamas [AAMAS ’23]Proc. of the 22nd International Conference on Autonomous
Agents and Multiagent Systems (AAMAS 2023)May 29 – June 2, 2023 London, United
KingdomA. Ricci, W. Yeoh, N. Agmon, B. An (eds.) 2023 2023 384 ShanghaiTech
University Shanghai China ShanghaiTech University Shanghai China ShanghaiTech
University Shanghai China ShanghaiTech University Shanghai China

# A Redistribution Framework for Diffusion Auctions

Sizhe Gu<EMAIL_ADDRESS>,  Yao Zhang
<EMAIL_ADDRESS>,  Yida Zhao<EMAIL_ADDRESS>and
Dengji Zhao<EMAIL_ADDRESS>
###### Abstract.

Redistribution mechanism design aims to redistribute the revenue collected by
a truthful auction back to its participants without affecting the
truthfulness. We study redistribution mechanisms for diffusion auctions, which
is a new trend in mechanism design Zhao ([n.d.]). The key property of a
diffusion auction is that the existing participants are incentivized to invite
new participants to join the auctions. Hence, when we design redistributions,
we also need to maintain this incentive. Existing redistribution mechanisms in
the traditional setting are targeted at modifying the payment design of a
truthful mechanism, such as the Vickrey auction. In this paper, we do not
focus on one specific mechanism. Instead, we propose a general framework to
redistribute the revenue back for all truthful diffusion auctions for selling
a single item. The framework treats the original truthful diffusion auction as
a black box, and it does not affect its truthfulness. The framework can also
distribute back almost all the revenue.

###### Key words and phrases:

Mechanism design; Redistribution framework; Social networks.

##  1\. Introduction

We focus on a resource allocation problem that involves a group of self-
interested agents competing for the resources. One important goal of the
allocation problem is to maximize social welfare, and a common method is to
hold an auction so that the agents with the highest valuations of the
resources can be found. The Vickrey-Clarke-Groves (VCG) mechanism Vickrey
(1961); Clarke (1971); Groves (1973) is a well-known method under which the
agents will truthfully report their valuations and the resources will be
allocated to the agents with the highest valuations. This will also lead to a
high revenue for the seller. However, in many situations, we do not seek for a
profit. Hence, there is another body of studies on how to return the revenue
to the participants Cavallo (2006); Guo and Conitzer (2009); Guo (2011a, 2016,
b); Moulin (2009); Manisha et al. (2018), which is called redistribution
mechanism design.

In recent years, researchers have started to design mechanisms on social
networks Jackson (2010); Easley and Kleinberg (2010), where the goal is to
incentivize agents to invite new agents via their social connections to join
in Li et al. (2017); Zhao et al. (2018); Li et al. (2019); Zhang et al.
(2020); Kawasaki et al. (2020); Zhao (2021). By doing so, the mechanism can
further improve social welfare or revenue in, for example, auctions.
Therefore, introducing social network to redistribution problems is a good
choice to break through the efficiency limitations of traditional settings.
There are many realistic scenarios of redistribution on social networks. For
example, consider a non-profit organization like a government who has some
idle resources, such as properties confiscated from criminals. These resources
are normally destroyed and sold cheaply to a small group of people, as the
organization does not want to gain much profit from clearing the resources. By
utilizing social networks, we could attract more buyers who are willing to pay
more to receive the idle resources, but the profit could still be
redistributed back to participants.

Redistribution on networks is also more challenging than traditional settings
because the action space of the participants is enlarged. Therefore, we are
not able to directly apply the existing solutions such as Cavallo’s mechanism
Cavallo (2006). The intuition behind this failure is that agents will have no
incentives to invite their competitors in an auction, or invite others to
share a limited redistribution. Another difficulty is that agents’ valuations
not only determine the winner of the auction, but also relate to how much
revenue can be redistributed. Therefore, the redistribution problem is not
about a simple combination of a truthful auction mechanism and a truthful
reward distribution mechanism, which may not produce a truthful redistribution
mechanism.

More importantly, there are a bunch of different diffusion mechanisms with
different allocation and payment policies. It is complex and tedious to design
the redistribution mechanism for each diffusion auction separately. Hence, we
design the first general redistribution framework for all diffusion auctions.
The framework can redistribute almost all the revenue of any diffusion auction
back to all agents without affecting the properties of incentive compatibility
and individual rationality. In fact, our framework can also be applied to all
traditional auctions. In particular, when the input mechanism is VCG, the
mechanism generated by our framework is Cavallo’s mechanism. Therefore, our
framework is a general solution for redistribution mechanism design with or
without networks.

##  2\. Preliminaries

We consider a setting where a sponsor $s$ wants to allocate a single item on a
social network. Apart from the sponsor, the social network consists of $n$
agents denoted by $N=\\{1,...,n\\}$. Each agent $i\in N\cup\\{s\\}$ has a
private neighbour set $r_{i}\subseteq N\cup\\{s\\}\backslash\\{i\\}$, which
represents the agents with whom $i$ can communicate directly. Furthermore,
each agent $i\in N$ has a private valuation for the item of $v_{i}\geq 0$.
Initially, the sponsor can only invite her neighbours to participate in the
allocation. In order to attract more participants, the sponsor asks
participants who have already joined the allocation to further invite their
neighbours to join. However, participants are competitors, so they would not
invite each other by default. Thus, we need to design mechanisms to
incentivize them to invite each other, which are called diffusion mechanisms.

Formally, the diffusion mechanism requires each agent to report not only her
valuation but also her neighbour set (which is equivalent to inviting her
neighbours). Let $\theta_{i}=(v_{i},r_{i})$ be the type of an agent $i\in N$
and $\theta_{i}^{\prime}=(v_{i}^{\prime},r_{i}^{\prime})$ be the reported type
of $i$, with $r_{i}^{\prime}\subseteq r_{i}$ representing the actual neighbour
set she has invited, which can only be a subset of her true neighbour set
$r_{i}$. Let
$\theta^{\prime}=(\theta^{\prime}_{1},\dots,\theta^{\prime}_{n})=(\theta^{\prime}_{i},\theta^{\prime}_{-i})$
be the overall report profile, and $\theta^{\prime}_{-i}$ is the overall
report profile except for $i$. Let $\Theta_{i}$ represent the type space of
agent $i$ and $\Theta=(\Theta_{1},\dots,\Theta_{n})$ represent the type
profile space of all agents. Given any report profile $\theta^{\prime}$, it
induces a directed graph denoted by
$G(\theta^{\prime})=(V(\theta^{\prime}),E(\theta^{\prime}))$, where
$V(\theta^{\prime})=N\cup\\{s\\}$ and $E(\theta^{\prime})=\\{(s,j)|j\in
r_{s}\\}\cup\\{(i,j)|i\in N,j\in r_{i}^{\prime}\\}$. Let
$D_{s}(G(\theta^{\prime}))$ denote the set of agents accessible from $s$ in
$G(\theta^{\prime})$. Because the others cannot receive the proper invitation
started by the sponsor, only the agents in $D_{s}(G(\theta^{\prime}))$ can
actually join the allocation (in practice, this means that the others will not
be informed about the allocation at all). An example of the induced graph
$G(\theta^{\prime})$ is shown in Figure 1.

The goal of the sponsor is to allocate the item to the agent with the highest
valuation, but she does not want to gain any profit from the allocation.
Hence, the sponsor need to redistribute the revenue from a given diffusion
auction mechanism.

######  Definition .

A diffusion auction mechanism $\mathcal{M}$ is defined by an allocation policy
$\pi=\\{\pi_{1},..,\pi_{n}\\}$ and a payment policy $x=\\{x_{1},...,x_{n}\\}$,
where $\pi_{i}:\Theta\rightarrow\\{0,1\\}$ and
$x_{i}:\Theta\rightarrow\mathbb{R}$ are the allocation and payment for $i$
respectively. Additionally, for all report profiles
$\theta^{\prime}\in\Theta$,

  * •

for any agent $i\not\in D_{s}(G(\theta^{\prime}))$,
$\pi_{i}(\theta^{\prime})=0$ and $x_{i}(\theta^{\prime})=0$;

  * •

for any agent $i\in D_{s}(G(\theta^{\prime}))$, $\pi_{i}(\theta^{\prime})$ and
$x_{i}(\theta^{\prime})$ are independent of the reports of agents who are not
in $D_{s}(G(\theta^{\prime}))$;

  * •

$\sum_{i\in N}\pi_{i}(\theta^{\prime})\leq 1$.

(1)

(2)

Figure 1. An example of induced graphs by agents’ type profile and report
profile. The number in each node is the real/reported valuation of the agent.
(1) is the graph induced by agents’ real types. (2) is the graph induced by
agents’ report profile where agent $B$ misreports
$\theta_{B}^{\prime}=(5,\\{D\\})$ (only agents in $D_{s}(G(\theta^{\prime}))$
are shown). Then, agents $E$, $H$ and $I$ cannot participate in the mechanism.

Given the agents’ report profile $\theta^{\prime}$,
$\pi_{i}(\theta^{\prime})=1$ means that the item is allocated to agent $i$,
while $\pi_{i}(\theta^{\prime})=0$ means that $i$ does not get the item. In
addition, $x_{i}(\theta^{\prime})\geq 0$ means that $i$ pays
$x_{i}(\theta^{\prime})$ to the sponsor, and $x_{i}(\theta^{\prime})<0$
indicates that $i$ receives $|x_{i}(\theta^{\prime})|$ from the sponsor.
Therefore, the surplus of the payment transfers in the mechanism (i.e., the
revenue) is defined by

$S(\theta^{\prime})=\sum_{i\in N}x_{i}(\theta^{\prime}).$

Then in our setting, given the type $\theta_{i}=(v_{i},r_{i})$ of an agent $i$
and the report profile $\theta^{\prime}$, the utility of agent $i$ under the
diffusion auction mechanism $\mathcal{M}=(\pi,x)$ is

$u_{i}(\theta_{i},\theta^{\prime})=\pi_{i}(\theta^{\prime})\cdot
v_{i}-x_{i}(\theta^{\prime}).$

In the following, we will define several properties that are required for the
diffusion auction mechanism. First, an agent should not suffer a loss if she
reports her true valuation on the item.

######  Definition .

A diffusion auction mechanism $\mathcal{M}=(\pi,x)$ is individually rational
(IR) if for all $i\in N$ and all $\theta^{\prime}\in\Theta$, we have

$u_{i}(\theta_{i},((v_{i},r_{i}^{\prime}),\theta_{-i}^{\prime}))\geq 0.$

Next, we want to incentivize all agents not only to report their true
valuations but also to invite all their neighbours to join the mechanism,
i.e., reporting their true types is a dominant strategy.

######  Definition .

A diffusion auction mechanism $\mathcal{M}=(\pi,x)$ is incentive compatible
(IC) if for all $i\in N$ with $\theta_{i}\in\Theta_{i}$, and all
$\theta_{i}^{\prime}\in\Theta_{i}$, $\theta_{-i}^{\prime}\in\Theta_{-i}$, we
have

$u_{i}(\theta_{i},(\theta_{i},\theta_{-i}^{\prime}))\geq
u_{i}(\theta_{i},(\theta_{i}^{\prime},\theta_{-i}^{\prime})).$

The sum of the payment transfers should be non-negative for the sponsor $s$;
otherwise, she will pay a deficit.

######  Definition .

A diffusion auction mechanism $\mathcal{M}=(\pi,x)$ is non-deficit (ND) if for
all $i\in N$ and all $\theta^{\prime}\in\Theta$, we have

$S(\theta^{\prime})=\sum_{i\in N}x_{i}(\theta^{\prime})\geq 0.$

Finally, recall that our sponsor does not want to gain any profit. Our goal is
to establish a framework that can create a diffusion redistribution mechanism
from a given diffusion auction mechanism $\mathcal{M}^{a}=(\pi^{a},x^{a})$.
Given the report profile $\theta^{\prime}\in\Theta$, denote the revenue
achieved by $\mathcal{M}^{a}$ as $S^{a}(\theta^{\prime})=\sum_{i\in
N}x^{a}_{i}(\theta^{\prime})$. Then our framework is to decide the amount
$R_{i}$ that is returned to each agent $i$, i.e., to decide a redistribution
mechanism $\mathcal{M}=(\pi,x)$ with
$\pi_{i}(\theta^{\prime})=\pi^{a}_{i}(\theta^{\prime})$ and
$x_{i}(\theta^{\prime})=x^{a}_{i}(\theta^{\prime})-R_{i}(\theta^{\prime})$. A
diffusion redistribution mechanism, speaking formally, is also a diffusion
auction mechanism, but we want it to redistribute the revenue back to agents
as much as possible, i.e., the sum of the payment transfers should be close to
0, which is define as follows.

######  Definition .

A diffusion redistribution mechanism $\mathcal{M}=(\pi,x)$ is asymptotically
budget-balanced (ABB) if for all $\theta^{\prime}\in\Theta$,

$\lim_{n\to\infty}S(\theta^{\prime})=0.$

It means that the remaining revenue that has not been redistributed is
approaching zero if the number of agents in the underlying network is large
enough. We also consider an approximation to ABB when it is hard to achieve.

######  Definition .

A diffusion redistribution mechanism $\mathcal{M}=(\pi,x)$ is
$\epsilon$-asymptotically budget-balanced ($\epsilon$-ABB) if for all
$\theta^{\prime}\in\Theta$,

$\lim_{n\to\infty}S(\theta^{\prime})\leq\epsilon$

where $\epsilon>0$ is a constant.

Before we introduce our framework, we show that directly applying classic
Cavallo’s mechanism fails to satisfy our properties. We recall Cavallo’s
mechanism as follows.

Cavallo’s Mechanism

  1. (1)

Given $G(\theta^{\prime})$, the mechanism chooses the winner
$w\in\arg\max_{i\in N}v_{i}^{\prime}$, and set $\pi_{w}(\theta^{\prime})=1$.

  2. (2)

For each agent $i$, her payment is
$x_{i}(\theta^{\prime})=x_{i}^{VCG}(\theta^{\prime})-x_{w^{\prime}}^{VCG}(\theta_{-i}^{\prime})/n$,
where $x_{i}^{VCG}(\theta^{\prime})$ is $i$’s payment under VCG and
$w^{\prime}$ is the winner when we run VCG without agent $i$.

###### Proposition

Cavallo’s mechanism is not an incentive compatible diffusion redistribution
mechanism.

###### Proof.

We prove this by giving an example in Figure 2. First for the situation
without diffusion shown in Figure 2(1), by Cavallo’s mechanism, agent $C$ wins
the item and $\pi_{C}(\theta^{\prime})\cdot v_{C}=4$,
$x_{C}^{VCG}(\theta^{\prime})=3$. If agent $C$ is removed, $B$ will win the
item, so $x_{w^{\prime}}^{VCG}(\theta_{-C}^{\prime})=2$. Similarly we can get
$x_{w^{\prime}}^{VCG}(\theta_{-A}^{\prime})=3$ and
$x_{w^{\prime}}^{VCG}(\theta_{-B}^{\prime})=2$. Therefore, agent $A$, $B$ and
$C$ will receive $1$, $\frac{2}{3}$, and $\frac{2}{3}$ as redistribution
respectively. However, in Figure 2(2), when agent $C$ invites agent $D$ and we
still apply Cavallo’s mechanism, $C$ is still the winner and all VCG payments
will not change. Then, agent $C$ can only get $\frac{2}{4}=\frac{1}{2}$ (since
$n$ becomes to 4) as redistribution. The payments for getting the item are the
same, but the revenue from redistribution decreases after inviting $D$ so
agent $C$ has no motivation to invite $D$.

Hence, Cavallo’s mechanism is not IC with diffusion. ∎

(1)

(2)

Figure 2. An example of Cavallo’s mechanism being applied in social network.
(1) is a graph of traditional setting of redistribution problem. (2) is a
graph induced by agents’ real types on social networks. (1) can also be viewed
as the result that agent $C$ does not invite agent $D$ in (2).

##  3\. Redistribution Framework for Diffusion Auctions

In this section, we propose a network-based redistribution mechanism framework
(NRMF) for all IC diffusion auction mechanisms. We first consider a subproblem
to redistribute a value to all agents without affect the IC property.

###  3.1. Proportional Reward Sharing in a Tree

We consider a problem that a sponsor $s$ wants to share a reward of $B\geq 0$
with a set of agents $N$ connected as a tree rooted by $s$.

For a tree $T(N\cup\\{s\\},E)$ rooted by $s$, we introduce the following two
notations.

  * •

Let $p_{i}\in N\cup\\{s\\}$ be the parent agent of $i\in N$ in $T$.

  * •

Let $C_{i}$ be the set of all agents in the subtree rooted by $i$ in $T$
(excluding $i$).

We define the following distribution mechanism.

Proportional Reward Sharing in a Tree (PRST)

Input: a tree $T=(N\cup\\{s\\},E)$ and a reward $\mathcal{B}$.

  1. (1)

Set $\Omega_{s}=1$.

  2. (2)

For each agent $i\in N$, let

$\mathsf{total}=\frac{|C_{i}|+1}{|C_{p_{i}}|},\quad\mathsf{base}=\frac{1}{|C_{p_{i}}|-|C_{i}|}$

and then recursively define

$\left\\{\begin{array}[]{l}\omega_{i}=\Omega_{p_{i}}\cdot\left(\mathsf{base}+\left(\mathsf{total}-\mathsf{base}\right)\alpha\right)\\\
\\\
\Omega_{i}=\Omega_{p_{i}}\cdot\mathsf{total}-\omega_{i}=\Omega_{p_{i}}\cdot\left(\mathsf{total}-\mathsf{base}\right)\cdot\left(1-\alpha\right)\end{array}\right.$

with predefined parameter $0<\alpha<1$.

  3. (3)

Set $b_{i}=\omega_{i}\mathcal{B}$.

Output: the share $b_{i}$ for all agents $i\in N$.

In the PRST, $\omega_{i}$ is the proportion of the reward allocated to agent
$i$ and $\Omega_{i}$ is the proportion of the reward that agent $i$ gives to
her descendants. The proportion $\omega_{i}$ has two parts. The first part is
the basic reward, which is determined by the number of descendants of her
siblings ($|C_{p_{i}}|-|C_{i}|$ in $\mathsf{base}$). The second part is the
reward for her diffusion, which increases proportionally to the number of her
descendants ($|C_{i}|$). A running example of the PRST is given in Figure 3.

Figure 3. An example of PRST. Here, we set $\mathcal{B}=1$ and $\alpha=1/2$.
Each node represents an agent and the value in the node is the share $b_{i}$
of the agent.

In Figure 3, considering agent $A$, $|C_{p_{A}}|$ means the number of agents
in the whole tree excluding $s$, which is 18. $|C_{A}|$ means the number of
descendants of agent $A$, which is 5. According to the definition,
$\Omega_{p_{A}}=\Omega_{s}=1$. Therefore,

$\displaystyle\omega_{A}$
$\displaystyle=\frac{1}{|C_{p_{A}}|-|C_{A}|}+\left(\frac{|C_{A}|+1}{|C_{p_{A}}|}-\frac{1}{|C_{p_{A}}|-|C_{A}|}\right)\cdot\alpha$
$\displaystyle=\frac{1}{18-5}+\left(\frac{5+1}{18}-\frac{1}{18-5}\right)\cdot\frac{1}{2}=\frac{8}{39}$

Similarly, considering agent $B$, $|C_{p_{B}}|$ means the number of
descendants of agent $A$, which is 5. $|C_{B}|$ means the number of
descendants of agent $B$, which is 2. Hence, we have
$\Omega_{p_{B}}=\Omega_{A}=\frac{|C_{A}|+1}{|C_{p_{A}}|}-\omega_{A}=\frac{6}{18}-\frac{8}{39}$.
Therefore,

$\displaystyle\omega_{B}$
$\displaystyle=\Omega_{p_{B}}\left[\frac{1}{|C_{p_{B}}|-|C_{B}|}+\left(\frac{|C_{B}|+1}{|C_{p_{B}}|}-\frac{1}{|C_{p_{B}}|-|C_{B}|}\right)\alpha\right]$
$\displaystyle=\left(\frac{6}{18}-\frac{8}{39}\right)\cdot\left(\frac{1}{3}+\left(\frac{3}{5}-\frac{1}{3}\right)\cdot\frac{1}{2}\right)=\frac{7}{117}$

In the PRST, each agent can get a basic share when she joins the mechanism,
and the base part only depends on the number of agents in the subtrees leading
by her siblings. Then she can get a bigger share if she invites her neighbours
to join in. The proportion of the share is determined by how many descendants
she has compared to her siblings. Intuitively, we introduce a propagation
competition among siblings, and the one with a larger propagation will get a
larger share of the reward. We illustrate several useful properties of the
procedure below.

###### Lemma

In the PRST, $b_{i}\geq 0$ for all $i\in N$.

###### Proof.

Considering $\omega_{i}$ for all $i\in N$,

$\omega_{i}=\Omega_{p_{i}}\left[\frac{1}{|C_{p_{i}}|-|C_{i}|}+\left(\frac{|C_{i}|+1}{|C_{p_{i}}|}-\frac{1}{|C_{p_{i}}|-|C_{i}|}\right)\alpha\right]$

Since

$\frac{1}{|C_{p_{i}}|-|C_{i}|}\geq
0,\frac{|C_{i}|+1}{|C_{p_{i}}|}-\frac{1}{|C_{p_{i}}|-|C_{i}|}\geq 0,\alpha\geq
0$
$\Omega_{p_{i}}=\left(\frac{|C_{p_{i}}|+1}{|C_{p_{p_{i}}}|}-\frac{1}{|C_{p_{p_{i}}}|-|C_{p_{i}}|}\right)\cdot(1-\alpha)\geq
0.$

which implies $b_{i}=\omega_{i}\mathcal{B}\geq 0$. ∎

###### Lemma

In the PRST, agents have no incentives to block any of her children’s
participation.

###### Proof.

Since the reward $\mathcal{B}$ is fixed, then we only need to consider the
coefficients $\omega_{i}$. Suppose an agent $i$’s coefficient becomes
$\omega_{i}^{\prime}$ when she blocks some of her children from participation.
Denote $|C_{i}|-|C_{i}^{\prime}|$ by $\Delta|C_{i}|$. Then for all agent $i$’s
ancestor $j\in N$, denote $|C_{p_{j}}|-|C_{j}|$ by $|C_{-j}|$, which will not
change and we have $|C_{j}|-|C_{j}^{\prime}|=\Delta|C_{j}|$. Hence

$\displaystyle\Omega^{\prime}_{j}$
$\displaystyle=\Omega^{\prime}_{p_{j}}\left(\frac{|C^{\prime}_{j}|+1}{|C^{\prime}_{p_{j}}|}-\frac{1}{|C^{\prime}_{-j}|}\right)(1-\alpha)$
$\displaystyle=\Omega^{\prime}_{p_{j}}\left(\frac{|C_{j}|+1-\Delta|C_{i}|}{|C_{p_{j}}|-\Delta|C_{i}|}-\frac{1}{|C_{-j}|}\right)(1-\alpha)$
$\displaystyle\leq\Omega^{\prime}_{p_{j}}\left(\frac{|C_{j}|+1}{|C_{p_{j}}|}-\frac{1}{|C_{-j}|}\right)(1-\alpha)$

Assume $\Omega^{\prime}_{k}\leq\Omega_{k}$ for agent $k$. Then for any child
$m$ of $k$,

$\displaystyle\Omega^{\prime}_{m}$
$\displaystyle\leq\Omega^{\prime}_{p_{m}}\left(\frac{|C_{m}|+1}{|C_{p_{m}}|}-\frac{1}{|C_{-m}|}\right)(1-\alpha)$
$\displaystyle=\Omega^{\prime}_{k}\left(\frac{|C_{m}|+1}{|C_{k}|}-\frac{1}{|C_{-m}|}\right)(1-\alpha)$
$\displaystyle\leq\Omega_{k}\left(\frac{|C_{m}|+1}{|C_{k}|}-\frac{1}{|C_{-m}|}\right)(1-\alpha)$
$\displaystyle=\Omega_{m}$ (1)

The base case is that

$\displaystyle\Omega^{\prime}_{s}=\Omega_{s}=1$ (2)

Combining (1) and (2), by induction, we know that for any agent $j$,

$\displaystyle\Omega^{\prime}_{j}\leq\Omega_{j}$

Then, for agent $i$,

$\displaystyle\omega^{\prime}_{i}$
$\displaystyle=\Omega^{\prime}_{p_{i}}\left[\frac{1}{|C^{\prime}_{-i}|}+\left(\frac{|C^{\prime}_{i}|+1}{|C^{\prime}_{p_{i}}|}-\frac{1}{|C^{\prime}_{-i}|}\right)\alpha\right]$
$\displaystyle\leq\Omega_{p_{i}}\left[\frac{1}{|C_{-i}|}+\left(\frac{|C_{j}|+1-\Delta|C_{i}|}{|C_{p_{i}}|-\Delta|C_{i}|}-\frac{1}{|C_{-i}|}\right)\alpha\right]$
$\displaystyle\leq\Omega_{p_{i}}\left[\frac{1}{|C_{-i}|}+\left(\frac{|C_{j}|+1}{|C_{p_{i}}|}-\frac{1}{|C_{-i}|}\right)\alpha\right]=\omega_{i}$

Therefore, agent $i$ will suffer a loss if the amount of her descendants
decreases so she has no incentives to block any of her children’s
participation. ∎

###### Lemma

In the PRST, the total share distributed to all agents is exactly
$\mathcal{B}$.

###### Proof.

Considering an agent $i\in N$, we have

$\omega_{i}=\Omega_{p_{i}}\left(\frac{1}{|C_{p_{i}}|-|C_{i}|}+\left(\frac{|C_{i}|+1}{|C_{p_{i}}|}-\frac{1}{|C_{p_{i}}|-|C_{i}|}\right)\cdot\alpha\right)$

and the descendants of $i$ can at most be distributed

$\Omega_{i}=\Omega_{p_{i}}\left(\frac{|C_{i}|+1}{|C_{p_{i}}|}-\frac{1}{|C_{p_{i}}|-|C_{i}|}\right)\cdot(1-\alpha)$

in total, which means that

$\omega_{i}+\sum_{j\in
C_{i}}\omega_{j}\leq\omega_{i}+\Omega_{i}=\frac{|C_{i}|+1}{|C_{p_{i}}|}\Omega_{p_{i}}$

where the equation holds if and only if

$\sum_{j\ \in\
C_{i}}\omega_{j}=\Omega_{p_{i}}\left(\frac{|C_{i}|+1}{|C_{p_{i}}|}-\frac{1}{|C_{p_{i}}|-|C_{i}|}\right)\cdot(1-\alpha)$

Then consider an agent $k$ whose children are all leaf nodes (i.e.,
$C_{l}=\emptyset$ for all $l\in C_{k}$). We can get

$\sum_{l\ \in\
C_{k}}\omega_{l}=\Omega_{p_{k}}\left(\frac{|C_{k}|+1}{|C_{p_{k}}|}-\frac{1}{|C_{p_{k}}|-|C_{k}|}\right)(1-\alpha)$

By the definition of $\omega_{k}$

$\omega_{k}=\Omega_{p_{k}}\left(\frac{1}{|C_{p_{k}}|-|C_{k}|}+\left(\frac{|C_{k}|+1}{|C_{p_{k}}|}-\frac{1}{|C_{p_{k}}|-|C_{k}|}\right)\cdot\alpha\right)$

Then

$\omega_{k}+\sum_{l\ \in\
C_{k}}\omega_{l}=\frac{|C_{k}|+1}{|C_{p_{k}}|}\Omega_{p_{k}}$

Hence, by induction, $\omega_{i}+\sum_{j\in
C_{i}}\omega_{j}=\frac{|C_{i}|+1}{|C_{p_{i}}|}\Omega_{p_{i}}$ holds for all
agent $i\in N$. Then the total share of all agents are

$\displaystyle\sum_{i\in N}b_{i}$ $\displaystyle=\sum_{i\in
N}\omega_{i}\mathcal{B}=\mathcal{B}\sum_{i\in N}\omega_{i}$
$\displaystyle=\mathcal{B}\sum_{i\in r_{s}}\left(\omega_{i}+\sum_{j\ \in\
C_{i}}\omega_{j}\right)$ $\displaystyle=\mathcal{B}\cdot\Omega_{s}\sum_{i\in
r_{s}}\frac{|C_{i}|+1}{|C_{s}|}=\mathcal{B}$

Therefore, the total share distributed is exactly $\mathcal{B}$. ∎

###  3.2. Network-based Redistribution Framework

Now we propose our redistribution framework for diffusion auctions. We first
introduce a key concept called the _diffusion critical tree_ , which reveals
who takes the most important role for each agent’s participation and
simplifies the graph structure.

Given a report profile $\theta^{\prime}$, and the induced graph
$G(\theta^{\prime})$, we can generate a diffusion critical tree
$T(\theta^{\prime})$ from $G(\theta^{\prime})$ as the following.

  * •

$T(\theta^{\prime})$ is a rooted tree, where sponsor $s$ is the root and there
is an edge $(s,i)$ for all $i\in r_{s}$.

  * •

For all agents $i,j\in N$, there is an edge $(i,j)$ if and only if (1) $i$ is
a cut-point to disconnect $j$ from $s$, (2) there is no cut-point to
disconnect $j$ from $i$. Intuitively, agent $i$ is the closest agent to $j$
whose leaving will block $j$’s participation.

(1)

(2)

Figure 4. (1) is a network $G(\theta^{\prime})$. (2) is the corresponding
diffusion critical tree $T(\theta^{\prime})$. The number in each node is the
reported valuation of the agent.

Figure 4 shows an example of the above process. In Figure 4(1), taking agent
$H$ as an example, we can see that the closest agent whose leaving will block
her participation is agent $A$. Hence, the parent of agent $H$ in
$T(\theta^{\prime})$ is agent $A$. We call agent $A$ as $H$’s _critical
parent_ , and agent $H$ and $A$ are $J$’s _critical ancestors_.

Then, we present our network-based redistribution mechanism framework with
diffusion auction mechanism $\mathcal{M}^{a}$ as the input.

Network-based Redistribution Mechanism Framework (NRMF)

Input: a diffusion auction mechanism $\mathcal{M}^{a}$ and

a report profile $\theta^{\prime}$.

  1. (1)

Run diffusion auction mechanism $\mathcal{M}^{a}$ on $\theta^{\prime}$ and it
outputs $\pi^{a}(\theta^{\prime})$, $x^{a}(\theta^{\prime})$. The revenue gain
by $\mathcal{M}^{a}$ is $S^{a}(\theta^{\prime})$.

  2. (2)

Let $\pi(\theta^{\prime})=\pi^{a}(\theta^{\prime})$.

  3. (3)

Let $T(\theta^{\prime})$ be the diffusion critical tree of
$G(\theta^{\prime})$. Let $T_{i}$ be the subtree in $T(\theta^{\prime})$
rooted by $i\in N$.

  4. (4)

Set $\mathcal{B}=1$ and run the PRST on $T(\theta^{\prime})$, and get $b_{i}$
for each $i\in N$.

  5. (5)

Let $\hat{r}_{s}$ be the set of the neighbours of the sponsor $s$ in
$T(\theta^{\prime})$. And agents in the set are labelled as
$(m_{1},..,m_{|\hat{r}_{s}|})$.

  6. (6)

For each subtree $T_{m_{k}}$, $1\leq k\leq|\hat{r}_{s}|$, set
$\theta^{\prime\prime}$ as

$\theta_{i}^{\prime\prime}=\left\\{\begin{array}[]{ccl}\theta_{i}^{\prime}&&{\text{if
agent}\ i\notin T_{m_{k}}}\\\ &&\\\ (0,\emptyset)&&{\text{if agent}\ i\in
T_{m_{k}}}\end{array}\right.$

and simulate $\mathcal{M}^{a}$ on $\theta^{\prime\prime}$. The revenue gained
by $\mathcal{M}^{a}$ is $S^{a}(\theta^{\prime\prime})$. Let
$B_{k}=S^{a}(\theta^{\prime\prime})$.

  7. (7)

For each $i\in N$, set share $\hat{b}_{i}=b_{i}\cdot B_{k}$ if $i\in
T_{m_{k}}$ ($1\leq k\leq|\hat{r}_{s}|$).

  8. (8)

Let $R_{i}(\theta^{\prime})=\hat{b}_{i}=\omega_{i}B_{k}$ (since
$\mathcal{B}=1$) and
$x_{i}(\theta^{\prime})=x^{a}_{i}(\theta^{\prime})-R_{i}(\theta^{\prime})$.

Output: the allocation $\pi(\theta^{\prime})$ and the payment
$x(\theta^{\prime})$.

Intuitively, the diffusion critical tree $T(\theta^{\prime})$ is divided into
$|\hat{r}_{s}|$ subtrees. The $B_{k}$ for a subtree $T_{m_{k}}$ is the revenue
obtained by running $\mathcal{M}^{a}$ on $\theta^{\prime\prime}$ where
$T_{m_{k}}$ is blocked. The $B_{k}$ is shared by all agents in $T_{m_{k}}$,
and it is independent of these agents’ report profiles. We will show that the
procedure of the PRST will not affect the independence of $B_{k}$ and that the
whole mechanism is incentive compatible. It should be noted that as $\alpha$
grows larger, it will redistribute more to the inviters; otherwise, the
invitees will receive more. We can flexibly change the value of $\alpha$ in
the PRST according to the practical requirements without affecting the
properties. Note that when the input mechanism is simply running traditional
mechanism (e.g., the VCG mechanism) in traditional settings (i.e., all agents
are sponsor’s neighbours), NRMF still works. Therefore, our framework is a
general solution for redistribution problems with or without networks.

We now demonstrate that NRMF can satisfy the desirable properties of IR, IC,
and non-deficit if the input diffusion auction $\mathcal{M}^{a}$ is IR, IC,
non-deficit and revenue monotonic.

The instance of diffusion redistribution mechanism given by NRMF is
individually rational (IR) if the input diffusion auction $\mathcal{M}^{a}$ is
IR and non-deficit.

###### Proof.

Consider agent $i$’s utility, $i\in N$.

$u_{i}(\theta_{i},\theta^{\prime})=\pi^{a}_{i}(\theta^{\prime})v_{i}-x^{a}_{i}(\theta^{\prime})+R_{i}(\theta^{\prime})$

The part of $\pi^{a}_{i}(\theta^{\prime})v_{i}-x^{a}_{i}(\theta^{\prime})$ is
the utility of $i$ in the diffusion auction mechanism $\mathcal{M}^{a}$, which
is non-negative if agent $i$ reports her type truthfully since
$\mathcal{M}^{a}$ is IR, i.e.,

$\pi^{a}_{i}((\theta_{i},\theta_{-i}^{\prime}))v_{i}-x^{a}_{i}((\theta_{i},\theta_{-i}^{\prime}))\geq
0$ (3)

On the other hand, considering the part
$R_{i}(\theta^{\prime})=\omega_{i}B_{k}$, for $i\in T_{m_{k}}$, $1\leq
k\leq|\hat{r}_{s}|$, since $\mathcal{M}^{a}$ is non-deficit, then

$B_{k}\geq 0$ (4)

Finally, according to Lemma 3.2, we have

$\omega_{i}\geq 0$ (5)

Combining (3), (4), and (5), we get

$u_{i}(\theta_{i},(\theta_{i},\theta_{-i}^{\prime}))\geq 0$

Therefore, the mechanism is individually rational. ∎

The instance of diffusion redistribution mechanism given by NRMF is incentive
compatible (IC) if the input diffusion auction $\mathcal{M}^{a}$ is IC.

###### Proof.

Consider agent $i$’s utility when she truthfully reports her type
$\theta_{i}$, $i\in N$.

$u_{i}(\theta_{i},\theta^{\prime})=\pi^{a}_{i}(\theta^{\prime})v_{i}-x^{a}_{i}(\theta^{\prime})+R_{i}(\theta^{\prime})$

where $\theta^{\prime}=(\theta_{i},\theta_{-i}^{\prime})$.

If agent $i$ misreports $\theta^{\prime}_{i}$, then suppose $\ell$ is the loss
of $i$ in diffusion auction mechanism $\mathcal{M}^{a}$ because of misreport.
Since $\mathcal{M}^{a}$ is IC, $\ell\geq 0$ and we have:

$u_{i}(\theta_{i},\theta^{\prime})-u_{i}(\theta_{i},\theta^{\prime\prime})=\ell+R_{i}(\theta^{\prime})-R_{i}(\theta^{\prime\prime})$

where $\theta^{\prime\prime}=(\theta_{i}^{\prime},\theta_{-i}^{\prime})$,
which means agent $i$ reports profile $\theta_{i}^{\prime}$ that may be
different from the type $\theta_{i}$, and the report profile of all agents
except for $i$ remains $\theta_{-i}^{\prime}$.

Suppose $i\in T_{m_{k}}$ in $T(\theta^{\prime})$. Since $i$ cannot change her
position in critical diffusion tree, which only depends on agents who invite
her, then $i\in T_{m_{k}}$ in $T(\theta^{\prime\prime})$, too. Let
$R_{i}(\theta^{\prime})=\omega_{i}B_{k}$ and
$R_{i}(\theta^{\prime\prime})=\omega_{i}^{\prime}B_{k}^{\prime}$. Since
$B_{k}$ and $B_{k}^{\prime}$ is the revenue $\mathcal{M}^{a}$ can achieve
without the participation of agents in $T_{m_{k}}$, we have
$B_{k}=B_{k}^{\prime}$. Finally, with misreporting, $i$ can only decrease the
number of her descendants in $T_{m_{k}}$. According to Lemma 3.1, we have
$\omega_{i}\geq\omega_{i}^{\prime}$. Therefore,

$\displaystyle
u_{i}(\theta_{i},\theta^{\prime})-u_{i}(\theta_{i},\theta^{\prime\prime})$
$\displaystyle=\ell+R_{i}(\theta^{\prime})-R_{i}(\theta^{\prime\prime})$
$\displaystyle=\ell+(\omega_{i}-\omega^{\prime}_{i})\cdot B_{k}\geq 0$

from which we can conclude that the mechanism is IC. ∎

A diffusion auction is revenue monotonic if the revenue of the auction
monotonically increases as the number of participants increases.

######  Definition .

A diffusion auction is revenue monotonic if for all
$\theta^{\prime},\theta^{\prime\prime}\in\Theta$ with
$D_{s}(G(\theta^{\prime}))\subseteq D_{s}(G(\theta^{\prime\prime}))$, and for
all $i\in D_{s}(G(\theta^{\prime}))$, $v_{i}^{\prime}=v_{i}^{\prime\prime}$
and $r_{i}^{\prime}\subseteq r_{i}^{\prime\prime}$, we have
$S(\theta^{\prime})\leq S(\theta^{\prime\prime})$.

Furthermore, if all the new participants have relatively small valuations, it
should not affect the revenue of the sponsor since they have no contribution.
We call it _revenue invariance_.

######  Definition .

A diffusion auction is revenue invariant if

  * •

for all $\theta^{\prime},\theta^{\prime\prime}\in\Theta$ with
$D_{s}(G(\theta^{\prime}))\subseteq D_{s}(G(\theta^{\prime\prime}))$, and for
all $i\in D_{s}(G(\theta^{\prime}))$, $v_{i}^{\prime}=v_{i}^{\prime\prime}$
and $r_{i}^{\prime}\subseteq r_{i}^{\prime\prime}$;

  * •

for all agents in $D_{s}(G(\theta^{\prime\prime}))\setminus
D_{s}(G(\theta^{\prime}))$, any of them cannot be the winner even if we remove
the winner and all her critical ancestors under $\theta^{\prime}$,

then we have $S(\theta^{\prime})=S(\theta^{\prime\prime})$.

It is easy to prove that almost all the existing auction mechanisms (with or
without diffusion) Vickrey (1961); Li et al. (2017); Zhang et al. (2020); Li
et al. (2022), satisfy revenue invariance.

The instance of diffusion redistribution mechanism given by NRMF is non-
deficit (ND) if the input diffusion auction $\mathcal{M}^{a}$ is revenue
monotonic.

###### Proof.

According to Lemma 3.1, we have $\sum_{i\in N}\omega_{i}=1$.

On the other hand, since $\mathcal{M}^{a}$ is revenue monotonic, then for each
subtree $T_{m_{k}}$ in the diffusion critical tree $T(\theta^{\prime})$, we
have $B_{k}\leq S^{a}(\theta^{\prime})$. Hence,

$\displaystyle S(\theta^{\prime})$ $\displaystyle=\sum_{i\in
N}x_{i}(\theta^{\prime})=S^{a}(\theta^{\prime})-\sum_{k}\sum_{i\in
T_{m_{k}}}\omega_{i}\cdot B_{k}$ $\displaystyle\geq
S^{a}(\theta^{\prime})-\sum_{i\in N}\omega_{i}\cdot S^{a}(\theta^{\prime})=0$

Therefore, the mechanism is non-deficit. ∎

Then we will discuss the properties of ABB and $\epsilon$-ABB. In the
traditional setting, when we talk about ABB, the increase of agents
corresponds to the increase of the sponsor’s neighbours in our setting.
However, on the social networks, it is unreasonable to only increase sponsor’s
neighbours. So the number of other agents’ neighbours on the graph will grow
together. Due to the existence of common neighbours, the increase of each
agent’s neighbours on the origin graph is hard to describe. So we will discuss
agents that grow to infinity in the diffusion critical tree, which reflects
the invitation relationship in social networks. If all agents have the same
probability of inviting someone new in the critical tree, we define it as
evenly growing.

######  Definition .

A diffusion critical tree $T$ is evenly growing if for all subtree
$T_{i}\subset T$ where $i\in N$, we have

$\lim_{n\to\infty}\frac{|T_{i}|}{n}=0.$

Since the process of the diffusion auction is naturally seeking more agents,
then we are also interested in the increase of the agents as a continuous
process, i.e., the sponsor’s neighbours are fixed and the critical tree only
grows in height. If assuming each neighbour of the sponsor have the same
potential in terms of the number of agents in their leading branches, we call
the critical tree is branch-independent growing.

######  Definition .

A diffusion critical tree $T$ is branch-independent growing if for all subtree
$T_{i}\subset T$ rooted by $i\in\hat{r}_{s}$, we have

$\lim_{n\to\infty}\frac{|T_{i}|}{n}=\frac{1}{|\hat{r}_{s}|}.$

###### Lemma

If a diffusion auction $\mathcal{M}^{a}$ is IR and ND, we have $0\leq
S^{a}(\theta^{\prime})\leq\overline{v}$, where $\overline{v}$ is the upper
bound of all possible valuations111Otherwise, the valuation can be infinity,
which is not reasonable in practice..

###### Proof.

Since the the diffusion auction $\mathcal{M}^{a}$ is ND, we can get:

$S^{a}(\theta^{\prime})\geq 0$

We have mentioned in Theorem 4 that
$\pi^{a}_{i}(\theta^{\prime})v_{i}-x^{a}_{i}(\theta^{\prime})$ is the utility
of agent $i$ in the diffusion auction mechanism $\mathcal{M}^{a}$ and it is
non-negative when $\mathcal{M}^{a}$ is IR. So for agent $w$ who wins the item,
her $\pi^{a}_{w}(\theta^{\prime})=1$ and payment
$x^{a}_{w}(\theta^{\prime})\leq v_{w}$. For others, they will not get the item
and their payment $x^{a}_{i}(\theta^{\prime})\leq 0$. Therefore,

$S^{a}(\theta^{\prime})=\sum_{i\in N}x^{a}_{i}(\theta^{\prime})\leq v_{w}$

The report valuations of all agents have a finite upper bound $\overline{v}$
($\mathop{max}\limits_{i\in N}$ $v_{i}\leq\overline{v}$). Hence, $0\leq
S^{a}(\theta^{\prime})\leq\overline{v}$.

∎

If the input diffusion auction mechanism $\mathcal{M}^{a}$ is IR, non-deficit
and revenue invariant, then the instance of NRMF is

  * 1.

asymptotically budget-balanced (ABB) when the diffusion critical tree
$T(\theta^{\prime})$ is evenly growing;

  * 2.

$\epsilon$-asymptotically budget-balanced ($\epsilon$-ABB) when the diffusion
critical tree $T(\theta^{\prime})$ is branch-independent growing.

###### Proof.

After we first run diffusion auction mechanism $\mathcal{M}^{a}$ on
$\theta^{\prime}$, $T_{m_{w}}$ is the subtree that contains the item winner
and we can get $S^{a}(\theta^{\prime})$. Then when we remove the agents in
$T_{m_{w}}$ from the corresponding $G(\theta^{\prime})$ and run
$\mathcal{M}^{a}$ again, the new winner is in subtree $T_{m_{w^{\prime}}}$.
Agent $i\in N\setminus(T_{m_{w}}\cup T_{m_{w^{\prime}}})$ will never be the
item winner even if we remove the agents in $T_{m_{w}}$ or
$T_{m_{w^{\prime}}}$. Therefore, according to the definition of revenue
invariance, the attendance of these agents does not influence the revenue
gained by the $\mathcal{M}^{a}$. Hence, we can get
$B_{k}=S^{a}(\theta^{\prime})$ for
$k\in\\{1,\dots,{|\hat{r}_{s}|}\\}\setminus\\{m_{w},m_{w^{\prime}}\\}$. Let
$B_{m_{w}}=S^{a}(\theta^{\prime\prime}_{-m_{w}})$ and
$B_{m_{w}^{\prime}}=S^{a}(\theta^{\prime\prime}_{-m_{w^{\prime}}})$, and the
remaining part of revenue that has not been redistributed is

$\displaystyle S(\theta^{\prime})$
$\displaystyle=S^{a}(\theta^{\prime})-\sum_{k=1}^{|\hat{r}_{s}|}\sum_{i\in
T_{m_{k}}}\omega_{i}\cdot B_{k}$
$\displaystyle=S^{a}(\theta^{\prime})-\sum_{k=1}^{|\hat{r}_{s}|}\frac{|T_{m_{k}}|}{n}\cdot
B_{k}$
$\displaystyle=\left(1-\sum_{k\in\\{1,\dots,{|\hat{r}_{s}|}\\}\setminus\\{m_{w},m_{w^{\prime}}\\}}\frac{|T_{m_{k}}|}{n}\right)S^{a}(\theta^{\prime})$
$\displaystyle\quad-\frac{|T_{m_{w}}|}{n}\cdot
S^{a}(\theta^{\prime\prime}_{-m_{w}})-\frac{|T_{m_{w^{\prime}}}|}{n}\cdot
S^{a}(\theta^{\prime\prime}_{-m_{w^{\prime}}})$
$\displaystyle=\frac{|T_{m_{w}}|}{n}\cdot(S^{a}(\theta^{\prime})-S^{a}(\theta^{\prime\prime}_{-m_{w}}))$
$\displaystyle\quad+\frac{|T_{m_{w^{\prime}}}|}{n}\cdot(S^{a}(\theta^{\prime})-S^{a}(\theta^{\prime\prime}_{-m_{w^{\prime}}}))$

According to the Lemma 3.2, $S^{a}(\theta^{\prime})$,
$S^{a}(\theta^{\prime\prime}_{-m_{w}})$ and
$S^{a}(\theta^{\prime\prime}_{-m_{w^{\prime}}})$ are bounded. Obviously,
$(S^{a}(\theta^{\prime})-S^{a}(\theta^{\prime\prime}_{-m_{w}}))$ and
$(S^{a}(\theta^{\prime})-S^{a}(\theta^{\prime\prime}_{-m_{w^{\prime}}}))$ are
also bounded.

  * 1.

When the diffusion critical tree $T(\theta^{\prime})$ is evenly growing,
$\frac{|T_{m_{w}}|}{n}$ and $\frac{|T_{m_{w^{\prime}}}|}{n}$ approach to 0 if
$n$ approaches to infinity. Hence,

$\lim_{n\to\infty}S(\theta^{\prime})=0$

Therefore, the instance is asymptotically budget-balanced.

  * 2.

When the diffusion critical tree $T(\theta^{\prime})$ is branch-independent
growing, let $(S^{a}(\theta^{\prime})-S^{a}(\theta^{\prime\prime}_{-m_{w}}))$
and $(S^{a}(\theta^{\prime})-S^{a}(\theta^{\prime\prime}_{-m_{w^{\prime}}}))$
less than $\overline{S^{a}}$. We can get

$\lim_{n\to\infty}S(\theta^{\prime})\leq\frac{2}{|\hat{r}_{s}|}\cdot\overline{S^{a}}=\epsilon$

where $\epsilon$ is a constant. Therefore, the instance is
$\epsilon$-asymptotically budget-balanced.

∎

Note that if the corresponding diffusion auction is also revenue monotonic,
$S^{a}(\theta^{\prime})\geq S^{a}(\theta^{\prime\prime}_{-m_{w}})$ and
$S^{a}(\theta^{\prime})\geq S^{a}(\theta^{\prime\prime}_{-m_{w^{\prime}}})$.
Then the $\epsilon$ in Theorem 3.2 can be
$\frac{2}{|\hat{r}_{s}|}\cdot\overline{v}$.

##  4\. Instances of The Redistribution Mechanism Framework

In our network-based redistribution mechanism framework, if we require the
output mechanism to be IC and IR, then the input diffusion auction mechanism
should also be IC, IR and non-deficit. The largest known set of diffusion
auction mechanisms with the above properties is Critical Diffusion Mechanism
(CDM) Li et al. (2019). Especially, the first diffusion auction mechanism,
Incentive Diffusion Mechanism (IDM) Li et al. (2017) is also a member in CDM,
which has the highest efficiency. In this section, we input IDM and another
mechanism in CDM called Threshold Neighbourhood Mechanism (TNM) Li et al.
(2022) into our framework to see the outcomes.

For convenience, we briefly introduce the idea of the IDM and TNM with our
notations. Both IDM and TNM first find the agent with the highest valuation
and their critical ancestors. Then the mechanisms check these agents from the
sponsor to the agent with the highest valuation. For IDM, each agent will pay
a certain amount to her critical parent, which is the highest valuation after
removing herself from the graph. Then, she will acquire the item temporarily.
If her valuation is the highest after removing her critical descendants, she
will be the winner and the mechanism terminates. By contrast, agent under TNM
will remove all her descendants (including non-critical ones) when we check
the winner. In addition, when agents get item, they will also pay the same
amount of money as the IDM, but their critical parents will just get the value
of the highest valuation when we ignore all their descendants. The rest of the
payments will be directly given to the sponsor.

(1)

(2)

(3)

(4)

(5)

(6)

Figure 5. Two running examples of the IDM based and TNM based instance
mechanisms of NRMF. (1) shows a graph $G(\theta^{\prime})$ generated from a
report profile $\theta^{\prime}$. (2) is the corresponding graph
$G(\theta^{\prime})$ under the diffusion action mechanism IDM, where the red
arrows mean the payment transfers of agents. The item is allocated to agent
$J$. (3) is the corresponding graph $G(\theta^{\prime})$ under TNM. The red
arrows also mean the payment transfers of agents. However, the item is
allocated to agent $H$ which is the difference. (4) shows the coefficients
$\omega_{i}$ of agents and we set $\alpha=0.8$. (5) and (6) shows the final
utilities corresponding to IDM mechanism input and TNM mechanism input
respectively.

We show two running examples of the redistribution mechanism with IDM and TNM
in Figure 5. Both IDM and TNM first find the agent $J$ who has the highest
valuation. Then they check the critical path $s\rightarrow A\rightarrow
H\rightarrow J$. Under IDM, the item is allocated to the agent $J$ and the
sponsor’s revenue is $9$. After removing the all agents in the subtree rooted
by agent $A$, the revenue gained by the sponsor under IDM is $7$. Therefore,
if we set $\alpha=0.8$, the final utility of agent $J$ is $14-13+0.032\times
7=1.224$. When it comes to TNM, the agent $H$ will win the item because she is
the agent who reports the highest valuation after removing the agent $J$ and
$K$ on the critical path. $H$’s critical parent $A$ will get the highest
valuation $9$ after removing all $A$’s descendants and the rest $1$ of $H$’s
payment will be directly given to the sponsor. Similarly, after removing the
all agents in the subtree rooted by $A$, sponsor still gets $7$. The final
utility of agent $H$ is $11-10+0.117\times 7=1.819$.

##  5\. Discussion and Conclusion

In this paper, we focus on redistribution mechanism design on social networks,
where a sponsor wants to incentivize agents to invite their neighbours to
participate in, and allocate a single item without seeking any profit. To
achieve the goal, we propose a network-based redistribution mechanism
framework (NRMF) that can construct a diffusion redistribution mechanism from
any diffusion auction. The NRMF will maintain the properties of incentive
compatibility and individual rationality of the original diffusion auction,
and also be non-deficit if the original diffusion auction is revenue
monotonic.

Moreover, without affecting the efficiency of the diffusion auction, NRMF can
achieve the property of asymptotically budget-balanced (ABB) or
$\epsilon$-asymptotically budget-balanced. We consider ABB rather than budget-
balance (BB), which requires that all revenue be returned back to buyers
ideally. It is common even under the traditional settings because no
mechanisms can satisfy all the properties of efficiency , IC, IR and BB
according to Green-Laffont impossibility theorem Green and Laffont (1979).
When it comes to our setting, the above impossibility theorem still holds. The
reason is that the special cases where all agents are directly connected to
the sponsor in the network are equivalent to the cases in the traditional
settings. However, in diffusion auction mechanism design, efficiency is
usually abandoned because it is even impossible to design a diffusion auction
mechanism that satisfies efficiency, IC, IR and non-deficit simultaneously Li
et al. (2022).

If we require the output mechanism to be IC and IR in NRMF, then the input
mechanism must be IC, IR and non-deficit. The output redistribution mechanism
achieves the same level of social welfare as the input mechanism.

In theory, without efficiency, the impossibility that BB cannot be achieved is
missing in our setting. Actually, it is possible to satisfy the properties of
IC, IR and BB simultaneously. For example, when we input the fixed pricing
diffusion auction mechanisms into our framework, the corresponding output
mechanisms are always BB. It is an interesting future work that finding the
relationship between the efficiency and the residual budget after the
redistribution.

This work is supported by Science and Technology Commission of Shanghai
Municipality (No. 23010503000 and No. 22ZR1442200) and Shanghai Frontiers
Science Center of Human-centered Artificial Intelligence (ShangHAI).

## References

  * (1)
  * Cavallo (2006) Ruggiero Cavallo. 2006\.  Optimal decision-making with minimal waste: strategyproof redistribution of VCG payments. In _5th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2006), Hakodate, Japan, May 8-12, 2006_. ACM, 882–889.
  * Clarke (1971) Edward H Clarke. 1971\.  Multipart pricing of public goods.  _Public choice_ (1971), 17–33.
  * Easley and Kleinberg (2010) David A. Easley and Jon M. Kleinberg. 2010.  _Networks, Crowds, and Markets - Reasoning About a Highly Connected World_.  Cambridge University Press.
  * Green and Laffont (1979) Jerry Green and Jean-Jacques Laffont. 1979.  _Incentives in public decision-making_.  Elsevier North-Holland.
  * Groves (1973) Theodore Groves. 1973\.  Incentives in teams.  _Econometrica: Journal of the Econometric Society_ (1973), 617–631.
  * Guo (2011a) Mingyu Guo. 2011a.  VCG Redistribution with Gross Substitutes. In _Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2011, San Francisco, California, USA, August 7-11, 2011_ , Wolfram Burgard and Dan Roth (Eds.). AAAI Press.  http://www.aaai.org/ocs/index.php/AAAI/AAAI11/paper/view/3733
  * Guo (2011b) Mingyu Guo. 2011b.  VCG redistribution with gross substitutes. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 25. 675–680.
  * Guo (2016) Mingyu Guo. 2016\.  Competitive VCG redistribution mechanism for public project problem. In _International Conference on Principles and Practice of Multi-Agent Systems_. Springer, 279–294.
  * Guo and Conitzer (2009) Mingyu Guo and Vincent Conitzer. 2009.  Worst-case optimal redistribution of VCG payments in multi-unit auctions.  _Games and Economic Behavior_ 67, 1 (2009), 69–98.
  * Jackson (2010) Matthew O Jackson. 2010\.  _Social and economic networks_.  Princeton university press.
  * Kawasaki et al. (2020) Takehiro Kawasaki, Nathanaël Barrot, Seiji Takanashi, Taiki Todo, and Makoto Yokoo. 2020\.  Strategy-Proof and Non-Wasteful Multi-Unit Auction via Social Network. In _The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020_. 2062–2069.
  * Li et al. (2022) Bin Li, Dong Hao, Hui Gao, and Dengji Zhao. 2022\.  Diffusion auction design.  _Artificial Intelligence_ 303 (2022), 103631.
  * Li et al. (2019) Bin Li, Dong Hao, Dengji Zhao, and Makoto Yokoo. 2019\.  Diffusion and Auction on Graphs. In _Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019_. 435–441.
  * Li et al. (2017) Bin Li, Dong Hao, Dengji Zhao, and Tao Zhou. 2017\.  Mechanism Design in Social Networks. In _Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA_. AAAI Press, 586–592.  http://aaai.org/ocs/index.php/AAAI/AAAI17/paper/view/14879
  * Manisha et al. (2018) Padala Manisha, CV Jawahar, and Sujit Gujar. 2018\.  Learning Optimal Redistribution Mechanisms Through Neural Networks. In _Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems_. 345–353.
  * Moulin (2009) Hervé Moulin. 2009\.  Almost budget-balanced VCG mechanisms to assign multiple objects.  _Journal of Economic theory_ 144, 1 (2009), 96–119.
  * Vickrey (1961) William Vickrey. 1961\.  Counterspeculation, auctions, and competitive sealed tenders.  _The Journal of finance_ 16, 1 (1961), 8–37.
  * Zhang et al. (2020) Wen Zhang, Dengji Zhao, and Yao Zhang. 2020.  Incentivize Diffusion with Fair Rewards.  In _ECAI 2020_. IOS Press, 251–258.
  * Zhao ([n.d.]) Dengji Zhao. [n.d.].  Mechanism design powered by social interactions: a call to arms. In _Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22_. 5831–5835.
  * Zhao (2021) Dengji Zhao. 2021\.  Mechanism Design Powered by Social Interactions. In _Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems_. 63–67.
  * Zhao et al. (2018) Dengji Zhao, Bin Li, Junping Xu, Dong Hao, and Nicholas R. Jennings. 2018.  Selling Multiple Items via Social Networks. In _Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS 2018, Stockholm, Sweden, July 10-15, 2018_. 68–76.


# A remark on certain integral operators of fractional type

Pablo A. Rocha  Universidad Nacional del Sur, INMABB (Conicet), Bahía Blanca,
8000 Buenos Aires, Argentina<EMAIL_ADDRESS>
###### Abstract.

For $m,n\in\mathbb{N}$, $1<m\leq n$, we write $n=n_{1}+...+n_{m}$ where
$\\{n_{1},...,n_{m}\\}\subset\mathbb{N}$. Let $A_{1},...,A_{m}$ be $n\times n$
singular real matrices such that

$\bigoplus_{i=1}^{m}\bigcap_{1\leq j\neq i\leq
m}\mathcal{N}_{j}=\mathbb{R}^{n},$

where $\mathcal{N}_{j}=\\{x:A_{j}x=0\\}$, $dim(\mathcal{N}_{j})=n-n_{j}$ and
$A_{1}+...+A_{m}$ is invertible. In this paper we study integral operators of
the form

$Tf(x)=\int_{\mathbb{R}^{n}}\,|x-A_{1}y|^{-n_{1}+\alpha_{1}}\cdot\cdot\cdot|x-A_{m}y|^{-n_{m}+\alpha_{m}}f(y)\,dy,$

$n=n_{1}+...+n_{m}$,
$\frac{\alpha_{1}}{n_{1}}=...=\frac{\alpha_{m}}{n_{m}}=r$, $0<r<1$, and the
matrices $A_{i}^{\prime}$s are as above. We obtain the
$H^{p}(\mathbb{R}^{n})-L^{q}(\mathbb{R}^{n})$ boundedness of $T$ for
$0<p<\frac{1}{r}$ and $\frac{1}{q}=\frac{1}{p}-r$.

Key words and phrases: Integral operators, Hardy spaces.

2.010 Math. Subject Classification: 42B20, 42B30.

Partially supported by CONICET

##  1\. Introduction

For $0\leq\alpha<n$ and $m>1$, ($m\in\mathbb{N}$), let $T_{\alpha,m}$ be the
integral operator defined by

(1)
$T_{\alpha,m}f(x)=\int_{\mathbb{R}^{n}}\left|x-A_{1}y\right|^{-\alpha_{1}}\cdot\cdot\cdot\left|x-A_{m}y\right|^{-\alpha_{m}}f(y)dy,$

where $\alpha_{1},...,\alpha_{m}$ are positive constants such that
$\alpha_{1}+...+\alpha_{m}=n-\alpha$, and $A_{1},...,A_{m}$ are $n\times n$
invertible matrices such that $A_{i}\neq A_{j}$ if $i\neq j$. We observe that
for the case $\alpha>0$, $m=1$, and $A_{1}=I$, $T_{\alpha,1}$ is the Riesz
potential $I_{\alpha}$. Thus for $0<\alpha<n$ the operator $T_{\alpha,m}$ is a
kind of generalization of the Riesz potential. The case $\alpha=0$ and $m>1$
was studied under the additional assumption that $A_{i}-A_{j}$ are invertible
if $i\neq j$. The behavior of this class of operators and generalizations of
them on the spaces of functions $L^{p}(\mathbb{R}^{n})$, $L^{p}(w)$,
$H^{p}(\mathbb{R}^{n})$ and $H^{p}(w)$ was studied in [1], [2], [4], [5], [7]
and [8].

If $0<\alpha<n$ and $m>1$, then the operator $T_{\alpha,m}$ has the same
behavior that the Riesz potential on $L^{p}(\mathbb{R}^{n})$. Indeed

$|T_{\alpha,m}f(x)|\leq
C\sum_{j=1}^{m}\int_{\mathbb{R}^{n}}|A_{j}^{-1}x-y|^{\alpha-n}|f(y)|dy=C\sum_{j=1}^{m}I_{\alpha}(|f|)(A_{j}^{-1}x),$

for all $x\in\mathbb{R}^{n}$, this pointwise inequality implies that
$T_{\alpha,m}$ is a bounded operator from $L^{p}(\mathbb{R}^{n})$ into
$L^{q}(\mathbb{R}^{n})$ for $1<p<\frac{n}{\alpha}$ and
$\frac{1}{q}=\frac{1}{p}-\frac{\alpha}{n}$, and it is of type weak
$(1,n/n-\alpha)$.

It is well known that the Riesz potential $I_{\alpha}$ is bounded from
$H^{p}(\mathbb{R}^{n})$ into $H^{q}(\mathbb{R}^{n})$ for $0<p\leq 1$ and
$\frac{1}{q}=\frac{1}{p}-\frac{\alpha}{n}$ (see [11] and [3]). In [8], the
author jointly with M. Urciuolo proved the
$H^{p}(\mathbb{R}^{n})-L^{q}(\mathbb{R}^{n})$ boundedness of the operator
$T_{\alpha,m}$ and we also showed that the
$H^{p}(\mathbb{R})-H^{q}(\mathbb{R})$ boundedness does not hold for
$0<p\leq\frac{1}{1+\alpha}$, $\frac{1}{q}=\frac{1}{p}-\alpha$ and
$T_{\alpha,m}$ with $0\leq\alpha<1$, $m=2$, $A_{1}=1$, and $A_{2}=-1$. This is
a significant difference with respect to the case $0<\alpha<1$, $n=m=1$, and
$A_{1}=1$.

In this note we will prove that if we consider certain singular matrices in
(1), then such an operator is still bounded from $H^{p}$ into $L^{q}$. More
precisely, for $m,n\in\mathbb{N}$, $1<m\leq n$, we write $n=n_{1}+...+n_{m}$
where $\\{n_{1},...,n_{m}\\}\subset\mathbb{N}$, we also consider $n\times n$
singular real matrices $A_{1},...,A_{m}$ such that

$\bigoplus_{i=1}^{m}\bigcap_{1\leq j\neq i\leq
m}\mathcal{N}_{j}=\mathbb{R}^{n},$

where $\mathcal{N}_{j}=\\{x:A_{j}x=0\\}$, $dim(\mathcal{N}_{j})=n-n_{j}$,
$A_{1}+...+A_{m}$ is invertible. Given $0<r<1$ and $n_{1},...,n_{m}$ such that
$n_{1}+...+n_{m}=n$, let $\alpha_{1},...,\alpha_{m}$ be positive constants
such that $\frac{\alpha_{1}}{n_{1}}=...=\frac{\alpha_{m}}{n_{m}}=r$, for such
parameters we define the integral operator $T_{r}$ by

(2)
$T_{r}f(x)=\int_{\mathbb{R}^{n}}\,|x-A_{1}y|^{-n_{1}+\alpha_{1}}\cdot\cdot\cdot|x-A_{m}y|^{-n_{m}+\alpha_{m}}f(y)\,dy,$

where the matrices $A_{i}^{\prime}$s are as above.

We observe that the operator defined in (2) can be written as in (1) taking
there the matrices $A_{i}$’s singular. In fact, $T_{r}=T_{\beta,m}$ with
$\beta_{i}=n_{i}-\alpha_{i}$ for each $i=1,2,...,m$ and $\beta=nr$.

Our main result is the following

Theorem 1. Let $T_{r}$ be the integral operator defined in $(\ref{T})$. If
$0<r<1$, $0<p<\frac{1}{r}$ and $\frac{1}{q}=\frac{1}{p}-r$, then $T_{r}$ can
be extended to an $H^{p}(\mathbb{R}^{n})-L^{q}(\mathbb{R}^{n})$ bounded
operator.

In Section 2 we state two auxiliary lemmas to get the main result in Section
3. We conclude this note with an example in Section 4.

Throughout this paper, $c$ will denote a positive constant, not necessarily
the same at each occurrence. The symbol $A\lesssim B$ stands for the
inequality $A\leq cB$ for some constant $c$.

##  2\. Preliminary results

Let $K$ be a kernel in $\mathbb{R}^{n}\times\mathbb{R}^{n}$, we formally
define the integral operator $T_{K}$ by
$T_{K}f(x)=\int_{\mathbb{R}^{n}}K(x,y)f(y)dy$.

We start with the following

Lemma 1. Let $m,n\in\mathbb{N}$, with $1<m\leq n$, and let $n_{1},...,n_{m}$
be natural numbers such that $n_{1}+...+n_{m}=n$. For each $i=1,...,m$ let
$K_{i}$ be kernels in $\mathbb{R}^{n_{i}}\times\mathbb{R}^{n_{i}}$ such that
the operator $T_{K_{i}}$ is bounded from $L^{p}(\mathbb{R}^{n_{i}})$ into
$L^{q}(\mathbb{R}^{n_{i}})$ with $1<p,q<\infty$, then the operator
$T_{K_{1}\otimes\cdot\cdot\cdot\otimes K_{m}}$ is bounded from
$L^{p}(\mathbb{R}^{n})$ into $L^{q}(\mathbb{R}^{n})$.

Proof. Since
$\mathbb{R}^{n}=\mathbb{R}^{n_{1}}\times\cdot\cdot\cdot\times\mathbb{R}^{n_{m}}$
let
$x=(x^{1},...,x^{m})\in\mathbb{R}^{n_{1}}\times\cdot\cdot\cdot\times\mathbb{R}^{n_{m}}$,
now the operator $T_{K_{1}\otimes\cdot\cdot\cdot\otimes K_{m}}$ is given by

$T_{K_{1}\otimes\cdot\cdot\cdot\otimes
K_{m}}f(x)=\int_{\mathbb{R}^{n_{1}}\times\cdot\cdot\cdot\times\mathbb{R}^{n_{m}}}\,K_{1}(x^{1},y^{1})\cdot\cdot\cdot
K_{m}(x^{m},y^{m})f(y^{1},...,y^{m})\,dy^{1}...dy^{m}.$

Using that the kernels $K_{i}$ define bounded operators for $1\leq i\leq m$,
the lemma follows from an iterative argument and the Minkowski’s inequality
for integrals.$\blacksquare$

Lemma 2. Let $m,n\in\mathbb{N}$, with $1<m\leq n$, and let $n_{1},...,n_{m}$
be natural numbers such that $n_{1}+...+n_{m}=n$. If $A_{1},...,A_{m}$ are
$n\times n$ singular real matrices such that

$\bigoplus_{i=1}^{m}\bigcap_{1\leq j\neq i\leq
m}\mathcal{N}_{j}=\mathbb{R}^{n},$

where $\mathcal{N}_{j}=\\{x:A_{j}x=0\\}$, $dim(\mathcal{N}_{j})=n-n_{j}$, and
$A_{1}+...+A_{m}$ is invertible, then there exist two $n\times n$ invertible
matrices $B$ and $C$ such that $B^{-1}A_{j}C$ is the canonical projection from
$\mathbb{R}^{n}$ on
$\\{0\\}\times\cdot\cdot\cdot\times\mathbb{R}^{n_{j}}\times\cdot\cdot\cdot\times\\{0\\}$
for each $j=1,...,m$.

Proof. It is easy to check that

$\bigoplus_{i=1}^{m}\bigcap_{1\leq j\neq i\leq
m}\mathcal{N}_{j}=\mathbb{R}^{n}\Rightarrow\bigoplus_{1\leq i\neq k\leq
m}\bigcap_{1\leq j\neq i\leq m}\mathcal{N}_{j}=\mathcal{N}_{k}$

so

(3) $A_{k}\left(\bigcap_{1\leq j\neq k\leq
m}\mathcal{N}_{j}\right)=\mathcal{R}(A_{k}),\,\,\,\,\,\,\,\,k=1,...,m,$

since $dim(\mathcal{N}_{k})=n-n_{k}$ then $dim\left(\bigcap_{1\leq j\neq k\leq
m}\mathcal{N}_{j}\right)=dim(\mathcal{R}(A_{k}))=n_{k}$. Let
$\\{\gamma_{1}^{k},...,\gamma_{n_{k}}^{k}\\}$ be a basis of $\bigcap_{1\leq
j\neq k\leq m}\mathcal{N}_{j}$ thus
$\\{\gamma_{1}^{1},...,\gamma_{n_{1}}^{1},...,\gamma_{1}^{m},...,\gamma_{n_{m}}^{m}\\}$
is a basis for $\mathbb{R}^{n}$. Let $C$ be the $n\times n$ matrix which
columns are the elements of the above basis. Since $A_{1}+...+A_{m}$ is
invertible we have that $B=(A_{1}+...+A_{m})C$ is invertible, so (3) gives
that $B^{-1}A_{j}C$ is the canonical projection from $\mathbb{R}^{n}$ on
$\\{0\\}\times\cdot\cdot\cdot\times\mathbb{R}^{n_{j}}\times\cdot\cdot\cdot\times\\{0\\}$
for each $j=1,...,m$. $\blacksquare$

##  3\. The main result

Proof of the Theorem 1. We begin by obtaining the $L^{p}-L^{q}$ boundedness of
the operator $T_{r}$ for $1<p<\frac{1}{r}$ and $\frac{1}{q}=\frac{1}{p}-r$,
and then with this result we will prove the $H^{p}-L^{q}$ boundedness of
$T_{r}$ for $0<p\leq 1$ and $\frac{1}{q}=\frac{1}{p}-r$.

$L^{p}-L^{q}$ boundedness. If $A$ is a $n\times n$ invertible matrix we put
$f_{A}(x)=f(A^{-1}x)$. Let $B$ and $C$ be the matrices given by Lemma 2, then

$\left[T_{r}\left(f_{C}\right)\right]_{B^{-1}}(x)=$
$\int_{\mathbb{R}^{n}}\,\left|(Bx-
A_{1}y)\right|^{-n_{1}+\alpha_{1}}\cdot\cdot\cdot\left|(Bx-
A_{m}y)\right|^{-n_{m}+\alpha_{m}}f(C^{-1}y)\,dy=$
$\left|det(C)\right|\int_{\mathbb{R}^{n}}\,\left|B(x-B^{-1}A_{1}Cy)\right|^{-n_{1}+\alpha_{1}}\cdot\cdot\cdot\left|B(x-B^{-1}A_{m}Cy)\right|^{-n_{m}+\alpha_{m}}f(y)\,dy.$

Since $B$ is invertible, then there exists a positive constant $c$ such that
$c|x|\leq|Bx|$ for all $x\in\mathbb{R}^{n}$. Thus

$\left|\left[T_{r}\left(f_{C}\right)\right]_{B^{-1}}(x)\right|\leq
c\int_{\mathbb{R}^{n}}\,\left|x-B^{-1}A_{1}Cy\right|^{-n_{1}+\alpha_{1}}\cdot\cdot\cdot\left|x-B^{-1}A_{m}Cy\right|^{-n_{m}+\alpha_{m}}|f(y)|\,dy$
$\leq
c\int_{\mathbb{R}^{n_{1}}\times...\times\mathbb{R}^{n_{m}}}\,\left|x^{1}-y^{1}\right|^{-n_{1}+\alpha_{1}}\cdot\cdot\cdot\left|x^{m}-y^{m}\right|^{-n_{m}+\alpha_{m}}|f(y^{1},...,y^{m})|\,dy^{1}...dy^{m},$

the second inequality it follows from Lemma 2 and from that
$|x^{j}-y^{j}|\leq|x-P_{j}y|$, where $P_{j}=B^{-1}A_{j}C$ is the canonical
projection from $\mathbb{R}^{n}$ on
$\\{0\\}\times\cdot\cdot\cdot\times\mathbb{R}^{n_{j}}\times\cdot\cdot\cdot\times\\{0\\}$.
Since $\gamma(\alpha_{j})^{-1}|x^{j}-y^{j}|^{-n_{j}+\alpha_{j}}$, for an
appropriate constant $\gamma(\alpha_{j})$ (see [9], p. 117), is the kernel of
the Riesz potential on $\mathbb{R}^{n_{j}}$, then Theorem 1 (in [9], p. 119)
and Lemma 1 give the $L^{p}-L^{q}$ boundedness of the operator $T_{r}$ for
$1<p<\frac{1}{r}$ and $\frac{1}{q}=\frac{1}{p}-r$.

$H^{p}-L^{q}$ boundedness. Let $0<p\leq 1.$ We recall that a $p$-atom is a
measurable function $a$ supported on a ball $B$ of $\mathbb{R}^{n}$ satisfying

$a)$ $\left\|a\right\|_{\infty}\leq\left|B\right|^{-\frac{1}{p}}$

$b)$ $\int y^{\beta}a(y)dy=0$ for every multiindex $\beta$ with
$\left|\beta\right|\leq\lfloor n(p^{-1}-1)\rfloor$, ($\lfloor s\rfloor$
denotes the integer part of $s$).

Let $0<p\leq 1<p_{0}<\frac{1}{r}$, $0<r<1$, and $\frac{1}{q}=\frac{1}{p}-r$.
Given $f\in H^{p}(\mathbb{R}^{n})\cap L^{p_{0}}(\mathbb{R}^{n})$, from Theorem
2, p. 107, in [10] we have that there exist a sequence of nonnegative numbers
$\\{\lambda_{j}\\}_{j=1}^{\infty}$, a sequence of balls
$B_{j}=B(z_{j},\delta_{j})$ centered at $z_{j}$ with radius $\delta_{j}$ and
$p$ \- atoms $a_{j}$ supported on $B_{j}$, satisfying

(4) $\sum\limits_{j\in\mathbb{N}}\left|\lambda_{j}\right|^{p}\leq
c\left\|f\right\|_{H^{p}}^{p},$

such that $f$ can be decomposed as
$f=\sum\limits_{j\in\mathbb{N}}\lambda_{j}a_{j},$ where the convergence is in
$H^{p}$ and in $L^{p_{0}}$ (for the converge in $L^{p_{0}}$ see Theorem 5 in
[6]). So the $H^{p}-L^{q}$ boundedness of $T_{r}$ will be proved if we show
that there exists $c>0$ such that

(5) $\left\|T_{r}a_{j}\right\|_{L^{q}}\leq c$

with $c$ independent of the $p$-atom $a_{j}$. Indeed, since
$f=\sum_{j=1}^{\infty}\lambda_{j}a_{j}$ in $L^{p_{0}}$ and $T_{r}$ is a
$L^{p_{0}}-L^{\frac{p_{0}}{1-rp_{0}}}$ bounded operator, we have that
$|T_{r}f(x)|\leq\sum_{j=1}^{\infty}\lambda_{j}|T_{r}a_{j}(x)|$ a.e.$x$, this
pointwise estimate, the inequality in (5), joint to the inequality

$\left(\sum_{j\in\mathbb{N}}|\lambda_{j}|^{\min\\{1,q\\}}\right)^{\frac{1}{\min\\{1,q\\}}}\leq\left(\sum_{j\in\mathbb{N}}|\lambda_{j}|^{p}\right)^{\frac{1}{p}}$

and (4) we obtain $\left\|T_{r}f\right\|_{q}\leq c\left\|f\right\|_{H^{p}}$,
for all $f\in H^{p}(\mathbb{R}^{n})\cap L^{p_{0}}(\mathbb{R}^{n})$, so the
theorem follows from the density of $H^{p}(\mathbb{R}^{n})\cap
L^{p_{0}}(\mathbb{R}^{n})$ in $H^{p}(\mathbb{R}^{n})$.

We will prove the estimate in (5). We define $D=\max_{1\leq i\leq
m}\max_{|y|=1}|A_{i}(y)|$. Let $a_{j}$ be an $p$ \- atom supported on a ball
$B_{j}=B(z_{j},\delta_{j})$, for each $1\leq i\leq m$ let
$B_{ji}^{\ast}=B(A_{i}z_{j},4D\delta_{j})$. Since $T_{r}$ is bounded from
$L^{p_{0}}\left(\mathbb{R}^{n}\right)$ into
$L^{q_{0}}\left(\mathbb{R}^{n}\right)$ for
$\frac{1}{q_{0}}=\frac{1}{p_{0}}-r,$ $1<p_{0}<\frac{1}{r},$ the Hölder
inequality gives

$\int\limits_{\bigcup\limits_{1\leq i\leq
m}B_{ji}^{\ast}}\left|T_{r}a_{j}(x)\right|^{q}dx\leq\sum\limits_{1\leq i\leq
m}\int\limits_{B_{ji}^{\ast}}\left|T_{r}a_{j}(x)\right|^{q}dx$ $\leq
c\sum\limits_{1\leq i\leq
m}\left|B_{ji}^{\ast}\right|^{1-\frac{q}{q_{0}}}\left\|T_{r}a_{j}\right\|_{q_{0}}^{q}\leq
c\delta_{j}^{n-\frac{nq}{q_{0}}}\left\|a_{j}\right\|_{p_{0}}^{q}$ $\leq
c\delta_{j}^{n-\frac{nq}{q_{0}}}\left(\int\limits_{B_{j}}\left|a_{j}\right|^{p_{0}}\right)^{\frac{q}{p_{0}}}\leq
c\delta_{j}^{n-\frac{nq}{q_{0}}}\delta_{j}^{-\frac{nq}{p}}\delta_{j}^{\frac{nq}{p_{0}}}=c.$

We denote
$k(x,y)=\left|x-A_{1}y\right|^{-n_{1}+\alpha_{1}}...\left|x-A_{m}y\right|^{-n_{m}+\alpha_{m}}$
and we put $N-1=\lfloor n(p^{-1}-1)\rfloor$. In view of the moment condition
of $a_{j}$ we have

(6)
$T_{r}a_{j}(x)=\int\limits_{B_{j}}k(x,y)a_{j}(y)dy=\int\limits_{B_{j}}\left(k(x,y)-q_{N,j}\left(x,y\right)\right)a_{j}(y)dy,$

where $q_{N,j}$ is the degree $N-1$ Taylor polynomial of the function
$y\rightarrow k(x,y)$ expanded around $z_{j}$. By the standard estimate of the
remainder term of the taylor expansion, there exists $\xi$ between $y$ and
$z_{j}$ such that

$\left|k(x,y)-q_{N,j}\left(x,y\right)\right|\lesssim\left|y-z_{j}\right|^{N}\sum\limits_{k_{1}+...+k_{n}=N}\left|\frac{\partial^{N}}{\partial
y_{1}^{k_{1}}...\partial y_{n}^{k_{n}}}k(x,\xi)\right|$
$\lesssim\left|y-z_{j}\right|^{N}\left(\prod\limits_{i=1}^{m}\left|x-A_{i}\xi\right|^{-n_{i}+\alpha_{i}}\right)\left(\sum\limits_{l=1}^{m}\left|x-A_{l}\xi\right|^{-1}\right)^{N}.$

Now we decompose $\mathbb{R}^{n}=\bigcup_{i=1}^{m}B_{ji}^{\ast}\cup R_{j}$,
where $R_{j}=\left(\bigcup_{i=1}^{m}B_{ji}^{\ast}\right)^{c}$, at the same
time we decompose $R_{j}=\bigcup_{k=1}^{m}R_{jk}$ with

$R_{jk}=\\{x\in R_{j}:|x-A_{k}z_{j}|\leq|x-A_{i}z_{j}|\,\,for\,\,all\,\,i\neq
k\\}.$

If $x\in R_{j}$ then $|x-A_{i}z_{j}|\geq 4D\delta_{j}$, for all $i=1,...,m$,
since $\xi\in B_{j}$ it follows that $|A_{i}z_{j}-A_{i}\xi|\leq
D\delta_{j}\leq\frac{1}{4}|x-A_{i}z_{j}|$ so

$|x-A_{i}\xi|=|x-A_{i}z_{j}+A_{i}z_{j}-A_{i}\xi|\geq|x-A_{i}z_{j}|-|A_{i}z_{j}-A_{i}\xi|\geq\frac{3}{4}|x-A_{i}z_{j}|.$

If $x\in R_{j}$, then $x\in R_{jk}$ for some $k$, and since
$\sum_{i=1}^{m}(-n_{i}+\alpha_{i})=-n(1-r)$ we obtain

$\left|k(x,y)-q_{N,j}\left(x,y\right)\right|\lesssim\left|y-z_{j}\right|^{N}\left(\prod\limits_{i=1}^{m}\left|x-A_{i}z_{j}\right|^{-n_{i}+\alpha_{i}}\right)\left(\sum\limits_{l=1}^{m}\left|x-A_{l}z_{j}\right|^{-1}\right)^{N},$
$\lesssim\left|y-z_{j}\right|^{N}\left|x-A_{k}z_{j}\right|^{-n(1-r)-N},\,\,\,\,\,if\,\,x\in
R_{jk}\,\,\,and\,\,\,y\in B_{j}.$

This inequality allow us to conclude that

$\int\limits_{R_{j}}\left|\int\limits_{B_{j}}K(x,y)a_{j}(y)dy\right|^{q}dx=\int\limits_{R_{j}}\left|\int\limits_{B_{j}}\left[K(x,y)-q_{N,j}(x,y)\right]a_{j}(y)dy\right|^{q}dx$
$\lesssim\sum_{k=1}^{m}\int\limits_{R_{jk}}\left(\int\limits_{B_{j}}\left|y-z_{j}\right|^{N}\left|x-A_{k}z_{j}\right|^{-n(1-r)-N}\left|a_{j}(y)\right|dy\right)^{q}dx$
$\lesssim\left(\int\limits_{B_{j}}\left|y-z_{j}\right|^{N}\left|a_{j}(y)\right|dy\right)^{q}\sum_{k=1}^{m}\int\limits_{\left(B_{jk}^{\ast}\right)^{c}}\left|x-A_{k}z_{j}\right|^{-n(1-r)q-Nq}dx$
$\lesssim\delta_{j}^{qN-n\frac{q}{p}+nq}\int\limits_{4D\delta_{j}}^{\infty}t^{-q\left(n(1-r)+N\right)+n-1}dt\leq
c$

with $c$ independent of the $p-$atom $a_{j}$ since
$-q\left(n(1-r)+N\right)+n<0.\blacksquare$

##  4\. An example

For $n=m=3$, $n_{1}=n_{2}=n_{3}=1$ we consider the following $3\times 3$
singular matrices

$A_{1}=\left(\begin{array}[]{ccc}\,\,\,4&\,\,\,4&-1\\\
\,\,\,0&\,\,\,0&\,\,\,0\\\ -4&-4&\,\,\,1\\\
\end{array}\right),\,\,\,\,\,\,A_{2}=\left(\begin{array}[]{ccc}\,\,\,1&-1&0\\\
-2&\,\,\,2&0\\\ \,\,\,0&\,\,\,0&0\\\
\end{array}\right),\,\,\,\,\,\,A_{3}=\left(\begin{array}[]{ccc}\,\,\,1&0&-1\\\
-3&0&\,\,\,3\\\ -1&0&\,\,\,1\\\ \end{array}\right).$

It is clear that

$A_{1}+A_{2}+A_{3}=\left(\begin{array}[]{ccc}\,\,\,6&\,\,\,3&-2\\\
-5&\,\,\,2&\,\,\,3\\\ -5&-4&\,\,\,2\\\ \end{array}\right)$

is invertible. For each $j=1,2,3,$ let
$\mathcal{N}_{j}=\\{x\in\mathbb{R}^{3}:A_{j}x=0\\}$. A computation gives

$\mathcal{N}_{1}=\langle(1,0,4),(0,1,4)\rangle,\,\,\,\mathcal{N}_{2}=\langle(1,1,0),(0,0,1)\rangle,\,\,\,\mathcal{N}_{3}=\langle(1,0,1),(0,1,0)\rangle,$

one can check that

$\mathcal{N}_{1}\cap\mathcal{N}_{2}=\langle(1,1,8)\rangle,\,\,\,\mathcal{N}_{1}\cap\mathcal{N}_{3}=\langle(4,-3,4)\rangle,\,\,\,and\,\,\,\mathcal{N}_{2}\cap\mathcal{N}_{3}=\langle(1,1,1)\rangle.$

We observe that
$\mathcal{N}_{1}\cap\mathcal{N}_{2}\oplus\mathcal{N}_{1}\cap\mathcal{N}_{3}\oplus\mathcal{N}_{2}\cap\mathcal{N}_{3}=\mathbb{R}^{3}$.
As in the proof of Lemma 2, we define the matrices $C$ and $B$ by

$C=\left(\begin{array}[]{ccc}1&\,\,\,4&1\\\ 1&-3&1\\\ 1&\,\,\,4&8\\\
\end{array}\right),\,\,\,B=(A_{1}+A_{2}+A_{3})\,C=\left(\begin{array}[]{ccc}\,\,\,7&\,\,\,7&-7\\\
\,\,\,0&-14&\,\,\,21\\\ -7&\,\,\,0&\,\,\,7\\\ \end{array}\right),$

both matrices are invertibles with

$B^{-1}=\left(\begin{array}[]{ccc}\frac{2}{21}&\frac{1}{21}&-\frac{1}{21}\\\
\\\ \frac{1}{7}&0&\,\,\,\frac{1}{7}\\\ \\\
\frac{2}{21}&\frac{1}{21}&\,\,\,\frac{2}{21}\\\ \end{array}\right).$

Now it is easy to check that

$B^{-1}A_{1}C=\left(\begin{array}[]{ccc}1&0&0\\\ 0&0&0\\\ 0&0&0\\\
\end{array}\right),\,\,\,B^{-1}A_{2}C=\left(\begin{array}[]{ccc}0&0&0\\\
0&1&0\\\ 0&0&0\\\
\end{array}\right),\,\,\,B^{-1}A_{3}C=\left(\begin{array}[]{ccc}0&0&0\\\
0&0&0\\\ 0&0&1\\\ \end{array}\right).$

So, from Theorem 1, it follows that the operator $T_{r}$ defined by

$T_{r}f(x)=\int_{\mathbb{R}^{3}}|x-A_{1}y|^{-1+r}|x-A_{2}y|^{-1+r}|x-A_{3}y|^{-1+r}f(y)dy,$

with $0<r<1$, is a bounded operator from $H^{p}(\mathbb{R}^{3})$ into
$L^{q}(\mathbb{R}^{3})$ for $0<p<1/r$ and $\frac{1}{q}=\frac{1}{p}-r$.

## References

  * [1] T. GODOY, M. URCIUOLO, About the $L^{p}$ boundedness of some integral operators, Revista de la UMA 38, 192-195, (1993).
  * [2] T. GODOY and M. URCIUOLO, On certain integral operators of fractional type, Acta Mathematica Hungar. (82), 99-105, (1999).
  * [3] S. KRANTZ, Fractional integration on Hardy spaces, Studia Mathematica, vol 73 (2), 87-94, (1982).
  * [4] M. S. RIVEROS and M. URCIUOLO, Weighted inequalities for integral operators with some homogeneous kernels, Czechoslovak Math. J., 55 (130), (2005), 423-432.
  * [5] M. S. RIVEROS and M. URCIUOLO, Weighted $H^{p}-L^{q}$ boundedness of integral operators with rough kernels. Preprint.
  * [6] P. ROCHA, A note on Hardy spaces and bounded linear operators . To appear in Georgian Math. Journal.
  * [7] P. ROCHA and M. URCIUOLO, On the Hp-Lp boundedness of some integral operators. Georgian Math. Journal, Vol 18, (4), 801 - 808, (2011).
  * [8] P. ROCHA and M. URCIUOLO, On the Hp-Lq boundedness of some fractional integral operators. Czechoslovak Math. Journal, 62 (137), 625 - 635, (2012).
  * [9] E. STEIN, Singular Integrals and Differentiability Properties of Functions, Princeton Univ. Press, 1970.
  * [10] E. STEIN, Harmonic Analysis, Real Variable Methods, Orthogonality and Oscillatory Integrals, Princeton Univ. Press, 1993.
  * [11] M. H. TAIBLESON and G. WEISS, The molecular characterization of certain Hardy spaces, Asterisque 77, 67-149, (1980).