# Connected Trading Cycles

Xinwei Song  ,  Tianyi Yang  and  Dengji Zhao  Shanghaitech UniversityChina

###### Abstract.

This paper studies one-sided matching with initial endowments and the social
connections between participants are specifically considered (their social
network). Different from the traditional setting, the matching starts with a
group of initial participants, and the others need their invitation to join
the matching game. Thus, the incentive compatibility (IC) notion here
considers both reporting preferences and inviting others via their social
connections. This is challenging because inviters and invitees might compete
in the game. Besides IC, stability and optimality are two properties
extensively studied in matching, but they both are incompatible with the new
IC. In the new setting, compatible stability has been discussed, but no
discussion about compatible optimality yet. We complete this and prove the
theoretical boundaries regarding both stability and optimality in the new
setting. We then propose a mechanism called Connected Trading Cycles to
satisfy all the desirable properties for the first time. Unlike the previous
solutions that add restrictions on participants’ matching choices to achieve
IC, we allow participants to choose anyone in the game, which in principle
improves everyone’s satisfiability in the matching. Finally, we give the first
characterization of IC in the network setting to facilitate IC mechanism
design.

††conference: ; ;

##  1\. Introduction

Mechanism design on social networks is a new trend (Zhao, 2021). It
specifically models the participants’ social connections in various games
including matching, auctions and cooperative games. The social connections are
private information for each participant, and those who are already in the
game can decide whether or not to invite their direct neighbors. The primary
purpose of this new study is to utilize participants’ social connections to
expand the markets for better outcomes. In matching, more participants will
give more matching choices and lead to a more satisfying matching outcome.
This is essentially very useful to promote a game on a social network and to
inspire new applications utilizing social platforms (such as online housing
market111https://www.homeexchange.com, https://www.lovehomeswap.com and
second-hand goods exchange markets222https://www.freecycle.org). However,
inviting others is not always beneficial. Let’s consider a simple example that
might happen in a house exchange game. Suppose there are two initial users,
Alice and Bob. As shown in Figure 1(a), Alice and Bob prefer each other’s
house and they will exchange if there is no other choice. Assuming Alice has a
friend Charlie, Bob and Charlie will prefer to exchange with each other if
three of them are in the game (Figure 1(b)). As a result, Alice will not
invite Charlie if Charlie is not in the game yet.

AliceBobCharlie

(a) Initial Market

AliceBobCharlie

(b) Inviting Charlie

Figure 1. Driving Example

According to the example, we can see that participants have the power to
selectively invite others for their own interests. Thus, the main obstacle for
mechanism design in the network setting is to provide incentives for
participants to invite all their neighbors to join the game. In auctions, we
can pay the harmed inviters some rewards (Li et al., 2022). In cooperative
games, we can let the inviters share their invitees’ contributions (Zhang and
Zhao, 2022). Matching as a non-monetary game faces a greater challenge since
the mechanism cannot compensate for the loss caused by invitation through
payments.

To evaluate a matching mechanism, optimality and stability are two crucial
properties. The former characterizes how good a matching is while the latter
depicts the robustness of a matching, i.e., whether participants have
incentives to deviate from the matching and exchange in a smaller group. The
Top Trading Cycles (TTC) presented by Shapley and Scarf (Shapley and Scarf,
1974) is proved to be the only Pareto optimal and stable mechanism for one-
sided matching with endowments (Ma, 1994). However, TTC cannot work in the
social network setting due to the lack of invitation incentives. As shown by
Kumar et al. (Kumar et al., 2022), more than half of the participants tend to
form a smaller market under TTC. In the network setting, participants can
decide the size of the market through strategic invitations, which causes the
incompatibility between IC, stability, and optimality. Hence, it is valuable
to understand what else we can achieve with IC near stability or optimality
(Kawasaki et al., 2021; Yang et al., 2022).

Previous work has defined a new notion of stability under the network setting
and has designed mechanisms to achieve it (Yang et al., 2022). As far as we
are concerned, no previous work has investigated the new notion of optimality
compatible with IC in the network setting. Therefore, we propose new notions
of optimality and prove their compatibility with IC and stability (Section 4).

Given the achievable notions of stability and optimality, we design an IC
mechanism called Connected Trading Cycles (CTC) to satisfy them (Section 5).
We concentrate on two features, trading cycles and social connections, which
are the principles of one-sided matching and social networks respectively. An
allocation in one-sided matching consists of several trading cycles among
agents. The key is to let everyone point to her favorite item, so the
correlated trading cycles ensure optimality and stability. However, whether a
trading cycle can get formed and traded is determined by its corresponding
social connections in the network. Intrinsically, in the network setting, the
trading cycles should build on a particular group of agents who know each
other through their social connections within the group. In this way, no one
outside the cycle has the power to break the trading cycle. Following this
principle, we combine two features together to design Connected Trading
Cycles. Different from the previous solutions, we do not restrict agents’
choice scope, and they can choose anyone in the game.

Finally, we give the first characterization of IC in the network setting
(Section 7). We propose two monotonicity conditions that depict IC one-sided
matching on networks to help mechanism designers construct and identify new IC
solutions.

Our Contributions

  * •

We prove the achievable notions/boundaries of stability and optimality with
incentive compatibility for one-sided matching in the network setting.

  * •

We propose a new mechanism called Connected Trading Cycles that reaches the
theoretical boundaries and dominates the existing mechanisms.

  * •

We give the first characterization of incentive-compatible one-sided matching
mechanisms in the network setting.

##  2\. Literature Review

Li et al. (Li et al., 2017) initiate the line of research on mechanism design
over social networks. This new setting models the market in a dynamic way and
makes use of the power of social networks to offer both the participants and
the market owner a better outcome (Zhao, 2021). In the social network setting,
the classic solutions cannot work anymore because they fail to provide
invitation incentives. For games with monetary transfers, like auctions and
cooperative games, we can incentivize invitations to form a larger game by
giving them rewards (Li et al., 2022; Zhang and Zhao, 2022). However, when it
comes to non-transferable utility games like matching, incentives for
invitation are harder to design.

In the network setting, the incentive compatibility notion for one-sided
matching is defined in two dimensions. Due to the expansion of IC, the
appropriate solution space for mechanism designers also changes. Thus, how to
characterize the IC one-sided matching mechanisms in the network setting is an
important problem. In literature, finding the characterization for desired
properties has always been a rich research topic. Takamiya (Takamiya, 2001)
characterizes the IC as well as the core solution for the housing market.
Later on, Sönmez and Ünver (Sönmez and Ünver, 2010) study the characterization
of a variant of the housing market. Seeking alternative depictions for TTC is
also an active research field (Sethuraman, 2016; Chen and Zhao, 2021; Anno,
2015). These works provide insights for the mechanism designers and help them
come up with better algorithms. In this paper, we present an IC
characterization of the new setting.

For matching over social networks, designing invitation incentives can help
enlarge the selection space and improve matching results for the participants.
Kawasaki et al. (Kawasaki et al., 2021) and You et al. (You et al., 2022)
degenerate social networks to trees and modify the classic mechanisms to
incentivize invitations for housing market as well as its variant
(Abdulkadiroğlu and Sönmez, 1999). Specifically, they add limits on the
selection space of the participants in a tree to incentivize invitations. Yang
et al. (Yang et al., 2022) take a step forward and propose a mechanism that
works for all networks. In their mechanism, participants can only choose from
their current neighbor set, and their neighbor set is dynamically shared when
participants leave the market. Due to the sharing process, their mechanism
gives a more efficient outcome. For two-sided matching, Cho et al. (Cho et
al., 2022) model the school choice problem into the network setting and design
invitation incentives for the student side only. Another thread of work also
takes the social network and its influence into consideration, but they differ
from our setting (Gourvès et al., 2017; Hoefer, 2013). In their setting, the
social network is priorly known and acts as a constraint for possible
allocations.

Besides incentive compatibility, optimality is another concerned property for
one-sided matching mechanisms (Abdulkadiroglu and Sönmez, 2013). The
celebrated TTC is the only Pareto optimal and stable solution in the
traditional setting (Ma, 1994). When it comes to the house allocation problem,
optimal solutions are multiple. Abraham et al. (Abraham et al., 2005) study
various ways to evaluate the optimality of a house allocation mechanism and
illustrate why TTC gives the Pareto optimal allocation. Fleischer and Wang
(Fleischer and Wang, 2008) point out the transitions between different optimal
allocations in the house allocation problem. Brandt and Wilczynski (Brandt and
Wilczynski, 2019) analyze whether different types of dynamic pairwise swaps
converge to Pareto optimal allocations for matching markets. However, no
previous work has investigated achievable optimality in the network setting.
To evaluate the efficiency of a mechanism, we need to redefine an optimality
notion in the new setting. Hence, we construct a tight optimality notion and
design a mechanism to reach it.

##  3\. The Model

In this section, we model one-sided matching over social networks with formal
definitions. A one-sided matching market consists of a set of agents
$N=\\{1,\dots,n\\}$, each with an indivisible initial endowment, usually
referred to as a house. We denote the set of endowments as
$H=\\{h_{1},\dots,h_{n}\\}$. Every agent $i$ has a strict preference
$\succ_{i}$ over the endowment set $H$. Specifically, $h_{j}\succ_{i}h_{k}$
indicates agent $i$ prefers $h_{j}$ over $h_{k}$. We use $\succeq_{i}$ to
represent a weak preference where $h_{j}\succeq_{i}h_{k}$ implies that agent
$i$ strictly prefers $h_{j}$ over $h_{k}$, or $i$ is indifferent with $h_{j}$
and $h_{k}$. To characterize the social network, we use an undirected graph
$G=(N,E)$ to depict the social connections among agents in $N$. We say agents
$i$ and $j$ are neighbors to each other if there exists an edge $(i,j)\in E$.
Let $r_{i}$ represent the neighbor set of agent $i$, then $(i,j)\in E$
indicates $i\in r_{j}$ and $j\in r_{i}$.

In our setting, the social network $G$ is not priorly known to anyone. Both
the preference and the neighbor set are private information to each agent. We
define a type profile $\theta_{i}=(\succ_{i},r_{i})$ for agent $i$, which
consists of her preference $\succ_{i}$ and her neighbor set $r_{i}$. We denote
the type profile for all agents as $\theta=(\theta_{1},\dots,\theta_{n})$ and
$\Theta$ as the type profile space. Let $\theta_{-i}$ be the type profile
without agent $i$, then we have $\theta=(\theta_{i},\theta_{-i})$.
Analogously, $\Theta=(\Theta_{i},\Theta_{-i})$. We denote agent $i$’s reported
type profile as
$\theta^{\prime}_{i}=(\succ^{\prime}_{i},r^{\prime}_{i}),\theta^{\prime}_{i}\in\Theta_{i}$.
In practice, reporting one’s neighbor set equals inviting one’s neighbors to
join the game. One cannot report a non-neighbor as her neighbor, because she
does not know the others. Thus, we have $r^{\prime}_{i}\subseteq r_{i}$ for
each agent $i$.

###### Definition 3.1.

A one-sided matching mechanism is defined by an allocation policy
$\pi=(\pi_{i})_{i\in N}$, where $\pi_{i}:\Theta\to H$ satisfies for all
$\theta\in\Theta$, for all $i$, $\pi_{i}(\theta)\in H$, and
$\pi_{i}(\theta)\neq\pi_{j}(\theta)$ for all $i\neq j$.

The above definition is the standard, and we need some constraints to cope
with the two-dimensional type profile. Since the social connections are
private information in our setting, a matching market over social networks
usually starts with an initial set of agents $N_{0}\subset N$, who are the
selected seed participants, or neighbors of the sponsor. The agents already in
the market then report their type profile $\theta^{\prime}$ to enlarge the
market. With the reported profile $\theta^{\prime}$, we construct the
diffusion matching market as a directed graph
$G(\theta^{\prime})=(N(\theta^{\prime}),E(\theta^{\prime}))$, with
$N(\theta^{\prime})=\\{1,\dots,n\\}$ and $\langle i,j\rangle\in
E(\theta^{\prime})$ indicates $j\in r^{\prime}_{i}$. We define
$Q(\theta^{\prime})$ as the set of qualified agents who can participate in the
matching and $N(\theta^{\prime})\setminus Q(\theta^{\prime})$ as the set of
unqualified agents who stay outside of the diffusion market with their initial
endowments. Note that agent $i\in Q(\theta^{\prime})$ if and only if there
exists a path from $N_{0}$ to $i$ in $G(\theta^{\prime})$, which means $i$ is
invited to the market by a series of invitations. Thus, all agents in
$Q(\theta^{\prime})$ forms a connected graph in $G(\theta^{\prime})$.

###### Definition 3.2.

A diffusion one-sided matching mechanism in social networks is a one-sided
matching mechanism, $\pi=(\pi_{i})_{i\in N}$, such that for all reported type
profiles $\theta^{\prime}\in\Theta$, it satisfies:

  1. (1)

for all unqualified agents $i\notin Q(\theta^{\prime})$,
$\pi_{i}(\theta^{\prime})=h_{i}$.

  2. (2)

for all qualified agents $i\in Q(\theta^{\prime})$, $\pi_{i}(\theta^{\prime})$
is independent of the report of all unqualified agents.

We then define desirable properties for a diffusion one-sided matching
mechanism. Firstly, to incentivize rational agents to join a game, a mechanism
should at least guarantee joining in the game is not losing for each agent if
she behaves truthfully. We call this property individual rationality.

###### Definition 3.3 (Individual Rationality (IR)).

A diffusion one-sided matching mechanism $\pi$ is individually rational if for
all $i\in N$, all $\theta_{i}\in\Theta_{i}$, and all
$\theta^{\prime}_{-i}\in\Theta_{-i}$, we have
$\pi_{i}(\theta_{i},\theta_{-i}^{\prime})\succeq_{i}h_{i}$.

Furthermore, incentivizing all agents to report their types truthfully is the
key property of diffusion mechanisms. This requires that revealing true
preference and inviting all neighbors to join in the game is a dominant
strategy for all agents. We formulate this property as incentive
compatibility.

###### Definition 3.4 (Incentive Compatibility (IC)).

A diffusion one-sided matching mechanism $\pi$ is incentive compatible if for
all $i\in N$, all $\theta^{\prime}_{-i}\in\Theta_{-i}$ and all
$\theta_{i},\theta^{\prime}_{i}\in\Theta_{i}$, we have
$\pi_{i}(\theta_{i},\theta^{\prime}_{-i})\succeq_{i}\pi_{i}(\theta^{\prime}_{i},\theta^{\prime}_{-i})$.

For one-sided matching mechanisms, stability and Pareto optimality are used to
measure the quality of the outcome. We formalize them for diffusion one-sided
matching mechanisms as follows.

###### Definition 3.5 (Stability).

A diffusion one-sided matching mechanism $\pi$ is stable if for all type
profiles $\theta$ and the allocation $\pi(\theta)$, there is no agent set
$S\subseteq N$ (with item set $H_{S}\subseteq H$) and another allocation
$\pi^{\prime}(\theta)$ with $\forall i\in S,\pi^{\prime}_{i}(\theta)\in H_{S}$
such that $\forall i\in S,\pi^{\prime}_{i}(\theta)\succeq_{i}\pi_{i}(\theta)$
and $\exists j\in S,\pi^{\prime}_{j}(\theta)\succ_{j}\pi_{j}(\theta)$.

Namely, a matching is stable if no coalition of agents wants to leave the
matching to match alone.

###### Definition 3.6 (Pareto Optimality (PO)).

A diffusion one-sided matching mechanism $\pi$ is Pareto optimal if for all
type profiles $\theta$ and the allocation $\pi(\theta)$, there is no other
diffusion one-sided matching mechanism $\pi^{\prime}$ such that $\forall i\in
N,\pi^{\prime}_{i}(\theta)\succeq_{i}\pi_{i}(\theta)$ and $\exists T\subseteq
N,T\neq\emptyset$, $\forall j\in
T,\pi^{\prime}_{j}(\theta)\succ_{j}\pi_{j}(\theta)$.

The above definition of PO is an equivalent form of that in the traditional
model. The reason why we define PO this way is for the simplicity of its
extensions in the network setting.

Yang et al.(Yang et al., 2022) prove that these two properties are not
compatible with IC and IR in the social network setting. For stability, they
propose that the group who deviate and swap among themselves be a connected
component or a complete component to define weaker notions. They show that
stable under complete components is compatible with IC. We apply the same
notions here.

###### Definition 3.7 (Stability under Connected Components (Stable-c)).

A diffusion one-sided matching mechanism $\pi$ is stable under connected
components if for all type profiles $\theta$ and the allocation $\pi(\theta)$,
there is no agent set $S\subseteq N$ (with item set $H_{S}\subseteq H$), that
forms a connected component in $G(\theta)$, and another allocation
$\pi^{\prime}(\theta)$ with $\forall i\in S,\pi^{\prime}_{i}(\theta)\in H_{S}$
such that $\forall i\in S,\pi^{\prime}_{i}(\theta)\succeq_{i}\pi_{i}(\theta)$
and $\exists j\in S,\pi^{\prime}_{j}(\theta)\succ_{j}\pi_{j}(\theta)$.

###### Definition 3.8 (Stability under Complete Components (Stable-cc)).

A diffusion one-sided matching mechanism $\pi$ is stable under complete
components if for all type profiles $\theta$ and the allocation $\pi(\theta)$,
there is no agent set $S\subseteq N$ (with item set $H_{S}\subseteq H$), that
forms a complete component in $G(\theta)$, and another allocation
$\pi^{\prime}(\theta)$ with $\forall i\in S,\pi^{\prime}_{i}(\theta)\in H_{S}$
such that $\forall i\in S,\pi^{\prime}_{i}(\theta)\succeq_{i}\pi_{i}(\theta)$
and $\exists j\in S,\pi^{\prime}_{j}(\theta)\succ_{j}\pi_{j}(\theta)$.

For optimality, we follow the new notions of stability and do a similar
relaxation. By definition, Pareto optimality requires that the allocation
cannot improve without making anyone worse off. Intuitively, we can regard the
Pareto improvement as a reallocation process posterior to a certain
allocation. In such way, we require those who can be reallocated should at
least have a path to their reallocated items. Therefore, we further require
the improved agents to be a connected component or a complete component to
weaken optimality.

###### Definition 3.9 (Optimality under Connected Components (Optimal-c)).

A diffusion one-sided matching mechanism $\pi$ is optimal under connected
components if for all type profiles $\theta$ and the allocation $\pi(\theta)$,
there is no other diffusion one-sided matching mechanism $\pi^{\prime}$ such
that $\forall i\in N,\pi^{\prime}_{i}(\theta)\succeq_{i}\pi_{i}(\theta)$ and
$\exists T\subseteq N,T\neq\emptyset$, $\forall j\in
T,\pi^{\prime}_{j}(\theta)\succ_{j}\pi_{j}(\theta)$ and $T$ forms a connected
component in $G(\theta)$.

###### Definition 3.10 (Optimality under Complete Components (Optimal-cc)).

A diffusion one-sided matching mechanism $\pi$ is optimal under complete
components if for all type profiles $\theta$ and the allocation $\pi(\theta)$,
there is no other diffusion one-sided matching mechanism $\pi^{\prime}$ such
that $\forall i\in N,\pi^{\prime}_{i}(\theta)\succeq_{i}\pi_{i}(\theta)$ and
$\exists T\subseteq N,T\neq\emptyset$, $\forall j\in
T,\pi^{\prime}_{j}(\theta)\succ_{j}\pi_{j}(\theta)$ and $T$ forms a complete
component in $G(\theta)$.

##  4\. Theoretical Boundaries

In this section, we study the relationship between stability and optimality.
Furthermore, we show that Swap With Neighbors (SWN), Swap With Children (SWC),
and Leave and Share (LS) (Yang et al., 2022), cannot satisfy any version of
optimality. We characterize the implication between different notions of
stability and optimality in Figure 2 and reveal the theoretical boundaries for
diffusion one-sided matching mechanisms.

optimal-ccoptimal-cPOstablestable-cstable-ccCTCSWCLSSWN Figure 2. Venn diagram
for optimality and stability notions. The shadowed area cannot coexist with IC
and IR.

By definition, Pareto optimality implies optimal-c and further implies
optimal-cc. Similarly, stable implies stable-c and further implies stable-
strict-c and stable-cc. The following theorems help us depict the relationship
between optimal and stable properties.

###### Theorem 4.1.

A mechanism $\pi$ is stable implies that $\pi$ is Pareto optimal.

###### Proof.

For all type profiles $\theta$, if a stable mechanism $\pi$ is not Pareto
optimal, there exists a group $T$ and $\pi^{\prime}$ such that $\forall j\in
T$, $\pi^{\prime}_{j}(\theta)\succ_{j}\pi_{j}(\theta)$, and $\forall i\in N$,
$\pi^{\prime}_{i}(\theta)\succeq_{i}\pi_{i}(\theta)$. In this case, we can
construct a group of agents $S$ starting from $T$, and consecutively add other
agents so that $\forall i\in S$, $\pi^{\prime}_{i}(\theta)\in H_{S}$. So, $S$
can deviate from the matching together which violates stable. Thus, $\pi$ is
stable implies that $\pi$ is Pareto optimal. ∎

###### Theorem 4.2.

A mechanism $\pi$ is stable-c implies that $\pi$ is Pareto optimal.

###### Proof.

For all type profiles $\theta$, if $\pi$ is stable under connected components
but fails Pareto optimal, there exists a group $T$ and $\pi^{\prime}$ such
that $\forall j\in T$, $\pi^{\prime}_{j}(\theta)\succ_{j}\pi_{j}(\theta)$, and
$\forall i\in N$, $\pi^{\prime}_{i}(\theta)\succeq_{i}\pi_{i}(\theta)$. Since
in diffusion one-sided matching, the unqualified agents always get their own
items, agents in group $T$ must be the qualified agents. Given that all
qualified agents is a connected component, they can deviate together to get
$\pi^{\prime}$ which violates stable under connected components. Thus, $\pi$
is stable-c implies that $\pi$ is Pareto optimal. ∎

###### Theorem 4.3.

A mechanism $\pi$ is stable-cc does not imply that $\pi$ is optimal-cc.

###### Proof.

Consider the example given in Figure 3, allocation
$\pi=(h_{2},h_{1},h_{4},h_{3})$ is stable under complete components. However,
there exists another allocation $\pi^{\prime}=(h_{2},h_{4},h_{1},h_{3})$ where
{2,3} is a strictly better off group. This means the stable-cc mechanism $\pi$
fails to be optimal-cc. ∎

1234 Figure 3. Preferences are $h_{3}\succ_{1}h_{2}\succ_{1}h_{1},\ \ \
h_{4}\succ_{2}h_{1}\succ_{2}h_{2},\ \ \ h_{1}\succ_{3}h_{4}\succ_{3}h_{3},\ \
\ h_{2}\succ_{4}h_{3}\succ_{4}h_{4}$.

###### Theorem 4.4.

A mechanism $\pi$ is Pareto optimal does not imply that $\pi$ is stable-cc.

###### Proof.

Consider the example given in Figure 4, allocation
$\pi=(h_{2},h_{3},h_{4},h_{1})$ is Pareto optimal. But it fails stable under
complete components because there exists another allocation
$\pi^{\prime}=(h_{1},h_{2},h_{4},h_{3})$ where {3,4} is a complete component,
they deviate and swap among themselves for a better match compared to $\pi$.
The existence of this subset of agents violates stable under complete
components. Thus, Pareto optimal fails to imply stable-cc. ∎

1234 Figure 4. Preferences are $h_{2}\succ_{1}h_{3}\succ_{1}h_{1},\ \ \
h_{3}\succ_{2}h_{2},\ \ \ h_{2}\succ_{3}h_{4}\succ_{3}h_{3},\ \ \
h_{3}\succ_{4}h_{1}\succ_{4}h_{4}$.

We can see that the theoretical boundary for diffusion one-sided matching is
attaining stable-cc and optimal-c. However, this boundary is not attainable by
any of the mechanisms proposed in the literature so far.

###### Theorem 4.5.

Swap With Children, Leave and Share, and Swap With Neighbor presented by
Kawasaki et al. and Yang et al. cannot satisfy optimal-c.

###### Proof.

In the example given in Figure 3, the allocations given by SWC, LS and SWN are
identical, which is $\pi=(h_{2},h_{1},h_{4},h_{3})$. There exists an optimal-c
allocation $\pi^{\prime}=(h_{2},h_{4},h_{1},h_{3})$ that dominates $\pi$.
Thus, these mechanisms fail optimal-c. ∎

In the next section, we present a mechanism called Connected Trading Cycles
(CTC), which allow agent 1 and 3, agent 2 and 4 swap with each other in Figure
3. We also prove that CTC satisfies optimal-c, which means it dominates the
other three mechanisms and reach the theoretical boundary.

##  5\. Connected Trading Cycles

In this section, we present our mechanism called Connected Trading Cycles
(CTC) which takes both the trading cycles and agents’ connections into
concerns. CTC can satisfy IC, optimal-c and stable-cc, which is the
theoretical boundary of the network setting. First of all, several definitions
are declared to simplify the description of our mechanism.

###### Definition 5.1.

Given a reported type profile $\theta^{\prime}$, we generate a directed graph
$F(\theta^{\prime})$, in which each qualified agent has exactly one out-degree
pointing to any qualified agent in $G(\theta^{\prime})$. The pointing from
each agent $i$ to $j$ ($i,j$ can be the same agent) means $j$ is a qualified
agent and $h_{j}$ is the smallest ranked item in $\succ_{i}^{\prime}$. We name
the graph as the favorite pointing graph for $\theta^{\prime}$.

There is at least one cycle in $F(\theta^{\prime})$ and we should clarify
whether the cycles can get traded or not. We classify the cycles into three
categories, independent connected-cycles, dependent connected-cycles and
unconnected-cycles, defined as follows. In this paper, we use connected-cycle
to represent either dependent connected-cycle or independent connected-cycle
for simplicity.

###### Definition 5.2.

Given a favorite pointing graph $F(\theta^{\prime})$ and a node sequence
$(c_{1},c_{2},...,c_{m})$, for simplicity we use $C_{i}$ to represent the node
sequence in which $i=c_{m}$. If there exists an edge $\langle
c_{j},c_{j+1}\rangle$ for any $c_{j}\in C_{i},c_{j}\neq c_{m}$ and $\langle
c_{m},c_{1}\rangle$, then there is a cycle involving $C_{i}$ in
$F(\theta^{\prime})$, we denote the cycle by $C_{i}$.

  1. a.

$C_{i}$ is an independent connected-cycle in $F(\theta^{\prime})$ if all
agents in $C_{i}$ can form a connected component in $G(\theta^{\prime})$.

  2. b.

$C_{i}$ is a dependent connected-cycle if there exists a cycle set
$\mathbb{C}=\\{C_{i},C_{j},\dots\\}$ in $F(\theta^{\prime})$ and all agents in
$\mathbb{C}$ can form a connected component in $G(\theta^{\prime})$,
$\forall\mathbb{C^{\prime}}\subsetneq\mathbb{C}$, all agents in
$\mathbb{C^{\prime}}$ cannot form a connected component in
$G(\theta^{\prime})$.

  3. c.

All cycles other than a. and b. are unconnected-cycles.

We illustrate the three types of cycles in Figure 5. As shown in sub-figure
(a), $C_{4}=(1,3,2,4)$ is an independent connected-cycle. In sub-figure (b),
$C_{3}=(1,3)$ and $C_{4}=(2,4)$ are two dependent connected-cycles. In sub-
figure (c), $C_{3}=(2,3)$ is an independent connected-cycle, and $C_{4}=(1,4)$
is an unconnected-cycle.

1234

1234

1234

Figure 5. Examples of independent connected-cycles, dependent connected-cycles
and unconnected-cycles. Double arrows represent agents’ connections in
$G(\theta^{\prime})$, and red single arrows represent their favorite pointing.

The heart of our mechanism is to find connected-cycles in the favorite
pointing graph $F(\theta^{\prime})$ and let them get traded. Inspired by the
sharing idea first proposed by Yang et al., we first match the connected-
cycles in the favorite pointing graph, and share their neighbors to construct
more connectivity among agents. This will not cause incompatibility with IC
because agents who get their favorite item have no incentives to misreport,
nor do they care about the rest of the market.

Unfortunately, not all agents can get their most preferred item, some have to
switch their pointing in $F(\theta^{\prime})$ to a less preferred one. So, we
define a next favorite function to adjust $F(\theta^{\prime})$ based on
agents’ preferences.

###### Definition 5.3.

Given a reported type profile $\theta^{\prime}$ and a favorite pointing graph
$F(\theta^{\prime})$, we have $\succ_{i}^{next}(F(\theta^{\prime}))=j,j\in
Q(\theta^{\prime})$, if $j$ is the qualified agent who owns $i$’s next
favorite item.

Since our mechanism involves preference switching, we need a strategy-proof
order, defined upon agent’s shortest length to the initial players, to decide
which agent should switch her preference under certain circumstances.

###### Definition 5.4.

An order of agents is a one-to-one function $\mathcal{O}:\mathbb{N}^{+}\to N$,
where agent $\mathcal{O}(i)$ is the $i^{th}$ agent in the order. Agents in
$\mathcal{O}$ are sorted in ascending order by the length of the shortest path
from agent set $N_{0}$ to them. Especially, for any agent $i\in N_{0}$, its
shortest path length is $0$. When multiple agents have the same length of the
shortest path, we use a random tie-breaking.

Now we are ready to introduce our mechanism.

Connected Trading Cycles

Given a reported type profile $\theta^{\prime}$, construct the favorite
pointing graph $F(\theta^{\prime})$. Initiate a settled agent set
$V=\emptyset$.

Executing the following steps until $V=N$

  1. a.

Find the agent $i\in N\setminus V$ with 0 in-degree in $F(\theta^{\prime})$
who has the minimum order. If there is no 0 in-degree agent, find the agent
$i\in N\setminus V$ with the minimum order.

  2. b.

Detect a path $P_{p_{1}}=(p_{1},\dots,p_{k},\dots,p_{m})$ in
$F(\theta^{\prime})$ starting from $p_{1}$ that satisfies there exists an edge
$\langle p_{j},p_{j+1}\rangle$ for any $p_{j}\in P_{i},p_{j}\neq p_{m}$, and
$\langle p_{m},p_{k}\rangle$. Especially, $C_{p_{m}}=(p_{k},\dots,p_{m})$ is a
cycle in $F(\theta^{\prime})$.

    1. i

If $C_{p_{m}}$ is an independent connected-cycle or a dependent connected-
cycle, add all agents in $C_{p_{m}}$ to settled agent set $V$.

    2. ii

If $C_{p_{m}}$ is an unconnected-cycle, reversely track $P_{p1}$ from $p_{m}$
to $p_{1}$, find the first $p_{l-1}$ who points to an agent $p_{l}$ and no
connected component containing $p_{l-1}$ and $p_{l}$ in $G(\theta^{\prime})$
is a subset of $C_{p_{m}}$. If $l=m$ and any path from $p_{k-1}$ to $p_{k}$
passes through $p_{m}$, change edge$\langle p_{k-1},p_{k}\rangle$ to $\langle
p_{k-1},\succ_{p_{k-1}}^{next}(F(\theta^{\prime}))\rangle$. Otherwise, change
the edge $\langle p_{l},p_{l^{\prime}}\rangle$ to $\langle
p_{l},\succ_{p_{l}^{next}}(F(\theta^{\prime}))\rangle$.

  3. c.

While there exists an edge $\langle p,q\rangle$ in $F(\theta^{\prime})$ that
satisfies $p\in N\setminus V,q\in V$, change $\langle p,q\rangle$ to $\langle
p,\succ_{p}^{next}(F(\theta^{\prime}))\rangle$

1234567891011(1)(2)1234567891011

i | $\succ_{i}$ | $r_{i}$ | $\pi_{i}$
---|---|---|---
1 | $h_{10}\succ h_{2}\succ\cdots$ | 2 | $h_{2}$
2 | $h_{4}\succ h_{1}\succ\cdots$ | 1,3 | $h_{1}$
3 | $h_{2}\succ h_{3}\succ\cdots$ | 2,4 | $h_{3}$
4 | $h_{6}\succ\cdots$ | 3,5 | $h_{6}$
5 | $h_{7}\succ\cdots$ | 4,6 | $h_{7}$
6 | $h_{4}\succ\cdots$ | 5,7,8 | $h_{4}$
7 | $h_{5}\succ\cdots$ | 6,9,10 | $h_{5}$
8 | $h_{9}\succ h_{8}\succ\cdots$ | 6 | $h_{8}$
9 | $h_{8}\succ h_{9}\succ\cdots$ | 7 | $h_{9}$
10 | $h_{2}\succ h_{11}\succ\cdots$ | 7,11 | $h_{11}$
11 | $h_{2}\succ h_{10}\succ\cdots$ | 10 | $h_{10}$

Figure 6. Sub-figure (1) represents the $G(\theta^{\prime})$. Sub-figure (2)
is the favorite pointing graph $F(\theta^{\prime})$. The table presents the
preference, neighbor set, and the allocation given by CTC for each agent.

In our mechanism, the allocation relies on the cycles in the favorite pointing
graph. These cycles ensure optimality, so agents will truthfully report their
preferences. We further classify the cycles by social connections and protect
the connected-cycles while break the unconnected-cycles. We allow the
connected-cycles to form because their connectivity is only determined by
agents in the cycles and cannot be influenced by others. It is natural for the
independent connected-cycle since the cycle itself is formed by a connected
component. For the dependent connected-cycle, we require that no subset of the
cycle set be a connected component. Namely, all agents in the cycle set rely
on each other to form connected-cycle and get traded, so they share the same
interest. This prevents agents from misreporting to form connected-cycles for
their own good using the already formed cycles. To sum up, these two types of
connected-cycles target at allowing cycles in the favorite pointing graph as
much as possible. As for the unconnected-cycles, to maintain optimality, we
try to sustain the favorite pointing along the cycles to the greatest extent.
We only let those who cannot connect to her pointing with the help of the
cycle switch pointing (as in b.ii).

We present a detailed example to illustrate our mechanism. The initial agent
set is $N_{0}=\\{1\\}$. The order is $\mathcal{O}=(1,2,3,4,5,6,7,8,9,$
$10,11)$. The social network, type profiles, and allocation are presented in
Figure 6. The following steps match the sub-figures in Figure 7.

1234567891011

1234567891011

1234567891011

1234567891011

1234567891011

1234567891011

1234567891011

1234567891011

1234567891011

Figure 7. A running example for our mechanism. Though $G(\theta^{\prime})$ is
a directed graph, we omit the double arrows here to make the figure clearer.
The single arrows represent the pointing for each agent. The blue lines
highlight the pointing of the path under consideration, and the start of the
path is marked. The settled agent set is dashed and in grey.

  1. (a)

At the beginning, agent 1 has 0 in-degree and the minimum order. The path is
$P_{1}=(1,10,2,4,6)$. Since $C_{6}=(4,6)$ is a dependent connected-cycle, add
$C_{6}$ to $V$. Since agent 2 is in $N\setminus V$ and agent $4$ is in $V$,
change $\langle 2,4\rangle$ to $\langle
2,\succ_{2}^{next}(F(\theta^{\prime}))=1\rangle$.

  2. (b)

Then agent 3 has 0 in-degree and the minimum order, the path is
$P_{3}=(3,2,1,10)$. Since $C_{10}=(2,1,10)$ is an unconnected-cycle and no
connected component containing $10$ and $2$ in $G(\theta^{\prime})$ is a
subset of $C_{10}$, change $\langle 10,2\rangle$ to $\langle
10,\succ_{10}^{next}(F(\theta^{\prime}))=11\rangle$.

  3. (c)

Agent 3 still has 0 in-degree and the minimum order. The path is
$P_{3}=(3,2,1,10,11)$. Since $C_{11}=(2,1,10,11)$ is an unconnected-cycle and
no connected component containing $11$ and $2$ in $G(\theta^{\prime})$ is a
subset of $C_{11}$, change $\langle 11,2\rangle$ to $\langle
11,\succ_{11}^{next}(F(\theta^{\prime}))=10\rangle$.

  4. (d)

Agent 3 still has 0 in-degree and the minimum order. The path is
$P_{3}=(3,2,1,10,11)$. Since $C_{11}=(10,11)$ is an independent connected-
cycle, add $C_{11}$ to $V$. Since agent 1 is in $N\setminus V$ and agent $10$
is in $V$, change $\langle 1,10\rangle$ to $\langle
1,\succ_{1}^{next}(F(\theta^{\prime})=2\rangle$

  5. (e)

Agent 3 still has 0 in-degree and the minimum order. The path is
$P_{3}=(3,2,1)$. Since $C_{1}=(2,1)$ is an independent connected-cycle, add
$C_{1}$ to $V$. Since agent $3$ is in $N\setminus V$ and agent $2$ is in $V$,
change $\langle 3,2\rangle$ to $\langle
3,\succ_{3}^{next}(F(\theta^{\prime}))=3\rangle$.

  6. (f)

No agent in $F(\theta^{\prime})$ has 0 in-degree. Agent $3$ has the minimum
order in $N\setminus V$. The path is $P_{3}=(3)$. Since $C_{3}=(3)$ is an
independent connected-cycle, add $C_{3}$ to $V$.

No agent in $F(\theta^{\prime})$ has 0 in-degree. Agent $5$ has the minimum
order in $N\setminus V$. The path is $P_{5}=(5,7)$. Since $C_{7}=(5,7)$ is a
dependent connected-cycle, add $C_{7}$ to $V$.

  7. (g)

No agent in $F(\theta^{\prime})$ has 0 in-degree. Agent $8$ has the minimum
order in $N\setminus V$. The path is $P_{8}=(8,9)$. Since $C_{9}=(8,9)$ is an
unconnected-cycle and no connected component containing $9$ and $8$ in
$G(\theta^{\prime})$ is a subset of $C_{9}$, change $\langle 9,8\rangle$ to
$\langle 9,\succ_{9}^{next}(F(\theta^{\prime}))=9\rangle$.

  8. (h)

Now agent 8 has 0 in-degree and the minimum order. The path is $P_{8}=(8,9)$.
Since $C_{9}=(9)$ is an independent connected-cycle, add $C_{9}$ to $V$. Since
agent 8 is in $N\setminus V$ and agent 9 is in $V$, change $\langle
8,9\rangle$ to $\langle 8,\succ_{8}^{next}(F(\theta^{\prime}))=8\rangle$.

  9. (i)

No agent in $F(\theta^{\prime})$ has 0 in-degree. Agent $8$ has the minimum
order in $N\setminus V$. The path is $P_{8}=(8)$. Since $C_{8}$ is an
independent connected-cycle, add $C_{8}$ to $V$.

Now $V=N$, the mechanism ends.

##  6\. Properties of CTC

In this section, we prove that Connected Trading Cycles (CTC) is IR, IC,
optimal-c and stable-cc. As shown in Table 1, all previous mechanisms fail to
satisfy optimal-c, and CTC reaches the theoretical boundaries.

Mechanism | Optimal-c | Stable-cc | IC
---|---|---|---
Trees | All Networks
TTC (Shapley and Scarf, 1974) | ✕ | ✕ | ✕ | ✕
SWN (Yang et al., 2022) | ✕ | ✓ | ✓ | ✓
SWC (Kawasaki et al., 2021) | ✕ | ✓(Trees) | ✓ | ✕
LS (Yang et al., 2022) | ✕ | ✓ | ✓ | ✓
CTC | ✓ | ✓ | ✓ | ✓
Table 1. Comparison on one-sided matching mechanisms over social networks.

###### Theorem 6.1.

For any order $\mathcal{O}$, CTC is IR.

###### Proof.

In CTC, every agent $i$ can point to her own item $h_{i}$. When $i$ does so,
$i$’s pointing to herself is an independent connected-cycle and our mechanism
will assign $h_{i}$ to $i$. So, CTC is IR. ∎

###### Theorem 6.2.

For any order $\mathcal{O}$, CTC is IC.

###### Proof.

We first consider the truthfulness of agent’s report on preference under any
given neighbor set report. Suppose
$\pi_{i}(((\succ_{i},r_{i}^{\prime}),\theta_{-i}^{\prime}))=h_{j}$,
$\pi_{i}(((\succ_{i}^{\prime},r_{i}^{\prime}),\theta_{-i}^{\prime}))=h_{j^{\prime}}$,
and $h_{j^{\prime}}\succ_{i}h_{j}$. Assume agent $q$ is allocated
$h_{j^{\prime}}$ when agent $i$ truthfully reports preference. Then there
exists a connected-cycle $C_{1}$ involving $\langle q,j^{\prime}\rangle$.
Since
$\pi_{i}(((\succ_{i}^{\prime},r_{i}^{\prime}),\theta_{-i}^{\prime}))=h_{j^{\prime}}$,
there exists another connected-cycle $C_{2}$ involving $\langle
i,j^{\prime}\rangle$. Thus, there must exist an agent $t$ on both $C_{1}$ and
$C_{2}$ whose pointing is different. Let the two pointing be $\langle
t,t_{1}\rangle,t_{1}\in C_{1}$ and $\langle t,t_{2}\rangle,t_{2}\in C_{2}$.
Given that $q$ is allocated $h_{j^{\prime}}$ when agent $i$ truthfully reports
preference, $C_{1}$ forms which means $h_{t_{1}}\succ^{\prime}_{t}h_{t_{2}}$.
Similarly, since agent $i$ is allocated $h_{j^{\prime}}$ when she misreports,
$C_{2}$ forms which means $h_{t_{2}}\succ^{\prime}_{t}h_{t_{1}}$. This is a
contradiction since each agent has a strict preference. Hence, regardless of
the report on neighbor set, truthfully reporting preference is a dominant
strategy for all agents.

Then we consider the truthfulness of agent’s report on neighbor set under any
given preference report. Suppose
$\pi_{i}(((\succ^{\prime}_{i},r_{i}),\theta_{-i}^{\prime}))=h_{j}$,
$\pi_{i}(((\succ^{\prime}_{i},r_{i}^{\prime}),\theta_{-i}^{\prime}))=h_{j^{\prime}}$,
and $h_{j^{\prime}}\succ^{\prime}_{i}h_{j}$. So, there exists a connected-
cycle $C_{1}$ involving $\langle i,j^{\prime}\rangle$ when $i$ misreports as
$(\succ^{\prime}_{i},r^{\prime}_{i})$. By the definition of connected-cycles,
$i$ and $j^{\prime}$ are involved in a connected component $S$ where no subset
of agents in $S$ forms a connected-cycle. Since
$h_{j^{\prime}}\succ^{\prime}_{i}h_{j}$, when truthfully reporting neighbor
set, $i$ must have pointed $\langle i,j^{\prime}\rangle$ before $\langle
i,j\rangle$ and is forced to switch to the next on her preference. This
indicates that the cycle $C_{2}$ involving $\langle i,j^{\prime}\rangle$ when
$i$ reports $(\succ^{\prime}_{i},r_{i})$ is an unconnected-cycle. Note that
the difference in these two cases is caused by $i$ misreporting
$r^{\prime}_{i}$. If some agents are unqualified because of $i$’s
misreporting, it means they can only connect to others by $i$, so their
joining in the match cannot change the fact that $\langle i,j^{\prime}\rangle$
can be involved in a connected-cycle. On the other hand, if no agent becomes
unqualified because of $i$’s misreporting, $i$ misreports as
$(\succ^{\prime}_{i},r^{\prime}_{i})$ can only decrease her connection to
others which is not beneficial. Hence, if $i$ is allocated $h_{j}^{\prime}$
when misreporting neighbor set, $i$ can also get $h_{j}^{\prime}$ when she
truthfully reports which contradicts our assumption. Though misreporting on
neighbor set can have impact on the order, with the truthfully reported
preferences, whether a cycle can get traded is only determined by the
connections as shown above. The changes in the order cannot influence the
allocation. Thus, regardless of the preference report, truthfully reporting
neighbor set is a dominant strategy for all agents.

Combining them together, CTC is IC.∎

###### Theorem 6.3.

For any order $\mathcal{O}$, CTC is optimal-c.

###### Proof.

For any given type profile $\theta$, if CTC violates optimal-c, there exists a
connected component $T\subseteq N$, with the allocation $\pi(\theta)$ given by
CTC, a reallocation $\pi^{\prime}(\theta)$ among $T$ based on $\pi(\theta)$
makes every agent in $T$ strictly better. We construct a cycle set
$\mathbb{C}$ which consists of the cycles given by $\pi$ involving agents in
$T$. By the rule of CTC, all the cycles in $\mathbb{C}$ are connected-cycles.
We denote the reallocation cycle set given by $\pi^{\prime}(\theta)$ as
$\mathbb{C}^{*}$. By definition of connected-cycles, since $T$ is a connected
component there exists at least one connected-cycle in $\mathbb{C}^{*}$.
Otherwise, $\mathbb{C}^{*}$ itself is a connected-cycle. For each connected-
cycle $C_{T}$ in $\mathbb{C}^{*}$, we let each agent $i$ on the cycle switch
her pointing to the owner of $\pi^{\prime}_{i}(\theta)$. We denote all the
cycles changed in $\mathbb{C}$ as $\mathbb{C}_{i}\subseteq\mathbb{C}$ and they
change to $\mathbb{C}_{i}^{*}$. Since all cycles in $\mathbb{C}_{i}$ are
changed, every cycle in $\mathbb{C}_{i}^{*}$ involves at least one agent in
$C_{T}$. Given that $C_{T}$ is a connected-cycle and all cycles in
$\mathbb{C}_{i}$ are connected-cycles, all cycles in $\mathbb{C}_{i}^{*}$ are
connected-cycles. Thus, $\mathbb{C}_{i}^{*}\subseteq\mathbb{C}$, which means
$\pi=\pi^{\prime}$ for all agents in $\mathbb{C}_{i}^{*}$. By the assumption,
the strictly better off group $T$ does not contain these connected-cycles.
Hence, all the cycles in $\mathbb{C}^{*}$ are unconnected-cycles. This means
agents in $T$ cannot form a connected component in $G(\theta)$ which
contradicts our assumption. Thus, CTC is optimal-c.∎

###### Theorem 6.4.

For any order $\mathcal{O}$, CTC is stable-cc.

###### Proof.

For any given type profile $\theta$, if CTC violates stable-cc, there exists a
group of agents $S$ that forms a complete component in $G(\theta)$, they
deviate together and swap among themselves can result in a better allocation
$\pi^{\prime}(\theta)$ compared to $\pi(\theta)$ given by CTC. Since group $S$
is a complete component, all the cycles formed in $\pi^{\prime}(\theta)$ are
independent connected-cycles. In CTC, all these cycles are allowed to get
traded. That is to say, CTC will assign them exactly $\pi^{\prime}$, which
contradicts our assumption. Hence, CTC is stable-cc. ∎

##  7\. Incentive Compatible Diffusion One-sided Matching

Takamiya (Takamiya, 2001) characterizes the strategy-proof housing market
mechanisms by preference monotonicity. He shows that with others’ preferences
fixed, if an agent $i$ gets $h_{j}$ when reporting $\succ^{\prime}_{i}$, she
also gets $h_{j}$ even if $h_{j}$ is moved to a higher rank in
$\succ^{\prime}_{i}$. TTC satisfies this condition since $i$ gets $h_{j}$
indicating all items better than $h_{j}$ for agent $i$ are in trading cycles
without $i$, and moving $h_{j}$ to a higher rank will not influence those
cycles without $i$. We can easily introduce preference monotonicity into the
network setting.

###### Definition 7.1.

Given agent $i$’s preference profile $\succ_{i}$ and her allocation $\pi_{i}$,
we denote the set of less preferred items for agent $i$ by
$L(\pi_{i},\succ_{i})=\\{k\in H|\pi_{i}\succ_{i}k\\}$. We say an allocation
$\pi$ is preference-monotonic if for any agent $i\in N$, if
$L(\pi_{i},\succ^{\prime}_{i})\subset L(\pi_{i},\succ^{\prime\prime}_{i})$, we
have
$\pi_{i}((\succ^{\prime}_{i},r^{\prime}_{i}),\theta^{\prime}_{-i})=\pi_{i}((\succ^{\prime\prime}_{i},r^{\prime}_{i}),\theta^{\prime}_{-i})$.

However, preference monotonicity cannot characterize IC in the network setting
for it lacks the constraint over the neighbor set report. Let’s look back to
the house exchange example in the Introduction to get some insights. To
incentivize Alice to invite Charlie, we should guarantee that inviting others
will not worsen her result. That is, if she can get Bob’s house in the Alice-
and-Bob market, she can get allocated a house no worse than Bob’s when
inviting more people. We define this monotonicity of invitation as diffusion
monotonicity, which is also studied in the diffusion auction setting (Li et
al., 2020).

###### Definition 7.2.

We say an allocation $\pi$ is diffusion-monotonic if for any agent $i\in N$,
if $r^{\prime\prime}_{i}\subset r^{\prime}_{i}$, we have
$\pi_{i}((\succ^{\prime}_{i},r^{\prime}_{i}),\theta^{\prime}_{-i})\succeq^{\prime}_{i}\pi_{i}((\succ^{\prime}_{i},r^{\prime\prime}_{i}),\theta^{\prime}_{-i})$.

Now, we are ready to present the IC characterization for the diffusion one-
sided matching.

###### Theorem 7.3.

A diffusion one-sided matching mechanism is incentive compatible if and only
if the allocation $\pi$ is preference-monotonic and diffusion-monotonic.

###### Proof.

Suppose an IC mechanism $\pi$ fails preference-monotonic, then there exists
agent $i\in N$ and a preference profile $\succ^{\prime}_{i}$ where
$L(\pi_{i},\succ^{\prime}_{i})\subset L(\pi_{i},\succ^{\prime}_{i})$, and we
have $h_{j^{\prime}}=\pi_{i}((\succ^{\prime}_{i},r^{\prime}_{i})$,
$\theta^{\prime}_{-i})$,
$h_{j}=\pi_{i}((\succ_{i},r^{\prime}_{i}),\theta^{\prime}_{-i})$, $h_{j}\neq
h_{j^{\prime}}$. Then either $h_{j^{\prime}}\succ_{i}h_{j}$ or
$h_{j}\succ_{i}h_{j^{\prime}}$. In the former case, misreporting
$\succ^{\prime}_{i}$ gives agent $i$ a better allocation and violates IC. In
the latter case, $\pi$ fails to be IC when $i$’s true preference is
$\succ^{\prime}_{i}$. Hence, if a mechanism is IC, it is preference-monotonic.

Similarly, suppose an IC mechanism $\pi$ fails diffusion-monotonic, then there
exists agent $i\in N$ and a neighbor set $r^{\prime}_{i}$ where
$r^{\prime}_{i}\subset r_{i}$, and we have
$h_{j^{\prime}}=\pi_{i}((\succ^{\prime}_{i},r^{\prime}_{i})$,
$\theta^{\prime}_{-i})$,
$h_{j}=\pi_{i}((\succ^{\prime}_{i},r_{i}),\theta^{\prime}_{-i})$, and
$h_{j^{\prime}}\succ^{\prime}_{i}h_{j}$. In other words, agent $i$ can
misreport to make her allocation better, which violates IC. Hence, if a
mechanism is IC then it is diffusion-monotonic.

We then prove that if a mechanism is preference-monotonic and diffusion-
monotonic, it is IC. That is to say, a mechanism fails IC suggesting that it
fails at least one of the monotonicity. If a mechanism $\pi$ is not IC, it
means that for at least one agent $i$, she can better her allocation by
misreporting her type. If $i$ misreports her neighbor set, the reported
$r^{\prime}_{i}$ must be a subset of the true neighbor set $r_{i}$. Thus, $i$
getting a better allocation under $r^{\prime}_{i}$ violates diffusion-
monotonic. On the other hand, if $i$ misreports her preference profile as
$\succ^{\prime}_{i}$ to get a better allocation which means
$h_{j^{\prime}}\succ_{i}h_{j}$, we will show that this violates preference-
monotonic. Let’s construct a preference profile $\succ^{*}_{i}$ for agent $i$,
such that the items that ranked first and second in $\succ^{*}_{i}$ are
$h_{j^{\prime}}$ and $h_{j}$ respectively. By this construction, we have
$L(h_{j^{\prime}},\succ^{\prime}_{i})\subset L(h_{j^{\prime}},\succ^{*}_{i})$.
Since $h_{j^{\prime}}\succ_{i}h_{j}$, we know that $h_{j^{\prime}}\notin
L(h_{j},\succ_{i})$, so we have $L(h_{j},\succ_{i})\subset
L(h_{j},\succ^{*}_{i})$. So, if $\pi$ is preference-monotonic,
$h_{j}=h_{j^{\prime}}$ which contradicts with our assumption.

To sum up, a diffusion one-sided matching mechanism is IC if and only if it is
preference-monotonic and diffusion-monotonic. ∎

Next, we show how to use our characterization to design an IC diffusion one-
sided matching mechanism.

12′234

12′234

12′234

12′234

Figure 8. Examples for the IC mechanisms designed by monotonicity conditions.
Sub-figure (a) depicts the pair-wise mechanism. The other three sub-figures
are the extended versions, (d) illustrates SWN.

Based on the two monotonicity conditions, we construct a simple pair-wise
rule. Following a pre-defined order, we let agent 1 with the smallest order
choose her favorite neighbor agent 2. If agent 2 finds $h_{1}$ acceptable,
agents 1 and 2 form a trading cycle and get traded. Otherwise, agent 2 leaves
with her own item, and agent 1 chooses her next favorite neighbor (as shown in
Figure 8 (a)). This trivial mechanism satisfies preference monotonicity since
agents always trade with their favorite neighbors that find them acceptable.
For diffusion monotonicity, since agents can only choose from their neighbors
and the chosen neighbor either accepts the trade or leaves alone, inviting
more neighbors guarantees the same, if not better, result.

We can take one step further and extend it to a three-agent version without
violating the monotonicity conditions. Whenever an agent chooses her favorite
neighbor agent 2, 2 can also choose one from the common neighbors of agents 1
and 2, say agent 3. Now, agent 3 can either choose agent 1 or stay with her
own good (as shown in Figure 8 (b)). Notice that, it is also natural to allow
agent 3 to choose agent 2, and they can get traded. This is because the
neighbor relationship between agents 2 and 3 is irrelevant to others’ actions
(as shown in Figure 8 (c)). We can further expand this to any size. All agents
can choose their favorite among their neighbors (as shown in Figure 8 (d)). By
doing so, we no longer need the pre-defined order to determine which agent
should leave or trade, since there always exists at least one trading cycle
and each agent’s allocation is only determined by whether the agent is in a
trading cycle or not. Therefore, we can ignore the pre-defined order and then
the mechanism is equivalent to SWN.

As shown above, we can first construct a trivial solution that satisfies the
monotonicity conditions, and gradually refine it to meet other properties.

##  8\. Conclusion

This work promotes the theoretical boundary regarding optimality and stability
for one-sided matching with initial endowments over social networks. We design
the Connected Trading Cycles that satisfies IC, IR, stable-cc, and optimal-c.
Furthermore, we propose the first IC characterization in the network setting
to complete the theoretical framework. There are still open questions worth
investigating in this field. One possible future work is to design diffusion
mechanisms for the variants of one-sided matching problems. In addition, the
optimal-c solution for diffusion one-sided matching is not unique. How to
determine the superiority among different optimal-c allocations and their
relationships to one another would be an intriguing research topic.

## References

  * (1)
  * Abdulkadiroğlu and Sönmez (1999) Atila Abdulkadiroğlu and Tayfun Sönmez. 1999.  House allocation with existing tenants.  _Journal of Economic Theory_ 88, 2 (1999), 233–260.
  * Abdulkadiroglu and Sönmez (2013) Atila Abdulkadiroglu and Tayfun Sönmez. 2013.  Matching markets: Theory and practice.  _Advances in Economics and Econometrics_ 1 (2013), 3–47.
  * Abraham et al. (2005) David J. Abraham, Katarína Cechlárová, David F. Manlove, and Kurt Mehlhorn. 2005\.  Pareto Optimality in House Allocation Problems. In _Algorithms and Computation_ , Rudolf Fleischer and Gerhard Trippen (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 3–15.
  * Anno (2015) Hidekazu Anno. 2015\.  A short proof for the characterization of the core in housing markets.  _Economics Letters_ 126 (2015), 66–67.
  * Brandt and Wilczynski (2019) Felix Brandt and Anaëlle Wilczynski. 2019.  On the Convergence of Swap Dynamics to Pareto-Optimal Matchings. In _Web and Internet Economics_ , Ioannis Caragiannis, Vahab Mirrokni, and Evdokia Nikolova (Eds.). Springer International Publishing, Cham, 100–113.
  * Chen and Zhao (2021) Yajing Chen and Fang Zhao. 2021.  Alternative characterizations of the top trading cycles rule in housing markets.  _Economics Letters_ 201 (2021), 109806.
  * Cho et al. (2022) Sung-Ho Cho, Taiki Todo, and Makoto Yokoo. 2022.  Two-Sided Matching over Social Networks. In _Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22_ , Lud De Raedt (Ed.). International Joint Conferences on Artificial Intelligence Organization, 186–193.  https://doi.org/10.24963/ijcai.2022/27 Main Track.
  * Fleischer and Wang (2008) Rudolf Fleischer and Yihui Wang. 2008.  Dynamic Pareto Optimal Matching. In _Proceedings of the 2008 International Symposium on Information Science and Engieering - Volume 02_ _(ISISE ’08)_. IEEE Computer Society, USA, 797–802.  https://doi.org/10.1109/ISISE.2008.237
  * Gourvès et al. (2017) Laurent Gourvès, Julien Lesca, and Anaëlle Wilczynski. 2017.  Object Allocation via Swaps along a Social Network. In _Proceedings of the 26th International Joint Conference on Artificial Intelligence_ (Melbourne, Australia) _(IJCAI’17)_. AAAI Press, 213–219.
  * Hoefer (2013) Martin Hoefer. 2013\.  Local matching dynamics in social networks.  _Information and Computation_ 222 (2013), 20–35.  https://doi.org/10.1016/j.ic.2012.10.005 38th International Colloquium on Automata, Languages and Programming (ICALP 2011).
  * Kawasaki et al. (2021) Takehiro Kawasaki, Ryoji Wada, Taiki Todo, and Makoto Yokoo. 2021\.  Mechanism Design for Housing Markets over Social Networks. In _Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems_ (Virtual Event, United Kingdom) _(AAMAS ’21)_. International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 692–700.
  * Kumar et al. (2022) Rajnish Kumar, Kriti Manocha, and Josué Ortega. 2022\.  On the integration of Shapley–Scarf markets.  _Journal of Mathematical Economics_ 100 (2022), 102637.
  * 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. (2020) Bin Li, Dong Hao, and Dengji Zhao. 2020.  Incentive-Compatible Diffusion Auctions. In _Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20_ , Christian Bessiere (Ed.). International Joint Conferences on Artificial Intelligence Organization, 231–237.  https://doi.org/10.24963/ijcai.2020/33 Main track.
  * 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_ (San Francisco, California, USA) _(AAAI’17)_. AAAI Press, 586–592.
  * Ma (1994) Jinpeng Ma. 1994\.  Strategy-proofness and the strict core in a market with indivisibilities.  _International Journal of Game Theory_ 23, 1 (1994), 75–83.
  * Sethuraman (2016) Jay Sethuraman. 2016\.  An alternative proof of a characterization of the TTC mechanism.  _Operations Research Letters_ 44, 1 (2016), 107–108.
  * Shapley and Scarf (1974) Lloyd Shapley and Herbert Scarf. 1974.  On cores and indivisibility.  _Journal of mathematical economics_ 1, 1 (1974), 23–37.
  * Sönmez and Ünver (2010) Tayfun Sönmez and M Utku Ünver. 2010.  House allocation with existing tenants: A characterization.  _Games and Economic Behavior_ 69, 2 (2010), 425–445.
  * Takamiya (2001) Koji Takamiya. 2001\.  Coalition strategy-proofness and monotonicity in Shapley–Scarf housing markets.  _Mathematical Social Sciences_ 41, 2 (2001), 201–213.  https://doi.org/10.1016/S0165-4896(00)00062-7
  * Yang et al. (2022) Tianyi Yang, Yuxiang Zhai, Dengji Zhao, Xinwei Song, and Miao Li. 2022.  One-Sided Matching with Permission.  https://doi.org/10.48550/ARXIV.2201.05787
  * You et al. (2022) Bo You, Ludwig Dierks, Taiki Todo, Minming Li, and Makoto Yokoo. 2022.  Strategy-Proof House Allocation with Existing Tenants over Social Networks. In _Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems_ (Virtual Event, New Zealand) _(AAMAS ’22)_. International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 1446–1454.
  * Zhang and Zhao (2022) Yao Zhang and Dengji Zhao. 2022.  Incentives to Invite Others to Form Larger Coalitions. In _Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems_ (Virtual Event, New Zealand) _(AAMAS ’22)_. International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 1509–1517.
  * Zhao (2021) Dengji Zhao. 2021\.  Mechanism Design Powered by Social Interactions. In _Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems_ (Virtual Event, United Kingdom) _(AAMAS ’21)_. International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 63–67.


# musicaiz: A Python Library for Symbolic Music Generation, Analysis and
Visualization

Carlos Hernandez-Olivan<EMAIL_ADDRESS>[ Jose R. Beltran
<EMAIL_ADDRESS>Department of Electronic Engineering and Communications,
University of Zaragoza, 50018 Zaragoza, Spain

###### Abstract

In this article, we present musicaiz, an object-oriented library for
analyzing, generating and evaluating symbolic music. The submodules of the
package allow the user to create symbolic music data from scratch, build
algorithms to analyze symbolic music, encode MIDI data as tokens to train deep
learning sequence models, modify existing music data and evaluate music
generation systems. The evaluation submodule builds on previous work to
objectively measure music generation systems and to be able to reproduce the
results of music generation models. The library is publicly available online.
We encourage the community to contribute and provide feedback.

###### keywords:

music information retrieval, music generation, machine learning, deep learning

url]https://carlosholivan.github.io/

##  1 Motivation and significance

The field of Music Information Retrieval (MIR) research has grown
significantly in the last few decades. In recent years, with the growth of
Artificial Intelligence, several models have been proposed in the subfields of
MIR that are becoming real-world applications, such as music production. The
automation and scalability of new models has become a necessity for music
companies such as Sony, Spotify, Apple Music, Pandora or Dolby.

One of the fastest growing subfields of MIR in recent years is music
generation. The reason for this growing interest is the emergence of new deep
learning models that allow researchers to build better performance models
versus previous rule-based approaches [1], [2].

This has increased the interest in building open source tools and software to
help researchers in the preprocessing stages when working, on the one hand,
with symbolic music data like jSymbolic [3], music21 [4], Humdrum [5], mido or
pretty_midi [6] and, on the other hand, with audio samples such as librosa
[7]. Other libraries have been proposed to deal with symbolic music data for
music generation purposes such as muspy [8] or libraries to help construct
encodings for training sequence models such as miditok [9].

Each of these softwares works on a particular step of the music generation or
analysis flow. The goal of musicaiz is to bring together music theory, music
processing, models for music generation and evaluation techniques to provide
all the steps necessary to build a music generation system that can be
reproducible and scalable. The library is publicly
available111https://github.com/carlosholivan/musicaiz. We also provide the
documentation and
examples222https://carlosholivan.github.io/musicaiz/index.html. The software
is tested with pytest333https://github.com/pytest-dev/pytest.

In Table 1 we compare the features offered by these packages in comparison
with the musicaiz library.

Musicaiz library (Fig.1) is build on pretty_midi [6] and its design principles
are aligned with the music theory principles.

Figure 1: Musicaiz utilities and submodules. Package |  Lang. |  Purpose |  Music Theory |  Tokenizers |  Models |  Eval.
---|---|---|---|---|---|---
jSymbolic |  java |  analysis |  ✓ |  ✗ |  ✗ |  ✓
music21 |  python |  general |  ✓ |  ✗ |  ✗ |  ✗
mido |  python |  processing |  ✗ |  ✗ |  ✗ |  ✗
pretty_midi |  python |  processing |  ✗ |  ✗ |  ✗ |  ✗
Humdrum |  awk |  analysis |  ✓ |  ✗ |  ✗ |  ✓
Miditok |  python |  tokenize |  ✗ |  ✓ |  ✗ |  ✗
Muspy |  python |  generation |  ✗ |  ✗ |  ✗ |  ✓
Musicaiz |  python |  generation, visual., analysis |  ✓ |  ✓ |  ✓ |  ✓
Table 1: Frameworks for MIDI and symbolic music generation, analysis and
representation.

##  2 Software description

###  2.1 Software architecture

Musicaiz is written in Python 3. The software is divided into several
submodules to suit the user’s needs. There are submodules that allow to
represent the symbolic format in an OOP approach by following music theory
principles such as rhythm, harmony and structure. From these submodules we
build a features submodule that allows to extract information from the raw
symbolic music data. These features form the basis of the eval submodule that
allows us to evaluate music generation systems to help make them reproducible,
which is a current need in the music generation subfield [1]. Since deep
learning models often require a significant preprocessing step, especially
sequence models such as the Transformer [10], we also provide a tokenizer
module that allows tokenizing symbolic music data with the Multi-track Music
Machine encoding [11]. This submodule can be easily extended to different
encodings due to its OOP design. In the datasets submodule, we provide classes
that allow processing symbolic music datasets used in the field of music
generation. Furthermore, symbolic music can be represented as a pianoroll and
there are no programs that allow to plot these representations with a grid of
subdivisions as digital audio workstations (DAWs) do. We provide a plotting
submodule that helps to plot symbolic musical pianorolls and save them as HTML
files with plotly. This can not only help to visualize the symbolic musical
data, but also could be used as a debugging tool. Finally, the exports
submodule converts musicaiz objects to a JSON format so that music information
can be sent via REST APIs. This allows building music generation applications
with musicaiz on the backend that could be used not only for research
purposes, but also in industry.

###  2.2 Software Functionalities

The goal of musicaiz is to provide researchers, practitioners and users with a
framework for music generation. We can group the submodules of the software
into a high-level abstraction that caters to the software’s functionalities
(see Fig. 1). These groups are: music theory, processing, generation,
evaluation, visualization and export. Although the software is intended to
serve as a music generation framework, it could serve more purposes with the
configuration of the current submodules.

####  2.2.1 Loaders

The module loaders contains the main class of the library which is called
Musa. It allows to import a MIDI file and initialize all its corresponding
attributes. The default tempo or bpm value is set to 120 and the resolution or
Ticks per Quarter Note (TPQN) is set to 96, however, if a MIDI file is
provided, the tempo value will be the MIDI tempo attribute if set in the MIDI
metamessages.

####  2.2.2 Music Theory

The main submodules that allow computing and processing symbolic information
following the principles of music theory are: rhythm, structure and harmony.

##### Rhythm

In this module the user can operate with different time signatures and apply
different quantizations to data imported from a MIDI file. The classes and
methods contained in the musicaiz.rhythm module allow us to group notes into
measures, calculate the duration of notes, etc. This module contains two
submodules: time and quantization.

##### Structure

The structure is another basic submodule of the library. It contains elements
referring to musical form or structure such as piece, instrument or notes. The
main elements of this module are are: Instrument, Bar and Note:

  * 1.

structure.notes contains classes that are based on Pearce and Wiggins’ work
[12]. It allows the construction of note objects for analysis or symbolic
music generation. Notes can contain pitch, time and performance attributes.

  * 2.

structure.bars has a class Bar that helps to define the measures. The purpose
of this submodule is to use this class to build music processors and provide
more ways to organize symbolic musical data that are aligned with the score
representation.

  * 3.

structure.instruments helps to define and group notes and measures within
their corresponding instrument.

##### Harmony

We have built the main structure blocks on the time axis of the music, but the
music also works on a vertical or pitch axis. We include a harmony submodule
to be able to analyze or generate harmonic data. The main elements of this
submodule are: Intervals, Chords and Tonalities and Scales:

  * 1.

harmony.intervals contain definitions of common intervals as defined in music
theory [13].

  * 2.

harmony.chords contains the chord definitions. Chords are defined by the root
note, its quality, its type or complexity (triads or sevenths) and the list of
intervals from the root note containing the chord.

  * 3.

harmony.keys. We define the keys from zero to seventh alterations, sharps and
flats. Each tonality and mode (major and minor) has its corresponding scales
in major, minor and Greek modes.

####  2.2.3 Processing

Token representations allow training deep learning sequence models. In recent
years, several works include token representations to train such models in the
music generation task. We provide the submodules tokenizers and datasets to
build token representations and process commonly used open-source music
generation datasets.

##### Tokenizers

In musicaiz, we implemented the tokenization defined in the Multitrack Music
Machine model (MMM) [11] which uses the GPT-2 model [14] to generate multi-
track music. We can export the tokens in .txt format to be able to use the
tokens with other software. We also provide the get_vocabulary method to save
the vocabulary of a given tokenization also as a .txt file.

##### Datasets

For simplifying the processing of common datasets, we include this submodule
that uses the tokenizers submodule to process the following datasets: MAESTRO
[15], Lakh MIDI Dataset [16] and JSB Chorales [17].

####  2.2.4 Generation

For the specific task of symbolic music generation, musicaiz contains two
submodules: algorithms and models.

##### Algorithms

This submodule contains the implementation of a harmonic transposition
algorithm. Given the degrees per measure and the scale of a given symbolic
music data, it transposes the music to the target degrees and scale. This can
serve as a data augmentation technique for training large deep learning
models.

##### Models

This submodule contains another submodule transformer_composers which contains
the implementation of a GPT-based model with its corresponding training and
dataloaders modules in Pytorch [18]. The model can be trained to generate
symbolic music. With the submodules mentioned above, we can easily evaluate
the results and calculate the preprocessing steps required by the model. The
submodule models can be easily extended to provide more state-of-the-art model
implementations for music generation such as the Music Transformer [19].

####  2.2.5 Evaluation

From the music theory classes and functions, we built a submodule features to
extract features from the symbolic music data that we use in the submodule
eval.

##### Features

The submodule features contains implementations of some pitch, rhythm and
harmonic features. The goal of this module is to extract features from
symbolic music data that can be used to analyze, measure or also build
encodings to condition deep learning sequence models. The main elements of
this module are: Rhythm, Harmony and Pitch and Self-Similarity:

  * 1.

features.rhythm. We implemented part of the work of Roig et al. [20] to
provide a time signature numerator estimation.

  * 2.

features.harmony. Contains a basic algorithm to detect the global key of a
MIDI file.

  * 3.

features.pitch. It contains basic pitch characteristics from which the
submodule eval is subsequently built, allowing the evaluation of the musical
generation models.

  * 4.

features.self_similarity. Allows to build self-similarity matrices [21] in the
symbolic domain.

##### Eval

We can evaluate music generation from a subjective perspective [22] or an
objective method. This submodule corresponds to the implementation of Yang and
Lerch’s evaluation method [23] for the objective evaluation of music
generation. With it, we can cross-validate 2 or more data sets (trained and
generated). To do so, we first calculate the Euclidean distances of the data
sets from each other (inter-set) and from ecah other (intra-set), and
construct the histograms of the calculated distances. We extract the
probability density functions (PDF) from the histograms so that we can
calculate the overlap area (OA) and the Kullback Leibler divergence (KLD). We
can do this with each feature that we can calculate with the features
submodule which are: Pitch count (PC), Pitch class histogram (PCH), Pitch
class transition matrix (PCTM), Pitch range (PR) and Average pitch interval
(PI). The implemented rhythm-based features are: Note count (NC) or Note
Density, Average inter-onset-interval (IOI), Note length histogram (NLH), Note
length transition matrix (NLTM). An example of the PDFs extracted from 2
different datasets and features are shown in Fig. 2.

Figure 2: An example of objective evaluation of the intra-set PDFs of the JSB
Fakes and the JSB Chorales datasets. From left to right, up and down we show:
a) Pitch Counts (PC) b) Pitch class Histogram (PCH) c) Pitch Class Transition
Matrix (PCTM) d) Pitch Range (PR) e) Average Pitch Interval (PI) f) Note
Counts (NC) g) Inter Onset Interval (IOI) h) Note Length Histogram (NLH) i)
Note Length Transition Matrix (NLTM) PDFs.

####  2.2.6 Visualization

We can use the musaiz library also to plot symbolic music data as pianorolls.
We provide two classes that allow us to generate and save the plots in .png
(with matplotlib) and .html (with plotly) format. We set the x-axis (or time
axis) with the bars and subdivisions that the user can set. This is useful to
visualize the data as it is done in DAWs. We show an example of a pianoroll
with the grid of subdivisions on the x-axis in Fig. 3.

Figure 3: Pianoroll with subdivision’s grid.

####  2.2.7 Exports

The latest functionality of the musicaiz software is the export function. The
software provides a JSON representation of its objects that allows sending the
music information via REST APIs, which makes the software useful for
industrial applications as well.

##  3 Illustrative examples

⬇

1from musicaiz.loaders import Musa

2from musicaiz.plotters import Pianoroll

3from musicaiz import eval

4

5# \-------------Importing files----------------

6# Read MIDI file

7file = "mozart.mid"

8midi = Musa(file, structure="bars", quantize=False)

9

10# \-------------Evaluation---------------------

11# Extract features from MIDIs datasets and cross-validate

12midis_path_1 = "midis_path_1/"

13midis_path_1 = "midis_path_2/"

14measures_1 = eval.get_all_dataset_measures(midis_path_1)

15measures_2 = eval.get_all_dataset_measures(midis_path_2)

16# Get the intra-set distances of dataset 1

17intra_set_dists_1 = eval.euclidean_distance(measures_1)

18# Get the intra-set distances

19inter_set_dists = eval.euclidean_distance(measures_1, measures_2)

20

21# \-------------Plotting files----------------

22# Plot the pianoroll of the 1st instrument

23plot = Pianoroll()

24plot.plot_instrument(

25 total_bars=8,

26 track=midi.instrument[0].notes,

27 subdivision="quarter",

28 print_measure_data=False,

29 show_bar_labels=True,

30)

Listing 1: Musicaiz loading, evaluation and visualization examples

##  4 Impact

Software is one of the foundations of AI research and is becoming essential to
the scientific process. In MIR, researchers and engineers spend a lot of time
building the processing or evaluation tools they use in their work, and
sometimes these tools are often not published. By providing a general
framework that not only follows best practices for scientific computing, but
is also made following the principles of music, it is easier to build new
models and reproduce the results, increasing the quality of scientific
research. Therefore, musicaiz is built on top of well-established quality
packages such as prettymidi and mido for handling symbolic musical
information.

MusicAIz is tested with pytest and it is part of
AIBeatz’s444https://app.aibeatz.com/, last access July 2022 code base, a
company that makes music beats with AI.

##  5 Conclusions

We have presented a new open source object-oriented library for symbolic music
data that provides all the steps to generate and evaluate music with AI. We
hope that this library will be a useful tool for the community and will help
to build music generation systems with (or without) AI approaches. Since it
has been released as free and open source software, musicaiz can be easily
updated to add other symbolic music formats such as MusicXML or adding more
features for evaluating music generation such as structure pattern detection
with self-similarity matrices [21] [24]. Apart from that, further extensions
can be made by adding new token representations that may be needed by future
deep learning models or implementing new or other algorithms for feature
extraction, either by us as original authors or by any other researcher or
developer interested in it.

##  6 Acknowledgments

The authors would like to thank Ignacio Zay for his help in the implementation
of the quantization algorithm.

This research has been partially supported by the Spanish Science, Innovation
and University Ministry by the RTI2018-096986-B-C31 contract and the Aragonese
Government by the AffectiveLab-T60-20R project.

## References

  * [1] C. Hernandez-Olivan, J. R. Beltrán, Music composition with deep learning: A review, CoRR abs/2108.12290 (2021).
  * [2] J.-P. Briot, G. Hadjeres, F.-D. Pachet, Deep learning techniques for music generation, Vol. 1, Springer, 2020.
  * [3] C. McKay, J. Cumming, I. Fujinaga, JSYMBOLIC 2.2: Extracting features from symbolic music for use in musicological and MIR research, in: Proceedings of the 19th International Society for Music Information Retrieval Conference, ISMIR 2018, Paris, France, September 23-27, 2018, 2018, pp. 348–354.
  * [4] M. S. Cuthbert, C. Ariza, Music21: A toolkit for computer-aided musicology and symbolic music data, in: Proceedings of the 11th International Society for Music Information Retrieval Conference, ISMIR 2010, Utrecht, Netherlands, August 9-13, 2010, International Society for Music Information Retrieval, 2010, pp. 637–642.
  * [5] D. Huron, Music information processing using the humdrum toolkit: Concepts, examples, and lessons, Computer Music Journal 26 (2) (2002) 11–26.
  * [6] C. Raffel, D. P. Ellis, Intuitive analysis, creation and manipulation of midi data with pretty_midi, in: 15th international society for music information retrieval conference late breaking and demo papers, 2014, pp. 84–93.
  * [7] B. McFee, C. Raffel, D. Liang, D. P. Ellis, M. McVicar, E. Battenberg, O. Nieto, librosa: Audio and music signal analysis in python, in: Proceedings of the 14th python in science conference, Vol. 8, 2015, pp. 18–25.
  * [8] H. Dong, K. Chen, J. J. McAuley, T. Berg-Kirkpatrick, Muspy: A toolkit for symbolic music generation, in: Proceedings of the 21th International Society for Music Information Retrieval Conference, ISMIR 2020, Montreal, Canada, October 11-16, 2020, 2020, pp. 101–108.
  * [9] N. Fradet, J.-P. Briot, F. Chhel, A. El Fallah-Seghrouchni, N. Gutowski, Miditok: A python package for midi file tokenization, in: 22nd International Society for Music Information Retrieval Conference, 2021.
  * [10] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, I. Polosukhin, Attention is all you need, in: I. Guyon, U. von Luxburg, S. Bengio, H. M. Wallach, R. Fergus, S. V. N. Vishwanathan, R. Garnett (Eds.), Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, 2017, pp. 5998–6008.
  * [11] J. Ens, P. Pasquier, Mmm: Exploring conditional multi-track music generation with the transformer, arXiv preprint arXiv:2008.06048 (2020).
  * [12] M. T. Pearce, G. A. Wiggins, Expectation in melody: The influence of context and learning, Music Perception 23 (5) (2006) 377–405.
  * [13] W. Piston, M. DeVoto, A. Jannery, Harmony, WW Norton New York, 1978.
  * [14] A. Radford, J. Wu, R. Child, D. Luan, D. Amodei, I. Sutskever, Language models are unsupervised multitask learners (2019).
  * [15] C. Hawthorne, A. Stasyuk, A. Roberts, I. Simon, C.-Z. A. Huang, S. Dieleman, E. Elsen, J. Engel, D. Eck, Enabling factorized piano music modeling and generation with the MAESTRO dataset, in: International Conference on Learning Representations, 2019.
  * [16] C. Raffel, Learning-based methods for comparing sequences, with applications to audio-to-midi alignment and matching, Ph.D. thesis, Columbia University (2016).
  * [17] N. Boulanger-Lewandowski, Y. Bengio, P. Vincent, Modeling temporal dependencies in high-dimensional sequences: Application to polyphonic music generation and transcription, in: Proceedings of the 29th International Conference on Machine Learning, ICML 2012, Edinburgh, Scotland, UK, June 26 \- July 1, 2012, icml.cc / Omnipress, 2012.
  * [18] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf, E. Yang, Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, S. Chintala, Pytorch: An imperative style, high-performance deep learning library, in: Advances in Neural Information Processing Systems 32, Curran Associates, Inc., 2019, pp. 8024–8035.
  * [19] C. A. Huang, A. Vaswani, J. Uszkoreit, I. Simon, C. Hawthorne, N. Shazeer, A. M. Dai, M. D. Hoffman, M. Dinculescu, D. Eck, Music transformer: Generating music with long-term structure, in: 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019.
  * [20] C. Roig, L. J. Tardón, I. Barbancho, A. M. Barbancho, Automatic melody composition based on a probabilistic model of music style and harmonic rules, Knowledge-Based Systems 71 (2014) 419–434.
  * [21] J. Foote, Visualizing music and audio using self-similarity, in: J. F. Buford, S. M. Stevens, D. C. A. Bulterman, K. Jeffay, H. Zhang (Eds.), Proceedings of the 7th ACM International Conference on Multimedia ’99, Orlando, FL, USA, October 30 - November 5, 1999, Part 1, ACM, 1999, pp. 77–80.
  * [22] C. Hernandez-Olivan, J. A. Puyuelo, J. R. Beltran, Subjective evaluation of deep learning models for symbolic music composition, Workshop on Generative AI and CHI abs/2203.14641 (2022).
  * [23] L.-C. Yang, A. Lerch, On the evaluation of generative models in music, Neural Computing and Applications 32 (9) (2020) 4773–4784.
  * [24] C. Hernandez-Olivan, J. R. Beltran, D. Diaz-Guerra, Music boundary detection using convolutional neural networks: A comparative analysis of combined input features, International Journal of Interactive Multimedia and Artificial Intelligence 7 (2) (2021) 78–88.

## Current code version

Nr. |  Code metadata description |  Please fill in this column
---|---|---
C1 |  Current code version |  0.0.2
C2 |  Permanent link to code/repository used for this code version |  https://github.com/carlosholivan/musicaiz
C3 |  Permanent link to Reproducible Capsule |  https://codeocean.com/capsule/3873536/tree
C4 |  Legal Code License |  GNU Affero General Public License
C5 |  Code versioning system used |  git
C6 |  Software code languages, tools, and services used |  python
C7 |  Compilation requirements, operating environments & dependencies |  https://github.com/carlosholivan/musicaiz/blob/master/requirements.txt
C8 |  If available Link to developer documentation/manual |  http://carlosholivan.github.io/musicaiz
C9 |  Support email for questions |<EMAIL_ADDRESS>
Table 2: Code metadata (mandatory)