# EC-KitY: Evolutionary Computation Tool Kit in Python with Seamless Machine
Learning Integration

Moshe Sipper  Tomer Halperin  Itai Tzruia  Achiya Elyasaf

###### Abstract

EC-KitY is a comprehensive Python library for doing evolutionary computation
(EC), licensed under the BSD 3-Clause License, and compatible with scikit-
learn. Designed with modern software engineering and machine learning
integration in mind, EC-KitY can support all popular EC paradigms, including
genetic algorithms, genetic programming, coevolution, evolutionary multi-
objective optimization, and more. This paper provides an overview of the
package, including the ease of setting up an EC experiment, the architecture,
the main features, and a comparison with other libraries.

###### keywords:

Evolutionary Algorithms , Evolutionary Computation , Genetic Programming ,
Machine Learning , scikit-learn

††journal: SoftwareX

[cs] organization=Department of Computer Science, Ben-Gurion University of the
Negev, city=Beer-Sheva, postcode=8410501, country=Israel

[sise] organization=Department of Software and Information Systems
Engineering, Ben-Gurion University of the Negev, city=Beer-Sheva,
postcode=8410501, country=Israel

##  1 Introduction

In Evolutionary Computation (EC)—or Evolutionary Algorithms (EAs)—core
concepts from evolutionary biology—inheritance, random variation, and
selection—are harnessed in algorithms that are applied to complex
computational problems. As discussed by Sipper et al. [1], EAs present several
important benefits over popular machine learning (ML) methods, including: less
reliance on the existence of a known or discoverable gradient within the
search space; ability to handle design problems, where the objective is to
design new entities from scratch; fewer required a priori assumptions about
the problem at hand; seamless integration of human expert knowledge; ability
to solve problems where human expertise is very limited; support of
interpretable solution representations; support of multiple objectives.

Importantly, these strengths often dovetail with weak points of ML algorithms,
which has resulted in an increasing number of works that fruitfully combine
the fields of EC and ML or deep learning (DL). For example, Sipper and Moore
[2] “converted” a selection method in EC to a random forest ensemble producer;
Lapid and Sipper [3] used EC to evolve activation functions for DL-based image
classifiers; Lapid et al. [4] designed an evolutionary algorithm for
generating adversarial instances in deep convolutional neural networks; Livne
et al. [5] utilized EC and DL to create accurate and interpretable context-
aware recommender systems. Major conferences in the field of EC now regularly
address the combining of EC and ML, e.g., GECCO, arguably the major EC event,
devotes two entire tracks and three workshops to the blending of evolution and
learning. There are a number of good surveys on evolutionary machine learning:
Telikani et al. [6], Al-Sahaf et al. [7], and Zhang et al. [8].

EC is thus a popular family of potent algorithms that complements ML and DL to
the benefit of all fields concerned. Further, there is a large and growing
community of EC+ML practitioners. We have used several EC open-source software
packages over the years and have identified a large “hole” in the software
landscape—there is a lacuna in the form of an EC package that is:

  1. 1.

A comprehensive toolkit for running evolutionary algorithms.

  2. 2.

Written in Python.

  3. 3.

Can work with or without scikit-learn (aka sklearn), the most popular ML
library for Python. To wit, the package should support both sklearn and
standalone (non-sklearn) modes.

  4. 4.

Designed with modern software engineering in mind.

  5. 5.

Designed to support all popular EC paradigms: genetic algorithms (GAs),
genetic programming (GP), evolution strategies (ES), coevolution, multi-
objective, etc’.

While there are several EC Python packages, none fulfill all five
requirements. Some are not written in Python, some are badly documented, some
do not support multiple EC paradigms, and so forth. Importantly for the ML
community, most tools do not intermesh with extant ML tools. Indeed, we have
personally had experience with the hardships of combining EC tools with
scikit-learn when doing evolutionary machine learning. We hope that by
adhering to the above five pillars EC-KitY will be deemed useful by a large
community.

##  2 EC-KitY

###  2.1 Setting up an evolutionary experiment

EC-KitY is available at github.com/ec-kity/ec-kity/, along with examples,
tutorials, Google Colab notebooks, and more. Installing it is simply done by:

⬇

pip install eckity

As noted, EC-KitY can work both in standalone, non-sklearn mode, and in
sklearn mode. In the following code examples, we use both modes for solving a
symbolic regression problem, where the goal is to seek regressors of arbitrary
complexity, i.e., beyond linear or polynomial ones [9].

We begin with the standalone mode, demonstrating how the user can run an EA
with a mere three lines of code:

⬇

from eckity.algorithms.simple_evolution import SimpleEvolution

from eckity.subpopulation import Subpopulation

from examples.treegp.non_sklearn_mode.symbolic_regression.sym_reg_evaluator
import SymbolicRegressionEvaluator

algo = SimpleEvolution(Subpopulation(SymbolicRegressionEvaluator()))

algo.evolve()

print('algo.execute(x=2, y=3, z=4):', algo.execute(x=2, y=3, z=4))

An algorithm can operate on a single Subpopulation (as in the case of
SimpleEvolution), two Subpopulations (e.g., in a coevolutionary setup), or $n$
($>2$) Subpoplations (e.g., island model). Each Subpopulation may have its own
evaluation function, which is why in the above example the
SymbolicRegressionEvaluator is a parameter of Subpopulation. There are
additional parameters of Subpopulation (e.g., genetic operators), and the
algorithm (e.g., breeder and statistics). In the example, these parameters
received the default values. The default function set is [add, sub, mul, div],
the default terminal set is ['x', 'y', 'z', 0, 1, -1], and there are
additional parameters, as defined in the API [10]. Below we show examples that
demonstrate, among others, the use of non-default values.

The above code takes 4 minutes to run in Google Colab; by adding a simple
early-termination condition (as in the last example below) runtime can be
reduced to 9 seconds.

Here is an example of an evolved GP tree:

⬇

add

add

z

z

add

add

z

y

add

x

y

The evolved tree’s fitness (mean absolute error) is 9.41e-15. The code’s
output was:

⬇

algo.execute(x=2, y=3, z=4): 20

Running an EA in sklearn mode is just as simple (again, a symbolic-regression
problem):

⬇

from sklearn.datasets import make_regression

from sklearn.metrics import mean_absolute_error

from sklearn.model_selection import train_test_split

from eckity.algorithms.simple_evolution import SimpleEvolution

from eckity.creators.gp_creators.full import FullCreator

from eckity.genetic_encodings.gp.tree.utils import create_terminal_set

from eckity.sklearn_compatible.regression_evaluator import RegressionEvaluator

from eckity.sklearn_compatible.sk_regressor import SKRegressor

from eckity.subpopulation import Subpopulation

X, y = make_regression(n_samples=100, n_features=3)

terminal_set = create_terminal_set(X)

algo = SimpleEvolution(

Subpopulation(creators=FullCreator(terminal_set=terminal_set),

evaluator=RegressionEvaluator()))

regressor = SKRegressor(algo)

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)

regressor.fit(X_train, y_train)

print('MAE on test set:',

mean_absolute_error(y_test, regressor.predict(X_test)))

In this example, we wrap the algorithm as a sklearn regressor and execute it
from sklearn. The toolkit repository contains examples of more-advanced ways
in which EC-KitY interacts with sklearn, including grid search and pipeline.

Running this code in Google Colab took 14 minutes without an early-termination
condition, and the output was:

⬇

MAE on test set: 0.07

The user may wish to specify additional components of the EA rather than rely
on default values; this can be readily achieved through the relevant
constructor, e.g.:

⬇

algo = SimpleEvolution(

Subpopulation(creators=

RampedHalfAndHalfCreator(init_depth=(2, 4),

terminal_set=terminal_set,

function_set=function_set,

bloat_weight=0.0001),

population_size=200,

evaluator=SymbolicRegressionEvaluator(),

higher_is_better=False,

elitism_rate=0.05,

operators_sequence=[

SubtreeCrossover(probability=0.9, arity=2),

SubtreeMutation(probability=0.2, arity=1),

ERCMutation(probability=0.05, arity=1)

],

),

breeder=SimpleBreeder(),

max_workers=4,

max_generation=500,

statistics=BestAverageWorstStatistics(),

termination_checker=

ThresholdFromTargetTerminationChecker(optimal=0, threshold=0.001)

)

Detailed API, tutorials, and several use cases are available at [10].

###  2.2 Architecture

As previously noted, we plan for EC-KitY to support all main EC paradigms,
including genetic algorithms, genetic programming, evolution strategies,
coevolution, and evolutionary multi-objective optimization. To support this
plethora of algorithms and genetic operators, we based our design on ECJ,
likely the most comprehensive EC package to date, which has been in use and
under development for over two decades [11]. We did, however, veer away from
ECJ on a crucial point: Statistics can be drawn from any operation using event
hooks, thus improving the decoupling and the separation of concerns.

The architecture of EC-KitY is depicted in Figure 1. The Algorithm class
serves as the entry point to EC-KitY. It contains all the needed information
for an experiment and acts on the population using the Breeder class. Several
classes extend the Operator class (these are denoted by a small triangle);
they emit events that can be intercepted by Statistics. The same EC-KitY code
can be used both in standalone mode (Figure 1, left) and in sklearn mode
(Figure 1, right). The latter is achieved by wrapping an Algorithm instance
with an SKLearnWrapper.

Nameg Class _Name_ g _Abstract_ class Nameg Class generalized by _Operator_
GeneralizationCompositionAssociation

_Operator_ g _Algorithm_ g _Breeder_ g Population g _PopulationEvaluator_ g
Subpopulation g _Individual_ g _Fitness_ g _IndividualEvaluator_ g
_TerminationChecker_ g _Creator_ g _SelectionMethod_ g _GeneticOperator_ g
_Statistics_ g

_SKLearnWrapper_ g _Algorithm_ g _SKClassifier_ g _SKRegressor_ g
ClassifierMixin g RegressionMixin g

Figure 1: The general architecture of EC-KitY (left), and the added components
for sklearn mode (right).

EC-KitY is designed to be easily extended: it is heavily over-architected,
with many hooks that facilitate system modification and enhancement. The
architecture supports the following features: execution in the cloud or in a
cluster, multiple statistics, multithreaded evaluation, replicability
standards (all of which have already been implemented), as well as
checkpointing and logging facilities (under active development).

##  3 Comparison with Other Packages

Through considerable hands-on experience with EC open-source software over
many years, and through additional extensive research, we have identified the
following eight tools, whose major features are compared in Table 3, along
with EC-KitY [10]: gplearn [12], geatpy [13], DEAP [14], Platypus [15], ECJ
[11], Jenetics [16], KEEL [17], HeuristicLab [18].

Only two packages are written in Python and are also sklearn-compatible:
geatpy and gplearn. However, as shown in Table 3, they lack many important
features that EC-KitY possesses.

Table 1: Feature comparison of EC-KitY with extant software packages. ✔:
feature exists, (✔): feature planned soon, : feature mostly lacking, ✗:
feature completely lacking.

Feature | EC-KitY | geatpy | gplearn | DEAP | Platypus | ECJ | Jenetics | KEEL | HeuristicLab
---|---|---|---|---|---|---|---|---|---
Language | Python | Python | Python | Python | Python | Java | Java | Java | C#
sklearn-compatible | ✔ | ✔ | ✔ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗
SE Design | ✔ |  | ✗ | ✗ | ✗ | ✔ | ✔ |  | ✔
GA representations | ✔ | ✔ | ✗ | ✔ | ✔ | ✔ | ✔ | ✔ | ✔
GP representations | ✔ | ✗ | ✔ | ✔ | ✗ | ✔ |  | ✔ | ✔
User-defined operators | ✔ | ✗ | ✗ | ✔ | ✔ | ✔ | ✔ | ✗ | ✔
User-defined representation | ✔ | ✗ | ✗ | ✔ | ✔ | ✔ | ✔ | ✗ | ✔
Coevolution | (✔) | ✗ | ✗ | ✔ | ✗ | ✔ | ✗ | ✔ | ✗
Multiobjective | ✔ | ✔ | ✗ | ✔ | ✔ | ✔ | ✔ | ✔ | ✔
Statistics | ✔ | ✔ | ✔ | ✔ |  | ✔ | ✔ | ✔ | ✔
Documentation | ✔ |  | ✔ |  |  | ✔ | ✔ |  | ✔
API | ✔ |  | ✔ | ✔ | ✗ | ✔ | ✔ | ✗ | ✔
Latest version | 2022 | 2022 | 2019 | 2019 | 2020 | 2019 | 2022 | 2015 | 2022

##  4 Concluding Remarks

The EC-KitY library is under active development. Presently, we plan to add a
variety of evolutionary algorithms, individual types, genetic operators, and
tests. We are also working on extending and enhancing the documentation. We
wish to broaden both the user and developer communities by implementing more
sample use cases from different domains and by encouraging developers to
contribute.

We recently taught a course in which 48 students worked in groups of two or
three, submitting a total of 22 projects that used EC-KitY to solve a diverse
array of complex problems, including evolving Flappy Bird agents, evolving
blackjack strategies, evolving Super Mario agents, evolving chess players, and
solving problems such as maximum clique and vehicle routing. EC-KitY proved
quite up to the tasks.

Given the popularity and diverse applicability of evolutionary algorithms, we
hope that EC-KitY finds multitudinous and beneficial uses.

## Acknowledgements

This research was partially supported by the following grants: 2714/19 from
the Israeli Science Foundation; Israeli Smart Transportation Research Center
(ISTRC); Israeli Council for Higher Education (CHE) via the Data Science
Research Center, Ben-Gurion University of the Negev, Israel.

## References

  * Sipper et al. [2017] M. Sipper, R. S. Olson, J. H. Moore,  Evolutionary computation: the next major transition of artificial intelligence?,  BioData Mining 10 (2017) 26.
  * Sipper and Moore [2021] M. Sipper, J. H. Moore,  Conservation machine learning: a case study of random forests,  Nature Scientific Reports 11 (2021) 3629.
  * Lapid and Sipper [2022] R. Lapid, M. Sipper,  Evolution of activation functions for deep learning-based image classification,  in: Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO ’22, Association for Computing Machinery, New York, NY, USA, 2022, p. 2113–2121.
  * Lapid et al. [2022] R. Lapid, Z. Haramaty, M. Sipper,  An evolutionary, gradient-free, query-efficient, black-box algorithm for generating adversarial instances in deep convolutional neural networks,  Algorithms 15 (2022).
  * Livne et al. [2022] A. Livne, E. S. Tov, A. Solomon, A. Elyasaf, B. Shapira, L. Rokach,  Evolving context-aware recommender systems with users in mind,  Expert Systems with Applications 189 (2022) 116042.
  * Telikani et al. [2022] A. Telikani, A. Tahmassebi, W. Banzhaf, A. H. Gandomi,  Evolutionary machine learning: A survey,  ACM Computing Surveys 54 (2022).
  * Al-Sahaf et al. [2019] H. Al-Sahaf, Y. Bi, Q. Chen, A. Lensen, Y. Mei, Y. Sun, B. Tran, B. Xue, M. Zhang,  A survey on evolutionary machine learning,  Journal of the Royal Society of New Zealand 49 (2019) 205–228.
  * Zhang et al. [2011] J. Zhang, Z.-h. Zhan, Y. Lin, N. Chen, Y.-j. Gong, J.-h. Zhong, H. S. Chung, Y. Li, Y.-h. Shi,  Evolutionary computation meets machine learning: A survey,  IEEE Computational Intelligence Magazine 6 (2011) 68–75.
  * Sipper [2022] M. Sipper,  Binary and multinomial classification through evolutionary symbolic regression,  in: Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO ’22, Association for Computing Machinery, New York, NY, USA, 2022, p. 300–303.
  * Sipper et al. [2022] M. Sipper, T. Halperin, I. Tzruia, A. Elyasaf, EC-KitY: Evolutionary Computation Tool Kit in Python, https://www.eckity.org/, 2022.
  * Scott and Luke [2019] E. O. Scott, S. Luke,  ECJ at 20: Toward a general metaheuristics toolkit,  in: Proceedings of the Genetic and Evolutionary Computation Conference Companion, 2019, pp. 1391–1398.
  * Stephens [2019] T. Stephens, Genetic Programming in Python, with a scikit-learn inspired API, https://github.com/trevorstephens/gplearn, 2019\.
  * geatpy [2022] geatpy, Evolutionary algorithm toolbox and framework with high performance for Python, https://github.com/geatpy-dev/geatpy, 2022\.
  * Fortin et al. [2012] F.-A. Fortin, F.-M. De Rainville, M.-A. Gardner, M. Parizeau, C. Gagné,  DEAP: Evolutionary algorithms made easy,  Journal of Machine Learning Research 13 (2012) 2171–2175.
  * Platypus [2020] Platypus, A Free and Open Source Python Library for Multiobjective Optimization, https://github.com/Project-Platypus/Platypus, 2020\. Accessed: 2022-4-29.
  * Wilhelmstötter [2022] F. Wilhelmstötter, Genetic Algorithm, Genetic Programming, Evolutionary Algorithm, and Multi-objective Optimization, https://github.com/jenetics/jenetics, 2022\.
  * KEEL [2015] KEEL, Knowledge Extraction based on Evolutionary Learning, https://github.com/SCI2SUGR/KEEL, 2015\.
  * Elyasaf and Sipper [2014] A. Elyasaf, M. Sipper,  Software review: The HeuristicLab framework,  Genetic Programming and Evolvable Machines 15 (2014) 215–218.

## Required Metadata

## Current code version

C1 |  Current code version |  v0.3.0
---|---|---
C2 |  Permanent link to code/repository used for this code version |  https://github.com/EC-KitY/EC-KitY
C3 |  Permanent link to Reproducible Capsule |  https://codeocean.com/capsule/8740191/tree
C4 |  Legal Code License |  BSD 3-Clause License
C5 |  Code versioning system used |  git
C6 |  Software code languages, tools, and services used |  Python
C7 |  Compilation requirements, operating environments & dependencies |  numpy ($>=1.14.6$), pandas
($>=0.25.0$), overrides ($>=6.1.0$). For sklearn mode: scikit-learn
($>=0.24.2$)
C8 |  Link to developer documentation/manual |  API—https://api.eckity.org/eckity.html
Tutorials—https://github.com/EC-KitY/EC-KitY/wiki/Tutorials
Examples—https://github.com/EC-KitY/EC-KitY/tree/main/examples
C9 |  Support email for questions |<EMAIL_ADDRESS>
Table 2: Code metadata

## Current executable software version

S1 |  Current software version |  v0.3.0
---|---|---
S2 |  Permanent link to executables of this version |  https://pypi.org/project/eckity
S3 |  Permanent link to Reproducible Capsule |  https://codeocean.com/capsule/8740191/tree
S4 |  Legal Software License |  BSD 3-Clause License
S5 |  Computing platforms/Operating Systems |  Cross-platform
S6 |  Installation requirements & dependencies |  numpy ($>=1.14.6$), pandas
($>=0.25.0$), overrides ($>=6.1.0$). For sklearn mode: scikit-learn
($>=0.24.2$)
S7 |  Link to user manual |  API—https://api.eckity.org/eckity.html
Tutorials—https://github.com/EC-KitY/EC-KitY/wiki/Tutorials
Examples—https://github.com/EC-KitY/EC-KitY/tree/main/examples
S8 |  Support email for questions |<EMAIL_ADDRESS>
Table 3: Software metadata


# A Strategyproof Mechanism for Ownership Restructuring in Privately Owned
Assets

Gal Danino<EMAIL_ADDRESS><EMAIL_ADDRESS>and
<EMAIL_ADDRESS>Equal author contribution. Technion - Israel
Institute of Technology  Moran Koren  Ben Gurion University of the Negev  Omer
Madmon  Technion - Israel Institute of Technology

###### Abstract

It is unclear how to restructure ownership when an asset is privately held,
and there is uncertainty about the owners’ subjective valuations. When
ownership is divided equally between two owners, a commonly used mechanism is
called a BMBY mechanism. This mechanism works as follows: each owner can
initiate a BMBY by naming her price. Once an owner declares a price, the other
chooses to sell his holdings or buy the shares of the initiator at the given
price. This mechanism is simple and tractable; however, it does not elicit
actual owner valuations, does not guarantee an efficient allocation, and, most
importantly, is limited to an equal partnership of two owners. In this paper,
we extend this rationale to a multi-owner setting. Our proposed mechanism
elicits owner valuations truthfully. Additionally, our proposed mechanism
exhibits several desirable traits: it is easy to implement, budget balanced,
robust to collusion (weakly group strategyproof), individually rational, and
ex-post efficient.

##  1 Introduction

Firms often need to perform ownership restructure. This may be due to a major
strategic shift, just before a merger or an acquisition, or simply due to co-
owners’ desire to dissolve their partnership. If the firm is public, it can
trigger a “share buyback” process in which it absorbs the shares of interested
sellers at the market price. Such buybacks have gained popularity since the
1980s, and are often considered a good omen as to the firm’s financial
fortitude (Wohlner, 2019).

The “buyback” mechanism in public firms exists due to the availability of a
market price which serves as an anchor to the seller compensation. This anchor
price does not exist in privately held firms which constitute the vast
majority of companies in the US (e.g., in 2013, less than 15% of the firms
with over 500 employees were public and in 2010 private firms account for 59%
of US sales, Biery, 2019). For this sector, which comprises various firm sizes
ranging from small mom-and-pop shops to huge conglomerates (Forbes ), the
buyback mechanism cannot simply be applied and often requires a costly due
diligence process to assess the company share value.

When the firm is co-owned by two partners, each owning half, there exists an
alternative ownership restructuring mechanism called “BMBY - buy me out or I
will buy you out.” The BMBY mechanism works as follows, say Alice and Bob co-
own an indivisible asset, and wish to part ways. In BMBY, one partner, say
Alice, declares a price and the other partner - Bob decides whether he wants
to buy Alice out or sell his share to Alice at the aforementioned price. This
simple mechanism is extremely useful and intuitive, yet may be susceptible to
strategic behavior and may lead to an inefficient allocation.111To see why,
assume that agent types are determined by i.i.d draws from a uniform
distribution over $[0,1],$ and consider a case where Alice’s valuation is
extremely low. In this case, as Bob’s expected value is half, she can benefit
from misreporting her value and declare a higher price.

In this work we extend the simple two agent BMBY mechanism to a setting in
which the asset is owned by many share holders, while maintaining the
mechanism simplicity. We introduce a mechanism for decreasing the number of
owners of a stock from $n$ to $\bar{m}<n$, which we call Multi-BMBY Mechanism
(MBM). The mechanism receives bids from all agents, and sets an asset price,
at which agents trade shares of the asset. To show strategyproofness of the
mechanism we use simple second-price auction-type arguments, and show that for
each agent either increasing or decreasing her truthful bid does not increase
her gain, regardless of the bidding of other agents. Additionally, the
mechanism is immune to collusions (weak group strategyproof), budget balanced,
individually rational and ex-post efficient, meaning that the subset of agents
who remain owners are those who value it most.

Recall that a celebrated result of Myerson and Satterthwaite (1983) shows that
in bilateral trading there exists no mechanism that is strategyproof, budget
balanced, individually rational and ex-post efficient. In this work we show
that these properties can be satisfied in a setting of ownership
restructuring. A main difference between our setting and bilateral trading is
that in our setting we allow for mechanisms that randomly draw the number of
owners after restructuring, while this is impossible in bilateral trading, as
the good is indivisible. In practice, the MBM mechanism is non-deterministic
only with respect to a single agent, meaning that the number of owners after
the restructuring is approximately deterministic.

##  2 Related Literature

In this work we study how to perform “buyback” in privately held firms. This
can be thought of as a case of a multilayer partnership dissolvement problem
which was introduced by Cramton et al. (1987). They study whether a
partnership of multiple parties can be dissolved efficiently. As in our case,
the partner valuations are held private and the mechanism must elicit truthful
behavior in order to produce an efficient allocation. In their model, inspired
by the FCC’s cell phone licensing allocation, they attempt to allocate a co-
owned, indivisible asset to a single owner which values it most. They conclude
that such a mechanism exists as long as no owner posses too large share in the
original partnership. Additionally, they propose a bidding mechanism which
generates the ex-post efficient allocation. Their mechanism is a sealed bid
auction in which agents are either paid or participate in an all-pay auction.
This bidding mechanism, is shown to be incentive compatible, individually
rational, and ex-post efficient, yet it is not budget balanced. Recent work
following Cramton et al. (1987) have examined the problem of partnership
dissolvement to account for complementaries (see for example Ensthaler et al.,
2014; Landeo and Spier, 2013). Our work is closest to Wasser, 2013, where the
author introduced a $k+1$ auction where the price is a convex combination of
the bidder’s bids, and thus not incentive compatible. Our proposed mechanism
guarantees budget balanceness. In addition, it generates an equal share price
for all participants, which is crucial for the case of equity restructuring.
Additional work on partnership dissolvement examined the legal and social
aspects of the problem, e.g. Adler and Ayres (2001) and Bredin and Parkes
(2005).

Our work strongly relates to Myerson and Satterthwaite (1983), who studied
mechanism design in the context of bilateral trading with private information.
Myerson and Satterthwaite (1983) showed that any incentive-compatible and
individually rational trading mechanism inherently experiences a degree of
inefficiency. This model was then extended by Loertscher and Marx (2023) to a
model of multi-unit with supply and demand, in which the agents’ utility is
geometric, meaning it can represent either increasing or decreasing marginal
cost.

In our work, we show that such a mechanism does exist in a different model of
ownership restructuring. In the initial state, all agents are owners of the
products, and the mechanism then determines which agents are buyers (and
remain owners) and which are sellers (and sell their shares). We introduce a
mechanism that satisfies axioms that are analogous to the ones studied by
Myerson and Satterthwaite (1983). Our mechanism is randomized with respect to
a single agent, meaning a single agent can be either a buyer or a seller.

An additional related line of work is the study of double auctions. In a
double auction a set of buyers and a set of sellers are interested in
performing trades with each other. McAfee (1992), in his seminal paper have
suggested a mechanism ,similar to ours, in which the price facing the sellers
will be set by the declarations of the buyers and vice versa. The number of
trades will be determined by supply and demand. A similar approach was applied
to matching markets by Azevedo and Leshno (2016). Dütting et al. (2017)
extended the modular approach, which is often used for one sided matching
problems, into the realm of double auctions, and identify the conditions under
which incentive compatibility and feasibility are guaranteed. Bredin and
Parkes (2005) examined the ability of a dynamic pricing policy to reduce the
volatility and improve efficiency in online double auction markets. Our model
covey an intuition similar to the McAfee auction, only we tackle a case where
agents can be both buyers or sellers.

Finally, the problem of partnership dissolvement can be thought of as a cake
cutting problem, where the size of the “cake” is the value of the co-owned
asset plus the sum of agent payments. In this set of models, the lion share of
existing literature develop algorithms for dividing an asset among its owners.
The main emphasis is on algorithms which are both “fair” and efficient (see
Procaccia, 2013 for a recent review). The existing solutions in this field
rely heavily on the order in which the agents are approached, and thus can be
immensely time consuming to apply. Our mechanism is invariant to the order as
bids are assumed to be simultaneous.

##  3 The Model

Let $I=\\{1,...,n\\}$ be the set of agents such that $n>2$. Each agent $i\in
I$ has a private value $v_{i}\in\mathbb{R_{+}}$ for the asset. The private
values can be completely arbitrary and we do not assume that they are drawn
from any particular distribution. Let allocation space
$\mathcal{A}\subset[0,1]^{n}\times\mathbb{R}^{n}$ consist of allocations for
shares and money for all $n$ agents, such that in every allocation
$A\in\mathcal{A}$ the shares of all agents sum up to $1.$ Denote respectively
by $s_{i}^{A},x_{i}^{A}$ the share and money of agent $i$ under allocation
$A$.

The MBM mechanism is a mapping
$F:\mathcal{A}\times\mathbb{R}^{n}\rightarrow\mathcal{A}$ from an initial
allocation and a bid vector to a new allocation. For each agent $i$, the
mechanism defines the agent’s monetary payment, which can be positive or
negative, and resulting share, which is non-negative.

Denote by $u_{i}(s_{i},x_{i})=s_{i}v_{i}+x_{i}$ the utility of agent $i$ from
shares $s_{i}$, and money $x_{i}$. We normalize the initial amounts of money
to be zero, and therefore the initial utility of each agent is simply
$s_{i}v_{i}$. In addition, we assume agents face no monetary constraints. The
planner employs the mechanism to reallocate shares and money among the owners
in a way that a subset $M\subset I$ of the initial owners remain owners at the
end of the process.

For the reallocation process, the mechanism receives declarations from all $n$
agents of their valuation of the asset as bids $(b_{i})_{i\in I}$ and selects
$m<n$ agents who remain owners. The other $n-m$ initial owners sell their
holdings. The mechanism also decides on a single asset price $p$ that is used
for all sales and purchases of shares. Denote by $A_{0}$ the initial
allocation and by $(\bar{b}_{i})_{i\in I}=(v_{i})_{i\in I}$ and
$\bar{A}=F(A_{0},(v_{i})_{i\in I})$ the bids and allocation when all agents
bid their private valuation.

The mechanism works as follows: the planner limits the number of eventual
owners with $\bar{m}$. Each agent bids $b_{i}$ as a price for the whole asset,
which represents her proportional declared valuation to every share size.
Agents are ranked by their bids in descending order. We assume there are no
ties in the agents’ valuations.222Alternatively, one can assume that the agent
valuations are drawn i.i.d. from an atom-less distribution and that ties occur
with probability zero. Let $r((b_{j})_{j\in I},i)$ denote the ranking of agent
$i$ in $(b_{j})_{j\in I}$. When clear from context, we suppress $(b_{j})_{j\in
I}$ and write $r(i)$ for brevity. Let subscript $(i)$ denote the order
statistic of bids such that $s^{A}_{(1)}$ is the share of the lowest bidder.
Then, the mechanism chooses the number of eventual owners
$m\in\\{\bar{m}-1,\bar{m}\\}$ at random (we describe the probabilities below),
where $m=\bar{m}$ means that the $\bar{m}$’th ranked agent becomes a buyer,
while $m=\bar{m}-1$ means that the $\bar{m}$’th ranked agent becomes a seller.

We set the probability of $m=\bar{m}$ and $m=\bar{m}-1$ in a way which makes
the $m$’th ranked agent receive a utility of zero in expectation. As we show
later, the resulting probability for $m=\bar{m}$ is
$\sum_{i=n-\bar{m}+1}^{n}s^{A_{0}}_{(i)}$ , and the probability for
$m=\bar{m}-1$ is $\sum_{i=1}^{n-\bar{m}}s^{A_{0}}_{(i)}$.

The mechanism then sets $p=b_{(\bar{m})},$ i.e., the price equals the
$\bar{m}$’th highest ranked agent’s bid. A higher ranked agent, say agent $j$,
becomes a buyer. Her share in the final allocation increases by
$s^{A_{0}}_{j}\frac{\sum_{i=1}^{n-m}s^{A_{0}}_{(i)}}{\sum_{i=n-m+1}^{n}s^{A_{0}}_{(i)}}>0$
(i.e., by a factor of $\frac{1}{\sum_{i=n-m+1}^{n}s^{A_{0}}_{(i)}}>1$), and
all lower ranked agents become sellers to whom the mechanism allocates no
shares. All low ranking bidders receive compensation, which equal the price
times their respective share in the initial allocation. Denote by
$\bar{r},\bar{p}$ the ranking and price, respectively, when all agents bid
their private valuation.

###  3.1 Definitions

We begin by providing a formal definition of the MBM mechanism:

######  Definition 1.

The MBM mechanism $F$ receives as an input the initial allocation $A_{0}$ and
a bidding profile $(b_{i})_{i\in I}\in\mathbb{R}^{n}$, and outputs the
following allocation:

$s_{(j)}^{F(A_{0},(b_{i})_{i\in
I})}=\begin{cases}s_{(j)}^{A_{0}}\bigg{(}1+\frac{\sum_{i=1}^{n-m}s^{A_{0}}_{(i)}}{\sum_{i=n-m+1}^{n}s^{A_{0}}_{(i)}}\bigg{)}&j\geq
n-m+1\\\ 0&j<n-m+1\end{cases}$

$x_{(j)}^{F(A_{0},(b_{i})_{i\in
I})}=\begin{cases}-s_{(j)}^{A_{0}}\frac{\sum_{i=1}^{n-m}s^{A_{0}}_{(i)}}{\sum_{i=n-m+1}^{n}s^{A_{0}}_{(i)}}p&j\geq
n-m+1\\\ s_{(j)}^{A_{0}}p&j<n-m+1\end{cases}$

where $p=b_{(\bar{m})}$ and $m=\bar{m}$ with probability
$\sum_{i=n-\bar{m}+1}^{n}s^{A_{0}}_{(i)}$, and $m=\bar{m}-1$ otherwise.

Below we introduce the mechanism characteristics we wish to analyze. These
properties are analogous the the properties studied by Myerson and
Satterthwaite (1983) in a bilateral trading framework. We start by defining
the well-known notion of a “strategyproof” mechanism. A mechanism is
considered strategyproof if bidding one’s private value is a weakly dominant
strategy for all agents, regardless of all the other agent bids. Formally:

######  Definition 2.

A mechanism is considered strategyproof if for every agent $i\in I$, every
$(b_{i})_{i\in I}\in\mathbb{R}^{n}$, and every $A_{0}\in\mathcal{A}$, it holds
that

$u_{i}(s^{F(A_{0},(\bar{b}_{i},b_{-i}))}_{i},x^{F(A_{0},(\bar{b}_{i},b_{-i}))}_{i})\geq
u_{i}(s^{F(A_{0},(b_{i},b_{-i}))}_{i},x^{F(A_{0},(b_{i},b_{-i}))}_{i})$

where $b_{-i}$ are the bids of all the agents other than $i$.

While the definition above tackles the case in which a single agent deviates,
our mechanism also resolves cases in which a subset of agents all benefit from
working in collusion. Next, we define the notion of a weak group strategyproof
mechanism. A mechanism is considered weak group strategyproof if it is
impossible for all the agents who deviate from bidding their private valuation
to strictly benefit simultaneously. Formally:

######  Definition 3.

A mechanism is considered weak group strategyproof if there does not exist a
subset of agents $J\subseteq I$, bids $(b_{i})_{i\in J}\in\mathbb{R}^{||J||}$,
and initial allocation $A_{0}\in\mathcal{A}$, such that for every agent $j\in
J$, it holds that

$u_{j}\bigg{(}s^{F(A_{0},((b_{i})_{i\in J},(\bar{b}_{i})_{i\in I\setminus
J}))}_{j},x^{F(A_{0},((b_{i})_{i\in J},(\bar{b}_{i})_{i\in I\setminus
J}))}_{j}\bigg{)}>u_{j}(s^{\bar{A}}_{j},x^{\bar{A}}_{j})$

Next, we define the notion of a budget balanced mechanism. Note that our
definition of budget balanced, also includes a requirement that the asset will
be fully allocated.

######  Definition 4.

We say that a mechanism $F$ is budget balanced if for every $(b_{i})_{i\in
I}\in\mathbb{R}^{n}$, and every $A_{0}\in\mathcal{A}$, it holds that

$\sum_{i\in I}s^{F(A_{0},(b_{i})_{i\in I})}_{i}=\sum_{i\in I}s^{A_{o}}_{i}$

and

$\sum_{i\in I}x^{F(A_{0},(b_{i})_{i\in I})}_{i}=\sum_{i\in I}x^{A_{o}}_{i}$

When considering a strategyproof mechanism, it is sufficient to discuss the
outcome of the mechanism in the case where agents play their dominant
strategy, which is bidding their true valuations. Hence the following two
properties, which are related to the quality of the outcome, are only defined
with respect to truthful bidding of the agents.

An allocation is said to be efficient if the remaining owners are the agents
with the highest valuations. Ex-post efficiency is then defined as follows:

######  Definition 5.

We say that a mechanism $F$ satisfies ex-post efficiency if for every
$A_{0}\in\mathcal{A}$, the allocation $\bar{A}$ contains no pair of agents
$j,k\in I$ such that $s_{j}^{\bar{A}}=0$ (agent $j$ is a seller),
$s_{k}^{\bar{A}}>0$ (agent $k$ is a buyer), and $v_{j}>v_{k}$.

Finally, we define individual rationality, which implies that under truthful
bidding all agents improve their utility with respect to the initial
allocation:

######  Definition 6.

We say that a mechanism $F$ satisfies individual rationality if for every
$j\in I$ and every $A_{0}\in\mathcal{A}$, it holds that

$u_{j}(s_{j}^{\bar{A}},x_{j}^{\bar{A}})\geq
u_{j}(s_{j}^{A_{0}},x_{j}^{A_{0}})$

Lastly, we define the useful notion of adjusted utility, which is simply the
difference between the agent’s utility before and after applying a
restructuring mechanism:

######  Definition 7.

Given an allocation $A\in\mathcal{A}$, the adjusted utility of agent $j$ with
respect to the initial allocation $A_{0}\in\mathcal{A}$ is defined as follows:

$\tilde{u}_{j}(s_{j}^{A},x_{j}^{A})=u_{j}(s_{j}^{A},x_{j}^{A})-u_{j}(s_{j}^{A_{0}},x_{j}^{A_{0}})$

Note that individual rationality can be redefined by requiring that the
adjusted utility of each agent with respect to the allocation obtained by
truthful bidding is non-negative. Moreover, note that since the initial
utilities are constant, properties like strategyproof and weak group
strategyproof can be equivalently defined with respect to the adjusted
utility, as agents always have a beneficial deviation with respect to their
standard utility if and only if they have a beneficial deviation with respect
their adjusted utility. Therefore, from now on we only consider the agents’
adjusted utility, without explicitly specifying it.

##  4 Analysis and Results

In this section we show that The MBM mechanism is strategyproof, weakly group
strategyproof, budget balanced, individually rational and ex-post efficient.
An essential part of our mechanism is the monotone relation between the bids
and the price. The next lemma shows that if an agent increases her bid, then
the mechanism sets a weakly higher price. If she decreases her bid then the
mechanism sets a weakly lower price.

######  Lemma 1.

let $b,b^{h},b^{l}$ be bid vectors such that $b^{h}$ is derived by increasing
one bid in $b$ and $b^{l}$ is derived by decreasing one bid in $b$. Let
$p,p^{h},p^{l}$ be the mechanism prices corresponding to the vector bids of
$b,b^{h},b^{l}$, respectively. Then, $p^{l}\leq p\leq p^{h}$.

###### Proof.

Proof Denote by $h,l$ the agents who bids higher and lower in $b^{h},b^{l}$,
respectively. By increasing agent $h$’s bid, the value associated with each
ranking weakly increases, and in particular the value associated with the
$m$’th ranking weakly increases from $p$ to $p^{h}$. Similarly, by decreasing
agent $l$’s bid, the value associated with the $m$’th ranking weakly decreases
from $p$ to $p^{l}$. ∎

To show strategyproofness we take advantage of a characteristic for each type
the mechanism can assign to agent $j:$ a definite buyer (i.e., $r(j)>m$), a
definite seller (i.e., $r(j)<m$), and the threshold agent (i.e.,
$r(j)=\bar{m}$). If agent $j$ is definite buyer then her utility equals
$~{}{s^{A_{0}}_{j}\frac{\sum_{i=1}^{n-m}s^{A_{0}}_{(i)}}{\sum_{i=n-m+1}^{n}s^{A_{0}}_{(i)}}(v_{j}-p)}$,
which is positive if and only if the asset price is lower than she values it.
If the mechanism designates agent $j$ as a definite seller then her utility is
$s^{A_{0}}_{j}(p-v_{j})$, which is positive whenever the asset price is higher
than her valuation of it. Finally, if $r(j)=\bar{m}$, then the agent can be
designated both as a buyer and as a seller. We observe that according to the
probabilities for each realization, the agent’s expected utility is zero.

######  Observation 1.

The threshold agent’s expected utility is zero.

###### Proof.

Proof Let $j\in I$ such that $r(j)=\bar{m}$. Agent $j$ can be either a buyer
or a seller, but the price will always be $p=b_{(\bar{m})}$. Therefore, it
holds that

$\sum_{i=n-\bar{m}+1}^{n}s^{A_{0}}_{(i)}\left[s^{A_{0}}_{j}\frac{\sum_{i=1}^{n-\bar{m}}s^{A_{0}}_{(i)}}{\sum_{i=n-\bar{m}+1}^{n}s^{A_{0}}_{(i)}}(v_{j}-p)\right]+\sum_{i=1}^{n-\bar{m}}s^{A_{0}}_{(i)}\left[s^{A_{0}}_{j}(p-v_{j})\right]=0.$

∎

We also observe that since the mechanism sets the $\bar{m}$’th bid as the
price, under $\bar{r}$ all agents receive a non-negative utility, which
implies that the mechanism satisfies individual rationality:

######  Lemma 2.

The MBM mechanism satisfies individual rationality.

###### Proof.

Proof Recall that under $\bar{r}$ every agent $i\in I$ bid her private
valuation $\bar{b}_{i}=v_{i}$, and the price is $\bar{p}=\bar{b}_{(\bar{m})}$.
In addition, for every definite buyer $i$, since $r(i)>m$, it holds that
$\bar{b}_{i}\geq\bar{b}_{(\bar{m})}$. Therefore, $v_{i}\geq\bar{p}$. Since the
difference $v_{i}-\bar{p}\geq 0$ the buyer utility is non-negative. Similarly,
for every definite seller the difference $\bar{p}-v_{i}\geq 0$, thus the
seller utility is non-negative as well. ∎

Next, we show that agents will play their type in equilibrium.

######  Lemma 3.

The MBM mechanism is strategyproof.

###### Proof.

Proof Let $i\in I$, and let $b_{-i}$ be some arbitrary bidding profile of all
players except player i (not necessarily truthful bids). We show that player
$i$ is weakly prefers bidding $b_{i}=v_{i}$:

First, assume that bidding truthfully makes agent $i$ a definite buyer. In
this case, the price must be weakly lower than her valuations (otherwise she
was a seller). Increasing her bid does not change her utility. Decreasing her
bid will only change her utility when she hits the price $p$. If she bids the
price $p$ she becomes the threshold agent and gets utility $0$, and if she
gets lower than the price then she becomes a seller, but she sells at a price
lower than her valuations - which leads to a negative utility, and therefore
this is not beneficial for her. Similar arguments can be applied to the case
where bidding truthfully makes agent $i$ a definite seller.

Lastly, if bidding truthfully makes agent $i$ a threshold agent, her expected
utility is $0$, and it is straightforward to see that either increasing or
decreasing her bid is not beneficial: increasing the bid either leaves her as
the threshold agent (and then she obtains zero payoff, regardless of the
price), or make her a definite buyer - but with a price higher than her
valuation which causes negative payoff. Similarly, decreasing the bid either
leaves her as the threshold agent, of causes a negative utility due to selling
at a price lower than her valuation. ∎

Ex-post efficiency of the MBM mechanism then follows as an immediate
corollary, as when agents bid their true valuations, the highest bidders
remain owners:

######  Corollary 1.

The MBM mechanism is ex-post efficient.

By Lemma 3, every agent is better off bidding her true valuation. However, if
agent $j$ is ranked $m$’th and $b_{(m-1)}<b_{(m)}<b_{(m+1)}$, she increases
sellers’ (buyers’) payoff by increasing (decreasing) her bid and the price by
a small amount, while maintaining her ranking. Thus, the MBM mechanism is not
strong group strategyproof. However, to show that the mechanism is weakly
group strategyproof we need to show that it is impossible for all the agents
who deviate from bidding their true valuation to strictly benefit
simultaneously. We show this in the next Lemma:

######  Lemma 4.

The MBM mechanism is weakly group strategyproof.

###### Proof.

Proof Assume contrary to the lemma that there exists a set of agents
$J\subseteq I$ such that $\|J\|\geq 2$ that do not bid their private valuation
under $r$, and that all agents in $J$ strictly gain by deviating from
$\bar{r}$ to $r$.

By Lemma 2, all agents get non-negative utility under the truthful bidding
profile. Let $J_{B}$, $J_{S}\subseteq J$ the definite buyers and sellers in
$J$ under $r$, respectively. $J=J_{B}\cup J_{S}$ (i.e., no deviating agent is
the threshold agent under $r$). To see why, suppose that there exists agent
$j\in(J\setminus J_{B})\setminus J_{S}$, then $r(j)=\bar{m}$, and her expected
payoff is zero. Denote by $\bar{J_{B}},\bar{J_{S}}\subseteq J$ the definite
buyers and sellers in $J$ under $\bar{r}$, respectively, and denote by
$\bar{j}$ the threshold agent for which $\bar{r}(\bar{j})=\bar{m}$.

Because the subset size is fixed by the mechanism, if
$J_{B}\subseteq\bar{J_{B}}$ then $J_{B}=\bar{J_{B}}$. Therefore,
$J_{S}=J\setminus
J_{B}=J\setminus\bar{J_{B}}\supseteq(J\setminus\bar{J_{B}})\setminus\\{\bar{j}\\}=\bar{J_{S}}$,
and because the set size is fixed it holds that $J_{S}=\bar{J_{S}}$. Namely,
in this case, all the definite buyers remain definite buyers and all the
definite seller remain definite sellers after subset $J$ of agents deviate
from $\bar{r}$. Thus, the price and shares in $r$ remain as in $\bar{r}$, and
no agent gains by deviating. Similarly, no agent gains if
$J_{S}\subseteq\bar{J_{S}}$.

Hence, if the deviating agents can simultaneously strictly gain, then there
exist $j_{b}\in J_{B}\cap\\{J\setminus\bar{J_{B}}\\}$ and $j_{s}\in
J_{S}\cap\\{J\setminus\bar{J_{S}}\\}$. That is, $r$ must produce a new
definite buyer and a new definite seller. Since agents bid their private
valuation under $\bar{r}$, it holds that $v_{j_{b}}\leq\bar{p}\leq v_{j_{s}}$.
Therefore, for every price $p$ either $v_{j_{b}}-p\leq 0$ or $p-v_{j_{s}}\leq
0$. Thus, at least one agent does not strictly increase her expected utility.
∎

The mechanism is designed such that all the seller shares are distributed to
the buyers. In addition, the price is tied to the asset itself, and the share
price is the asset price multiplied by share size. The next lemma shows that
the MBM mechanism is budget balanced.

######  Lemma 5.

The MBM mechanism is budget balanced.

###### Proof.

Proof Recall that $A_{0}$ is the initial allocation. The summation of the
realized buyers’ additional shares is equal to the summation of the realized
sellers’ initial shares:

$\sum_{j=n-m+1}^{n}s^{A_{0}}_{(j)}\frac{\sum_{i=1}^{n-m}s^{A_{0}}_{(i)}}{\sum_{i=n-m+1}^{n}s^{A_{0}}_{(i)}}=\frac{\sum_{i=1}^{n-m}s^{A_{0}}_{(i)}}{\sum_{i=n-m+1}^{n}s^{A_{0}}_{(i)}}\sum_{j=n-m+1}^{n}s^{A_{0}}_{(j)}=\sum_{i=1}^{n-m}s^{A_{0}}_{(i)}$

In addition, because a price $p$ is set for the asset itself, combined with
the previous equation, the summation of payments and compensations over all
agents yields:

$\sum_{j=n-m+1}^{n}s_{(j)}^{A_{0}}\frac{\sum_{i=1}^{n-m}s^{A_{0}}_{(i)}}{\sum_{i=n-m+1}^{n}s^{A_{0}}_{(i)}}p-\sum_{j=1}^{n-m}s_{(j)}^{A_{0}}p=0$

and the sum of agents’ initial money is also zero. Thus, the mechanism is
balanced in both shares and money. ∎

We derive the main theorem directly by combining lemmas 2, 3, 4, 5 and
corollary 1:

######  Theorem 1.

The MBM mechanism is strategyproof, weakly group strategyproof, budget
balanced, individually rational and ex-post efficient.

##  5 Discussion

In this work we present an intuitive mechanism for ownership restructuring in
private firms. Our newly introduced MBM mechanism reallocates shares of a
shared asset with the goal of decreasing the number of owners as needed. The
mechanism is robust to strategic behavior and collusion (weak group
strategyproofness), and maintains budget balance. An additional aspect of the
mechanism robustness comes from the fact that it does not assume any
distribution of private valuations (unlike Cramton et al., 1987).

The mechanism receives bids from the original owners. Based on the bids and
the original allocation, it decides on a new allocation of shares and a single
price that is used for all the transactions. In the resulting allocation, the
remaining owners increase their shares in proportion to their original
holdings in exchange for payments that are lower than their valuation of their
additional share. The rest of the original owners are compensated with
payments that are higher than their valuation for the share they forfeit.

An alternative mechanism that generalizes the rational behind the BMBY
rational in order to solve a multi-agent scenario is a series of 2-agent BMBY
“matches”, where the share holder who wins a match and remains an owner is
matched with the next share holder, until the number of owners decreases as
required. Yet another alternative is having multiple 2-agent BMBY run
simultaneously, and rematch the remaining owners with each other, until the
required number of owners is reached. In both mechanisms the outcome depends
heavily on the agents that are selected for a match and the order of matches.
Hence, such mechanisms could let low value agents remain owners while high
value agents sell their share. In addition, these alternatives are not
strategyproof since an agent could bid high to win one match only to sell at a
higher price in the next match.

In contrast to the above, the order of bids in the MBM mechanism does not
affect the outcome, and it can be implemented when agents observe prior bids.
Besides efficiency, budget balance, and weak group strategyproofness, a
notable strength of our mechanism is its low computational time complexity.
Moreover, the mechanism is easy to comprehend and to implement, which makes it
a fitting business tool for ownership restructuring.

An interesting follow-up work may include the development of similar
mechanisms for the case of non-linear utilities, or adding additional
constraints such as upper-bounding agents’ shares. For instance, one may
require that no agent holds more than 50% of the asset after the
restructuring. Additionally, note that there is a gap between the willingness
to pay of the highest ranking seller and the valuation of the lowest ranking
buyer. One may consider devising a mechanism in which the firm utilizes this
gap to raise funds, as is often the reason for ownership restructuring.

## References

  * Adler and Ayres (2001) Barry E. Adler and Ian Ayres.  A dilution mechanism for valuing corporations in bankruptcy.  _Yale Law Journal_ , 111(1):83–149, 2001.  ISSN 00440094.  doi: 10.2307/797516.
  * Azevedo and Leshno (2016) Eduardo M. Azevedo and Jacob D. Leshno.  A Supply and Demand Framework for Two-Sided Matching Markets.  _Journal of Political Economy_ , 124(5):1235–1268, oct 2016.  ISSN 0022-3808.  doi: 10.1086/687476.  URL https://www.journals.uchicago.edu/doi/10.1086/687476.
  * Biery (2019) Mary E. Biery.  4 Things You Don’t Know About Private Companies.  _Forbes_ , 2019.  URL https://www.forbes.com/sites/sageworks/2013/05/26/4-things-you-dont-know-about-private-companies/{#}62f3984291aa.
  * Bredin and Parkes (2005) Jonathan Bredin and David C. Parkes.  Models for truthful online double auctions.  _Proceedings of the 21st Conference on Uncertainty in Artificial Intelligence, UAI 2005_ , pages 50–59, 2005.
  * Cramton et al. (1987) Peter Cramton, Robert Gibbons, and Paul Klemperer.  Dissolving a Partnership Efficiently.  _Econometrica_ , 55(3):615, may 1987.  ISSN 00129682.  doi: 10.2307/1913602.
  * Dütting et al. (2017) Paul Dütting, Inbal Talgam-Cohen, and Tim Roughgarden.  Modularity and greed in double auctions.  _Games and Economic Behavior_ , 105:59–83, 2017.  ISSN 10902473.  doi: 10.1016/j.geb.2017.06.008.  URL http://dx.doi.org/10.1016/j.geb.2017.06.008.
  * Ensthaler et al. (2014) Ludwig Ensthaler, Thomas Giebe, and Jianpei Li.  Speculative partnership dissolution with auctions.  _Review of Economic Design_ , 18(2):127–150, 2014\.  ISSN 14344742.  doi: 10.1007/s10058-013-0154-x.
  * (8) Forbes.  America’s Largest Private Companies List.  Technical report.  URL https://www.forbes.com/largest-private-companies/list/.
  * Landeo and Spier (2013) Claudia M. Landeo and Kathryn E. Spier.  Shotgun mechanisms for common-value partnerships: The unassigned-offeror problem.  _Economics Letters_ , 121(3):390–394, 2013.  ISSN 01651765.  doi: 10.1016/j.econlet.2013.09.016.  URL http://dx.doi.org/10.1016/j.econlet.2013.09.016.
  * Loertscher and Marx (2023) Simon Loertscher and Leslie M Marx.  Bilateral trade with multiunit demand and supply.  _Management Science_ , 69(2):1146–1165, 2023\.
  * McAfee (1992) R. Preston McAfee.  A dominant strategy double auction.  _Journal of Economic Theory_ , 56(2):434–450, 1992.  ISSN 10957235.  doi: 10.1016/0022-0531(92)90091-U.
  * Myerson and Satterthwaite (1983) Roger B Myerson and Mark A Satterthwaite.  Efficient mechanisms for bilateral trading.  _Journal of economic theory_ , 29(2):265–281, 1983.
  * Procaccia (2013) Ariel D. Procaccia.  Cake cutting: Not just child’s play.  _Communications of the ACM_ , 56(7):78–87, 2013\.  ISSN 00010782.  doi: 10.1145/2483852.2483870.
  * Wasser (2013) Cédric Wasser.  Bilateral k+1-price auctions with asymmetric shares and values.  _Games and Economic Behavior_ , 82:350–368, 2013.  ISSN 08998256.  doi: 10.1016/j.geb.2013.07.014.  URL http://dx.doi.org/10.1016/j.geb.2013.07.014.
  * Wohlner (2019) Roger Wohlner.  Are Stock Buybacks a Good Thing or Not?, 2019.  URL https://www.investopedia.com/articles/financial-advisors/121415/stock-buybacks-good-thing-or-not.asp.


# Local structure of convex surfaces
near regular and conical points

Alexander Plakhov Center for R&D in Mathematics and Applications, Department
of Mathematics, University of Aveiro, Portugal and Institute for Information
Transmission Problems, Moscow, Russia<EMAIL_ADDRESS>
###### Abstract

Consider a point on a convex surface in $\mathbb{R}^{d}$, $d\geq 2$ and a
plane of support $\Pi$ to the surface at this point. Draw a plane parallel to
$\Pi$ cutting a part of the surface. We study the limiting behavior of this
part of surface when the plane approaches the point, being always parallel to
$\Pi$. More precisely, we study the limiting behavior of the normalized
surface area measure in $S^{d-1}$ induced by this part of surface. In this
paper we consider two cases: (a) when the point is regular and (b) when it is
singular conical, that is, the tangent cone at the point does not contain
straight lines. In the case (a) the limit is the atom located at the outward
normal vector to $\Pi$, and in the case (b) the limit is equal to the measure
induced by the part of the tangent cone cut off by a plane.

> Mathematics subject classifications: 52A20, 26B25

> Key words and phrases: convex surfaces, surface area measure of a convex
> body, Newton’s problem of minimal resistance

##  1 Introduction

Consider a convex compact set $C$ with nonempty interior in Euclidean space
${\mathbb{R}}^{d}$, $d\geq 2$. Let $r_{0}\in\partial C$ be a point on its
boundary, and let $\Pi$ be a plane of support to $C$ at $r_{0}$. Consider the
part of the boundary $\partial C$ containing $r_{0}$ and bounded by a plane
parallel to $\Pi$. We are interested in studying the limiting properties of
this part of boundary when the bounding plane approaches $\Pi.$

In what follows, a convex compact set with nonempty interior will be called a
convex body.

The point $r_{0}\in\partial C$ is called regular, if the plane of support at
this point is unique, and singular otherwise. It is well known that regular
points form a full-measure set in $\partial C$.

Let $e$ denote the outward unit normal vector to $\Pi$. Take $t>0$, and let
$\Pi_{t}$ be the plane parallel to $\Pi$ at the distance $t$ from it, on the
side opposite to the normal vector. Thus, the plane $\Pi=\Pi_{0}$ is given by
the equation $\langle{r}-{r}_{0},\,e\rangle=0$ and $\Pi_{t}$, by the equation
$\langle{r}-{r}_{0},\,e\rangle=-t$. The body $C$ is contained in the closed
half-space $\\{r:\langle r-r_{0},\,e\rangle\leq 0\\}$. Here and in what
follows, $\langle\cdot\,,\cdot\rangle$ means the scalar product.

Consider the convex body

$C_{t}=C\cap\\{{r}:\langle{r}-{r}_{0},\,e\rangle\geq-t\\}.$

In other words, $C_{t}$ is the part of $C$ cut off by the plane $\Pi_{t}$. The
boundary of $C_{t}$ is the union of the convex set of codimension 1

$B_{t}=C\cap\\{{r}:\langle{r}-{r}_{0},\,e\rangle=-t\\}$ (1)

and the convex surface

$S_{t}=\partial C\cap\\{{r}:\langle{r}-{r}_{0},\,e\rangle\geq-t\\};$ (2)

thus, $\partial C_{t}=B_{t}\cup S_{t}$.

In what follows, we will denote as $|\mathcal{A}|_{m}$ the $m$-dimensional
Hausdorff measure of the Borel set $\mathcal{A}\subset{\mathbb{R}}^{d}$. By
default, $|\cdot|$ means $|\cdot|_{d-1}$.

Let $n_{r}$ denote the outward unit normal to $C$ at a regular point
$r\in\partial C$, and let $S$ be a Borel subset of $\partial C$. The surface
area measure induced by $S$ is the Borel measure $\nu_{S}$ defined in
$S^{d-1}$ satisfying

$\nu_{S}(\mathcal{A}):=|\\{r\in S:n_{r}\in\mathcal{A}\\}|$

for any Borel subset $\mathcal{A}\subset S^{d-1}$. In the case when $S$
coincides with $\partial C$, we obtain the well-known measure $\nu_{\partial
C}$ called the surface area measure of the convex body $C$. For this measure
the following well-known relation takes place:

$\int_{S^{d-1}}n\,\nu_{\partial C}(dn)=\vec{0}.$ (3)

Denote by $\nu_{t}$ the normalized measure induced by the surface $S_{t}$;
more precisely,

$\nu_{t}:=\frac{1}{|B_{t}|}\,\nu_{S_{t}}.$

That is, for any Borel set $\mathcal{A}\subset S^{d-1}$ holds

$\nu_{t}(\mathcal{A})=\frac{1}{|B_{t}|}|\\{{r}\in
S_{t}:n_{r}\in\mathcal{A}\\}|.$

The surface area measure of $\partial C_{t}$ equals $\nu_{\partial
C_{t}}=|B_{t}|\delta_{-e}+|B_{t}|\nu_{t}$, hence

$\int_{S^{d-1}}n\,d\nu_{\partial
C_{t}}(n)=|B_{t}|(-e+\int_{S^{d-1}}n\,\nu_{t}(dn)).$

Here and in what follows, $\delta_{e}$ means the unit atom supported at $e$.
Applying formula (3) to $\partial C_{t}$, one obtains

$\int_{S^{d-1}}n\,\nu_{t}(dn)=e.$ (4)

We say that $\nu_{t}$ weakly converges to $\nu_{*}$ as $t\to 0$, and denote
$\lim_{t\to 0}\nu_{t}=\nu_{*}$, if for any continuous function $f$ on
$S^{d-1}$ holds

$\lim_{t\to
0}\int_{S^{d-1}}f(n)\,\nu_{t}(dn)=\int_{S^{d-1}}f(n)\,\nu_{*}(dn).$

Similarly, we say that $\nu_{*}$ is a weak partial limit of the measure
$\nu_{t}$, if there exists a sequence of positive numbers
$t_{i},\,i\in\mathbb{N}$ converging to 0 such that for any continuous function
$f$ on $S^{d-1}$ holds

$\lim_{i\to\infty}\int_{S^{d-1}}f(n)\,\nu_{t_{i}}(dn)=\int_{S^{d-1}}f(n)\,\nu_{*}(dn).$

In this article we are going to study the limiting properties of the measure
$\nu_{t}$ as $t\to 0$.

One such property is derived immediately. Let $\nu_{*}$ be a weak limit or a
weak partial limit of $\nu_{t}$. Passing to the limit $t\to 0$ or to the limit
$t_{i}\to 0$ in formula (4), one obtains

$\int_{S^{d-1}}n\,\nu_{*}(dn)=e.$ (5)

The tangent cone to $C$ at $r_{0}\in\partial C$ is the closure of the union of
all rays with vertex at $r_{0}$ that intersect $C\setminus r_{0}$.
Equivalently, the tangent cone at $r_{0}$ is the smallest closed cone with the
vertex at $r_{0}$ that contains $C$; see Fig. 1.

Figure 1: The tangent cone and the normal cone to a convex body $C$.

If the tangent cone at $r_{0}$ is a half-space then the point $r_{0}$ is
regular, and vice versa.

The normal cone to $C$ at $r_{0}$ is the union of all rays with vertex at
$r_{0}$ whose director vector is the outward normal to a plane of support at
$r_{0}$. It is denoted as $N(r_{0})$. An equivalent definition is the
following: the normal cone at $r_{0}$ is the set of points $r$ that satisfy
$\langle r-r_{0},\,r^{\prime}-r_{0}\rangle\leq 0$ for all $r^{\prime}\in C$.
The normal cone to a convex body does not contain straight lines. Both tangent
and normal cones are, of course, convex sets.

If the dimension of $N(r_{0})$ equals $d$ (equivalently, if the tangent cone
does not contain straight lines) then $r_{0}$ is called a conical point of
$C$. If the dimension of $N(r_{0})$ equals 1 then $r_{0}$ is regular, and vice
versa. In the intermediate case, that is, if the dimension of $N(r_{0})$ is
greater than 1 but smaller than $d$, $r_{0}$ is called a ridge point. This
notation goes back to Pogorelov [13].

The motivation for this study comes, to a great extent, from extremal problems
in classes of convex bodies and, in particular, from Newton’s problem of least
resistance for convex bodies [4]. It is natural to try to develop a geometric
method of small variation of convex bodies for such problems, and perhaps the
simplest way would be cutting a small part of the body by a plane. This method
proved itself to be effective in the case of Newton’s problem. Let us describe
this problem in some detains.

The problem in a class of radially symmetric bodies was first stated and
solved by Newton himself in 1687 in [9]. The more general version of the
problem was posed by Buttazzo and Kawohl in 1993 in [4]. This general problem
can be formulated in the functional form as follows:

> Find the smallest value of the functional
>
> $\int\\!\\!\\!\int_{\Omega}\frac{1}{1+|\nabla u(x,y)|^{2}}\,dxdy$ (6)
>
> in the class of convex functions $u:\Omega\to{\mathbb{R}}$ satisfying $0\leq
> u\leq M$, where $\Omega\subset{\mathbb{R}}^{2}$ is a planar convex body and
> $M>0$.

Physical meaning of this problem is as follows: find the optimal streamlined
shape of a convex body moving downwards through an extremely rarefied medium,
provided that the body-particle collisions are perfectly elastic.

Problem (6) (along with its further generalizations) has been studied in
various papers including [1, 2, 3, 5, 6, 7, 8, 10, 11, 14], but is not solved
completely until now.

It was conjectured in 1995 in [3] that the slope of the graph of an optimal
function near the zero level set $L_{0}=\\{(x,y):u(x,y)=0\\}$ equals 1. This
conjecture was numerically disproved by Wachsmuth111 Personal communication.
in the case when $L_{0}$ has empty interior, and therefore, is a line segment.
Moreover, numerical simulation shows that the infimum of $|\nabla u|$ in the
complement of $L_{0}$ is strictly greater than 1.

On the other hand, this conjecture was proved by the author in [12] in the
case when $L_{0}$ has nonempty interior. More precisely, it was proved that if
$u$ minimizes functional (6) then for almost all $(x,y)\in\partial L_{0}$
holds

$\lim_{(x^{\prime},y^{\prime})\,(\not\in L_{0})\to(x,y)}|\nabla
u(x^{\prime},y^{\prime})|=1.$

The proof is based on the results concerning local properties of convex
surfaces near ridge points in the case $d=3$. These results were formulated,
with the proofs being briefly outlined, in [12].

######  Remark 1.

The limiting behavior of $\nu_{t}$ in the case $d=2$ is quite simple. In this
case the tangent cone is an angle, which degenerates to a half-plane if the
point is regular. We will call it the tangent angle. Let the tangent angle to
$C\subset{\mathbb{R}}^{2}$ at $r_{0}$ be given by

$\langle{r}-{r}_{0},\,e_{1}\rangle\leq
0,\quad\langle{r}-{r}_{0},\,e_{2}\rangle\leq 0,\quad|e_{1}|=1,\ |e_{2}|=1,$

and $e$ be given by

$e=\lambda_{1}e_{1}+\lambda_{2}e_{2},\quad\lambda_{1}\geq 0,\ \lambda_{2}\geq
0,\quad|e|=1.$

Thus, $e_{1}$ and $e_{2}$ are the outward unit normals to the sides of the
angle, and $e$ is the outward unit normal to a line of support at $r_{0}$.
Then the limiting measure is the sum of two atoms

$\lim_{t\to 0}\nu_{t}=\lambda_{1}\delta_{e_{1}}+\lambda_{2}\delta_{e_{2}}.$

The proof of this relation is simple and is left to the reader.

Note that if the point $r_{0}$ is regular then $e_{1}=e_{2}=e$. It may also
happen that the point is singular, that is, $e_{1}\neq e_{2}$, and $e$
coincides with one of the vectors $e_{1}$ and $e_{2}$. In both cases the
limiting measure is an atom,

$\lim_{t\to 0}\nu_{t}=\delta_{e}.$

The limiting behavior of $\nu_{t}$ is different for different kinds of points.

(a) If the point $r_{0}$ is regular then the limiting measure is an atom.

(b) If $r$ is a conical point then the limiting measure coincides with the
measure induced by the part of the boundary of the tangent cone cut off by a
plane $\Pi_{t}$, $t=\sigma$ (note that all the induced measures with $t>0$ are
proportional).

(c) The case of ridge points is the most interesting. In this case the
limiting measure may not exist, and the characterization of all possible
partial limits is a difficult task.

Still, the study is nontrivial also in the cases (a) and (b). In this paper we
restrict ourselves to these cases, while the case (c) is postponed to the
future. The main results of the paper are contained in the following Theorems
1 and 2.

######  Theorem 1.

If $r_{0}$ is a regular point of $\partial C$ then

$\lim_{t\to 0}\nu_{t}=\delta_{e}.$ (7)

Let $r_{0}$ be a conical point, $K$ be the tangent cone at $r_{0}$,
$\hat{S}_{t}$ be the part of $\partial K$ containing $r_{0}$ cut off by the
plane $\Pi_{t}$, and $\hat{B}_{t}$ be the intersection of the cone wit the
cutting plane $\Pi_{t}$, $t>0$, that is,

$\hat{S}_{t}=\partial K\cap\\{r:\langle
r-r_{0},\,e\rangle\geq-t\\}\\!\quad\text{and}\\!\quad\hat{B}_{t}=K\cap\\{{r}:\langle{r}-{r}_{0},\,e\rangle=-t\\}.$

Let $K_{t}=K\cap\\{r:\langle r-r_{0},\,e\rangle\geq-t\\}$ be the part of the
cone cut off by the plane $\Pi_{t}$; its boundary is $\partial
K_{t}=\hat{S}_{t}\cup\hat{B}_{t}$.

All measures induced by ${\hat{S}_{t}}$ are proportional, that is, the measure

$\nu_{\star}:=\frac{1}{|\hat{B}_{t}|}\,\nu_{\hat{S}_{t}}$

does not depend on $t$.

######  Theorem 2.

If $r_{0}$ is a conical point of $\partial C$ then

$\lim_{t\to 0}\nu_{t}=\nu_{\star}.$ (8)

##  2 Proof of Theorem 1

The proof is based on several propositions.

Consider a convex set $D\subset{\mathbb{R}}^{d-1}$, and let $A=|D|$ be its
$(d-1)$-dimensional volume, and $P=|\partial D|_{d-2}$ be the
$(d-2)$-dimensional volume of its boundary.

######  Proposition 1.

If $D$ contains a circle of radius $a$ then

$P\leq\frac{d-1}{a}\,A.$ (9)

###### Proof.

Let $ds\subset\partial D$ be an infinitesimal element of the boundary of $D$,
and denote by $p(ds)$ its $(d-2)$-dimensional volume. Consider the pyramid
with the vertex at the center $O$ of the circle and with the base $ds$, that
is, the union of line segments joining $O$ with the points of $ds$. Let
$A(ds)$ be the element of $(d-1)$-dimensional volume of this pyramid; see Fig.
2.

Figure 2: The convex set $D$ containing a circle of radius $a$.

Then we have

$A(ds)\geq\frac{a}{d-1}\,p(ds),$

and therefore,

$A=\int_{\partial D}A(ds)\geq\frac{a}{d-1}\int_{\partial
D}p(ds)=\frac{a}{d-1}\,P.$

From here follows inequality (9). ∎

Consider Euclidean space ${\mathbb{R}}^{d}$ with the coordinates $(x,z)$,
$x=(x_{1},\ldots,x_{d-1})$, and fix $t>0$ and $0<\varphi<\pi/2$.

######  Proposition 2.

Let a convex body $C\subset{\mathbb{R}}^{d}$ be contained between the planes
$z=0$ and $z=t$, $t>0$. Let $D$ be the image of $C$ under the natural
projection of ${\mathbb{R}}^{d}$ on the $x$-plane, $(x,z)\mapsto x$, and let
$P=|\partial D|_{d-2}$ be the $(d-2)$-dimensional volume of $\partial D$. Let
a domain ${\cal U}\subset\partial C$ be such that the outward normal
$n_{r}=(n_{r,1},\ldots n_{r,d-1},n_{r,d})$ at each regular point $r\in{\cal
U}$ satisfies $|n_{r,d}|\leq\cos\varphi$. (In other words, the angles between
$n_{r}$ for $r\in{\cal U}$ and the vectors $\pm(0,\ldots,0,1)$ are
$\geq\varphi$.) Then

$|{\cal U}|\leq\frac{2tP}{\sin\varphi}.$

###### Proof.

The body $C$ is bounded below by the graph of a convex function, say $u_{1}$,
and above by the graph of a concave function, say $u_{2}$; see Fig. 3.

Figure 3: The body $C$ between two parallel planes $z=0$ and $z=t$ is shown.
Here ${\cal U}$ is represented by the union of two curves bounded by the
points.

Both functions are defined on $D$. That is, we have

$C=\\{(x,z):\,x\in D,\ u_{1}(x)\leq z\leq u_{2}(x)\\}.$

Let ${\cal U}_{i}$ $(i=1,\,2)$ denote the intersection of ${\cal U}$ with the
graph of $u_{i}$. Clearly, if a point $(x,u_{i}(x))$ is regular and belongs to
${\cal U}_{i}$ then $|\nabla u_{i}(x)|\geq\tan\varphi$.

For $0\leq z\leq t$ denote by $P_{z}$ the $(d-2)$-dimensional volume of the
set

$L_{z}=\\{x:\,u_{1}(x)=z\ \text{and}\ (x,u_{1}(x))\in{\cal U}_{1}\\}.$

One clearly has $P_{z}\leq P$. Let $s$ be the $(d-2)$-dimensional parameter in
$L_{z}$, and let $ds$ be the element of $(d-2)$-dimensional volume in $L_{z}$.
Denote by $x(z,s)$ the point in $L_{z}$ corresponding to the parameter $s$.
Then the $(d-1)$-dimensional volume of ${\cal U}_{1}$ equals

$|{\cal U}_{1}|=\int_{0}^{t}dz\int_{L_{z}}\sqrt{1+\frac{1}{|\nabla
u_{1}(x(z,s))|^{2}}}\,ds\leq\int_{0}^{t}P_{z}\sqrt{1+\cot^{2}\varphi}\,dz\leq\frac{tP}{\sin\varphi}.$

The same argument holds for ${\cal U}_{2}$. It follows that $|{\cal U}|=|{\cal
U}_{1}|+|{\cal U}_{2}|\leq 2tP/\sin\varphi$. ∎

######  Proposition 3.

If a convex set in ${\mathbb{R}}^{d-1}$ contains $d-1$ mutually orthogonal
line segments of length 1, then it also contains a ball of radius
$c=1/2(d-1)$.

###### Proof.

Denote the convex set by $D$, and the segments by $[A_{i}^{0},\,A_{i}^{1}]$,
$i=1,\ldots,d-1$. Since all points $A_{i}^{j}$ lie in $D$, each convex
combination of the form $P_{J}=\frac{1}{d-1}\sum_{i=1}^{d-1}A_{i}^{J(i)}$,
where $J$ denotes a map $\\{1,\ldots,d-1\\}\mapsto\\{0,1\\}$, also lies in
$D$. The convex combination of the set of points $P_{J}$ is a hypercube with
the size of length $1/(d-1)$, and contains the ball of the radius $1/2(d-1)$
with the center at the hypercube’s center. ∎

######  Proposition 4.

$B_{t}$ contains $d-1$ mutually orthogonal line segments of length
$\beta_{t}$, where $\beta_{t}/t\to\infty$ as $t\to 0$.

###### Proof.

Take a unit vector $e^{\prime}$ orthogonal to $e$ and consider the
2-dimensional plane $\Pi^{\prime}$ through $r_{0}$ parallel to $e$ and
$e^{\prime}$. The intersection $\Pi^{\prime}\cap C=:C^{\prime}$ is a
2-dimensional convex body, and $r_{0}$ is a regular point on its boundary; the
intersection $\Pi^{\prime}\cap\Pi_{t}=l^{\prime}_{t}$ is a line orthogonal to
$e$ at the distance $t$ from $r_{0}$; and the intersection $\Pi^{\prime}\cap
B_{t}$ is a line segment (maybe degenerating to a point or the empty set).
Equivalently, this segment is the intersection of the body $C^{\prime}_{t}$
with the line $l^{\prime}_{t}$. Since the point $r_{0}\in\partial C^{\prime}$
is regular, we conclude that the length of this segment $\beta^{\prime}_{t}$
satisfies $\beta^{\prime}_{t}/t\to\infty$ as $t\to 0$.

Now choose unit vectors $e_{1},\ldots,e_{d-1}$ in such a way that the set of
vectors $e_{1},\ldots,e_{d-1},e$ forms an orthonormal system in
${\mathbb{R}}^{d}$. For each $i=1,\ldots,d-1$ draw the 2-dimensional plane
$\Pi^{i}$ through $r_{0}$ parallel to $e$ and $e_{i}$. The intersections
$\Pi^{i}\cap B_{t}$ are line segments parallel to $e_{i}$, and therefore, they
are mutually orthogonal. The lengths of these segments $\beta^{i}_{t}$ satisfy
$\beta^{i}_{t}/t\to\infty$ as $t\to 0$. Taking $\beta_{t}=\min_{1\leq i\leq
d-1}\beta^{i}_{t}$, one comes to the statement of the proposition. ∎

Recall that $S_{t}$ is the intersection of $\partial C$ with the half-space
$\\{r:\,\langle r-r_{0},\,e\rangle\geq-t\\}$ and $\Pi_{t}$ is the plane of the
equation $\langle{r}-{r}_{0},\,e\rangle=-t$. For $\varphi\in(0,\,\pi/2)$
denote by $S_{t,\varphi}$ the part of $S_{t}$ containing the regular points
$r$ satisfying $\langle n_{r},\,e\rangle\leq\cos\varphi$. In other words,
$S_{t,\varphi}$ is the set of regular points $r$ in $S_{t}$ such that the
angle between $e$ and $n_{r}$ is greater than or equal to $\varphi$.

######  Proposition 5.

We have

$\frac{|S_{t,\varphi}|}{|B_{t}|}\to 0\quad\text{as}\ \,t\to 0.$

###### Proof.

Consider a coordinate system $(x,z)$, $x=(x_{1},\ldots,x_{d-1})$ such that the
$x$-plane coincides with $\Pi_{t}$ and the $z$-axis is directed toward the
vector $e$. For $t_{0}>0$ sufficiently small, the intersection of $\Pi_{t}$
and the interior of $C$ is nonempty for all $t\leq t_{0}$. The angle between
$-e$ and the outward normal at each regular point of $S_{t}$, $t\leq t_{0}$ is
greater that a positive value $\varphi_{0}$. That is, for any regular point
$r\in S_{t}$ holds $\langle n_{r},\,e\rangle\geq-\cos\varphi_{0}$. Without
loss of generality one can take $\varphi<\varphi_{0}$, and then for all
regular points $r\in S_{t,\varphi}$ holds $|\langle
n_{r},\,e\rangle|\leq\cos\varphi$.

In the chosen coordinate system $C_{t}$ is contained between the planes $z=0$
and $z=t$. Denote by $D_{t}$ the image of $C_{t}$ under the natural projection
$(x,z)\mapsto x$. The domain $D_{t}$ contains $B_{t}$ and is contained in the
$(t\cot\varphi)$-neighborhood of $B_{t}$, hence its $(d-2)$-dimensional volume
does not exceed $P_{t}=|\partial B_{t}|_{d-2}+s_{d-2}(t\cot\varphi)^{d-2}$,
where $s_{d-2}=|S^{d-2}|_{d-2}$ means area of the $(d-2)$-dimensional unit
sphere.

Applying Proposition 2 to the body $C=C_{t}$ and the domain ${\cal
U}=S_{t,\varphi}$, one obtains

$|S_{t,\varphi}|\leq\frac{2tP_{t}}{\sin\varphi}=2t\,\frac{|\partial
B_{t}|_{d-2}+s_{d-2}(t\cot\varphi)^{d-2}}{\sin\varphi}.$

By Propositions 3 and 4, $B_{t}$ contains a ball of radius $c\beta_{t}$, and
therefore, by Proposition 1,

$|\partial B_{t}|_{d-2}\leq\frac{d-1}{c\beta_{t}}\,|B_{t}|$

and, additionally, $|B_{t}|\geq b_{d-1}(c\beta_{t})^{d-1}$, where $b_{d-1}$
means the volume of the unit ball in ${\mathbb{R}}^{d-1}$. Hence

$\frac{|S_{t,\varphi}|}{|B_{t}|}\leq
2t\frac{\frac{d-1}{c\beta_{t}}\,|B_{t}|+s_{d-2}(t\cot\varphi)^{d-2}}{\sin\varphi|B_{t}|}\leq\frac{2(d-1)}{c\sin\varphi}\,\frac{t}{\beta_{t}}+\frac{2s_{d-2}}{c\sin\varphi\,b_{d-1}}\,\frac{t}{\beta_{t}}\to
0\quad\text{as}\ \,t\to 0.$

∎

Let us now finish the proof of Theorem 1.

Recall that $\nu_{S}$ is the surface area measure induced by $S$. For all
$\varphi\in(0,\,\pi/2)$ one has

$\nu_{t}=\frac{1}{|B_{t}|}\,\nu_{S_{t,\varphi}}+\frac{1}{|B_{t}|}\,\nu_{S_{t}\setminus
S_{t,\varphi}}.$

Proposition 5 implies that the measure
$\frac{1}{|B_{t}|}\,\nu_{S_{t,\varphi}}$ converges to 0 as $t\to 0$. Indeed,
for any continuous function $f$ on $S^{d-1}$,

$\int_{S^{d-1}}f(n)\,\frac{1}{|B_{t}|}\,\nu_{S_{t,\varphi}}(dn)\leq\max|f|\,\frac{|S_{t,\varphi}|}{|B_{t}|}\to
0\quad\text{as}\ \,t\to 0.$

On the other hand, the measure $\frac{1}{|B_{t}|}\,\nu_{S_{t}\setminus
S_{t,\varphi}}$ is supported in the set in $S^{d-1}$ containing all points
whose radius vector forms the angle $\leq\varphi$ with $e$. It follows that
each partial limit of $\frac{1}{|B_{t}|}\,\nu_{S_{t}\setminus S_{t,\varphi}}$,
and therefore, each partial limit of $\nu_{t}$, are supported in this set.
Since $\varphi>0$ can be made arbitrary small, one concludes that each partial
limit of $\nu_{t}$ is proportional to $\delta_{e}$. Finally, utilizing
equality (5) true for each partial limit $\nu_{*}$, one concludes that the
limit of $\nu_{t}$ exists and is equal to $\delta_{e}$.

##  3 Proof of Theorem 2

In the proof we will use the well-known fact that the surface area measure is
continuous with respect to the Hausdorff topology in the space of convex
bodies.

More precisely, we say that a family of convex bodies $C_{t}$, $t>0$ in
${\mathbb{R}}^{d}$ converges to a convex body $C\subset{\mathbb{R}}^{d}$ as
$t\to 0$ in the sense of Hausdorff, and write $C_{t}\xrightarrow[t\to 0]{}C$,
if for any $\varepsilon>0$ there exists $t_{0}>0$ such that for all $t\leq
t_{0}$, $C_{t}$ is contained in the $\varepsilon$-neighborhood of $C$ and $C$
is contained in the $\varepsilon$-neighborhood of $C_{t}$.

It is well known that if $C_{t}\xrightarrow[t\to 0]{}C$, then $\nu_{\partial
C_{t}}\to\nu_{\partial C}$ as $t\to 0$.

Choose $\sigma>0$ so as $|\hat{B}_{\sigma}|=1$, and therefore,

$\nu_{\hat{S}_{\sigma}}=\nu_{\star}.$ (10)

Let the origin coincide with the point $r_{0}$, that is, $r_{0}=\vec{0}$; then
the homothety of a set $\mathcal{A}$ with the center at $r_{0}$ and ratio $k$
is $k\mathcal{A}$. See Fig. 4.

Figure 4: The tangent cone at $r_{0}$, the cutting planes $\Pi_{t}$ and
$\Pi_{\sigma}$, and the sets $B_{t}$, $B_{\sigma}$, and $\hat{B}_{\sigma}$ in
the case when the point $r_{0}$ is conical.

######  Proposition 6.

$\frac{\sigma}{t}B_{t}\xrightarrow[t\to 0]{}\hat{B}_{\sigma}$.

###### Proof.

Note that for all positive $t_{1}$ and $t_{2}$,

$\frac{t_{1}}{t_{2}}\,\Pi_{t_{2}}=\Pi_{t_{1}}\quad\text{and}\quad\frac{t_{1}}{t_{2}}\,\hat{B}_{t_{2}}=\hat{B}_{t_{1}}.$

Additionally, since the tangent cone $K$ contains $C$ then $\hat{B}_{t}$
contains $B_{t}$, and so,

$\frac{\sigma}{t}\,B_{t}\subset\frac{\sigma}{t}\,\hat{B}_{t}=\hat{B}_{\sigma}.$

Let now $0<t_{1}\leq t_{2}$. Since $\vec{0}$ and $B_{t_{2}}$ belong to $C$, so
does their linear combination,

$\frac{t_{1}}{t_{2}}\,B_{t_{2}}=\Big{(}1-\frac{t_{1}}{t_{2}}\Big{)}\vec{0}+\frac{t_{1}}{t_{2}}\,B_{t_{2}}\subset
C.$

On the other hand,
$\frac{t_{1}}{t_{2}}\,B_{t_{2}}\subset\frac{t_{1}}{t_{2}}\,\Pi_{t_{2}}=\Pi_{t_{1}}$.
It follows that $\frac{t_{1}}{t_{2}}\,B_{t_{2}}\subset
C\cap\Pi_{t_{1}}=B_{t_{1}}$. We conclude that

$\frac{\sigma}{t_{2}}\,B_{t_{2}}\subset\frac{\sigma}{t_{1}}\,B_{t_{1}},$

that is, $\frac{\sigma}{t}B_{t},\,t>0$ form a nested family of sets contained
in $\hat{B}_{\sigma}$.

Suppose that $\frac{\sigma}{t}B_{t}$ does not converge to $\hat{B}_{\sigma}$.
This implies that the closure of the union

$\overline{\bigcup_{t>0}\,\frac{\sigma}{t}B_{t}}=:\tilde{B}_{\sigma}$

is contained in, but does not coincide with, $\hat{B}_{\sigma}$.

The union

$\bigcup\limits_{t>0}\,\frac{t}{\sigma}\tilde{B}_{\sigma}=:\tilde{K}$

is a cone with the vertex at $r_{0}$; it is contained in the tangent cone $K$,
but does not coincide with it. On the other hand,

$C=\bigcup_{t\geq 0}\,B_{t}\subset\bigcup_{t\geq
0}\,\frac{t}{\sigma}\tilde{B}_{\sigma}=\tilde{K};$

that is, $C$ is contained in the cone $\tilde{K}$, which is smaller than the
tangent cone $K$. This contradiction proves our proposition. ∎

From Proposition 6 follows, in particular, that

$\lim_{t\to 0}\Big{|}\frac{\sigma}{t}B_{t}\Big{|}=|\hat{B}_{\sigma}|=1,$ (11)

and therefore,

$\nu_{\frac{\sigma}{t}B_{t}}=\Big{|}\frac{\sigma}{t}B_{t}\Big{|}\delta_{-e}\longrightarrow|\hat{B}_{\sigma}|\delta_{-e}=\nu_{\hat{B}_{\sigma}}\quad\text{as}\
\,t\to 0.$ (12)

Denote

$\Sigma^{t}_{\sigma}:=\text{conv}\Big{(}\frac{\sigma}{t}\,B_{t}\cup
r_{0}\Big{)}.$

Since the convex body $\frac{\sigma}{t}\,C_{t}$ contains both $r_{0}$ and
$\frac{\sigma}{t}\,B_{t}$, we have
$\Sigma^{t}_{\sigma}\subset\frac{\sigma}{t}\,C_{t}.$

Recall that $K_{\sigma}$ is the part of the tangent cone cut off by the plane
$\Pi_{\sigma}$. We have $K_{\sigma}=\text{conv}(\hat{B}_{\sigma}\cup r_{0})$.
Since by Proposition 6, $\frac{\sigma}{t}B_{t}\xrightarrow[t\to
0]{}\hat{B}_{\sigma}$, we conclude that
$\text{conv}\big{(}\frac{\sigma}{t}\,B_{t}\cup r_{0}\big{)}\xrightarrow[t\to
0]{}\text{conv}(\hat{B}_{\sigma}\cup r_{0})$, that is,

$\Sigma^{t}_{\sigma}\xrightarrow[t\to 0]{}K_{\sigma}.$

Using this relation and the double inclusion

$\Sigma^{t}_{\sigma}\subset\frac{\sigma}{t}\,C_{t}\subset K_{\sigma},$

one concludes that $\frac{\sigma}{t}\,C_{t}$ converges to $K_{\sigma}$ in the
sense of Hausdorff, and therefore,

$\nu_{\frac{\sigma}{t}\partial C_{t}}\to\nu_{\partial
K_{\sigma}}\quad\text{as}\quad t\to 0.$

Using that $\frac{\sigma}{t}\partial
C_{t}=\frac{\sigma}{t}S_{t}\cup\frac{\sigma}{t}B_{t}$ and $\partial
K_{\sigma}=\hat{S}_{\sigma}\cup\hat{B}_{\sigma}$ and using (12), one obtains

$\nu_{\frac{\sigma}{t}S_{t}}\to\nu_{\hat{S}_{\sigma}}\quad\text{as}\quad t\to
0,$

and taking account of (11), one gets

$\lim_{t\to 0}\nu_{t}=\lim_{t\to
0}\frac{1}{|B_{t}|}\,\nu_{S_{t}}=\frac{1}{\lim_{t\to
0}\big{|}\frac{\sigma}{t}B_{t}\big{|}}\,\lim_{t\to
0}\nu_{\frac{\sigma}{t}S_{t}}=\nu_{\hat{S}_{\sigma}}=\nu_{\star}.$

Theorem 2 is proved.

## Acknowledgements

This work was supported by the Center for Research and Development in
Mathematics and Applications (CIDMA) through the Portuguese Foundation for
Science and Technology (FCT), within projects UIDB/04106/2020 and
UIDP/04106/2020.

## References

  * [1] M. Belloni and B. Kawohl. A paper of Legendre revisited. Forum Math. 9, 655-668 (1997).
  * [2] F. Brock, V. Ferone and B. Kawohl. A symmetry problem in the calculus of variations. Calc. Var. 4, 593-599 (1996).
  * [3] G. Buttazzo, V. Ferone, B. Kawohl. Minimum problems over sets of concave functions and related questions. Math. Nachr. 173, 71–89 (1995).
  * [4] G. Buttazzo, B. Kawohl. On Newton’s problem of minimal resistance. Math. Intell. 15, 7–12 (1993).
  * [5] G. Buttazzo, P. Guasoni. Shape optimization problems over classes of convex domains. J. Convex Anal. 4, No.2, 343-351 (1997).
  * [6] M. Comte, T. Lachand-Robert. Newton’s problem of the body of minimal resistance under a single-impact assumption. Calc. Var. Partial Differ. Equ. 12, 173-211 (2001).
  * [7] T. Lachand-Robert and E. Oudet. Minimizing within convex bodies using a convex hull method. SIAM J. Optim. 16, 368-379 (2006).
  * [8] T. Lachand-Robert, M. A. Peletier. Newton’s problem of the body of minimal resistance in the class of convex developable functions. Math. Nachr. 226, 153-176 (2001).
  * [9] I. Newton. Philosophiae naturalis principia mathematica. (London: Streater) 1687.
  * [10] A. Plakhov. Billiards and two-dimensional problems of optimal resistance. Arch. Ration. Mech. Anal. 194, 349-382 (2009).
  * [11] A. Plakhov and D. Torres. Newton’s aerodynamic problem in media of chaotically moving particles. Sbornik: Math. 196, 885-933 (2005).
  * [12] A. Plakhov. On generalized Newton’s aerodynamic problem. Trans. Moscow Math. Soc. 82, 217-226 (2021).
  * [13] A. V. Pogorelov. Extrinsic geometry of convex surfaces. Providence, R.I.: American Mathematical Society (AMS). (1973).
  * [14] G. Wachsmuth. The numerical solution of Newton’s problem of least resistance. Math. Program. A 147, 331-350 (2014).