# Green NFTs: A Study on the Environmental Impact of Cryptoart Technologies

Samuele Marro<EMAIL_ADDRESS>(equal contribution) University of
Bologna  Luca Donno<EMAIL_ADDRESS>(equal contribution) University of
Bologna

(May 2021)

###### Abstract

We introduce a model of greenhouse gas emissions due to on-chain activity on
Ethereum, focusing on cryptoart. We also estimate the impact of individual
transactions on the environment, both before and after the London hard fork.
We find that with the current fee mechanism, spending one dollar on
transaction fees corresponds to emitting at least the equivalent of 1.305
kilograms of CO2. We also describe several techniques to reduce cryptoart
emissions, both in the short and long term.

##  1 Introduction

In the last year, there has been an exponential growth of cryptoart, a new
blockchain-based art form. After the publication of several articles that
aimed to raise awareness about its environmental impact (Akten, 2020)
(Lemercier, 2021), there has also been a growing interest in developing
solutions to reduce greenhouse gas (GHG) emissions due to cryptoart. A range
of proposals have been advanced, from reducing gas usage (Pipkin, 2021) to
switching to Proof of Stake blockchains (Wintermeyer, 2021) to carbon offsets
(Kahn, 2021). Others have even asserted that cryptoart has no impact on carbon
emissions (SuperRare, 2021) (Mattei, 2021). We argue that a model of the
environmental impact of cryptoart is fundamental to properly evaluate the
effectiveness of potential solutions. We therefore introduce a model to
compute the GHG emissions of cryptoart hosted on the Ethereum blockchain. We
also analyze the impact of a single transaction, focusing on both the current
fee mechanism and the soon to be implemented EIP-1559. By estimating the
geographical distribution of Ether miners and their cost breakdown, we find
that spending one dollar in transaction fees leads to additional GHG emissions
amounting to 1.305 kgCO2eq. Finally, we illustrate different solutions that
would reduce the environmental impact of cryptoart, focusing on both
individual and collective actions. A summary of our key conclusions can be
found in Section 9.

##  2 Background

###  2.1 Cryptoart

Cryptoart is a category of art based on blockchain technology. Artworks are
stored as Non-Fungible Tokens (NFTs), unique digital assets whose ownership
and scarcity can be verified in a decentralized and trustless manner. The
actions of creating (also known as "minting"), bidding, buying and
transferring NFTs are performed by executing transactions on-chain. Some of
the most known cryptoart platforms, such as OpenSea111Website: opensea.io,
Nifty Gateway222Website: niftygateway.com and SuperRare333Website:
superrare.co are currently hosted on the Ethereum network.

###  2.2 Block production

In order for a transaction to be accepted by the network, it must be included
in a block. A block is a data structure containing a collection of
transactions. Protocols define an entity, called validator, which appends new
blocks to the blockchain. Since blocks are limited in size and frequency,
validators prioritize inserting transactions that maximize their revenue.
Users therefore pay fees to be included in new blocks. A transaction with a
higher fee will be included sooner.

###  2.3 Proof of Work

Proof of Work (PoW) blockchains use a consensus algorithm where blocks are
validated by solving an energy intensive computational puzzle. The protocol
defines a value, block difficulty, which is adjusted in order to maintain a
fixed block frequency. The energy consumption required to validate (or mine) a
block is proportional to the block difficulty.

The computational power of a miner is measured by its hash rate. The
difficulty of a block is proportional to the total hash rate of the network.
The probability that a miner will mine a block is proportional to the
percentage of their own hash rate compared to that of the network. Given a
certain difficulty, both full and empty blocks require approximately the same
amount of energy to be mined.

While Bitcoin is mined on application-specific integrated circuits (ASICs),
Ethereum is relatively ASIC-resistant and is therefore mined on graphical
processing units (GPUs).

###  2.4 EIP-1559

EIP-1559 is an Ethereum update that will take place in July with the London
hard fork.

The current fee mechanism is based on first-price auctions. A transaction
requires a certain amount of block space, called gas, which is proportional to
its complexity. Each user chooses the price paid per unit of gas. Miners
prioritize transactions with the highest gas price; therefore, users have to
estimate the minimum gas price required to be included. Since users do not
have perfect information on other bids, this price tends to be overestimated.

EIP-1559 solves this problem by introducing a protocol-defined gas price,
BASEFEE, which must be paid for a transaction to be included in the block.
EIP-1559 defines a target block size $T$ and a maximum block size $2T$. If the
previous block was larger than $T$, BASEFEE is increased, and vice versa.

BASEFEE is computed as follows:

$B_{n+1}=B_{n}\left(1+\frac{1}{8}\frac{B_{n}-T}{T}\right)$

where $B_{n}$ is the BASEFEE of the $n$-th block.

The key difference between EIP-1559 and the current fee mechanism is that the
transaction fee is burned. To incentivize miners to include transactions,
users pay an additional MINER_TIP, which only covers execution costs.

If, at any point in time, the total size of pending transactions is higher
than $2T$, this new fee mechanism degrades to a first-price auction using
MINER_TIP.

Roughgarden (2020) predicts that EIP-1559 will not affect the gas price.

##  3 Miners

In this section, we show that, under reasonable assumptions, the global mining
cost of a PoW blockchain is approximately equal to the global mining revenue.

We treat miners as rational agents that aim to increase their profits. A
rational agent would not undertake an activity which would result in a ongoing
loss in doing so. This approach ignores other incentives that might motivate a
miner, such as the desire for a more decentralized blockchain.

Miners have two main sources of revenue: The block reward, which consists of:
The fixed block reward; The uncle block reward444Uncle block rewards and uncle
block inclusion rewards (Wood et al., 2014) are mechanisms to promote
decentralization. They are designed to reward miners that successfully mined a
block which was not validated by the network. ; The uncle block inclusion
reward; Transaction fees.

and three main costs:

  * •

Electricity cost;

  * •

Hardware cost;

  * •

Other types of costs, which we assume to be negligible.

The probability of a miner collecting the block reward and the transaction
fees is equal to their hash rate divided by the global hash rate. More
formally, we model the expected revenue of a miner $k$ from a block as:

$\mathbb{E}\left[R_{k}\right]=\left(R_{block}+R_{fees}\right)\frac{H_{k}}{\sum_{i}H_{i}}$
(1)

where $R_{block}$ is the revenue due to the block reward, $R_{fees}$ is the
revenue from transaction fees and $H_{i}$ is the hash rate of the $i$-th
miner.

Since miners have a negligible impact on $R_{block}$ and $R_{fees}$, the only
way to increase their revenue is to increase their relative hash rate. We
treat variations in the per-unit cost of hardware and electricity due to
economy of scale effects as negligible. If GPUs are being already used at
maximum performance, a higher hash rate can only be achieved by acquiring more
GPUs. Since the hardware cost of a typical mining setup is dominated by GPUs,
doubling the number of GPUs also roughly doubles the hardware cost. Similarly,
since the power requirements are dominated by GPUs, doubling their number
would also approximately double the electricity cost. GPUs, however, have a
limited lifetime before becoming outdated or unusable. We therefore treat GPUs
not as a one-time cost but as a recurring one.

More formally, we model the hash rate of a miner as directly proportional to
both hardware and electricity costs.

Since Ether can be mined using consumer-grade hardware and with minimal
technical skills, new miners can easily enter the market. We therefore model
Ether mining as a competitive virtual commodity market, a market in which
agents reach an equilibrium where the marginal revenue is equal to the
marginal cost. In other words, the revenue of mining for an additional day is
equal to the cost. The total mining revenue during a certain period of time is
therefore equal to the total mining cost:

$R_{tot}=C_{tot}$ (2)

Our findings match the results obtained by Hayes (2017), who applied a similar
model to estimate the GHG impact of Bitcoin.

Our model assumes that miners can quickly adapt their costs to market
fluctuations. This is possible due to the existence of alternative sources of
revenue (e.g. mining on other blockchains). If the profitability of Ether
mining decreases, some miners will redirect their computational power towards
other tasks, and vice versa. For the purpose of this paper, we ignore
variations in the profitability of such activities.

##  4 GHG Impact of Proof of Work

In this section, we show that the GHG impact of a PoW blockchain is directly
proportional to its global mining revenue.

First, we assume that variations in mining revenue do not significantly affect
the distribution of energy sources, as well as of the hardware used.

Therefore, we treat the GHG impact of hardware and electricity as directly
proportional to their costs. We model the GHG emissions due to mining as
follows:

$E_{tot}=\alpha_{hw}C_{hw}+\alpha_{el}C_{el}$ (3)

where $E_{tot}$ are the global mining emissions (in kgCO2eq) of mining,
$C_{hw}$ is the global mining cost due to hardware, $C_{el}$ is the global
mining cost due to electricity, and $\alpha_{hw}$ and $\alpha_{el}$ are
constants that represent the kgCO2eq emitted per dollar spent respectively on
hardware and electricity.

Assuming that variations in mining revenue do not meaningfully influence the
ratio between hardware and electricity costs, we rewrite $C_{hw}$ and $C_{el}$
as follows:

$C_{hw}=\beta C_{tot}$ (4) $C_{el}=(1-\beta)C_{tot}$ (5)

where $C_{tot}=C_{hw}+C_{el}$ and $0\leq\beta\leq 1$ is a constant.

$E_{tot}$ can be therefore rewritten as:

$E_{tot}=\alpha_{hw}\beta
C_{tot}+\alpha_{el}(1-\beta)C_{tot}=\alpha_{tot}C_{tot}=\alpha_{tot}R_{tot}$
(6)

where $\alpha_{tot}=\alpha_{hw}\beta+\alpha_{el}(1-\beta)$ is a constant
measuring the kgCO2eq emitted per dollar spent on mining.

##  5 Estimating $\alpha_{tot}$

In this section, we estimate the kgCO2eq emitted per dollar earned by Ether
miners.

We compute a lower bound of $\alpha_{tot}$ by considering only two sources of
GHG emissions, namely GPU production and electricity usage. In order to do so:

  * •

We choose a representative mining GPU;

  * •

We estimate the geographical distribution of Ether miners;

  * •

We estimate the weighted average kgCO2eq emitted per dollar spent on
electricity;

  * •

We estimate the average lifetime of a GPU and the ratio of $C_{el}$ and
$C_{hw}$ compared to $C_{tot}$ in that time frame;

  * •

We use our gathered data to compute an estimate of $\alpha_{tot}$.

###  5.1 Representative GPU

For the sake of modelling the role of GPUs in mining emissions, we use the AMD
RX 590 as a representative GPU. As of May 2021, the RX 590 is the GPU with the
highest Ethereum hash rate per Watt-hour Minerstat (2021). The relevant
specifications of an RX 590 are outlined in table 1.

Following De Vries (2018), we estimate a maximum GPU lifespan of 2 years.
Ardente and Talens Peiró (2015) estimate that producing a GPU has a GHG impact
of 54 kgCO2eq.

Name | AMD RX 590
---|---
Launch quarter | Q4 2018
Current average price | USD 650
Hash rate | 27.31 MH/s
Power consumption | 163 W
Table 1: Specifications of an AMD RX 590 GPU. Since November 2020, a spike in
demand has led to several shortages and an increase in average prices from USD
450 to USD 850. We therefore use an estimate of the average price in the last
6 months. Sources: AMD (2018), Minerstat (2021) CamelCamelCamel (2021).

###  5.2 Geographical Distribution of Miners

While the approximate global hash rate of the Ethereum network is known, the
inherent anonymity and decentralization of its protocol prevent accurate
estimates of the geographical distribution of its nodes.

A naive approach would be to count the number of Ethereum nodes in each
country. This technique, however, ignores potential differences in node hash
rate between different countries.

A second approach involves using data on mining pools. Mining pools represent
a large portion of the global hash rate (Lin et al., 2021) and often provide
information on their hash rate share. However, several large mining pools are
based in multiple countries and do not provide information regarding their
internal geographical distribution. Moreover, if the increased payout and
reliability outweigh the revenue loss due to connection delays, a miner might
join a pool in a different country or continent.

We therefore follow a different strategy: we use the data collected by Silva
et al. (2020) on block observation as a proxy of the true geographical
distribution of Ether miners. In April 2019, the authors collected statistics
on which of four nodes (located in Western Europe, Central Europe, North
America and East Asia) was the first to receive updates on a newly mined
block. While during the last two years there might have been shifts in the
geographical distribution, we argue that, due to the relative stability of
Ether mining economics555Compare with Bitcoin, which saw a shift towards
industrial, ASIC-based large scale mining (Taylor, 2017)., such estimates are
still adequate for our purposes. In the context of impact estimation, we treat
Western and Central Europe as the same region. We also consider the role of
other regions negligible. We compute a weighted average of kgCO2eq per dollar
based on average industrial electricity prices and carbon-intensity-per-
kilowatthour (CIPK), as outlined in table 2.

Region | Hash rate % | $/kWh | kgCO2eq/kWh | kgCO2eq/$
---|---|---|---|---
Europe | 50 | 0.1419 | 0.230 | 1.621
East Asia | 38 | 0.0916 | 0.582 | 6.354
North America | 12 | 0.0815 | 0.331 | 4.061
Overall | ~100 | 0.1155 | 0.376 | 3.712
Table 2: Industrial electricity prices and CIPK by region. We use average
electricity prices in the European Union (Rademaekers et al., 2020), People’s
Republic of China (ESCAP, 2018) and the United States (EIA, 2021). Source for
CIPK data: IEA (2020).

###  5.3 Global estimate

We conclude that, over a 2-year period, a single GPU will cost 980 dollars and
have an impact of 1279 kgCO2eq (see table 3). Our estimate of $\alpha_{tot}$
is therefore 1.305 kgCO2eq/$. In order to put this value into context, we
apply it to the current Ethereum data. From April 29, 2021, to May 5, the
average global daily revenue for Ethereum miners was 58.91 millions of dollars
(EtherChain, 2021a) (EtherChain, 2021b), equivalent to a daily emission of
76.89 ktCO2eq or an annual emission of 28.06 MtCO2eq. The latter value is
compatible with the 19.64 MtCO2eq figure estimated by the Ethereum Energy
Consumption Index over the same period (De Vries, 2021).

Name | Cost (USD) | GHG emissions (kgCO2eq)
---|---|---
Hardware | 650 | 54
Electricity | 330 | 1225
Total | 980 | 1279
Table 3: Final breakdown of costs and emissions for one RX 590 GPU over 2
years.

##  6 Individual Impact

While estimating the total emissions of a network can be useful to compare
entire blockchains, we also model the impact of a single transaction, both
with the current fee mechanism and with EIP-1559. In order to isolate the
effects of individual transactions, we assume that both the aggregate real
value of transactions on Ethereum and the velocity of Ether are constant for a
given period of time.

###  6.1 First-Price Auction

Suppose that a user successfully executes a transaction that requires $G$ gas
at a price (in Gwei, equivalent to $10^{-9}$ Ether) of $P_{gas}$ per unit of
gas. We identify three main effects of this action:

  1. 1.

The user paid their fee to a miner, thereby directly increasing the global
mining revenue;

  2. 2.

The user caused other transactions amounting to $G$ gas to be left out of the
block, which are then666Due to the specifications of the Ethereum protocol, it
is not possible to reduce the gas price of a submitted transaction.:

    1. (a)

Accepted later at the same price;

    2. (b)

Accepted after their gas price is increased;

    3. (c)

Never accepted;

  3. 3.

The user increased estimates of the gas price, leading other users to bid more
in the following blocks.

On May 1, out of more than 1.1 billion total Ethereum transactions
(Blockchair, 2021), roughly 190 thousand (<0.02%) were still pending, the
majority of which were accepted within 24 hours (Etherscan, 2021c). We
therefore treat case 2c as negligible.

We compute a lower bound of the increase in miner revenue by considering only
cases 1, 2a and 2b. This approach ignores the long-term effects of a
transaction, therefore providing a conservative estimate of the true impact.

Specifically, we model the lower bound of the overall increase in miner
revenue (in dollars) $\Delta R$ as:

$\Delta R\geq
P_{Gwei}GP_{gas}+P_{Gwei}\sum_{i}g_{i}\left(p_{i}^{\prime}-p_{i}\right)$ (7)

where $G=\sum_{i}g_{i}$, $P_{Gwei}$ is the price of one Gwei, and $g_{i}$,
$p_{i}$ and $p_{i}^{\prime}$ are respectively the gas amount, the old gas
price and the new gas price of the $i$-th transaction that was excluded. For
case 2a, $p_{i}^{\prime}=p_{i}$, which means that the direct revenue impact of
delaying such transactions is zero. We compute a looser lower bound by
ignoring case 2b777We analyzed 20k transactions executed on May 3, 2021,
finding that case 2b was responsible for an increase of less than 2% in
transaction revenue. (Etherscan, 2021d).

We therefore simplify inequality 7 by rewriting it as:

$\Delta R\geq GP_{Gwei}P_{gas}$ (8)

In other words, the lower bound $\Delta E$ of the GHG impact of a transaction
is:

$\Delta E\geq\alpha_{tot}GP_{Gwei}P_{gas}$ (9)

###  6.2 EIP-1559

With EIP-1559, since the MINER_TIP only covers the execution costs, the total
mining revenue is dominated by the block reward. Therefore, the only non-
negligible impact that a transaction has on mining revenue is the deflationary
effect of burning BASEFEE Ether.

Let $s_{t}$ be the rate of growth of the Ether circulating supply after the
$t$-th block has been mined:

$s_{t}=\frac{u_{t}}{S_{t}}$ (10)

where $u_{t}$ is the absolute variation in the number of existing Ethers and
$S_{t}$ is the Ether circulating supply after the $t$-th block has been mined.

Since we treat the real value of transactions on Ethereum and the velocity of
Ether as constant, by applying Fisher’s equation for the quantity theory of
money we find that the dollar value $P_{t+1}$ of one Ether after the $t+1$-th
block has been mined is:

$P_{t+1}=\frac{P_{t}}{s_{t}+1}=P_{t}\frac{S_{t}}{S_{t}+u_{t}}$ (11)

Let $V_{t}=P_{t}S_{t}$ be the total dollar value of the Ether circulating
supply after the $t$-th block has been mined. Note that

$V_{t+1}=P_{t+1}S_{t+1}=P_{t}\frac{S_{t}}{S_{t}+u_{t}}(S_{t}+u_{t})=P_{t}S_{t}=V_{t}$
(12)

In other words, $V_{t}$ is constant. Let $V:\forall t.\;V_{t}=V$. $P_{t}$ is
therefore:

$P_{t}=\frac{V}{S_{t}}$ (13)

In EIP-1559, there are two factors that have opposite effects on the
circulating supply. After each block is mined, $m=2$ additional Ethers are
created to reward the miners, while users burn the equivalent of $b$ dollars
in transaction fees. We assume $m$ and $b$ to be constant. $u_{t}$ is
therefore:

$u_{t}=m-\frac{b}{P_{t}}=m-\frac{b}{V}S_{t}$ (14)

$S_{t+1}$ is then equal to:

$S_{t+1}=S_{t}+u_{t}=S_{t}+m-\frac{b}{V}S_{t}$ (15)

while the miner revenue $R_{t+1}$ in USD after the $t+1$-th block has been
mined is:

$R_{t+1}=R_{t}+m\frac{V}{S_{t+1}}$ (16)

Let $S_{0}$ be the Ether circulating supply at a $t=0$.

$R_{t}$ can be rewritten as:

$\displaystyle\begin{split}R_{t}=&R_{t-1}+\frac{mV}{S_{t}}=\\\
=&R_{t-2}+\frac{mV}{S_{t-1}}+\frac{mV}{S_{t}}=\\\
&\mathmakebox[\widthof{{}={}}][c]{\vdots}\\\
=&R_{0}+\sum_{j=1}^{t}\frac{mV}{S_{j}}\end{split}$

Since $R_{0}=0$:

$R_{t}=mV\sum_{j=1}^{t}\frac{1}{S_{j}}$ (17)

$S_{t+1}$ can be rewritten as:

$S_{t+1}=S_{t}+m-\frac{b}{V}S_{t}=S_{t}\underbrace{(1-\frac{b}{V})}_{:=K}+m=KS_{t}+m$
(18)

which is equal to:

$\displaystyle\begin{split}S_{t+1}=&KS_{t}+m=\\\ =&K^{2}S_{t-1}+mK+m=\\\
=&K^{3}S_{t-2}+mK^{2}+mK+m=\\\ &\mathmakebox[\widthof{{}={}}][c]{\vdots}\\\
=&K^{t+1}S_{0}+m\sum_{j=0}^{t}K^{j}\end{split}$

$S_{t}$ is therefore equal to:

$S_{t}=K^{t}S_{0}+m\left(\frac{1-K^{t}}{1-K}\right)$ (19)

Spending $l$ dollars on transaction fees is equivalent to removing
$lP_{0}=l\frac{V}{S_{0}}$ Ethers from the initial circulating supply. Between
the deployment of EIP-1559 (in July) and the transition to Proof of Stake (at
the beginning of 2022, after which the additional environmental impact of the
transaction will be negligible), only around 1.16 million blocks are expected
to be mined. Since the closed-form expression of $R_{t}$ (which we report in
Appendix A) does not provide an intuition on the effect of a transaction, we
instead plot the additional miner revenue $\Delta R_{t}$. As shown in figure
1, the additional revenue is at least one to two orders of magnitude lower
than with the current fee mechanism.

We estimate that, under our hypotheses, during the approximately 180 days
between the introduction of EIP-1559 and the transition to PoS, the total
miner revenue with the current fee mechanism would be 9.9 billion dollars.
Over the same period, with EIP-1559 the miner revenue would be 6.8 billion
dollars, corresponding to a reduction in the GHG emissions of Ethereum by
approximately a third.

$0$$0.1$$0.2$$0.3$$0.4$$0.5$$0.6$$0.7$$0.8$$0.9$$1$$1.1$$\cdot
10^{6}$$0$$0.2$$0.4$$0.6$$0.8$$1$$1.2$$1.4$$1.6$$1.8$$2$$t$ (Blocks)$\Delta
R_{tot}$ (USD) Figure 1: Difference in miner revenue due to the execution of a
transaction which requires a fee of 100 dollars. The x axis represents the
time of execution, with $t=0$ corresponding to the first block after the
introduction of EIP-1559. We set $S_{0}$ = 115.7M Ether and $V_{0}$ = 341B
USD, corresponding to the average circulating supply and total value on May 1,
2021 (CoinGecko, 2021). We use $b$ = 2650 USD, equal to the average revenue
per block due to transaction fees from April 29, 2021 to May 5, 2021
(Etherscan, 2021b).

##  7 Solutions

In this section, we present the most relevant solutions to reduce the GHG
impact of NFTs, focusing on both individual and collective actions.

###  7.1 Individual Actions

From the model described in section 6, we deduce that any action to reduce
transaction fees has a beneficial impact on GHG emissions. We therefore
outline some practices to reduce the individual impact of a user.

A simple yet effective solution is to perform transactions using a lower gas
price. This can be done by tolerating a longer confirmation time, executing
transactions during times of the day with lower gas demand, or both.

Another way to reduce the environmental impact is by decreasing gas usage. For
example, lazy minting minimizes gas requirements by treating the creation and
sale of an NFT as a single transaction.

Additionally, artists often auction NFTs on-chain. Since on-chain bids require
paying a transaction fee, we suggest using off-chain bids (supported for
example by the Wyvern Protocol, implemented by OpenSea) to help reduce
emissions.

Finally, most NFTs are sold through instant sales, where artists sell their
work for a fixed price. If the artwork is particularly sought after, buyers
are incentivized to use higher gas prices to outrun the others, therefore
paying a much higher transaction fee than necessary. Moreover, buyers that
fail to obtain a copy also pay transaction fees. In such cases, switching from
instant sales to off-chain bids can significantly reduce the impact of
cryptoart.

###  7.2 Proof of Stake

Proof of Stake (PoS) is a class of consensus algorithms that select and reward
validators as a function of their economic stake in the network (Bentov et
al., 2016). Unlike PoW, the probability of creating a block in a PoS network
does not depend on computational power, but rather on the staked amount that
might be lost in case of fraudulent activity. A PoS node has minimal hardware
and electricity requirements, and therefore has a significantly lower
environmental impact. Moreover, increasing the stake has no effect on the
energy consumption of the node. Ethereum 2.0, the upcoming PoS version of
Ethereum, is expected to reduce the environmental impact of the network by 99%
(Fairley, 2019).

###  7.3 Layer 2

Layer 2 is a collective term for solutions designed to help scale applications
by handling transactions off the main chain (referred to as layer 1).
Generally speaking, transactions are submitted to layer 2 nodes, which batch
them into groups before storing them on layer 1.

Layer 2 technologies that are based on Ethereum have a nontrivial impact on
the environment. However, layer 2 transactions require significantly less gas
and therefore represent a preferable alternative to executing them directly
on-chain. The main types of layer 2 solutions are sidechains and rollups.

####  7.3.1 Sidechains and Plasma

A sidechain is a separate blockchain which runs parallel to the layer 1 and
operates independently, usually with a Proof of Stake consensus algorithm.
Sidechains are connected to the main chain by a two-way bridge and are often
less decentralized and therefore less secure than their layer 1.

Plasma, on the other hand, is a technology that provides a way to execute
transactions off-chain at a higher frequency and lower cost. It regularly
stores on layer 1 information such as asset ownership, protecting it from
attacks. However, in extreme cases, it is not guaranteed that the full state
of Plasma can be recovered (Poon and Buterin, 2017). Sidechains and Plasma can
be used together, such as in the case of Polygon, which features a hybrid
protocol to mitigate the risk of information loss (Kanani et al., 2019).

####  7.3.2 Rollups

Rollups are a class of layer 2 technologies that execute transactions outside
layer 1 but store their data on-chain. This approach guarantees that, even in
case of attack, it is always possible to recover all performed transactions.
The same transaction, if executed on a rollup, requires two to three orders of
magnitude less gas compared to its layer 1 counterpart (Buterin, 2021).
Rollups can be divided into zero-knowledge and optimistic rollups.

Zero-knowledge (ZK) rollups bundle transactions off-chain and generate a
cryptographic proof of their validity. This proof, known as a SNARK (Succinct
Non-interactive ARgument of Knowledge), is then stored on layer 1. Being a
relatively new technology, as of May 2021 the only known NFT platform hosted
on ZK rollups is Immutable X888Website: immutable.com, which is currently in
closed alpha. The main disadvantage of ZK rollups is that they do not support
general computation. Because of this constraint, only basic NFT operations
(e.g. minting and trading) can be executed. Extending ZK rollups is currently
an active area of research.

Optimistic rollups, on the other hand, assume that all transactions are valid
(hence the name "optimistic"). In optimistic rollups, anyone can submit a new
transaction batch. However, if a user (also known as "fraud verifier")
suspects that a batch is fraudulent, it is possible to prove it by executing
the entire computation using the stored data. Fraud verifiers are usually
rewarded financially at the expense of malicious users. Unlike ZK rollups,
optimistic rollups support general computation, but, before withdrawing
assets, users must wait a "challenge period" during which other users can
claim fraudulent activity.

The two most known optimistic rollups, Optimism999Website: optimism.io and
Arbitrum101010Website: arbitrum.io, are currently in development. Optimism is
expected to launch in July, while, as of May 2021, the team behind Arbitrum
has not provided a launch date yet.

###  7.4 Carbon Offsets

Carbon offsets represent an alternative way to reduce the GHG impact of
blockchains. By purchasing carbon offsets, a user compensates for their
emissions by funding activites that have a negative GHG balance, such as
planting trees or increasing the commercial viability of renewable energy.
Several initiatives that use blockchains as a tool to complement carbon
markets have been introduced (Howson et al., 2019) (Kahn, 2021). Moreover,
some NFT platforms, such as Immutable X, compensate for their GHG emissions by
automatically purchasing carbon offsets (Immutable, 2020).

Another, more indirect, method to reduce the environmental impact is to donate
to climate non-profits. The cryptoart platform KnownOrigin111111Website:
knownorigin.io, for example, offers an interface for artists to donate part of
their revenue to sustainable causes (KnownOrigin, 2021).

##  8 Example

To put our results in context, we use our model to estimate the environmental
impact of a hypothetical cryptoart piece, focusing on Ethereum PoW with the
current fee mechanism. Consider an NFT with the following gas requirements:

  * •

Minting: 450k gas

  * •

Buying: 300k gas

  * •

Transferring: 80k gas

  * •

Bidding: 100k gas

Refer to table 4 for an estimate of the impact of these transactions.

Suppose that after minting the artwork, the creator auctions it on-chain,
receiving 10 bids. The winning bidder then purchases the NFT and transfers it
to a secondary account. The impact of this art piece is therefore equal to the
sum of the impacts of 1 mint, 10 bids, 1 purchase and 1 transfer. In other
words, the impact of our hypothetical NFT is 467.29 kgCO2eq, equivalent to
driving a typical passenger vehicle 1157 miles (or 1862 km) (EPA, 2018).

There are several simple actions that can be taken to reduce this figure:

  * •

Using off-chain bids would reduce emissions by 55%;

  * •

Executing transactions using the minimum required gas price (which, during
April 29, 2021 - May 5, 2021, was on average 45 Gwei (GasNow, 2021)) would
reduce transaction fees, and therefore emissions, by 26%;

  * •

Similarly, executing these transactions during times of the day with a lower
minimum gas price, such as at 5 p.m. UTC (see table 2), would reduce emissions
by an additional 31%;

All these actions together would reduce emissions to 107.37 kgCO2eq (-77%),
equivalent to driving 265 miles (or 426 km). Assuming 0.004 $/kgCO2eq
(SavingNature, 2021), offsetting these emissions would cost approximately 0.43
dollars.

Transaction | Gas usage | Cost (USD) | Impact (kgCO2eq)
---|---|---|---
Minting | 450k | 88.03 | 114.90
Buying | 300k | 58.69 | 76.60
Transferring | 80k | 15.65 | 20.42
Bidding | 100k | 19.56 | 25.54
Table 4: Impact of different transactions of a hypothetical cryptoart piece.
We use the average gas price from April 29, 2021 to May 5, 2021 of 61 Gwei
(Etherscan, 2021a), as well as the average Ether price of 3207 USD in the same
period (YCharts, 2021).
00:0006:0012:0018:0023:00$0$$10$$20$$30$$40$$50$$60$$70$$80$HourGas price
(Gwei) Figure 2: Minimum gas price required to be included in a block by time
of the day, with daily average. The data was collected from April 29, 2021 to
May 5, 2021. All times are in UTC. Source: GasNow (2021).

##  9 Key Takeaways

In this section, we list the most meaningful results of our study.

  1. 1.

The impact of a transaction does not depend only on the gas used, but is
instead proportional to the transaction fee;

  2. 2.

Spending 1 dollar on transaction fees on Ethereum is equivalent to emitting at
least 1.305 kgCO2eq;

  3. 3.

A blockchain with full blocks pollutes more than one with empty blocks;

  4. 4.

The single most effective action that a user can take to reduce their own
impact is to pay a reasonably lower gas price;

  5. 5.

Variations in the price of Ether influence the greenhouse gas emissions of the
Ethereum network;

  6. 6.

As of early May 2021, Ethereum emits 28.06 MtCO2eq per year;

  7. 7.

EIP-1559 is expected to reduce global Ethereum emissions by about a third;

  8. 8.

Using Layer 2 technologies significantly reduces the impact of transactions;

  9. 9.

Transitioning to Proof of Stake remains the best long-term solution for
Ethereum.

##  10 Conclusion

Our figure of 28.06 MtCO2eq per year represents a grim remainder of the need
for scalable solutions to reduce Ethereum emissions.

In this paper, we developed a model that can be used by cryptoartists to not
only estimate the emissions of the entire network, but also measure their own
environmental impact. We found that, in the short term, the most effective way
for a user to reduce their emissions is to execute transactions with longer
waiting times or during low-activity hours.

Our model, while designed with cryptoart in mind, can be easily applied to
other areas, such as decentralized finance or games. The focus on transactions
allows researches and members of the art community to evaluate the
effectiveness of new solutions (both on and off chain), providing an immediate
feedback and highlighting which research directions are worth pursuing.

A key limitation of our model is that it only takes into account the main
factors that influence the behaviour of miners. Future studies might expand
upon our work by considering other costs (e.g. human labour) or sources of
revenue (e.g. Miner-Extractable Value (Daian et al., 2020)). Since the GHG
emissions of the Ethereum blockchain also depend on the price of Ether,
modelling the role of activities that influence its value (e.g. financial
speculation) could provide a more complete picture of their environmental
impact.

We hope that this paper will provide a basis for further developments in the
field, with the eventual goal of building decentralized art platforms that
unite artist empowerment and sustainable emissions.

## Acknowledgements

We would like to thank Davide Evangelista, Violetta Van Veen and Giuseppe
Pignataro for their invaluable help with this paper.

Potential conflicts of interest. At the time of writing, both authors own
Ether and Ethereum-related cryptocurrencies. Moreover, both authors own NFTs
and have been involved in the creation of NFTs and NFT platforms.

## References

  * Akten [2020] Memo Akten.  The Unreasonable Ecological Cost of #CryptoArt.  December 2020.  URL https://memoakten.medium.com/the-unreasonable-ecological-cost-of-cryptoart-2221d3eb2053.
  * AMD [2018] AMD.  RX 590 specifications, 2018.  URL https://www.amd.com/en/products/graphics/radeon-rx-590.  [Online; accessed on May 1, 2021].
  * Ardente and Talens Peiró [2015] Fulvio Ardente and Laura Talens Peiró.  Environmental footprint and material efficiency support for product policy. Analysis of material efficiency requirements of enterprise servers.  2015\.  doi: http://dx.doi.org/10.2788/409022.
  * Bentov et al. [2016] Iddo Bentov, Ariel Gabizon, and Alex Mizrahi.  Cryptocurrencies without proof of work.  In _International conference on financial cryptography and data security_ , pages 142–157. Springer, 2016.
  * Blockchair [2021] Blockchair.  Ethereum Total transaction Chart, 2021.  URL https://blockchair.com/ethereum/charts/total-transaction-count.  [Online; accessed on May 3, 2021].
  * Buterin [2021] Vitalik Buterin.  An Incomplete Guide to Rollups.  January 2021.
  * CamelCamelCamel [2021] CamelCamelCamel.  RX 590 price chart, 2021.  URL https://camelcamelcamel.com/product/B07PQJ2S5G.  [Online; accessed on May 1, 2021].
  * CoinGecko [2021] CoinGecko.  Ethereum (ETH), 2021.  URL https://www.coingecko.com/en/coins/ethereum.  [Online; accessed on May 6, 2021].
  * Daian et al. [2020] Philip Daian, Steven Goldfeder, Tyler Kell, Yunqi Li, Xueyuan Zhao, Iddo Bentov, Lorenz Breidenbach, and Ari Juels.  Flash boys 2.0: Frontrunning in decentralized exchanges, miner extractable value, and consensus instability.  In _2020 IEEE Symposium on Security and Privacy (SP)_ , pages 910–927. IEEE, 2020.
  * De Vries [2018] Alex De Vries.  Bitcoin’s growing energy problem.  _Joule_ , 2(5):801–805, 2018.
  * De Vries [2021] Alex De Vries.  Ethereum Energy Consumption Index, 2021.  URL https://digiconomist.net/ethereum-energy-consumption.  [Online; accessed on May 2, 2021].
  * EIA [2021] EIA.  Monthly Electric Power Industry Report.  _U.S. Energy Information Administration_ , February 2021.
  * EPA [2018] EPA.  Greenhouse Gas Emissions from a Typical Passenger Vehicle.  _Office of Transportation and Air Quality_ , March 2018.  URL https://nepis.epa.gov/Exe/ZyPDF.cgi?Dockey=P100U8YT.pdf.
  * ESCAP [2018] ESCAP.  Sustainable Energy in Asia and the Pacific.  _United Nations Economic and Social Commission for Asia and the Pacific_ , 2018.  URL https://www.unescap.org/sites/default/files/Statistical\%20Perspective\%202018\%20WEB.pdf.
  * EtherChain [2021a] EtherChain.  Evolution of the Total Daily Mining Reward, 2021a.  URL https://etherchain.org/charts/miningReward.  [Online; accessed on May 2, 2021].
  * EtherChain [2021b] EtherChain.  Evolution of the Ethereum Price in USD, 2021b.  URL https://etherchain.org/charts/price_USD.  [Online; accessed on May 6, 2021].
  * Etherscan [2021a] Etherscan.  Ethereum Average Gas Price Chart, 2021a.  URL https://etherscan.io/chart/gasprice.  [Online; accessed on May 6, 2021].
  * Etherscan [2021b] Etherscan.  Ethereum Daily Block Rewards Chart, 2021b.  URL https://etherscan.io/chart/blockreward.  [Online; accessed on May 6, 2021].
  * Etherscan [2021c] Etherscan.  Ethereum Network Pending Transactions Chart, 2021c.  URL https://etherscan.io/chart/pendingtx.  [Online; accessed on May 3, 2021].
  * Etherscan [2021d] Etherscan.  Transactions, 2021d.  URL https://etherscan.io/txs.  [Online; accessed on May 4, 2021].
  * Fairley [2019] Peter Fairley.  Ethereum Plans to Cut Its Absurd Energy Consumption by 99 Percent.  _IEEE Spectrum_ , January 2019.  URL https://spectrum.ieee.org/computing/networks/ethereum-plans-to-cut-its-absurd-energy-consumption-by-99-percent.
  * GasNow [2021] GasNow.  Average GasPrice, 2021.  URL https://www.gasnow.org.  [Online; accessed on May 3, 2021].
  * Hayes [2017] Adam S Hayes.  Cryptocurrency value formation: An empirical study leading to a cost of production model for valuing bitcoin.  _Telematics and Informatics_ , 34(7):1308–1321, 2017.
  * Howson et al. [2019] Peter Howson, Sarah Oakes, Zachary Baynham-Herd, and Jon Swords.  Cryptocarbon: the promises and pitfalls of forest protection on a blockchain.  _Geoforum_ , 100:1–9, 2019.
  * IEA [2020] IEA.  Composition of CO2 emissions and emission intensity in 2020, 2020.  URL https://www.iea.org/data-and-statistics/charts/composition-of-co2-emissions-and-emission-intensity-in-2020.
  * Immutable [2020] Immutable.  Immutable X is Making NFTs Carbon Neutral on Ethereum.  October 2020.  URL https://www.immutable.com/blog/carbon-neutral-nfts.
  * Kahn [2021] Brian Kahn.  How to Fix Crypto Art NFTs’ Carbon Pollution Problem.  March 2021.  URL https://earther.gizmodo.com/how-to-fix-crypto-art-nfts-carbon-pollution-problem-1846440312.
  * Kanani et al. [2019] Jaynti Kanani, Sandeep Nailwal, and Anurag Arjun.  Matic Whitepaper.  2019\.
  * KnownOrigin [2021] KnownOrigin.  A step toward sustainability.  2021\.  URL https://knownorigin.io/journal/platformupdate/a-step-toward-sustainability.
  * Lemercier [2021] Joanie Lemercier.  The problem of CryptoArt.  February 2021.  URL https://joanielemercier.com/the-problem-of-cryptoart/.
  * Lin et al. [2021] Qinwei Lin, Chao Li, Xifeng Zhao, and Xianhai Chen.  Measuring decentralization in bitcoin and ethereum using multiple metrics and granularities.  _arXiv preprint arXiv:2101.10699_ , 2021.
  * Mattei [2021] Shanti Escalante-De Mattei.  Should You Worry About the Environmental Impact of Your NFTs?  _ARTNews_ , April 2021.  URL https://www.artnews.com/art-news/news/nft-carbon-environmental-impact-1234589742/.
  * Minerstat [2021] Minerstat.  GPU Mining Leaderboard, 2021.  URL https://minerstat.com/hardware/gpus?algo=Ethash.  [Online; accessed on May 1, 2021].
  * Pipkin [2021] Everest Pipkin.  Here is the article you can send to people when they say “But the environmental issures with cryptoart will be solved soon, right?”.  March 2021.  URL https://everestpipkin.medium.com/but-the-environmental-issues-with-cryptoart-1128ef72e6a3.
  * Poon and Buterin [2017] Joseph Poon and Vitalik Buterin.  Plasma: Scalable autonomous smart contracts.  _White paper_ , pages 1–47, 2017.
  * Rademaekers et al. [2020] Koen Rademaekers, Matthew Smith, and Perla C. et al. Torres Vega.  Study on energy prices, costs and their impact on industry and households - Final Report.  2020\.  URL https://op.europa.eu/en/publication-detail/-/publication/16e7f212-0dc5-11eb-bc07-01aa75ed71a1/language-en.
  * Roughgarden [2020] Tim Roughgarden.  Transaction Fee Mechanism Design for the Ethereum Blockchain: An Economic Analysis of EIP-1559.  _arXiv preprint arXiv:2012.00854_ , 2020.
  * SavingNature [2021] SavingNature.  Carbon Footprint Calculator, 2021.  URL https://savingnature.com/offset-your-carbon-footprint-carbon-calculator/.  [Online; accessed on May 7, 2021].
  * Silva et al. [2020] Paulo Silva, David Vavricka, Joao Barreto, and Miguel Matos.  Impact of geo-distribution and mining pools on blockchains: a study of Ethereum.  In _2020 50th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN)_ , pages 245–252. IEEE, 2020.
  * SuperRare [2021] SuperRare.  No, CryptoArtists Aren’t Harming the Planet.  2021\.  URL https://medium.com/superrare/no-cryptoartists-arent-harming-the-planet-43182f72fc61.  [Online; accessed on May 3, 2021].
  * Taylor [2017] Michael Bedford Taylor.  The evolution of bitcoin hardware.  _Computer_ , 50(9):58–66, 2017.
  * Wintermeyer [2021] Lawrence Wintermeyer.  Climate-Positive Crypto Art: The Next Big Thing Or NFT Overreach?  _Forbes_ , March 2021.  URL https://www.forbes.com/sites/lawrencewintermeyer/2021/03/19/climate-positive-crypto-art-the-next-big-thing-or-nft-overreach/?sh=482cfa04b0e6.
  * Wood et al. [2014] Gavin Wood et al.  Ethereum: A secure decentralised generalised transaction ledger.  _Ethereum project yellow paper_ , 151(2014):1–32, 2014.
  * YCharts [2021] YCharts.  Ethereum Price, 2021.  URL https://ycharts.com/indicators/ethereum_price.

##  Appendix A Closed-Form Expression of $R_{t}$

Let $\psi_{q}(x)=\frac{d}{dx}\Gamma_{q}(x)$ be the $q$-digamma function. Let

$h=\frac{\log\left(\frac{m}{m+KS_{0}-S_{0}}\right)}{\log K}$ (20)

The closed-form expression of $R_{t}$ is:

$mV\left(\frac{(K-1)\psi_{K}\left(t-h+1\right)}{m\log
K}+\frac{(1-K)\psi_{K}\left(-h\right)}{m\log K}-\frac{(K-1)(t+1)}{m}\right)$
(21)

where $\log$ is the natural logarithm.

$\Delta S_{t}=m-\frac{b}{V}S_{t}$ (22)

$\frac{dS}{dt}=m-\frac{b}{V}S$ (23)

$S_{t}=c_{1}e^{-bt/V}+\frac{mV}{b}$ (24)

For $t=0$, the formula is equal to the initial circulating supply $S_{0}$.
Therefore:

$c_{1}=S_{0}-\frac{mV}{b}$ (25)
$S_{t}=\frac{mV}{b}\left(S_{0}-e^{-bt/V}\right)$ (26)


# Elementary solution to the fair division problem

Michael Blank and Maxim Polyakov  Institute for Information Transmission
Problems RAS (Kharkevich Institute);National Research University “Higher
School of Economics”;e-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>
(May 2, 2024)

###### Abstract

A new and relatively elementary approach is proposed for solving the problem
of fair division of a continuous resource (measurable space, pie, etc.)
between several participants, the selection criteria of which are described by
charges (signed measures). The setting of the problem with charges is
considered for the first time. The problem comes down to analyzing the
properties of the trajectories of a specially constructed dynamical system
acting in the space of finite measurable partitions. Exponentially fast
convergence to a limit solution is proved for both the case of true measures
and the case of charges. Key words: fair division, mathematical economics,
multicriteria optimization, countably additive measures/charges, dynamical
systems.

##  1 Introduction

Problems associated with “optimal” division of resources under a given system
of constraints are one of the most basic problems of mathematical economics.
Their fundamental complexity is determined by the large number (usually)
conflicting criteria for “optimality” of the division. The simplest example
here is the question of dividing a highly heterogeneous pie (treasure,
apartment, etc.) between several participants, whose assessments of the parts
they obtain may essentially differ from each other.

Thus, the fair division problem belongs to the class of multicriteria
optimization problems; however, this problem has several important distinct
features. The main one is that instead of searching for an “optimal” (in one
sense or another) solution (which may not exist), it is proposed to search for
an acceptable solution. The latter setting in most cases turns out to be much
simpler. In a sense, this approach is a far generalization of the search for a
base point (one of the vertices of a simplex) in the classical linear
programming problem.

The problem of fair division in the simplest case is formulated as follows.
Suppose that we need to divide a pie among $r$ people so that everyone
believes that he was not deprived. At the same time, the pie is highly
heterogeneous, and each participant has his own criteria for comparing
different pieces of the pie. For example, someone likes a piece with
strawberries better, while someone else notices that the left side of the pie
is slightly burnt, etc. The question arises of whether it is always possible
to do this? Despite its seemingly school-like nature, this task turns out to
be very difficult and a huge number of publications was devoted to it in
various settings (reviews of known results can be found, e.g., in [1, 2, 3,
4]).

The first rigorous mathematical results for the case when the participants’
criteria are determined by non-atomic countably additive measures, were
obtained in 1961 by Dubins and Spanier [5], who, relying on the results of
Lyapunov [6] and Halmos [7] on the convexity property for vector measures,
proved that for any set of criteria of the participants in the division
(represented by non-atomic measures) the pie can be cut “fairly”. In 1980, W.
Stromquist [8] proved that this can be done in exactly $r-1$ cuts. However,
this proof (as well as the result of [5]) is not constructive, and an explicit
algorithm for such division is known only for $r<4$. Much later, in 1999, F.E.
Su [9] developed a fundamentally different combinatorial-topological approach
to solve this problem, based on an iterative exponentially fast converging
algorithm.

Since we will be interested in approaching the fair division problem from the
point of view of abstract measure theory, we do not consider numerous
important and interesting geometric aspects of this problem such as
representing a resource as a subset of Euclidean space, the possibility of
partitioning by hyperplanes, or restricting partitions to connected sets only.
The reader can find references to relevant results in the above reviews.

Until recently, it was believed that there was no final algorithm for solving
the fair division problem (under some “natural” technical assumptions111The
resource is represented by a unit segment, and the partition elements are
intervals.) (see, for example, [10]) . However, in 2016, H. Aziz and S.
McKenzie [11] proposed a finite algorithm. The algorithm is technically very
complex, and the estimate $r^{r^{r^{r^{r^{r}}}}}$ for the number of steps
required to construct a solution is astronomically large even for a small
number of participants.

In real life, criteria for participants can naturally turn out to be much more
complex and not reducible to classical measures. A complete study of
functionals that allow the solution of the fair division problem has not been
completed to date. The only progress here is related to the situation where it
is not the “best” but the worst parts are chosen. Formally, in terms of
measure theory, this means that the corresponding criterion is equal to some
measure with a minus sign. A version of the finite Aziz-McKenzie algorithm for
this case is proposed in [12]. Oddly enough, the combination of these options,
i.e., the situation where the criteria are described by charges (signed
measures), has not been studied in the mathematical literature.222As the
reviewer pointed out to us, a particular example for 3 participants was
considered in [13]. A possible explanation is that the authors were unable to
reconcile in one algorithm the contradictions that arise in approaches with
positive and negative measures.

In this work, we propose a fairly simple exponentially fast convergent
algorithm for solving the fair division problem for the case where criteria of
participants are described by non-atomic countably additive charges.

Due to the non-atomicity of the functionals under consideration, various parts
of the measurable space in a whole (for all participants simultaneously) seem
to be homogeneous. Therefore, at first glance, our solution looks somewhat
paradoxical. The idea is to successively select disjunctive parts of the space
on each of which it is possible to present an exact solution. The total
remainder measure turns out to be exponentially small (relative to the step
number of the division process), which guarantees exponentially fast
convergence of the process.

The paper is organized as follows. Section 2 provides a formal mathematical
formulation of the problem; after that, facts on which the given algorithm is
based are presented, and the main ideas of its construction are demonstrated
in cases with a small number of participants. The last two sections describe
the algorithm for constructing a strong solution for measures and its
generalization to the case of charges.

##  2 Formulation of the problem. Strong and weak solutions.

Let $(M,\Sigma)$ be a measurable space, that is, a pair of a set $M$ and a
$\sigma$-algebra of its measurable subsets $\Sigma$. Let us fix a natural
number $r$, a set $\\{\mu_{i}\\}_{i=1}^{r}$ of functionals
$\mu_{i}\colon\Sigma\to\mathbb{R}$, and a measurable partition
$\mathcal{F}:=\\{F_{i}\\}_{i=1}^{r}$ of the set $M$.

###### Definition 2.1

In the fair division problem, we call a partition $\mathcal{F}$

  * •

a _weak_ solution, if
$\mu_{i}(F_{i})\geq\frac{1}{r}\sum\limits_{j=1}^{r}\mu_{i}(F_{j})$ for all
$i$;

  * •

a _strong_ solution, if $\mu_{i}(F_{i})\geq\mu_{i}(F_{j})$ for all $i,j$.

A weak solution to the problem corresponds to the case where the $i$-th
participant has gained on average, relative to the functional $\mu_{i}$, no
less than the others. A strong solution corresponds to the case where everyone
believes that any other participant has gained no more than himself.

Note that in the literature on economics, a weak solution is often referred to
as a “proportional”, and a strong solution as an “envy-free” solution. In
mathematics context, our terminology (first proposed by M. Blank in [14])
seems more convenient and adequate. Conceptually, this terminology goes back
to the classical notions of weak and strong solutions in theory of
differential equations.

###### Lemma 2.1

Let $\mathcal{M}$ be a class of functionals for which the fair division
problem has a solution. Then for any $r$ and any $\mu\in\mathcal{M}$ there is
a partition of $M$ into $r$ measurable subsets
$\left\\{F_{i}\right\\}_{i=1}^{r}$such that $\mu(F_{i})=\mu(F_{j})$, $\forall
i,j$.

Proof.  For the existence of any of the above types of solutions to the fair
division problem, a necessary requirement is the presence of a corresponding
solution for the case when all functionals $\mu_{i}$ coincide and are equal to
$\mu$. In this case, the conditions for the weak and strong solutions are as
follows:

  * •

$\mu(F_{i})\geq\frac{1}{r}\sum\limits_{j=1}^{r}\mu(F_{j})$, $\forall i$;

  * •

$\mu(F_{i})\geq\mu(F_{j})$, $\forall i,j$.

Each of these conditions imply that $\mu(F_{i})=\mu(F_{j})$ for all $i,j$.
Thus, there is a measurable partition of the set $M$ into $r$ parts $F_{i}$
that are equal with respect to the functional $\mu$.

An important question is sufficiency of this condition for different types of
the problem setting. A full answer to this question remains open, but the
following theorem provides the most complete solution for today.

###### Theorem 2.1

For any non-atomic countably additive charges
$\left\\{\psi_{i}\right\\}_{i=1}^{r}$ there is an explicit constructive
algorithm for finding a strong solution to the fair division problem.

The proof of this result is an elementary construction presented below for
constructing a strong solution for the case of non-atomic countably additive
charges.

##  3 Technical means

The main statement that we will use when constructing a solution for charges
is the Hahn-Jordan expansion of a charge $\psi$ on a set $M$ according to
which there is a measurable partition $M=A^{+}\cup A^{-}$ such that

  * •

$\psi(a)\geq 0$ for any set $a\subset A^{+}$;

  * •

$\psi(b)\leq 0$ for any set $b\subset A^{-}$.

In other words, $\psi=\mu^{+}-\mu^{-}$, where $\mu^{\pm}$ are countably
additive measures that are restrictions of the charge $\psi$ on the sets
$A^{\pm}$, respectively.

###### Definition 3.1

We say that a charge $\psi$ is _non-atomic_ if its corresponding measures
$\mu^{+}$ and $\mu^{-}$ are non-atomic.

Also, below we will need the following important statement, proved by A.A.
Lyapunov for the case of vector measures (see [6, 7]).

###### Theorem 3.1

For any countably additive nonatomic measure $\mu$ on $(M,\Sigma)$, the set of
values of the measure $\mu$ on the $\sigma$-algebra $\Sigma$ is convex.

###### Corollary 3.1

For any countably additive nonatomic measure $\mu$ on $(M,\Sigma)$, any
measurable set $A\subset M$ and any number $\delta\in[0,\mu(A)]$ there is a
measurable subset $B\subseteq A$ with $\mu(B)=\delta$.

The last statement (sometimes referred to as W. Sierpinski’s theorem; 1922)
states the existence of a set of any given measure. In the framework of the
approach under consideration, we assume that such a subset can be presented
explicitly.

##  4 Strong solution for the case of $r\in\\{2,3\\}$ measures

###### Definition 4.1

For the partition $\mathcal{F}=\\{F_{i}\\}_{i=1}^{r}$, we will say that the
set $A$ is associated to the $j$th participant if $F_{j}=A$.

Let us start with constructing a strong solution to the problem for non-atomic
countably additive measures in the simplest situation of two participants in
the division process, $r=2$ (the Cut-and-Choose algorithm).

By Corollary 3.1, $M$ has a subset $A_{1}$ of half the $\mu_{1}$-measure.
Then, for $A_{2}:=M\setminus A_{1}$, we have

$\mu_{1}(A_{2})=\mu_{1}(M\setminus
A_{1})=\mu_{1}(M)-\frac{1}{2}\mu_{1}(M)=\frac{1}{2}\mu_{1}(M).$

We obtain a partition of $M$ into two parts equal in $\mu_{1}$-measure. Then
if the 2nd participant is associated with a larger (or equal) part (denoted by
$A_{2}$) with respect to the measure $\mu_{2}$, and the remaining part
(denoted by $A_{1}$) is associated with the 1st, then we obtain a strong
solution to our problem. Indeed,

$\mu_{1}(A_{1})=\mu_{1}(A_{2})\Longrightarrow\mu_{1}(A_{1})\geq\mu_{1}(A_{2}),$
$\mu_{2}(A_{2})\geq\mu_{2}(A_{1}).$

At first glance, it seems that this pattern of sequential “halving” can easily
be extended to a larger number, say $r=3$, of participants. More precisely,
the 1st participant divides $M$ into $r$ parts that are equal from his point
of view, and the remaining participants order this partition, each in
accordance with his own measure. Next, all “disputed” elements of the
partition are divided between pairs of participants claiming them. In fact, a
large number of publications popularizing the problem of fair division reduce
to this algorithm. The division algorithm is finite and extremely simple, but
its detailed analysis shows that the result will only be a weak solution,
since it may turn out that a participant who does not participate in any of
the halvings will receive a share strictly less than one of other participants
(see, for example, [10]).

Below we will need the following technical statement.333Here and in what
follows, $\bigsqcup$ denotes the union of disjoint (non-intersecting) sets..

###### Lemma 4.1

Let $\mu$ be a countably additive functional,
$M=\bigsqcup_{i=1}^{\infty}H_{i}$, and let on each set $H_{i}$ there be a
strong solution $\mathcal{F}_{i}=\left\\{F_{j,i}\right\\}_{j=1}^{n}$. Then the
partition $\mathcal{F}=\left\\{F_{j}\right\\}_{j=1}^{n}$ of $M$ with
$F_{j}=\bigsqcup_{i=1}^{\infty}F_{j,i}$ is a strong solution on $M$.

Proof.  First, $\mathcal{F}$ is indeed a partition of $M$:

$\bigsqcup\limits_{j=1}^{n}F_{j}=\bigsqcup\limits_{j=1}^{n}\bigsqcup\limits_{i=1}^{\infty}F_{j,i}=\bigsqcup\limits_{i=1}^{\infty}\bigsqcup\limits_{j=1}^{n}F_{j,i}=\bigsqcup\limits_{i=1}^{\infty}H_{i}=M.$

Second, since $\mu_{j}(F_{j,i})\geq\mu_{j}(F_{k,i})$, $\forall i,j,k$, we have

$\mu_{j}(F_{j})=\mu_{j}\biggl{(}\,\bigsqcup\limits_{i=1}^{\infty}F_{j,i}\biggr{)}=\sum_{i=1}^{\infty}\mu_{j}(F_{j,i})\geq\sum_{i=1}^{\infty}\mu_{j}(F_{k,i})=\mu_{j}\biggl{(}\,\bigsqcup\limits_{i=1}^{\infty}F_{k,i}\biggr{)}=\mu_{j}(F_{k}).$

This means $\mathcal{F}$ is a strong solution. $\sqcup\\!\\!\\!\\!\sqcap$

Using this result, we will analyze the construction of a strong solution for
the case $r=3$.

Similar to the case $r=2$, we first divide $M$ into $r=3$ equal in measure
$\mu_{1}$ parts $A_{1}$, $A_{2}$ and $A_{3}$. To do this, by Corollary 3.1 we
can choose a subset $A_{1}$ in $M$ such
$\mu_{1}(A_{1})=\frac{1}{3}\mu_{1}(M)$, and since

$\mu_{1}(M\setminus
A_{1})=\mu_{1}(M)-\frac{1}{3}\mu_{1}(M)=\frac{2}{3}\mu_{1}(M),$

there is $A_{2}\subset M\setminus A_{1}$ such that
$\mu_{1}(A_{2})=\frac{1}{3}\mu_{1}(M)$.

Letting $A_{3}:=M\setminus(A_{1}\cup A_{2})$, we obtain

$\displaystyle\mu_{1}(A_{3})\\!\\!\\!$
$\displaystyle=\mu_{1}(M\setminus(A_{1}\cup A_{2}))=\mu_{1}(M\setminus
A_{1})-\mu_{1}(A_{2})$
$\displaystyle=\frac{2}{3}\cdot\mu_{1}(M)-\frac{1}{3}\cdot\mu_{1}(M)=\frac{1}{3}\cdot\mu_{1}(M).$

Let us order these sets with respect to the 2nd measure. Without loss of
generality, we assume $\mu_{2}(A_{1})\geq\mu_{2}(A_{2})\geq\mu_{2}(A_{3})$.
Since $\mu_{2}(A_{1})\geq\mu_{2}(A_{2})$, there exists $A^{\prime}\subset
A_{1}$, such that $\mu_{2}(A^{\prime})=\mu_{2}(A_{2})$. Therefore,
$\mu_{1}(A^{\prime})\leq\mu_{1}(A_{1})=\mu_{1}(A_{2})=\mu_{1}(A_{3})$.

We want to divide the sets $A^{\prime}$, $A_{2}$ and $A_{3}$ between the
participants. Let us associate with the third participant the largest of these
sets relative to his measure $\mu_{3}$. If this is $A^{\prime}$, then by
associating $A_{3}$ with the first participant and $A_{2}$ with the second, we
obtain a strong solution on $M^{\prime}:=A^{\prime}\cup A_{2}\cup A_{3}$.
Indeed,

$\mu_{1}(A^{\prime})\leq\mu_{1}(A_{2})=\mu_{1}(A_{3}),$
$\mu_{2}(A^{\prime})=\mu_{2}(A_{2})\geq\mu_{2}(A_{3}).$

If $\mu_{3}(A_{2})$ is the largest, then above the inequalities prove that if
we associate $A_{3}$ with the first participant and $A^{\prime}$ with the
second, then the resulting partition turns out to be a strong solution.

Finally, if $\mu_{3}(A_{3})$ is the largest, then to obtain a strong solution
it is necessary to associate $A_{2}$ with the first participant and
$A^{\prime}$ with the second.

Next, we will look for a strong solution on the remaining part
$M_{1}=M\setminus M^{\prime}$. Since $M^{\prime}=A^{\prime}\cup A_{2}\cup
A_{3}$, then $M_{1}\subset A_{1}$, which means
$\mu_{1}(M_{1})\leq\mu_{1}(A_{1})=\frac{1}{3}\mu_{1}(M)$. Note that the
enumeration of measures was absolutely arbitrary, which means that our
algorithm allows us to reduce any of the measures $\\{\mu_{i}\\}$ in the
remaining part by a factor of more than 3. Thus, any of these remainder
measures decreases exponentially. Therefore, in the limit, we get a partition
of $M$ into a countable number of parts on which there is a strong solution,
and the remainder is a set $M_{\infty}$ that is zero with respect to each
measure (each partition $M_{\infty}$ is a strong solution). Hence, by Lemma
4.1 we obtain a strong solution on $M$.

###### Definition 4.2

A sequence of sets $\\{A_{n}\\}$ is called _convergent_ if the upper limit of
this sequence
$\bigcap\limits_{n=1}^{\infty}\bigcup\limits_{k=n}^{\infty}A_{k}$ coincides
with the lower limit
$\bigcup\limits_{n=1}^{\infty}\bigcap\limits_{k=n}^{\infty}A_{k}$.

We will give a rigorous description of the construction of a sequence of sets
converging to a strong solution when describing the algorithm for constructing
a solution for the general case of $r\geq 3$ participants.

The above elementary algorithm for constructing a strong solution for the case
$r=3$ cannot be generalized to a larger number of participants. First of all,
the point is that in the process of redistributing the parts $A_{i}$ among the
participants, looping may occur. Therefore, retaining the inductive scheme of
the division process, we propose another somewhat more complex design (see the
next section).

It is also worth noting that even if we know how to solve the problem for
measures, there still remains an important situation where functionals are
charges. Let us discuss possible approaches to solving this problem. We start
with the situation where the charges under consideration are strictly
negative, that is, the $\\{-\mu_{i}\\}$ (taken with the opposite sign) are
countably additive measures.

At first glance it seems that if these measures are probabilistic444A measure
$\mu$ on $(M,\Sigma)$ is called probabilistic if $\mu(M)=1$. then the setting
under consideration is reduced to the previous one by replacing
$\\{\mu_{i}\\}$ with a set of positive functionals $\\{1-\mu_{i}\\}$. However,
the $1-\mu_{i}$ functionals are not additive, which means that they are not
measures.

Indeed, if the functional $\phi=1-\mu$ were additive, then we would have

$\displaystyle\phi(A\sqcup B)\\!\\!\\!$
$\displaystyle=\phi(A)+\phi(B)=(1-\mu(A))+(1-\mu(B))=2-\mu(A)-\mu(B),$
$\displaystyle\phi(A\sqcup B)\\!\\!\\!$ $\displaystyle=1-\mu(A\sqcup
B)=1-\mu(A)-\mu(B).$

We arrive at a contradiction:

$2-\mu(A)-\mu(B)=1-\mu(A)-\mu(B).$

Therefore, even for the case of strictly negative charges, a special
construction for the process of forming a strong solution is needed, which
will be described in Section 6.

##  5 Construction of a strong solution for the case of $r>3$ measures.

A special case of Theorem 2.1 is a situation where the functionals
$\left\\{\mu_{i}\right\\}_{i=1}^{r}$ are measures. Below we will formulate and
prove this statement.

###### Theorem 5.1

For any non-atomic countably additive measures
$\left\\{\mu_{i}\right\\}_{i=1}^{r}$ there is an explicit constructive
algorithm for constructing a strong solution to the fair division problem.

###### Definition 5.1

For a disjunctive555Sets $\left\\{A_{i}\right\\}_{i=1}^{r}$ are called
disjunctive if they are pairwise disjoint. set of sets
$\left\\{A_{i}\right\\}_{i=1}^{r}$ by the preferences of the $k$th
participant666As the reviewer pointed out to us, a similar construction of
preferences was described in the work [15], where some examples were analyzed
for 3 and 4 participants. we call an index $j$ such that
$\mu_{k}(A_{j})\geq\mu_{k}(A_{i})$ for any $i$.

###### Lemma 5.1

For a given set of measures $\left\\{\mu_{i}\right\\}_{i=1}^{r}$ and any index
$k$ from an arbitrary measurable set $S\subset\Sigma$ we can select its subset
$H\subset S$ of a “large” measure

$\mu_{k}(H)\geq\frac{1}{2^{r-1}}\mu_{k}(S),$

on which there exists a strong solution to the fair division problem.

Proof.  For convenience, we renumber the measures $\\{\mu_{i}\\}$ so that the
measure $\mu_{k}$ has index $1$.

At the first step, we divide $S$ into $2^{r-1}$ parts
$A_{1}^{1},\ldots,A_{2^{r-1}}^{1}$ equal in measure $\mu_{1}$. To do this, we
will sequentially consider subsets $A_{i}^{1}$ in $S$. First, by Corollary 3.1
there is a set $A_{1}^{1}$ such that
$\mu_{1}(A_{1}^{1})=\frac{1}{2^{r-1}}\mu_{1}(S)$.

Next, at the $t$-th step, in $S\setminus\bigcup_{i=1}^{t-1}A_{i}^{1}$ there is
such a subset $A_{i}^{1}$ that
$\mu_{1}(A_{t}^{1})=\frac{1}{2^{r-1}}\mu_{1}(S)$, since

$\mu_{1}(S\setminus\cup_{i=1}^{2^{r-1}-1}A_{i}^{1})=\frac{2^{r-1}-(2^{r-1}-1))}{2^{r-1}}\mu_{1}(S)=\frac{1}{2^{r-1}}\mu_{1}(S).$

Let us denote the sets obtained at the $t$-th step by
$A_{1}^{t},\ldots,A_{2^{r-1}}^{t}$. Each of our next steps (at which we will
select some preferences of the participants) will consist of changing a
current collection of sets. Let $K_{i}^{t}$ be the set of selected preferences
of the $i$th participant at the $t$th step. At the first step,
$K_{1}^{1}=\\{1,\ldots,2^{r-1}\\}$ (all the $A_{i}^{1}$ are his preferences),
while the remaining $K_{i}^{1}$ are set to be empty.

Next, at the $t$-th step, we do the following:

We arrange all sets $A_{1}^{t-1},\ldots,A_{2^{r-1}}^{t-1}$ according to
measure $\mu_{t}$ and consider the $2^{r-t}$ largest among them:

$\mu_{1}(A_{k_{1}}^{t-1})\geq\mu_{1}(A_{k_{2}}^{t-1})\geq\ldots\geq\mu_{1}(A_{k_{2^{r-t}}}^{t-1}).$

Then in each set $A_{k_{i}}^{t-1}$ there is a subset

$A_{k_{i}}^{\prime}\subset
A_{k_{i}}^{t-1}:\>\mu_{t}(A_{k_{i}}^{\prime})=\mu_{t}(A_{k_{2^{r-t}}}^{t-1}).$

The new collection $A_{i}^{t}$ is the collection $A_{i}^{t-1}$ in which
elements $A_{k_{i}}^{t-1}$ are replaced by $A_{k_{i}}^{\prime}$. The set of
new selected preferences $K_{i}^{t}$ is such that
$K_{t}^{t}=\\{k_{1},\ldots,k_{2^{r-t}}\\}$, and
$K_{i}^{t}=K_{i}^{t-1}\setminus K_{t}^{t}$ for $i\neq t$ (in particular,
$K_{i}^{t}=\emptyset$ for $i>t$).

Let us verify by induction on $t$ that the following properties are satisfied
at each step:

  1. 1.

Sets $K_{i}^{t}$ are disjunctive.

  2. 2.

$|K_{j}^{t}|\geq 2^{r-t}$ for $j\leq t$.

  3. 3.

For any $j$ and any $k\in K_{j}^{t}$ it is true that $A_{k}^{t}$ is the
preference of the $j$th participant.

Let us check the induction base:

  1. 1.

$K_{1}^{1}=\\{1,\ldots,2^{r-1}\\}$, and the remaining $K_{i}^{1}$ are empty,
which means they are disjunctive.

  2. 2.

For $j=1$, we have $|K_{j}^{1}|=|K_{1}^{1}|=2^{r-1}$.

  3. 3.

For $j=1$, for any $k$ it is true that $A_{k}^{1}$ is the preference of the
$1$th participant by the construction. For $j\neq 1$, we have
$K_{j}^{1}=\emptyset$.

Proof of the induction step:

  1. 1.

For $j>t$, the sets $K_{j}^{t}$ are empty, which means no set can intersect
with them. For $s,k<t$, the sets $K_{s}^{t}=K_{s}^{t-1}\setminus K_{t}^{t}$
and $K_{k}^{t}=K_{k}^{t-1}\setminus K_{t}^{t}$ are disjoint, since
$K_{s}^{t-1}$ and $K_{k}^{t-1}$ were disjoint by the induction hypothesis. For
$j=t$ and $s<t$, the sets $K_{t}^{t}$ and $K_{s}^{t}=K_{s}^{t-1}\setminus
K_{t}^{t}$ are disjoint. This means that $K_{i}^{t}$ are disjoint as well.

  2. 2.

$|K_{t}^{t}|\geq 2^{r-t}$, since $|K_{t}^{t}|=2^{r-t}$, and for $j\leq t-1$

$|K_{j}^{t}|=|K_{j}^{t-1}\setminus K_{t}^{t}|\geq|K_{j}^{t-1}|-|K_{t}^{t}|\geq
2^{r-(t-1)}-2^{r-t}=2^{r-t}$

(by the induction hypothesis $|K_{j}^{t-1}|\geq 2^{r-(t-1)}$ for $j\leq t-1$).

  3. 3.

For any $j\leq t-1$, we have $K_{j}^{t}=K_{j}^{t-1}\setminus K_{t}^{t}$. By
the induction hypothesis, the $A_{i}^{t-1}$ with indices lying in
$K_{j}^{t-1}$ were the preferences of the $j$-th participant. The $t$th step
consists in changing the sets with indices lying in $K_{t}^{t}$; each of them
is replaced by some subset and hence its measure $\mu_{j}$ is reduced. Thus,
the sets with indices from $K_{j}^{t}=K_{j}^{t-1}\setminus K_{t}^{t}$ remain
to be the preferences of the $j$th participant. For $k\in K_{t}^{t}$, we have
$\mu_{t}(A_{k}^{t})=\mu_{t}(A_{k_{2^{r-1}}}^{t-1})$; hence, since
$\mu_{t}(A_{k_{2^{r-1}}}^{t-1})$ is by construction the largest of the values
of $\mu_{t}(A_{i}^{t})$, then $A_{k}^{t}$ is the preference of the $j$th
participant.

As a result, at the $r$th step we have $|K_{i}^{r}|\geq 2^{r-r}=1$ for any
$i$; therefore, each participant has exactly one preference, and these
preferences do not coincide with each other due to the disjunctiveness of the
$\\{K_{i}^{r}\\}$. Let us associate to the $i$th participant his preference
$F_{i}$.

In this case, the first paeticipant is associated with a set $F_{1}$, such
that $\mu_{1}(F_{1})=\frac{1}{2^{r-1}}\mu_{1}(S)$, since by the construction
we remove from the selected preferences of the 1st participant those that we
have already changed.

This means that the set $H=\sqcup_{i=1}^{r}F_{i}$ is the desired one, since
$\mu_{1}(H)\geq\mu_{1}(F_{1})=\frac{1}{2^{r-1}}\mu_{1}(S)$, and also
$\mu_{i}(F_{i})\geq\mu_{i}(F_{j})$ for any $i$ and $j$, since $F_{i}$ is the
preference of the $i$th participant. $\sqcup\\!\\!\\!\\!\sqcap$

###### Definition 5.2

The set $H$ obtained in Lemma 5.1 will be called the _$\mu_{k}$ -satisfying
subset_ of $S$.

Let us construct a new sequence of sets $\\{H_{i}\\}$ according to the
following rules:

  * •

$H_{1}$ is a $\mu_{1}$-satisfying subset $M=M_{0}$.

  * •

If $k$ mod $r\neq 0$, then $t=$ $k$ mod $r$; otherwise $t=r$

  * •

$H_{k}$ is the $\mu_{t}$-satisfying subset of
$M\setminus\cup_{i=1}^{k-1}H_{i}$.

  * •

$M_{s}=M\setminus\cup_{i=1}^{sr}H_{i}$.

Define also the averaged measure
$\mu(A):=\frac{1}{r}\sum_{i=1}^{r}\mu_{i}(A)$.

In other words, for each measure we in turn select sets that are not less than
$1/2^{r-1}$ of the current measure of the remainder
$M\setminus\cup_{i=1}^{k-1}H_{i}$. Indeed,

$\mu_{t}(H_{k})\geq
2^{-(r-1)}\mu_{t}\Biggl{(}M\setminus\bigcup_{i=1}^{k-1}H_{i}\Biggr{)}.$

###### Lemma 5.2

We have $\mu(M_{s})\leq\frac{2^{r-1}-1}{2^{r-1}}\mu(M_{s-1})$.

Proof.  For any $j$ we have

$\displaystyle\mu_{j}(\cup_{i=(s-1)r+1}^{sr}H_{i})\\!\\!\\!$
$\displaystyle=\mu_{j}(H_{(s-1)r+j})+\mu_{j}(\cup_{i=(s-1)r+1}^{sr}H_{i}\setminus
H_{(s-1)r+j})$ $\displaystyle\geq
2^{-(r-1)}\cdot\mu_{j}(M\setminus\cup_{i=1}^{(s-1)r+j-1}H_{i})+\mu_{j}(\cup_{i=(s-1)r+1}^{sr}H_{i}\setminus
H_{(s-1)r+j})$ $\displaystyle\geq
2^{-(r-1)}\cdot(\mu_{j}(M_{s-1}\setminus\cup_{i=(s-1)r+1}^{(s-1)r+j-1}H_{i})+\mu_{j}(\cup_{i=(s-1)r+1}^{sr}H_{i}\setminus
H_{(s-1)r+j}))$ $\displaystyle\geq
2^{-(r-1)}\cdot\mu_{j}((M_{s-1}\setminus\cup_{i=(s-1)r+1}^{(s-1)r+j-1}H_{i})\cup(\cup_{i=(s-1)r+1}^{sr}H_{i}\setminus
H_{(s-1)r+j}))$
$\displaystyle=2^{-(r-1)}\cdot\mu_{j}(M_{s-1}\cup(\cup_{i=(s-1)r+j+1}^{sr}H_{i})))$
$\displaystyle\geq 2^{-(r-1)}\cdot\mu_{j}(M_{s-1}).$

Hence,

$\displaystyle\mu_{j}(M_{s})\\!\\!\\!$
$\displaystyle=\mu_{j}(M_{s-1}\setminus\cup_{i=(s-1)r+1}^{sr}H_{i})$
$\displaystyle=\mu_{j}(M_{s-1})-\mu_{j}(\cup_{i=(s-1)r+1}^{sr}H_{i})$
$\displaystyle\leq\frac{2^{r-1}-1}{2^{r-1}}\cdot\mu_{j}(M_{s-1}).$

Thus,

$\sum_{j=1}^{r}\mu_{j}(M_{s})\leq\frac{2^{r-1}-1}{2^{r-1}}\sum_{j=1}^{r}\mu_{j}(M_{s-1}).$

Finally we obtain $\mu(M_{s})\leq\frac{2^{r-1}-1}{2^{r-1}}\mu(M_{s-1})$.
$\sqcup\\!\\!\\!\\!\sqcap$

###### Corollary 5.3

We have $\mu(M_{s})\leq(\frac{2^{r-1}-1}{2^{r-1}})^{s}\mu(M)$.

###### Corollary 5.4

Let $M_{\infty}=M\setminus\cup_{i=1}^{\infty}H_{i}$, then
$\mu_{j}(M_{\infty})=0$ for every $j$.

Proof.  Let us tend the parameter $s$ in Corollary 5.3 to infinity. Since
$\frac{2^{r-1}-1}{2^{r-1}}<1$, we have $\mu(M_{\infty})\leq 0$, and from the
non-negativity of the measure $\mu$ it follows that $\mu(M_{\infty})=0$. Since
$\mu(M_{\infty})=\Sigma_{j=1}^{n}\mu_{j}(M_{\infty})$, we obtain the desired
statement. $\sqcup\\!\\!\\!\\!\sqcap$

Thus, we represented the set $M$ as follows:
$M=\bigsqcup_{i=0}^{\infty}H_{i}$, where on each $H_{i}$ there is a strong
solution $\mathcal{F}_{i}=\\{F_{j,i}\\}_{j=1}^{n}$. (On $M_{\infty}$ there is
a strong solution for which the 1st measure is associated with $M_{\infty}$,
and the others with an empty set, so we will assume that $M_{\infty}=H_{0}$).
This means that by Lemma 4.1 there exists a strong solution on $M$.

For each measure $\mu_{j}$, consider the sequence of sets
$N_{j,k}=\bigsqcup_{i=0}^{kr}F_{j,i}$.

###### Lemma 5.5

The sequence of sets $N_{j,k}$ converges as $k\to\infty$, and the limit of
$N_{j,k}$ is equal to $\bigcup_{k=1}^{\infty}N_{j,k}=:N_{j}^{\infty}$.

Proof.  Since $N_{j,k}\subset N_{j,k+1}$, we have

$\bigcup_{k=n}^{\infty}N_{j,k}=\bigcup_{k=1}^{\infty}N_{j,k}=N_{j}^{\infty}.$

This means that the upper limit of $N_{j,k}$ satisfy the relation

$\bigcap_{n=1}^{\infty}\bigcup_{k=n}^{\infty}N_{j,k}=\bigcap_{n=1}^{\infty}N_{j}^{\infty}=N_{j}^{\infty}.$

On the other hand, $\bigcap_{k=n}^{\infty}N_{j,k}=N_{j,n}$. Therefore, the
lower limit is

$\bigcup_{n=1}^{\infty}\bigcap_{k=n}^{\infty}N_{j,k}=\bigcup_{n=1}^{\infty}N_{j,n}=N_{j}^{\infty},$

###### Lemma 5.6

$\\{N_{j}^{\infty}\\}_{j=1}^{r}$ is a strong solution on $M$.

Proof.  Since the sets $F_{j,i}$ do not intersect for different $j$, then
$N_{j}^{\infty}\bigcap N_{l}^{\infty}=\emptyset$ for $j\neq l$.

On the other hand,

$\bigcup_{j=1}^{r}N_{j}^{\infty}=\bigcup_{j=1}^{r}\bigcup_{k=1}^{\infty}N_{j,k}=\bigcup_{j=1}^{r}\bigcup_{k=1}^{\infty}\bigsqcup_{i=0}^{kr}F_{j,i}=\bigcup_{j=1}^{r}\bigcup_{i=0}^{\infty}F_{j,i}=\bigcup_{i=0}^{\infty}H_{i}=M.$

Therefore $M=\bigsqcup_{j=1}^{r}N_{j}^{\infty}$.

Since by Lemma 4.1 we have $N_{j}^{\infty}=\bigcup_{k=1}^{\infty}N_{j,k}$, we
conclude that $\mu_{j}(N_{j}^{\infty})\geq\mu_{j}(N_{l}^{\infty})$ for all
$j,l$, which completes the proof. $\sqcup\\!\\!\\!\\!\sqcap$

##  6 Construction of a strong solution for charges

Now we pass to the case of non-atomic countably additive charges
$\\{\psi_{i}\\}_{i=1}^{r}$.

For each charge $\psi_{i}$, consider the corresponding sets $A^{+}_{i}$ and
$A^{-}_{i}$ from the Hahn-Jordan expansion. Then intersections of sets of sets
$\\{A^{+}_{i},A^{-}_{i}\\}$ split the entire set $M$ into $2^{r}$ parts, the
restriction of $\psi_{i}$ to each of these parts is either a measure or a
minus measure.

Therefore, according to Lemma 4.1, it suffices to find out how to solve the
problem on each of these $2^{r}$ parts. According to the previous section, the
problem has already been solved for those parts where all restrictions of the
charges are positive.

Call the resulting parts by $X_{1},\ldots,X_{2^{r}}$ and consider one of these
parts, which we will denote for simplicity by $X$.

###### Definition 6.1

Denote by $I^{+}$ ($I^{-}$) the set of indices $i$ for which the charge
restriction $\psi_{i}$ to $X$ is a measure (minus measure).

There are 2 possible cases: $I^{+}\neq\emptyset$ and $I^{+}=\emptyset$. Let us
first consider the first of them.

###### Lemma 6.1

If $I^{+}\neq\emptyset$, then $X$ has a strong solution.

Proof.  By Theorem 5.1, on the set $X$ there is a strong solution
$\mathcal{F^{+}}:=\\{F_{i}\\}_{i\in I^{+}}$ for measures $\\{\psi_{i}\\}_{i\in
I^{+}}$. Let us extend the collection $\mathcal{F^{+}}$ to a collection
$\mathcal{F}:=\\{F_{i}\\}_{i=1}^{r}$ by the sets $F_{i}=\emptyset$ for $i\in
I^{-}$.

Then for $i\in I^{-}$ and any $j$ we have
$\psi_{i}(F_{i})=\psi_{i}(\emptyset)=0\geq\psi_{i}(F_{j})$, since the $i$-th
signed measure is negative on the considered set.

If $i\in I^{+}$ and $j\in I^{+}$, then $\psi_{i}(F_{i})\geq\psi_{i}(F_{j})$,
since $\mathcal{F^{+}}$ is a strong solution for positive measures. If $i\in
I^{+}$ and $j\in I^{-}$, then $\psi_{i}(F_{i})\geq
0=\psi_{i}(\emptyset)=\psi_{i}(F_{j})$. $\sqcup\\!\\!\\!\\!\sqcap$

It remains to construct a strong solution on such a set that the restriction
of any considered charge to which is a minus measure. To do this, we notice
that the problem of finding a strong solution for minus measures is equivalent
to finding a partition as follows.

###### Definition 6.2

In the fair division problem with a set of measures $\\{\mu_{i}\\}_{i=1}^{r}$,
we call a partition $\mathcal{F}$ a _gentleman’s_ solution if
$\mu_{i}(F_{i})\leq\ mu_{i}(F_{j})$ for any $i,j$.

In the literature on economics, this setting is often called “chore division”.
It is not difficult to understand that from the point of view of solving the
problem of fair division with a set of strictly negative charges
$\\{\psi_{i}=-\mu_{i}\\}_{i=1}^{r}$ these two settings are equivalent.

Similar to Lemma 4.1, the following its variation can be formulated an proved.

###### Lemma 6.2

Let $\mu$ be a countably additive functional, $M=\sqcup_{i=1}^{\infty}H_{i}$
and assume that on each set $H_{i}$ there is a gentleman’s solution
$\mathcal{F}_{i}=\\{F_{j,i}\\}_{j=1}^{n}$. Then the partition
$\mathcal{F}=\\{F_{j}\\}_{j=1}^{n}$ with $F_{j}=\sqcup_{i=1}^{\infty}F_{j,i}$
is a strong solution on $M$.

Proof.  Since $\mu_{j}(F_{j,i})\leq\mu_{j}(F_{k,i})$ for all $i,j,k$, then

$\mu_{j}(F_{j})=\mu_{j}\biggl{(}\,\bigsqcup\limits_{i=1}^{\infty}F_{j,i}\biggr{)}=\sum_{i=1}^{\infty}\mu_{j}(F_{j,i})\leq\sum_{i=1}^{\infty}\mu_{j}(F_{k,i})=\mu_{j}\biggl{(}\,\bigsqcup\limits_{i=1}^{\infty}F_{k,i}\biggr{)}=\mu_{j}(F_{k}).$

$\sqcup\\!\\!\\!\\!\sqcap$

Let a set $S\in\Sigma$ satisfy the condition $\prod_{i=1}^{r}\mu_{i}(S)\neq
0$.

###### Lemma 6.3

There are sets $R^{1},\ldots,R^{r}$, $\sqcup_{i}R^{i}\subset S$ and a
renumbering of the measures $\mu_{l_{1}},\ldots,\mu_{l_{r}}$ such that for
each $k$ we have $\mu_{l_{k}}(R^{k})=\frac{1}{r}\mu_{l_{k}}(S)$, and for $j>k$
we have $\mu_{l_{j}}(R^{k})\leq\frac{1}{r}\mu_{l_{k}}(S)$.

Proof.  We will successively construct this collection of sets. At the 1st
step, we consider $R^{1}_{1}\subset S$ such that
$\mu_{1}(R^{1}_{1})=\frac{1}{r}\mu_{1}(S)$. Further, if at the $t$th step
$\mu_{t}(R_{t-1}^{1})>\frac{1}{r}\mu_{t}(S)$, then $R_{t}^{1}$ is such subset
$R_{t-1}^{1}$ that $\mu_{t}(R_{t}^{1})=\frac{1}{r}\mu_{t}(S)$; otherwise,
$R_{t}^{1}=R_{t-1}^{1}$.

At the end of the $r$-th step we obtain the set $R^{1}=R_{r}^{1}$. Let $l_{1}$
denote the step number after which we no longer changed $R_{i}^{1}$. Then, by
the construction, $\mu_{l_{1}}$ and $R^{1}$ satisfy the following conditions:

$\mu_{l_{1}}(R^{1})=\frac{1}{r}\mu_{l_{1}}(S),\qquad\mu_{j}(R^{1})\leq\frac{1}{r}\mu_{j}(S)~{}~{}j\neq
l_{1}.$

.

Now at the $k$th step, in a similar way we will select $R^{k}$ and a measure
$\mu_{l_{k}}$ from the set $S\setminus\sqcup_{i=1}^{k-1}R^{i}$ for all
measures except $\mu_{l_{1}},\ldots,\mu_{l_{k-1}}$, such that
$\mu_{l_{k}}(R^{k})=\frac{1}{r}\mu_{l_{k}}(S)$, and
$\mu_{j}(R^{k})\leq\frac{1}{r}\mu_{j}(S)$ for all
$j\notin\\{l_{1},\ldots,l_{k}\\}$. We only need to check that we can do the
1st stage of the $k$-th step, that is, with respect to some measure $\mu_{j}$
for $j\notin\\{l_{1},\ldots,l_{k-1}\\}$ remainder measure is not less than
$\frac{1}{r}\mu_{j}(S)$.

By the construction, $\mu_{j}(R^{i})\leq\frac{1}{r}\mu_{j}(S)$ for any
$j\notin\\{l_{1},\ldots,l_{k-1}\\}$. Hence,

$\mu_{j}(S\setminus\bigsqcup_{i=1}^{k-1}R^{i})=\mu_{j}(S)-\sum_{i=1}^{k-1}\mu_{j}(R^{i})\geq\mu_{j}(S)\left(1-\frac{k-1}{r}\right).$

Therefore, for $k\leq r$ we can take this step, and as a result we obtain the
desired ordering of the measures $\mu_{l_{i}}$ and the set $R^{i}$.
$\sqcup\\!\\!\\!\\!\sqcap$

###### Definition 6.3

In the case of a gentleman’s solution for a disjunctive collection of sets
$\\{A_{i}\\}_{i=1}^{r}$ the preference of the $k$th participant is an index
$j$ such that $\mu_{k}(A_{j})\leq\mu_{k}(A_{i})~{}~{}\forall i$.

###### Lemma 6.4

For a given set of measures $\\{\mu_{i}\\}_{i=1}^{r}$ from any set $S\subset
M$ one can select a subset $H$ such that if $\\{\mu_{l_{i}}\\}_{i=1}^{r}$ is
the ordering of measures for $S$ from Lemma 6.3, then

$\mu_{l_{1}}(H)\geq\frac{1}{2^{r-1}}\mu_{l_{1}}(S),$

and $H$ has a gentleman’s solution.

Proof.  To simplify the notation, we will enumerate the measures $\mu_{i}$,
rather than $\mu_{l_{i}}$, remembering that the enumeration is not arbitrary,
since it depends on the set that we are dividing.

First, we divide $R^{1}$ into $2^{r-1}$ parts equal in measure to $\mu_{1}$.
Let us denote the resulting partition elements at the $t$-th step by
$A_{1}^{t},\ldots,A_{2^{r-1}}^{t}$, and denote the selected preferences of the
$i$-th participant at the $t$-th step sets by $K_{i}^{t}$. At the first step
we set $K_{1}^{1}:=\\{1,\ldots,2^{r-1}\\}$ (all $A_{i}^{1}$ are his
preferences), and leave the remaining $K_{i}^{1}$ empty.

Next, at the $t$-th step, we do the following.

Order all sets $A_{1}^{t-1},\ldots,A_{2^{r-1}}^{t-1}$ according to the measure
$\mu_{t}$ and consider $2^{r-t}$ smallest sets among them:

$\mu_{1}(A_{k_{1}}^{t-1})\leq\mu_{1}(A_{k_{2}}^{t-1})\leq\ldots\leq\mu_{1}(A_{k_{2^{r-t}}}^{t-1}).$

We want to separate from $R^{t}$ such a collection of sets
$C_{1}^{t-1},\ldots,C_{2^{r-t}}^{t-1}$ that $\forall i$

$\mu_{t}(C_{i}^{t-1})=\mu_{t}(A_{k_{2^{r-t}}}^{t-1})-\mu_{t}(A_{k_{i}}^{t-1}).$

Then the new set $A_{i}^{t}$ is the “adjusted” set $A_{i}^{t-1}$ in which the
elements $A_{k_{i}}^{t-1}$ are replaced with $A_{k_{i}}^{t-1}\bigsqcup
C_{i}^{t-1}$. The set of new selected preferences $K_{i}^{t}$ is such that
$K_{t}^{t}=\\{k_{1},\ldots,k_{2^{r+1-t}}\\}$ and
$K_{i}^{t}=K_{i}^{t-1}\setminus K_{t}^{t}$ for $i\neq t$ (in particular
$K_{i}^{t}=\emptyset$ for $i>t$).

Note that we can make this step only if

$\sum_{i=1}^{2^{r-t}}\mu_{t}(C_{i}^{t-1})\leq\mu_{t}(R^{t}).$

Further,

$\displaystyle\sum_{i=1}^{2^{r-t}}\mu_{t}(C_{i}^{t-1})\\!\\!\\!$
$\displaystyle=\sum_{i=1}^{2^{r-t}}(\mu_{t}(A_{k_{2^{r-t}}}^{t-1})-\mu_{t}(A_{k_{i}}^{t-1}))\leq
2^{r-t}\cdot\mu_{t}(A_{k_{2^{r-t}}}^{t-1})$
$\displaystyle\leq\frac{2^{r-t}}{2^{r-1}-2^{r-t}}\cdot\sum_{i=2^{r-t}+1}^{2^{r-1}}\mu_{t}(A_{k_{i}}^{t-1}).$

Since all sets $A_{i}^{t-1}$ are contained in the union
$R^{1},\ldots,R^{t-1}$, then

$\mu_{t}\Biggl{(}\,\bigsqcup\limits_{i=1}^{2^{r-1}}A_{i}^{t-1}\Biggr{)}\leq\sum_{j=1}^{t-1}\mu_{t}(R^{j})\leq\frac{t-1}{r}\mu_{t}(S).$

The last inequality follows from the construction of $R^{i}$.

Thus,

$\sum_{i=2^{r-t}+1}^{2^{r-1}}\mu_{t}\bigl{(}A_{k_{i}}^{t-1}\bigr{)}\leq\mu_{t}\Biggl{(}\,\bigsqcup\limits_{i=1}^{2^{r-1}}A_{i}^{t-1}\Biggr{)}\leq\frac{t-1}{r}\mu_{t}(S).$

Since $\frac{t-1}{2^{t-1}-1}\leq 1$ for $t\geq 2$, then

$\displaystyle\frac{2^{r-t}}{2^{r-1}-2^{r-t}}\sum_{i=2^{r-t}+1}^{2^{r-1}}\mu_{t}(A_{k_{i}}^{t-1})\\!\\!\\!$
$\displaystyle\leq\frac{2^{r-t}}{2^{r-1}-2^{r-t}}\cdot\frac{t-1}{r}\cdot\mu_{t}(S)$
$\displaystyle=\frac{t-1}{(2^{t-1}-1)r}\cdot\mu_{t}(S)\leq\frac{1}{r}\mu_{t}(S)=\mu_{t}(R^{t}).$

Now, similarly to the previous considered situation, we prove by induction on
$t$ the following statements:

  1. 1.

The sets $K_{i}^{t}$ are disjunctive.

  2. 2.

$|K_{j}^{t}|\geq 2^{r-t}$ for $j\leq t$.

And to prove the 3rd point we need the following reasoning.

  3. 3.

For any $j$ and $k\in K_{j}^{t}$ it is true that $A_{k}^{t}$ is a preference
for the $j$-th measure. It is necessary to note that changing the parts is
made by combining them, which means that the parts do not decrease with
respect to any measure and therefore cannot become preferences if they were
not originally. Moreover, by the construction, the set $K_{t}^{t}$ consists
only of preferences of the $t$th measure.

At the $r$th step, each participant will have at least $2^{r-r}=1$ different
preferences. Let us associate each participant with his preference $F_{i}$.
The first participant is associated with a set $F_{1}$ such that
$\mu_{1}(F_{1})=1/2^{r-1}\mu_{1}(R^{1})$, since by the construction we remove
from the selected preferences of the 1st participant those that we have
changed.

It should also be noted that $\mu_{1}(F_{1})\leq\mu_{1}(F_{j})$ for any $j$,
since the original sets $A_{i}^{1}$ can only be enlarged. Therefore,

$\displaystyle\mu_{1}(H)\\!\\!\\!$
$\displaystyle=\mu_{1}(\sqcup_{j=1}^{r}F_{j})=\sum_{j=1}^{r}\mu_{1}(F_{j})\geq\sum_{j=1}^{r}\mu_{1}(F_{1})$
$\displaystyle=r\cdot\mu_{1}(F_{1})=r\cdot 1/2^{r-1}\cdot\mu_{1}(R^{1})$
$\displaystyle=r\cdot
1/2^{r-1}\cdot\frac{1}{r}\cdot\mu_{1}(S)=2^{-(r-1)}\cdot\mu_{1}(S).$

Thus, the partition $H=\bigsqcup_{i=1}^{r}F_{i}$ satisfies all the required
conditions. $\sqcup\\!\\!\\!\\!\sqcap$

###### Theorem 6.1

For non-atomic countably additive measures $\\{\mu_{i}\\}_{i=1}^{r}$ there
exists a gentleman’s division.

Proof.  Let us prove by induction on the number of participants that there is
a gentleman’s division of $M$.

Let us check the induction base $r=1$. For the 1st participant there is a
single partition with $F_{1}=M$ and it is obviously gentlemanly.

Let us check the induction step.

###### Definition 6.4

We call the set $H$ obtained in Lemma 6.4 the $\mu_{l_{1}}$-satisfying subset
of $S$.

Let us define by induction the following sequence of sets $H_{i}$:

  * •

$H_{1}$ is the $\mu_{h_{1}}$-satisfying subset of $M=M_{0}$;

  * •

$H_{k}$ is the $\mu_{h_{k}}$-satisfying subset of
$M\setminus\bigcup_{i=1}^{k-1}H_{i}$;

  * •

$M_{\infty}=M\setminus\bigsqcup_{i=1}^{\infty}H_{i}$.

All indices $h_{1},h_{2},\ldots$ belong to the finite set $\\{1,\ldots,r\\}$.
This means that one of them is repeated infinitely many times; denote it by
$\ell$.

###### Lemma 6.5

Let $k_{1}<k_{2}<\ldots$ be the set of all indices $i$ for which $h_{i}=\ell$.
Then

$\mu_{\ell}\Biggl{(}M\setminus\bigsqcup\limits_{i=1}^{k_{i+1}}H_{i}\Biggr{)}\leq\left(\frac{2^{r-1}-1}{2^{r-1}}\right)^{i+1}\mu_{\ell}(M).$

Proof.  We have Proof.

$\displaystyle\mu_{\ell}(\sqcup_{i=k_{i}+1}^{k_{i+1}}H_{i})\\!\\!\\!$
$\displaystyle=\mu_{\ell}(H_{k_{i+1}})+\mu_{\ell}(\cup_{i=k_{i}+1}^{k_{i+1}}H_{i}\setminus
H_{k_{i+1}})$ $\displaystyle\geq
2^{-(r-1)}\cdot\mu_{\ell}(M\setminus\cup_{i=1}^{{k_{i+1}}-1}H_{i})+\mu_{\ell}(\cup_{i=k_{i}+1}^{k_{i+1}}H_{i}\setminus
H_{k_{i+1}})$ $\displaystyle\geq
2^{-(r-1)}\cdot(\mu_{\ell}(M\setminus\cup_{i=1}^{{k_{i+1}}-1}H_{i})+\mu_{\ell}(\cup_{i=k_{i}+1}^{k_{i+1}}H_{i}\setminus
H_{k_{i+1}}))$ $\displaystyle\geq
2^{-(r-1)}\cdot\mu_{\ell}(M\setminus\sqcup_{1}^{k_{i}}H_{i}).$

Hence,

$\mu_{\ell}\Biggl{(}M\setminus\bigsqcup\limits_{i=1}^{k_{i+1}}H_{i}\Biggr{)}\leq\frac{2^{r-1}-1}{2^{r-1}}\mu_{\ell}\Biggl{(}M\setminus\bigsqcup\limits_{i=1}^{k_{i}}H_{i}\Biggr{)}.$

Finally we obtain

$\mu_{\ell}\Biggl{(}M\setminus\bigsqcup\limits_{i=1}^{k_{i+1}}H_{i}\Biggr{)}\leq\left(\frac{2^{r-1}-1}{2^{r-1}}\right)^{i+1}\mu_{\ell}(M).$

$\sqcup\\!\\!\\!\\!\sqcap$

###### Corollary 6.6

Letting the number of indices $i$ considered in Lemma 6.5 tend to infinity, we
obtain $\mu_{\ell}(M_{\infty})=0$.

By the induction hypothesis, for measures with indices $i\in\\{1,2\ldots
r\\}\setminus{\ell}$ there is a gentleman’s solution
$\mathcal{F}^{*}=\\{F_{i}\\}$ on $M_{\infty}$. Then, for $F_{\ell}=\emptyset$,
the partition $\mathcal{F}:=\\{F_{i}\\}_{i=1}^{r}$ of $M_{\infty}$ is a
gentleman’s solution for all $r$ participants.

Indeed, since $\mathcal{F}^{*}$ is a gentleman’s solution for measures with
indices $i\in\\{1,2\ldots r\\}\setminus{\ell}$, then we only need to check the
inequalities containing the conditions associated with the $\ell$th
participant:

$\mu_{i}(F_{i})\geq 0=\mu_{i}(\emptyset)=\mu_{i}(F_{\ell}),$
$\mu_{\ell}(F_{\ell})=\mu_{\ell}(\emptyset)=0=\mu_{\ell}(M_{\infty})\geq\mu_{\ell}(F_{i}).$

We have obtained the representation
$M=M_{\infty}\sqcup\Bigl{(}\bigsqcup\limits_{i=1}^{\infty}H_{i}\Bigr{)}$, and
at each element of the partition there is a gentleman’s solution. This means
that the required partition exists by Lemma 6.2. $\sqcup\\!\\!\\!\\!\sqcap$

At the request of an anonymous reviewer to present a simple, understandable
example, in low dimension, for two participants, we will analyze this simplest
situation in detail. Note, firstly, that neither the dimension, nor geometry
in the setting under consideration have any significance, and secondly, for
two participants, a strong solution for charges can be obtained by the Cut-
and-Choose method. However, perhaps a significantly more complex construction
of the formal implementation of the algorithm described in Section 6 for $r=2$
will help to understand the general situation for $r>2$.

Given charges $\psi_{1},\psi_{2}$, we construct two partitions of the space

$M=M_{1}^{+}\sqcup M_{1}^{-}=M_{2}^{+}\sqcup M_{2}^{-},$

corresponding to positive and negative parts of the charges
$\psi_{1},\psi_{2}$. We set

$M^{++}:=M_{1}^{+}\cap M_{2}^{+},~{}M^{+-}:=M_{1}^{+}\cap
M_{2}^{-},~{}M^{-+}:=M_{1}^{-}\cap M_{2}^{+},~{}M^{--}:=M_{1}^{-}\cap
M_{2}^{-}.$

Note that $\\{M^{++},M^{+-},M^{-+},M^{--}\\}$ is again a partition of $M$.
According to the construction of a strong solution for charges, the parts
$M^{++}$ and $M^{--}$ are divided between the participants “in half”, while
the part $M^{+-}$ is given entirely to the 1st participant, and the part
$M^{-+}$ is given entirely to the 2nd participant.

This completes the process of constructing the strong solution for 2
participants, since the need for an iterative scheme arises only for $r>2$.

##  7 Conclusion

In this paper, we have proposed a simple exponentially converging algorithm
for constructing a strong solution to the fair division problem for the case
of individual criteria described by non-atomic charges. As was already noted
in the Introduction, there are publications [11, 12] that describe finite
algorithms for solving this problem for the cases of strictly positive and
strictly negative measures, respectively (albeit with an astronomical estimate
of the number of necessary operations). Unfortunately, these publications are
not written at a completely mathematical level of rigor (the proofs given in
them are rather detailed descriptions of the program flow charts), and the
algorithms themselves are so complex that checking the adequacy of their
operation seems difficult. Apparently, something like a computer-assisted roof
is needed here. In any case, we were unable to check them “manually” even for
a small number of participants. However, if these algorithms really work, then
their combination with the scheme described in Section 6 for dividing the
space into positive and negative parts of the charges and working with their
combinations lead to a finite algorithm for constructing a strong solution.

Note that despite the seeming similarity of the fair division problem under
consideration with the better known setting of multicriteria Pareto
optimization, they are fundamentally different. Pareto optimality is
understood as a state of the system in which not a single criteria can be
improved without deteriorating any other criteria. One can easily see that any
Pareto optimal state is a strong solution to the fair division problem, but
the latter setting is much more flexible and allows to explore a wider class
of systems.

## References

  * [1] Brams, S.J., Jones, M.A., and Klamler, C., Better Ways to Cut a Cake, _Notices Amer. Math. Soc._ , 2006, vol. 53, no. 11, pp. 1314–1321.
  * [2] Moulin, H., _Fair Division and Collective Welfare_ , Cambridge: MIT Press, 2003.
  * [3] Brams, S.J., _Mathematics and Democracy: Designing Better Voting and Fair Division Procedures_ , Princeton, NJ: Princeton Univ. Press, 2008.
  * [4] Barbanel, J.B., Brams, S.J., and Stromquistm W., Cutting a Pie Is Not a Piece of Cake, _Amer. Math. Monthly_ , 2009, vol. 116, no. 6, pp. 496–514. https://doi.org/10.1080/00029890.2009.11920966
  * [5] Dubins, L.E. and Spanier, E.H., How to Cut a Cake Fairly, _Amer. Math. Monthly_ , 1961, vol. 68, no. 1, Part 1, pp. 1–17. https://doi.org/10.1080/00029890.1961.11989615
  * [6] Liapounoff, A.A., On Completely Additive Vector Functions, _Izv. Akad. Nauk SSSR Ser. Mat._ , 1940, vol. 4, no. 6, pp. 465–478. https://www.mathnet.ru/eng/im3907
  * [7] Halmos, P.R., The Range of a Vector Measure, _Bull. Amer. Math. Soc._ , 1948, vol. 54, no. 4, pp. 416–421. https://doi.org/10.1090/S0002-9904-1948-09020-6
  * [8] Stromquist, W., How to Cut a Cake Fairly, _Amer. Math. Monthly_ , 1980, vol. 87, no. 8, pp. 640–644. https://doi.org/10.1080/00029890.1980.11995109
  * [9] Su, F.E., Rental Harmony: Sperner’s Lemma in Fair Division, _Amer. Math. Monthly_ , 1999, vol. 106, no. 10, pp. 930–942. https://doi.org/10.2307/2589747
  * [10] Stromquist, W., Envy-free Cake Divisions Cannot Be Found by Finite Protocols, _Electron. J. Combin._ , 2008, vol. 15, no. 1, Research Paper R11 (10 pp.). https://doi.org/10.37236/735
  * [11] Aziz, H. and Mackenzie, S., A Discrete and Bounded Envy-free Cake Cutting Protocol for Any Number of Agents, in _Proc. 2016 IEEE 57th Annu. Symp. on Foundations of Computer Science (FOCS’2016), New Brunswick, NJ, USA, Oct. 9–11, 2016_ , Los Alamitos, CA: IEEE Comp. Soc., 2016, pp. 416–427. https://doi.org/10.1109/FOCS.2016.52
  * [12] Dehghani, S., Farhadi, A., HajiAghayi, M.T., and Yami, H., Envy-free Chore Division for an Arbitrary Number of Agents, in _Proc. 29th Annu. ACM–SIAM Symp. on Discrete Algorithms (SODA’2018), New Orleans, LA, USA, Jan. 7–10, 2018_ , Philadelphia, PA: SIAM, 2018, pp. 2564–2583. https://doi.org/10.1137/1.9781611975031.164
  * [13] Segal-Halevi, E., Fairly Dividing a Cake after Some Parts Were Burnt in the Oven, https://arxiv.org/abs/1704.00726v5 [math.CO], 2018.
  * [14] Blank, M.L., How to Divide the Indivisible, _Dokl. Akad. Nauk_ , 2016, vol. 471, no. 6, pp. 635–639 [_Dokl. Math._ (Engl. Transl.), 2016, vol. 94, no. 3, pp. 688-691. https://doi.org/10.1134/S1064562416060272
  * [15] Segal-Halevi, E., Hassidim, A., and Aumann, Y., Waste Makes Haste: Bounded Time Algorithms for Envy-free Cake Cutting with Free Disposal, _ACM Trans. Algorithms_ , 2016, vol. 13, no. 1, Art. 12 (32 pp.). https://doi.org/10.1145/2988232