# Generalized permutahedra and optimal auctions

Michael Joswig and Max Klimm and Sylvain Spitz  Technische Universität Berlin,
Chair of Discrete Mathematics/Geometry;
Max-Planck Institute for Mathematics in the Sciences, Leipzig
<EMAIL_ADDRESS>Technische Universität Berlin, Discrete Optimization
<EMAIL_ADDRESS>
###### Abstract.

We study a family of convex polytopes, called SIM-bodies, which were
introduced by Giannakopoulos and Koutsoupias (2018) to analyze so-called
Straight-Jacket Auctions. First, we show that the SIM-bodies belong to the
class of generalized permutahedra. Second, we prove an optimality result for
the Straight-Jacket Auctions among certain deterministic auctions. Third, we
employ computer algebra methods and mathematical software to explicitly
determine optimal prices and revenues.

###### 2020 Mathematics Subject Classification:

91B03, (52B12, 68W30, 14T15)

Support by the Deutsche Forschungsgemeinschaft (DFG, German Research
Foundation) under Germany’s Excellence Strategy - The Berlin Mathematics
Research Center MATH+ (EXC-2046/1, project ID 390685689) gratefully
acknowledged. M. Joswig has further been supported by Symbolic Tools in
Mathematics and their Application (TRR 195, project-ID 286237555); Facets of
Complexity (GRK 2434, project-ID 385256563).

##  1\. Introduction

The design of auctions that maximize the revenue of a seller is a central
question of economic theory. In the basic model, there is a single item and a
set of buyers interested in obtaining the item from the seller. Every buyer
individually holds a private value, which is the maximal price that they are
willing to spend in order to receive the item. The exact valuation of a buyer
is unknown to both the seller and the other buyers, but it is drawn from a
probability distribution that is common knowledge. In this setting, a
_mechanism_ (or auction) is a procedure that governs how the seller elicits
information from the buyers regarding their private valuations and decides to
whom to sell the item at which price. The seller seeks to maximize their
expected revenue, i.e., the price received from the successful buyer. The
mathematical properties of auctions in these settings are at the heart of two
Nobel Memorial Prizes in Economics. Vickrey [32] received the price in 1996
for showing that many popular auction formats give the same revenue to the
seller, and Myerson [25] received the prize in 2007 for a precise
characterization of the revenue-maximizing auction.

While auctions for selling a single item are reasonably well understood, the
case where multiple items are for sale is much more challenging due to the
underlying combinatorics of the problem. The main difficulty is to decide
which subset of items (or randomizations thereof) to sell to the buyer. It has
been observed that even in the simplest case of a single buyer whose valuation
for the items is additive, the optimal auction may be randomized [12, 30] and
may even require randomization among an uncountable set of allocations [13].
Optimal auctions are also challenging from a computational point of view since
computing the optimal auction is $\mathsf{NP}$-hard for distributions of
support three [8] and $\mathsf{\\#P}$-hard in general [12]. There are two main
ways to deal with these complexities. The first one is to study suboptimal
auctions; this approach avoids the combinatorial complexity by selling only
all items or only a single item; see, e.g., [1, 18, 22]. The second one
considers specific distributions that allow to study the combinatorial
structure of the problem. Giannakopoulos and Koutsoupias [17] examined the
case where the valuation for each item is drawn from the uniform distribution
and devise a deterministic auction, called _Straight-Jacket Auction (SJA)_. As
their main result, Giannakopoulos and Koutsoupias showed that SJA is optimal
for up to to six items [17, Theorem 4.8].

Giannakopoulos and Koutsoupias recognized that crucial properties of SJA are
expressed in terms of certain convex polytopes and their volumes; in [17]
these polytopes were called _SIM-bodies_ ; yet they previously occurred as
“$Q$-polytopes” in work of Doker [14, §2.4]. The SIM-bodies form our point of
departure, and we derive crucial structural information. Most notably, these
turn out to be generalized permutahedra; this is our Theorem 9. Generalized
permutahedra were introduced by Postnikov [26], and they received considerable
attention in the algebraic combinatorics community and beyond. Moreover,
generalized permutahedra are most tightly related to submodular functions,
polymatroids and $M$-convexity studied in optimization; see Frank and Murota
[15] for a survey. For instance, generalized permutahedra already occur as
“cores of cooperative games” in work of Danilov and Koshevoy [11, Proposition
5]. As our main theoretical contribution, in Theorem 17, we prove a general
uniqueness result for submodular and deterministic auctions. This leads us to
proving the optimality of SJA for any number of items, but for a restricted
choice of auctions, and subject to a technical condition (Corollary 25). The
existence of such auctions is far from obvious; in fact, the article [17] left
open if SJA exists for $n\geq 7$ items. A SIM-body arises as that portion of
the domain of the utility of the buyer where no bundle is sold. Equivalently,
SIM-bodies can be described as regions of tropical hypersurfaces induced by
the utilities. In this sense our present work is in line with recent efforts
to employ methods from tropical geometry to topics in mechanism design [3, 31,
10, 19].

The rest of our paper is devoted to actually computing the SJA-prices and
their revenues. Our method builds on a new parametric volume formula for SIM-
bodies, Proposition 34, which we derive from a general algorithm of Lawrence
[21]. We exploit that this method for computing the volume of a convex
polytope is particularly nice for (rational) polytopes whose normal fans are
smooth in the sense of toric geometry. An $n$-dimensional SIM-body depends on
$n$ parameters, which are real numbers corresponding to the prices of the $n$
items in the auction;. The normalized volume is an integral homogeneous
polynomial of degree $n$ in these $n$ parameters. Computing the SJA-prices
then amounts to finding real roots of a system of $n$ polynomials equations in
$n$ indeterminates and testing submodularity conditions (which yield linear
inequalities). In this way, we establish the existence of SJA for $n\leq 12$
items by computations using polymake [16] and HomotopyContinuation.jl [6].
Furthermore, it turns out that a certain linear substitution of the volume
polynomials of the SIM-bodies gives Lorentzian polynomials [4].

### Acknowledgments

We are grateful to Katharina Jochemko for pointing out [11].

##  2\. SIM-bodies

Our approach to studying auctions is primarily geometric and algorithmic. To
this end it is useful to begin with certain classes of (convex) polytopes. We
refer to [33] and [20] for the basics of polyhedral geometry and related
algorithms.

The _permutahedron_ ${\mathcal{P}}_{n+1}(\alpha_{1},\dots,\alpha_{n+1})$ is
the convex hull of all $(n+1)!$ points which arise from coordinate
permutations of $(\alpha_{1},\dots,\alpha_{n+1})$, and the parameters
$\alpha_{i}$ are arbitrary real numbers. By construction the symmetric group
$\operatorname{Sym}(n+1)$ of degree $n+1$ operates on
${\mathcal{P}}_{n+1}(\alpha_{1},\dots,\alpha_{n+1})$ by linear automorphisms.
Examples include the _regular permutahedron_
${\mathcal{P}}_{n+1}(n,n-1,\dots,0)$ and the _hypersimplex_
$\Delta(k,n)={\mathcal{P}}_{n}(1,\dots,1,0,\dots,0)$, with $k$ ones and $n-k$
zeros. The following is an $H$-description of permutahedra, which is known;
see [26, Proposition 2.5], where that result is attributed to Rado [27].

######  Lemma 1.

For $\alpha_{1}\geq\cdots\geq\alpha_{n+1}$ we have

$\begin{split}{\mathcal{P}}_{n+1}(&\alpha_{1},\dots,\alpha_{n+1})\\\ \ &=\
\biggl{\\{}x\in{\mathbb{R}}^{n+1}\biggm{|}\sum_{i=1}^{n+1}x_{i}=\bar{\alpha}\,,\
\sum_{i\in I}x_{i}\leq\alpha_{1}+\dots+\alpha_{k}\text{ for
}I\in\tbinom{[n+1]}{k}\,,\ k\geq 1\biggr{\\}}\enspace,\\\ \end{split}$

where $\bar{\alpha}:=\sum\alpha_{i}$.

Throughout we abbreviate $[n]=\\{1,2,\dots,n\\}$, and we write
$\tbinom{[n]}{k}$ for the set of $k$-element subsets of $[n]$. A key
construction comes from considering a map $z$ that assigns each nonempty
subset $I\subseteq[n+1]$ a real number $z_{I}$. Following Postnikov [26, §6]
this gives rise to the polyhedron

(1) ${\mathcal{P}}_{n+1}\\{z\\}\ =\
\biggl{\\{}x\in{\mathbb{R}}^{n+1}\biggm{|}\sum_{i=1}^{n+1}x_{i}=z_{[n+1]}\,,\
\sum_{i\in I}x_{i}\leq z_{[n+1]}-z_{I^{c}}\text{ for }\emptyset\neq
I\subseteq[n+1]\biggr{\\}}\enspace,$

where $I^{c}=[n+1]\setminus I$ is the complement of $I$ in $[n+1]$.

######  Example 2.

For $z_{I}=\alpha_{n+2-k}+\dots+\alpha_{n+1}$ with $k=\\#I$ we recover the
permutahedron
${\mathcal{P}}_{n+1}(\alpha_{1},\dots,\alpha_{n+1})={\mathcal{P}}_{n+1}\\{z\\}$.

Now we pick a fixed weakly descending sequence of $n$ nonnegative real numbers
$\alpha_{1}\geq\cdots\geq\alpha_{n}\geq 0$. Specializing (1) by letting

(2) $z_{I}\ =\ \begin{cases}\sum_{i=1}^{\\#I-1}\alpha_{n+1-i}&\text{ if
}n+1\in I\\\ 0&\text{ otherwise}\enspace,\end{cases}$

we obtain the polyhedron
$\Gamma(\alpha_{1},\dots,\alpha_{n}):={\mathcal{P}}_{n+1}\\{z\\}$. Observe
that $z_{[n+1]}=\alpha_{1}+\dots+\alpha_{n}=\bar{\alpha}$. Moreover, we define
$\Lambda(\alpha_{1},\dots,\alpha_{n})$ as the orthogonal projection of
$\Gamma(\alpha_{1},\dots,\alpha_{n})$ gotten by omitting the last coordinate.
As the polyhedron $\Gamma(\alpha_{1},\dots,\alpha_{n})$ is contained in the
affine subspace $\sum_{i=1}^{n+1}x_{i}=\bar{\alpha}$, the orthogonal
projection $\Lambda(\alpha_{1},\dots,\alpha_{n})$ is a polyhedron in
${\mathbb{R}}^{n}$ which is affinely isomorphic.

######  Proposition 3.

For $\alpha_{1}\geq\cdots\geq\alpha_{n}\geq 0$ we have

$\Lambda(\alpha_{1},\dots,\alpha_{n})\ =\ \biggl{\\{}x\in{\mathbb{R}}_{\geq
0}^{n}\biggm{|}\sum_{i\in I}x_{i}\leq\alpha_{1}+\dots+\alpha_{k}\text{ for
}I\in\tbinom{[n]}{k}\text{ and }k\geq 1\biggr{\\}}\enspace,$

###### Proof.

Let $\pi:{\mathbb{R}}^{n+1}\to{\mathbb{R}}^{n}$ be the projection which omits
the last coordinate, and let $z_{I}$ be defined for nonempty $I\subseteq[n+1]$
as in (2). Applying one Fourier–Motzkin step yields

$\pi\bigl{(}P_{n+1}\\{z_{I}\\}\bigr{)}\ =\
\biggl{\\{}x\in{\mathbb{R}}^{n}\biggm{|}z_{I}\leq\sum_{i\in
I}x_{i}\leq\bar{\alpha}-z_{I^{c}}\text{ for }\emptyset\neq
I\subseteq[n]\biggr{\\}}\enspace,$

where $I^{c}=[n+1]\setminus I$. This gives the claim. ∎

Proposition 3 says that $\Lambda(\alpha_{1},\dots,\alpha_{n})$ is a _SIM-body_
in the sense of Giannakopoulos and Koutsoupias [17, Definition 4.6]. However,
note that our parameters $\alpha_{i}$ are descending, whereas they are chosen
ascending in [17]. This deviation is suggested by aligning with Postnikov’s
notation [26]. The following is a $V$-description of the SIM-bodies.

$x_{1}$$x_{2}$$\alpha_{1}$$\alpha_{1}$$(\alpha_{1},\alpha_{2})$$(\alpha_{2},\alpha_{1})$

$x_{1}$$x_{2}$$x_{3}$$\alpha_{1}$$\alpha_{1}$$\alpha_{1}$$v$

Figure 1. SIM-bodies $\Lambda(\alpha_{1},\alpha_{2})$ and
$\Lambda(\alpha_{1},\alpha_{2},\alpha_{3})$. The vertex labeled $v$ in the
right picture has the coordinates $(\alpha_{1},\alpha_{2},\alpha_{3})$. Note
that the faces of the SIM-body, which are normal to the coordinate directions,
are also SIM-bodies. This property of SIM-bodies and more were shown in [17,
Lemma 6.1].

######  Proposition 4.

For $\alpha_{1}\geq\cdots\geq\alpha_{n}\geq 0$ we have

$\Lambda(\alpha_{1},\dots,\alpha_{n})\ =\
\operatorname{conv}\left\\{\bigcup_{k=0}^{n}{\mathcal{P}}_{n}(\alpha_{1},\dots,\alpha_{k},0,\dots,0)\right\\}\enspace.$

Moreover, if $\alpha_{1}>\cdots>\alpha_{n}>0$, those points form the pairwise
distinct vertices.

###### Proof.

A direct inspection shows that the points
$(\alpha_{1},\dots,\alpha_{k},0,\dots,0)$ and their permutations are feasible.
Assume $\alpha_{1}>\cdots>\alpha_{n}>0$. Then
$(\alpha_{1},\dots,\alpha_{k},0,\dots,0)$ is a vertex of
$\Lambda(\alpha_{1},\dots,\alpha_{n})$ because it is the only feasible point
that maximizes the linear objective function
$(\alpha_{1},\dots,\alpha_{k},-1,\dots,-1)$. If the parameters $\alpha_{i}$
are not pairwise distinct, the claim follows from the generic case by
continuity. ∎

######  Example 5.

For instance, for $\alpha_{1}>\alpha_{2}>0$ the $2$-dimensional SIM-body

$\Lambda(\alpha_{1},\alpha_{2})\ =\
\operatorname{conv}\bigl{\\{}(0,0),\,(\alpha_{1},0),\,(0,\alpha_{1}),\,(\alpha_{1},\alpha_{2}),\,(\alpha_{2},\alpha_{1})\bigr{\\}}$

is a convex pentagon, which resembles a SIM-card used to authenticate
subscribers on mobile phones; hence the name. In the telecommunication context
the term “SIM” is short for “subscriber identity module”.

There are several immediate consequences of Proposition 4. Recall that
_normally equivalent_ polytopes, by definition, share the same normal fan. In
particular, such polytopes are affinely (and thus combinatorially) isomorphic.

######  Corollary 6.

Let $\alpha_{1}\geq\cdots\geq\alpha_{n}\geq 0$.

  1. (a)

The SIM-body $\Lambda(\alpha_{1},\dots,\alpha_{n})$ is bounded; i.e., it is a
polytope;

  2. (b)

that polytope is integral if and only if all parameters $\alpha_{i}$ are
integers;

  3. (c)

we have $\dim\Lambda(\alpha_{1},\dots,\alpha_{n})=n$ if and only if
$\alpha_{1}>0$;

  4. (d)

for pairwise distinct parameters $\alpha_{i}$ the SIM-body
$\Lambda(\alpha_{1},\dots,\alpha_{n})$ is normally equivalent to
$\Lambda(n,n-1,\dots,1)$;

  5. (e)

the linear automorphism group of $\Lambda(n,n-1,\dots,1)$ is the symmetric
group $\operatorname{Sym}(n)$, and it has precisely $n+1$ vertex orbits;

  6. (f)

the number of vertices of $\Lambda(n,n-1,\dots,1)$ equals
$\sum_{k=0}^{n}n!/k!$.

For $\alpha_{1}>\cdots>\alpha_{n}>0$ we call
$\Lambda(\alpha_{1},\dots,\alpha_{n})$ a _proper_ SIM-body of _(permutation)
degree_ $n$. By Corollary 6(d), there is only one combinatorial type of proper
SIM-bodies for each degree. That is, for combinatorial purposes it suffices to
study the _regular_ SIM-body $\Lambda_{n}:=\Lambda(n,n-1,\dots,1)$ of rank
$n$. The sequence $a(n):=\sum_{k=0}^{n}n!/k!$ from Corollary 6(f), which gives
the number of vertices of $\Lambda_{n}$, occurs as A000522 in the On-Line
Encyclopedia of Integer Sequences [29]. The regular SIM-body $\Lambda_{n}$
occurs as “$Q_{n}$” in the work of Doker [14, §2.4]; general SIM-bodies are
special cases of _$Q$ -polytopes_ in [14].

######  Example 7.

For the most part we will focus on proper SIM-bodies, but there are some
interesting special cases which are not proper. For instance,
$\Lambda(1,1,\dots,1)=[0,1]^{n}$ is the unit cube, and
$\Lambda(1,0,\dots,0)=\operatorname{conv}\\{0,e_{1},e_{2},\dots,e_{n}\\}$ is
the standard simplex.

Next we will show that the $H$-description of
$\Lambda(\alpha_{1},\dots,\alpha_{n})$ from Proposition 3 is nonredundant if
the SIM-body is proper. Moreover, we will determine the vertex-facet
incidences. Any nonempty set $I\subseteq[n]$ yields the inequality

(3) $\sum_{i\in I}x_{i}\ \leq\ \alpha_{1}+\dots+\alpha_{k}\enspace.$

Consider the vertex $v:=(\alpha_{1},\dots,\alpha_{\ell},0,\dots,0)$ of
$\Lambda(\alpha_{1},\dots,\alpha_{n})$. Then we say that the set $I$ with
$\\#I=k$ is _active_ at $v$ if the inequality (3) is tight at $v$, i.e.,

$\sum_{i\in I}v_{i}\ =\ \sum_{i\in I\cap[\ell]}\alpha_{i}\ =\
\alpha_{1}+\dots+\alpha_{k}\enspace,$

or equivalently $I\cap[\ell]=[k]$. The latter holds if and only if

(4) $k\leq\ell\quad\text{and}\quad I=[k]\enspace.$

######  Lemma 8.

A proper SIM-body is a simple polytope, and it has exactly $2^{n}+n-1$ facets.

###### Proof.

Let $\alpha_{1}>\cdots>\alpha_{n}>0$. Then the SIM-body
$\Lambda:=\Lambda(\alpha_{1},\dots,\alpha_{n})$ is $n$-dimensional. We need to
show that each vertex is incident with exactly $n$ facets. As in our previous
deliberations we consider the vertex
$v:=(\alpha_{1},\dots,\alpha_{\ell},0,\dots,0)$. From (4) we obtain exactly
$\ell$ active sets at $v$. These contribute the same number of inequalities
like (3) which are tight at $v$. Additionally, exactly the last $n-\ell$
nonnegativity constraints are tight at $v$. The facet count results from
$2^{n}-1$ nonempty active sets and $n$ nonnegativity constraints. ∎

We are now able to prove our main result about the geometry of SIM-bodies.

######  Theorem 9.

Let $\alpha_{1}\geq\cdots\geq\alpha_{n}\geq 0$. Then each edge of the
homogeneous SIM-body $\Gamma(\alpha_{1},\dots,\alpha_{n})$ is parallel to the
difference of two standard basis vectors.

A polytope with that property is called a _generalized permutahedron_ [26].

###### Proof.

First, consider the special case where $\alpha_{k}=n-k+1$ for $k\in[n]$; i.e.,
$\Gamma_{n}:=\Gamma(n,n-1,\dots,1)$ is the regular homogeneous SIM-body of
rank $n$ in ${\mathbb{R}}^{n+1}$. We abbreviate
$\bar{\ell}:=\ell{+}1+\ell{+}2+\dots+n$. Then
$v:=(1,\dots,\ell,0,\dots,0,\bar{\ell})$ is a vertex of $\Gamma_{n}$. There
are $\ell$ active sets and $n-\ell$ (lifts of) nonnegativity constraints which
define the $n$ facets incident with $v$. Let $w$ be a vertex adjacent to $v$.
Then there are exactly $n-1$ facets incident to both vertices. Several cases
arise. For instance, it may happen that $\ell-1$ of the facets from sets
active at $v$ and all $n-\ell$ (lifts of) nonnegativity constraints are tight
at $w$. Then $w=(1,\dots,\ell{-}1,0,\dots,0,\overline{\ell{-}1})$, and
$v-w=\ell(e_{\ell}-e_{n+1})$. The same reasoning, with opposite signs, applies
if the number of active sets increases when we walk from $v$ to $w$. It
remains to discuss the situation when the number of facets from active sets
incident with $v$ and $w$ is the same. This occurs if and only if $v$ and $w$
lie in the same orbit of the action of $\operatorname{Sym}(n)$. From
Proposition 4 we see that these vertices form the vertices of the
permutahedron ${\mathcal{P}}_{n}(n,\dots,\ell,0,\dots,0)$, after projection to
${\mathbb{R}}^{n}$. So in this case the claim follows from Lemma 1.

Now Corollary 6(d) proves the claim for an arbitrary SIM-body which is proper,
i.e., it satisfies $\alpha_{1}>\cdots>\alpha_{n}>0$. This leaves the
degenerate cases where some, or all, of the parameters coincide. Then some
edge lengths shrink to zero, but this does not affect the edge directions. ∎

##  3\. Optimal Deterministic Auctions

We now turn to our main topic. A single buyer is interested in buying $n$
items. The value of the buyer for item $i\in[n]$ is denoted by $x_{i}$ and
drawn from the uniform distribution on $[0,1]$. The value $x_{i}$ corresponds
to the amount of money the buyer is willing to spend in order to receive item
$i$ and is the private information of the buyer. A _direct revelation
mechanism_ is a tuple $M=(a,r)$ of functions $a:[0,1]^{n}\to[0,1]^{n}$ and
$r:[0,1]^{n}\to{\mathbb{R}}$. The mechanism elicits a bid vector
$x^{\prime}\in[0,1]^{n}$ from the buyer. It then sells to the buyer at a price
of $r(x^{\prime})$ the following lottery: For each item $i\in[n]$ the buyer
receives item $i$ with probability $a_{i}(x^{\prime})$ where the probabilities
for different items are independent of each other. We call a direct revelation
mechanism an _auction_. An auction is _deterministic_ if
$a(x^{\prime})\in\\{0,1\\}^{n}$ for all $x^{\prime}\in[0,1]^{n}$. The price
$r(x^{\prime})$ payed by the buyer is also called the _revenue_ of the
auction. The buyer is risk-neutral and has additive valuations, meaning that
their utility is equal to the expected value of the items received by the
mechanism minus the payment. Fixing a direct revelation mechanism $M=(a,r)$,
the utility of the buyer with valuation $x$ who bids $x^{\prime}$ is given by

$u(x^{\prime}\mid x)\ =\
-r(x^{\prime})+\sum_{i=1}^{n}a_{i}(x^{\prime})x_{i}\enspace.$

We impose the following two assumptions on the design space of direct
revelation mechanisms. First, we require that the buyer prefers to bid
according to their actual valuation vector $x$ over claiming any other bid
vector $x^{\prime}\neq x$. Bidding the true valuation is also called
_truthful_ bidding. A mechanism is called _incentive compatible_ if bidding
truthfully is an optimal strategy of the buyer, i.e.,

(IC) $u(x\mid x)\geq u(x^{\prime}\mid x)\quad\text{for all
$x,x^{\prime}\in[0,1]^{n}$}\enspace.$

Second, we require that the mechanism is _individually rational_. This
property (which is sometimes also called _voluntary participation_) requires
that for every realization $x$ of the buyers’ valuations, they are guaranteed
to leave the auction with a nonnegative utility when bidding truthfully.
Formally, the individual rationality constraint reads

(IR) $\displaystyle u(x\mid x)\geq 0\quad\text{for all
$x\in[0,1]^{n}$}\enspace.$

Let $u(x)=u(x\mid x)$ for all $x\in[0,1]^{n}$. Our goal is to design an
auction that maximizes the expected revenue under the constraints that the
auction is incentive compatible and individual rational, i.e., we are
interested in solving

$\displaystyle\sup\quad$ $\displaystyle{\mathbb{E}}[r(x)]$ s.t. $\displaystyle
a:[0,1]^{n}\to[0,1]^{n}\text{ and }r:[0,1]^{n}\to{\mathbb{R}}\enspace,$
$\displaystyle M=(a,r)\text{ satisfies \eqref{eq:IC} and
\eqref{eq:IR}}\enspace,$

where the expectation in the objective is taken over all draws of $x_{i}$ from
the uniform distribution in $[0,1]$. The following result of Rochet [28]
characterizes the set of mechanisms satisfying (IC) in terms of convexity.

######  Proposition 10.

The auction $M=(a,r)$ satisfies (IC) if and only if the utility $u(x)$ is
convex and differentiable almost everywhere with

$\displaystyle{\partial u(x)}/{\partial x_{i}}=a_{i}(x)\quad\text{ for all
$i\in[n]$ and almost all $x\in[0,1]^{n}$}\enspace.$

Proposition 10 allows to parameterize the space of all auctions satisfying
(IC) by the utility functions $u:[0,1]^{n}\to{\mathbb{R}}$ that they impose on
the buyer. The constraint that the auction is (IR) can then be incorporated by
requiring that $u:[0,1]^{n}\to{\mathbb{R}}_{\geq 0}$. Together with the
observation that $r(x)=\sum_{i=1}^{n}a_{i}(x)x_{i}-u(x)$, we obtain the
following optimization problem to determine a revenue maximizing auction
satisfying (IC) and (IR)

(5) $\displaystyle\sup$
$\displaystyle{\mathbb{E}}\Biggl{[}\sum_{i=1}^{n}{\partial u(x)}/{\partial
x_{i}}\ x_{i}\,-\,u(x)\Biggr{]}$ s.t. $\displaystyle
u:[0,1]^{n}\to{\mathbb{R}}_{\geq 0}\text{ is convex}\enspace,$ $\displaystyle
0\leq\frac{\partial u(x)}{\partial x_{i}}\leq 1\quad\text{ for all $i\in[n]$
and almost all $x\in[0,1]^{n}$}\enspace.$

For the following, let us assume that the primal solution is a deterministic
auction. Formally, let $\\{p_{I}\\}_{I\subseteq[n]}$ be a _price schedule_
where we require $p_{\emptyset}=0$. A price schedule defines a unique
deterministic auction where the buyer reports their valuation and is assigned
a subset $I\subseteq[n]$ of items that maximizes their utility which is the
valuation attached to the items contained in the set minus the price $p_{I}$
for set $I$. Consequently, the utility of the buyer for this auction is given
by the function

(6) $u(x)\ =\ \max\biggl{\\{}\sum_{i\in
I}x_{i}-p_{I}\biggm{|}I\subseteq[n]\biggr{\\}}\enspace,$

which is the evaluation of a $\max$-tropical polynomial of degree $n$. The set
of points in ${\mathbb{R}}^{n}$ where that maximum is attained at least twice
is the _tropical hypersurface_ ${\mathcal{T}}(u)$; see [23, §3.1] or [19,
§1.1]. This agrees with the set of points where the evaluation $x\mapsto u(x)$
is nondifferentiable. For any price schedule $\\{p_{I}\\}_{I\subseteq[n]}$,
the tropical hypersurface of $u$ subdivides the $n$-dimensional unit cube
$[0,1]^{n}$ into polytopes $\\{D_{I}\\}_{I\subseteq[n]}$ such that $D_{I}$ is
the set of valuations $x$ for which the maximum in (6) is attained at $I$.
Formally, we have

$D_{I}\ =\ \Biggl{\\{}x\in[0,1]^{n}\;\Bigg{|}\;\sum_{i\in
I}x_{i}-p_{I}\geq\sum_{j\in J}x_{j}-p_{J}\text{ for all
}J\subseteq[n]\setminus I\Biggr{\\}}\enspace.$

The polytopes $D_{I}$ are called the _regions_ of
$\\{p_{I}\\}_{I\subseteq[n]}$. In fact, they are the intersections of the unit
cube with the regions of linearity of the tropical hypersurface
${\mathcal{T}}(u)$.

$x_{1}$$x_{2}$$p_{\\{1\\}}$$1$$p_{\\{2\\}}$$1$$\bar{D}_{\\{2\\}}$$D_{\\{2\\}}^{2}$$\bar{D}_{\\{1\\}}$$D_{\\{1\\}}^{1}$$x_{1}+x_{2}=p_{\\{1,2\\}}$$D_{\emptyset}$$D_{\\{1\\}}$$D_{\\{2\\}}$$D_{\\{1,2\\}}$
Figure 2. Tropical hypersurface and regions of the mechanism with price
schedule $p_{\\{1\\}}=\frac{2}{3}$, $p_{\\{2\\}}=\frac{1}{2}$ and
$p_{\\{1,2\\}}=\frac{5}{6}$, which is submodular. If the valuation of the
buyer lies in $D_{I}$, their utility is maximized by buying the items in $I$.
The polytope $\bar{D}_{I}$ is the projection of $D_{I}$ onto the coordinates
in $I$, and $D_{I}^{i}$ is the intersection of $D_{I}$ with the facet
$x_{i}=1$ of the cube.

Manelli and Vincent [24] describe necessary conditions for the optimality of a
price schedule for an arbitrary distribution of the valuations. In the uniform
case their criterion [24, Theorem 1] says that an optimal price schedule
$\\{p_{I}\\}_{I\subseteq[n]}$ necessarily satisfies

(7) $\operatorname{vol}_{n}{D_{I}}\,-\,\frac{1}{n+1}\sum_{i\in
I}\operatorname{vol}_{n-1}{D_{I}^{i}}\ =\ 0$

for all $I\neq\emptyset$ with $\operatorname{vol}_{n}D_{I}>0$, where $x_{-i}$
skips the $i$-th coordinate of $x$, and $D_{I}^{i}=\\{x_{-i}\mid(1,x_{-i})\in
D_{I}\\}$ is the _$i$ -th upper boundary_ of the region $D_{I}$. The following
lemma says that $D_{I}^{i}$, which is defined via intersecting the region
$D_{I}$ with one facet of the unit cube, agrees with a full projection of
$D_{I}$ by leaving out the $i$-th coordinate.

######  Lemma 11.

Let $\\{p_{I}\\}_{I\subseteq[n]}$ be an arbitrary price schedule. Further, let
$x\in[0,1]^{n}$ and $I\subseteq[n]$ such that $x\in D_{I}$. Then $x_{-i}\in
D_{I}^{i}$ for all $i\in I$.

###### Proof.

Fixing $i\in I$ our goal is to show that $x^{\prime}:=(1,x_{-i})\in D_{I}$. As
$x\in D_{I}$, we have

$x_{i}+\sum_{j\in I\setminus\\{i\\}}x_{j}-p_{I}\ \geq\ \sum_{j\in
J}x_{j}-p_{J}$

for all $J\subseteq[n]$. If $i\notin J$ the left hand side of that inequality
increases if we exchange $x$ for $x^{\prime}$, whereas the right hand side
stays the same. Otherwise, if $i\in J$, we have:

$\sum_{j\in I}x^{\prime}_{j}-p_{I}\ =\ 1+(x_{i}-x_{i})+\sum_{j\in
I\setminus\\{i\\}}x_{j}-p_{I}\ \geq\ 1-x_{i}+\sum_{j\in J}x_{j}-p_{J}\ =\
\sum_{j\in J}x^{\prime}_{j}-p_{J}\enspace.$

In both cases we obtain $x^{\prime}\in D_{I}$. ∎

The deficiency condition (7) leads us to analyzing regions of positive volume.

######  Lemma 12.

Let $\\{p_{I}\\}_{I\subseteq[n]}$ be an arbitrary price schedule. Further, let
$I\subseteq[n]$ with $\operatorname{vol}_{n}D_{I}>0$. Then $p_{I}<p_{J}$ for
all $J\supsetneq I$.

###### Proof.

By definition $\operatorname{vol}_{n}D_{I}>0$ if and only if there exists
$x\in[0,1]^{n}$ such that

$\sum_{i\in I}x_{i}-p_{I}\ >\ \sum_{j\in J}x_{j}-p_{J}$

for all $I\neq J\subseteq[n]$. For $J\supsetneq I$ we have $\sum_{j\in
J}x_{j}\geq\sum_{i\in I}x_{i}$, whence we conclude $p_{I}<p_{J}$. ∎

Let $\pi_{I}$ be the projection onto the coordinates in $I\subseteq[n]$. The
next lemma shows a recursive property of deterministic auctions. Under the
condition that for a given bundle $I$ all regions of its sub-bundles
$J\subseteq I$ have positive volume, the projections of those regions only
depend on the prices of sub-bundles of $I$. This will be useful later, when we
want to compute certain price schedules.

######  Lemma 13.

Let $\\{p_{I}\\}_{I\subseteq[n]}$ be an arbitrary price schedule. Further, let
$I\subseteq[n]$ with $\operatorname{vol}_{n}D_{J}>0$ for all $J\subseteq I$.
Then

$\pi_{I}(D_{J})\ =\ \biggl{\\{}x\in[0,1]^{I}\biggm{|}\sum_{j\in
J}x_{j}-p_{J}\geq\sum_{j\in K}x_{j}-p_{K}\text{ for all }K\subseteq
I\biggr{\\}}\enspace.$

###### Proof.

Let $J$ be a subset of $I$. As in Lemma 11 we can check that for $x\in D_{J}$
also $(0,x_{-j})$ is contained in $D_{J}$ if $j\notin J$. This implies that
$\pi_{I}(D_{J})$ arises from $D_{J}\cap\left\\{x\mid x_{i}=0\text{ for
}i\notin I\right\\}$ by skipping coordinates. So let $x\in[0,1]^{n}$ with
$x_{i}=0$ for $i\notin I$. From Lemma 12 we get $p_{K\cap I}\leq p_{K}$ for
each $K\subseteq[n]$ and hence

$\sum_{j\in K}x_{j}-p_{K}\ \leq\ \sum_{j\in K\cap I}x_{j}-p_{K\cap
I}\enspace,$

which finishes the proof. ∎

We are particularly interested in the following special class of price
schedules. A price schedule $p$ is _submodular_ , if

(8) $p_{I\cup J}+p_{I\cap J}\ \leq\ p_{I}+p_{J}\enspace.$

for all $I,J\subseteq[n]$; see Figure 2 for an example with $n=2$ items. The
submodularity of a price schedule is a desirable property for the seller.
Namely, it prevents a buyer interested in the items in $I\cup J$ from first
buying $I$ and $J$ separately at prices $p_{I}$ and $p_{J}$ and then returning
the (duplicate) items in the intersection $I\cap J$ at price $p_{I\cap J}$,
instead of buying the set $I\cup J$ at price $p_{I\cup J}$ directly. For a
more comprehensive discussion see [24, Definition 4]. The regions of
submodular price schedules can be written as products of some of their
projections.

######  Lemma 14.

Let $\\{p_{I}\\}_{I\subseteq[n]}$ be a submodular price schedule. Then
$D_{I}=\pi_{I}(D_{I})\times\pi_{I^{c}}(D_{I})$ for all $I\subseteq[n]$ and
$I^{c}=[n]\setminus I$. Moreover,
$D_{I}^{i}=\pi_{I\setminus\\{i\\}}(\pi_{I}(D_{I}))\times\pi_{I^{c}}(D_{I})$
for all $i\in I$.

###### Proof.

The first claim has been proved by Vincent and Manelli [24, Lemma 2]. The
second claim then follows from Lemma 11. ∎

To simplify our notation, we abbreviate $\bar{D}_{I}=\pi_{I}(D_{I})$ and
$\bar{D}_{I}^{i}=\pi_{I\setminus\\{i\\}}(\pi_{I}(D_{I}))$. Let us further
define

$\delta_{n}(I)\ \coloneqq\
\operatorname{vol}_{\\#I}{\bar{D}_{I}}\,-\,\frac{1}{n+1}\sum_{i\in
I}\operatorname{vol}_{\\#I-1}{\bar{D}_{I}^{i}}\enspace.$

It is a consequence of Lemma 11 that $\delta_{n}([n])$, which agrees with the
left hand side of (7), is the _deficiency_ of $D_{[n]}$ with respect to
$\frac{1}{n+1}$ in the sense of [17, Definition 4.5]. The expected revenue for
given prices $p=\\{p_{I}\\}_{I\subseteq[n]}$ is

(9) $\operatorname{Rev}(p)\ =\
\sum_{I\subseteq[n]}p_{I}\cdot\operatorname{vol}_{n}D_{I}\enspace,$

and this depends smoothly on $p$.

######  Lemma 15.

Let $\\{p_{I}\\}_{I\subseteq[n]}$ be a submodular price schedule. Then the
partial derivative of the expected revenue with respect to $p_{I}$ is given as

${\partial\operatorname{Rev}(p)}/{\partial p_{I}}\ =\
\delta_{n}(I)\cdot\operatorname{vol}_{\\#I^{c}}\pi_{I^{c}}(D_{I})\enspace.$

###### Proof.

The statement follows from [24, Theorem 1] and Lemma 14; see Equation (7). ∎

Since we are interested in maximizing the revenue it is natural to analyze the
critical points of the revenue function. However, we also need to take care of
boundary effects. To this end we investigate bundles where the submodularity
condition (8) is attained with equality. If $p_{I\cup J}+p_{I\cap
J}=p_{I}+p_{J}$ we call $I\cup J$ and $I\cap J$ _left tight_ , while we call
$I$ and $J$ _right tight_. A bundle is _tight_ if it is left or right tight.
The following describes the necessary critical point conditions and may be
seen as a refinement of [24, Theorem 1] for uniform valuations and submodular
price schedules.

######  Proposition 16.

Let $\\{p_{I}\\}_{I\subseteq[n]}$ be a submodular price schedule which
maximizes the expected revenue among all submodular price schedules. Then we
have, for all $I\subseteq[n]$:

  1. (1)

If $I$ is not tight and $\operatorname{vol}_{n}D_{I}>0$, then
$\delta_{n}(I)=0$;

  2. (2)

if $I$ is not tight and $\operatorname{vol}_{n}D_{I}=0$, then
$\delta_{n}(I)\geq 0$;

  3. (3)

if $I$ is just left tight, then $\delta_{n}(I)\geq 0$;

  4. (4)

if $I$ is just right tight and $\operatorname{vol}_{n}D_{I}>0$, then
$\delta_{n}(I)\leq 0$.

If $I$ is right tight and $\operatorname{vol}_{n}D_{I}=0$, there is no
condition on $\delta_{n}(I)$. The same applies if $I$ is left tight as well as
right tight.

###### Proof.

First assume that $I\subseteq[n]$ is not tight. Then the prices involving $I$
are strictly submodular, i.e., (8) is strictly satisfied for all $J\neq I$.
Hence we can slightly increase or decrease $p_{I}$, without loosing the
submodularity. Suppose that $\operatorname{vol}_{n}D_{I}>0$. As $p$ is optimal
and using Lemma 15, this forces $\delta_{n}(I)=0$, which says that $p$ is a
critical point of the revenue function.

Now, if $I$ is not tight but $\operatorname{vol}_{n}D_{I}=0$ the volume of
$D_{I}$ (and thus the revenue) can only change if we decrease $p_{I}$. The
optimality of the prices entails $\delta_{n}(I)\geq 0$, again using Lemma 15.

We are left with the analysis of those bundles which are tight. So we consider
$I\neq J$ with $p_{I\cup J}+p_{I\cap J}=p_{I}+p_{J}$. Decreasing $p_{I\cup J}$
or $p_{I\cap J}$ keeps the submodularity. Therefore, as in the case
$\operatorname{vol}_{n}D_{I}=0$ above, we conclude $\delta_{n}({I\cup J})\geq
0$ and $\delta_{n}({I\cap J})\geq 0$. This takes care of the left tight sets.
For $I$ right tight with $\operatorname{vol}_{n}D_{I}>0$ the situation is
symmetric, but with opposite signs. ∎

Giannakopoulos and Koutsoupias [17] used a generalization of the deficiency
$\delta_{n}(I)$, which is a property of the region $D_{I}$, to arbitrary
subsets of $[0,1]^{n}$. In Proposition 16 we used the condition
$\operatorname{vol}_{n}D_{I}=0$. Note however, that if
$\operatorname{vol}_{n}D_{I}=0$ we can set $p_{I}$ arbitrarily high without
affecting the auction. Following [17, Section 6.2] a price schedule is
_normalized_ if $p_{I}=\min\left\\{p_{J}\mid J\supsetneq I\right\\}$, whenever
$\operatorname{vol}_{n}D_{I}=0$. This entails unique prices, and so price
schedules bijectively correspond to auctions. Throughout we assume that our
price schedules are normalized, unless stated otherwise.

A set of bundles ${\mathcal{I}}\subseteq 2^{[n]}$ is a _selling candidate_ for
$n$ items if, firstly, $[n]\in{\mathcal{I}}$, secondly, ${\mathcal{I}}$
contains all singletons, and, thirdly, for all
$I\in{\mathcal{I}}\setminus\\{[n]\\}$ and $J\subseteq I$ we have
$J\in{\mathcal{I}}$. That is to say, ${\mathcal{I}}\setminus\\{[n]\\}$ is an
abstract simplicial complex with vertex set $[n]$. In fact, that simplicial
complex can be seen geometrically embedded into the vertex figure of the
vertex ${\mathbf{1}}$ of the unit cube $[0,1]^{n}$, which is also a vertex of
the region $D_{[n]}$. We say that a price schedule
$\\{p_{I}\\}_{I\subseteq[n]}$ _admits_ a selling candidate ${\mathcal{I}}$ if
and only if $\operatorname{vol}_{n}D_{I}>0$ for all $I\in{\mathcal{I}}$.
Moreover, the price schedule is _critical_ with respect to ${\mathcal{I}}$ if
additionally $\delta_{n}(I)=0$ for all
$I\in{\mathcal{I}}\setminus\\{\emptyset\\}$. The following is our main
technical result; it complements [17, Lemma 6.5] and generalizes [17, Appendix
A] to nonsymmetric prices. Our proof is constructive; the special case of most
interest to us is spelled out as Algorithm 1 in Section 5.

######  Theorem 17.

For each selling candidate ${\mathcal{I}}$ there is at most one critical price
schedule which is submodular. Moreover, it satisfies $p_{I}=p_{J}$ whenever
$\\#I=\\#J$ and $I,J\in{\mathcal{I}}$.

###### Proof.

Let $I\in{\mathcal{I}}$, where ${\mathcal{I}}$ is a selling candidate for $n$
items. We seek to determine a price for the bundle $I$, and we will do so by
induction on the cardinality of $I$. Let $i\in I$, whence the singleton
$\\{i\\}$ is contained in ${\mathcal{I}}$. We set
$p_{\\{i\\}}=\tfrac{n}{n+1}$. Then, by Lemma 13,

(10) $\delta_{n}({\\{i\\}})\ =\
\operatorname{vol}_{1}(\bar{D}_{\\{i\\}})-\tfrac{1}{n+1}\operatorname{vol}_{0}(\bar{D}_{\\{i\\}}^{i})\
=\ (1-p_{\\{i\\}})-\tfrac{1}{n+1}\ =\ 0\quad\text{for all }i\in[n]\enspace.$

This computation also shows that $p_{\\{i\\}}$ is uniquely determined. This
case serves as the basis of the induction.

Now let $I\in{\mathcal{I}}$ with $\\#I\geq 2$, and assume that $p_{J}$ is
fixed for all $J\subsetneq I$ such that the following conditions are
satisfied: $\delta_{n}(J)=0$, $p_{J}=p_{J^{\prime}}$ whenever
$\\#J=\\#J^{\prime}$, and $\\{p_{J}\\}_{J\subsetneq I}$ is submodular. We will
now construct $p_{I}$ such that $\delta_{n}(I)=0$ and $\\{p_{J}\\}_{J\subseteq
I}$ is submodular, or decide that such a price $p_{I}$ doesn’t exist.

Since $p_{\\{i\\}}=\frac{n}{n+1}$ for all $i\in[n]$, we have $(1,x_{-i})\notin
D_{\emptyset}$ for all $x_{-i}\in[0,1]^{\\#I-1}$. Further, by Lemma 13 we know
that $\\{\pi_{I}(D_{J})\\}_{J\subseteq I}$ is a polyhedral complex supported
on $[0,1]^{I}$. Therefore we get

(11) $\sum_{\\{i\\}\subseteq J\subseteq
I}\operatorname{vol}_{\\#I-1}\pi_{I}(D_{J}^{i})\ =\ 1\enspace,$

for all $i\in I$. The last equation uses the fact that for $i\in I$ and
$J\subset I$ with $i\notin J$ we have $D_{J}^{i}=\emptyset$. This can be seen
as follows. Let $x\in[0,1]^{n}$ satisfying $x_{i}=1$. Then $x\in D_{J}^{i}$ if
and only if $J=\operatorname{arg\,max}\left\\{\sum_{i\in I}x_{i}-p_{I}\mid
I\subseteq[n]\right\\}$. But from the submodular inequality
$p_{\emptyset}+p_{J\cup\\{i\\}}\leq p_{\\{i\\}}+p_{J}$ and $p_{\\{i\\}}<1$, we
have $\sum_{j\in J}x_{j}-p_{J}<\sum_{j\in
J}x_{j}-(p_{J\cup\\{i\\}}-1)=\sum_{j\in J\cup\\{i\\}}x_{j}-p_{J\cup\\{i\\}}$.
Hence, $D_{J}^{i}=\emptyset$. Now, using (11) and the fact that
$\delta_{n}(J)=0$ for all $J\subsetneq I$, the condition $\delta_{n}(I)=0$ is
equivalent to

(12) $\sum_{\emptyset\neq J\subseteq
I}\operatorname{vol}_{\\#I}\pi_{I}(D_{J})\ =\ \sum_{\emptyset\neq J\subseteq
I}\frac{1}{n+1}\cdot\sum_{j\in
J}\operatorname{vol}_{\\#I-1}\pi_{I}(D_{J}^{j})\ =\ \frac{\\#I}{n+1}\enspace.$

From Lemma 13 we get
$\operatorname{vol}_{\\#I}\pi_{I}(D_{\emptyset})=1-\sum_{\emptyset\neq
J\subseteq I}\operatorname{vol}_{\\#I}\pi_{I}(D_{J})$. Hence (12) becomes

(13) $\operatorname{vol}_{\\#I}\pi_{I}(D_{\emptyset})\ =\
1-\frac{\\#I}{n+1}\enspace.$

Note that $\pi_{I}(D_{\emptyset})=\\{x\in[0,1]^{I}\mid\sum_{j\in J}x_{j}\leq
p_{J}\text{ for }J\subseteq I\\}$ due to Lemma 13. Since the prices $p_{J}$
are fixed for $J\subsetneq I$, the volume
$\operatorname{vol}_{\\#I}\pi_{I}(D_{\emptyset})$ depends differentiably on
the variable $p_{I}$. We define $\hat{p}_{I}$ to be the maximal value for
$p_{I}$, such that all submodularity conditions of the form

$p_{I}+p_{J\cap J^{\prime}}\ \leq\ p_{J}+p_{J^{\prime}}$

are satisfied for all $J,J^{\prime}\subseteq I$ with $J\cup J^{\prime}=I$.
Choosing $J,J^{\prime}$ such that $J\cap J^{\prime}=\emptyset$, we get

$\hat{p}_{I}\ \leq\ \max\biggl{\\{}\sum_{i\in
I}x_{i}\biggm{|}x\in[0,1]^{I}\text{ and }\sum_{j\in J}x_{j}\leq p_{J}\text{
for all }J\subsetneq I\biggr{\\}}\enspace.$

Therefore, the volume $\operatorname{vol}_{\\#I}\pi_{I}(D_{\emptyset})$ is
strictly increasing on the interval $[0,\hat{p}_{I}]$. Hence, there is at most
one solution to (13) in this interval. If there is no solution in this
interval, there can not be a price $p_{I}$ satisfying both $\delta_{n}(I)=0$
and the submodularity of $\\{p_{J}\\}_{J\subseteq I}$. On the other hand, if
the solution exists, it satisfies both properties by the way we defined it.
Further, since the computation of the solution does not depend on prices
$p_{J}$ for bundles $J$ of higher or equal cardinality than $I$, the solution
is the same for all $I^{\prime}$ with $\\#I^{\prime}=\\#I$. Note however, that
the solution for $p_{I}$, may be strictly lower than a price $p_{J}$ for some
$J\subseteq I$. In that case $D_{J}$ is empty, whence
$\operatorname{vol}_{\\#J}(D_{J})=0$, and there is no submodular critical
price schedule for the selling candidate ${\mathcal{I}}$.

For the case $I=[n]$ we assume that $p_{J}$ is fixed for all
$J\in{\mathcal{I}}\setminus\\{[n]\\}$ and we also fix $p_{J}=\\#J$ for all
$J\notin{\mathcal{I}}$. This way, $D_{J}=\emptyset$ for $J\notin{\mathcal{I}}$
and hence $\delta_{n}(J)=0$ is trivially satisfied. We have that
$\\{D_{J}\\}_{J\subseteq[n]}$ is a polyhedral complex supported on
$[0,1]^{n}$. Moreover, for $i\in[n]$ and $J\subset[n]$ with $i\notin J$, we
get $D_{J}^{i}=\emptyset$, since for $J\in{\mathcal{I}}$ the prices $p_{J}$
are submodular, and for $J\notin{\mathcal{I}}$ the statement is trivially
satisfied. Therefore (11) still holds and we can apply the rest of the proof
to $D_{[n]}$. In order to normalize the price schedule, we will redefine
$p_{J}=p_{n}$ for all $J\notin{\mathcal{I}}$. This does not change the region
$D_{\emptyset}$ whence the computation of $p_{n}$ stays consistent. ∎

######  Remark 18.

We call the candidate set ${\mathcal{I}}$ _solvable_ if there is a solution of
(13) in the interval $[0,\hat{p}_{I}]$ for each bundle $I\in{\mathcal{I}}$.
However, even if ${\mathcal{I}}$ is solvable, a submodular critical price
schedule may fail to exist. This happens if there exists $I\in{\mathcal{I}}$
whose solution in the interval $[0,\hat{p}_{I}]$ is smaller than the price
$p_{J}$ for some $J\subsetneq I$ with $J\in{\mathcal{I}}$. This means that
$\operatorname{vol}_{n}(D_{J})$ vanishes despite that the bundle $J$ is
intended to be sold. This can always be fixed by removing bundles from the
selling candidate.

Let ${\mathcal{I}}$ be a selling candidate for $n$ items for which a
submodular critical price schedule $\\{p_{I}\\}_{I\subseteq[n]}$ exists; the
latter is unique by Theorem 17. Recall that a price schedule induces a utility
function $u(x)$ as in (6), which itself defines an auction. To be precise, the
functions $a:[0,1]^{n}\to\\{0,1\\}^{n}$ and $r:[0,1]^{n}\to{\mathbb{R}}$ of
the auction are given by

(14) $a(x)=I\quad\text{and}\quad r(x)=p_{I}\qquad\text{for }x\in
D_{I}\enspace;$

where we identify $I\subseteq[n]$ with its characteristic vector in
$\\{0,1\\}^{n}$. The functions $a$ and $r$ are well-defined as the regions
$D_{I}$, which depend on the prices $p_{I}$, form a polyhedral complex which
covers the unit cube. We call the auction $M({\mathcal{I}}):=(a,r)$ the
_generalized straight jacket auction_ (GSJA) for $n$ items with selling
candidate ${\mathcal{I}}$.

Next, we are focusing on symmetric price schedules. That is, the prices only
depend on the cardinality of the sets $I\in{\mathcal{I}}$. We define the
_straight jacket auction_ (SJA) as follows. Let $k\in[n]$ be the maximal
number for which submodular, symmetric critical prices exist for the selling
candidate
${\mathcal{I}}_{k,n}:=\tbinom{[n]}{1}\cup\dots\cup\tbinom{[n]}{k}\cup\\{\emptyset,[n]\\}$.
Then we call $M({\mathcal{I}}_{k,n})$ the _straight jacket auction_ (SJA) for
$n$ items. This deviates slightly from the definition of Giannakopoulos and
Koutsoupias [17]. They proved that SJA is optimal among all auctions,
deterministic or nondeterministic, for the uniform distribution and $n\leq 6$
items. Yet from their definition [17, Definition 4.1] it is not clear if such
an auction exists for all $n$. Our definition avoids this technical difficulty
since ${\mathcal{I}}_{1,n}$ always admits a (symmetric) submodular critical
price schedule. We say that the difference $n-k-1$ is the _gap_ of the SJA
with $n$ items. If the maximal selling candidate ${\mathcal{I}}_{n-1,n}$ is
solvable, then the gap counts the layers
$\tbinom{[n]}{n-1},\dots,\tbinom{[n]}{k+1}$ which must be removed to obtain a
submodular critical price schedule.

For the remainder of this section, we slightly abuse notation writing $p_{k}$
for the price for all sets of cardinality $k$. Moreover, we will refer to the
price vector $(p_{1},\dots,p_{n})$ associated to SJA as the _SJA-prices_. The
next proposition shows that SJA is a candidate for the optimal auction.

######  Proposition 19.

Let $n\in{\mathbb{N}}$ such that ${\mathcal{I}}_{n-1,n}$ is solvable. Then SJA
for $n$ items satisfies all necessary critical point conditions (1)–(4) in
Proposition 16.

###### Proof.

Condition (1) is satisfied, by the way we construct SJA, see the proof of
Theorem 17. We want to check condition (2). Let $p=(p_{1},\dots,p_{n})$ be the
vector of SJA-prices, and ${\mathcal{I}}_{k,n}$ be the corresponding candidate
set. We need to show that $\delta_{n}([\ell])\geq 0$ for all
$\ell\in\\{k+1,\dots,n-1\\}$. Let us fix such a $\ell$. Now
${\mathcal{I}}_{\ell,n}$ is solvable since ${\mathcal{I}}_{n-1,n}$ is.
Therefore, there is a price $q_{\ell}\in[0,\hat{p}_{\ell}]$ satisfying
$\operatorname{vol}_{\ell}\pi_{[\ell]}(D_{\emptyset})=1-\tfrac{\ell}{n+1}$.
Yet ${\mathcal{I}}_{\ell,n}$ fails to admit a critical price schedule, and so
$p_{n}<q_{\ell}$. Since we assume that $p$ is normalized, we have
$p_{\ell}=p_{n}$, whence
$\operatorname{vol}_{\ell}\pi_{[\ell]}(D_{\emptyset})<1-\tfrac{\ell}{n+1}$ and
$\delta_{n}([\ell])>0$. The conditions (3) and (4) are implied because (1) and
(2) hold for all bundles. ∎

######  Remark 20.

If ${\mathcal{I}}_{n-1,n}$ is solvable, our definition of SJA coincides with
[17, Definition 4.1]. More precisely, the solvability of
${\mathcal{I}}_{n-1,n}$ is equivalent to SJA of [17, Definition 4.1] being
well-defined and submodular. Note that submodularity is claimed in [17, Lemma
6.2], but the proof given has a flaw in the final line: the inequality
“$(r-1)p_{r-2}\leq(r-2)p_{r-1}$” needs to be reversed.

The next two lemmas are useful for the computation of the SJA-prices and their
expected revenue. They both establish connections between the SIM-bodies
studied in Section 2 and the regions of submodular and symmetric price
schedules.

######  Lemma 21.

Let $\\{p_{k}\\}_{k\in[n]}$ be a submodular and symmetric price schedule and
$I\subseteq[n]$. Then the projected region $\pi_{I}(D_{\emptyset})$ equals the
SIM-body $\Lambda(p_{1},p_{2}-p_{1},\dots,p_{\\#I}-p_{\\#I-1})$, provided
$p_{1}\leq 1$.

###### Proof.

We have

$\displaystyle\pi_{I}(D_{\emptyset})\ $ $\displaystyle=\
\left\\{x\in[0,1]^{I}\;\Bigg{|}\;\sum_{j\in J}x_{j}\leq p_{k}\text{ for all
$J\in\tbinom{I}{k}$, $k\geq 1$}\right\\}$ $\displaystyle=\
\Lambda(p_{1},p_{2}-p_{1},\dots,p_{\\#I}-p_{\\#I-1})\enspace,$

since $p_{1}\leq 1$. Note that for the first equality we used Lemma 13, and
for the latter equality we used Proposition 3. ∎

######  Lemma 22.

Let $\\{p_{k}\\}_{k\in[n]}$ be a submodular and symmetric price schedule. Then
the region $D_{[k]}$ is congruent to the product of SIM-bodies

$\Lambda\Big{(}1-(p_{k}-p_{k-1}),\dots,1-(p_{2}-p_{1}),1-p_{1}\Big{)}\times\Lambda\Big{(}p_{k+1}-p_{k},\dots,p_{n}-p_{n-1}\Big{)}\enspace,$

for all $k\in[n]$.

###### Proof.

Recall from Lemma 14 that for a submodular price schedule the region $D_{I}$
can be written as

$D_{I}=\pi_{I}(D_{I})\times\pi_{I^{c}}(D_{I})\enspace,$

where $\pi_{I}$ is the projection onto the coordinates in $I$ and
$I^{c}=[n]\setminus I$. Lemma 6.4 in [17] shows, that for a region $D_{[k]}$
of SJA we get

$\pi_{I}(D_{[k]})\ =\ \biggl{\\{}x\in[0,1]^{k}\biggm{|}\sum_{j\in J}x_{j}\geq
p_{k}-p_{k-\\#J}\text{ for all }J\subseteq[k]\biggr{\\}}$

and

$\pi_{I^{c}}(D_{[k]})\ =\ \biggl{\\{}x\in[0,1]^{n-k}\biggm{|}\sum_{j\in
J}x_{j}\leq p_{k+\\#J}-p_{k}\text{ for all
}J\subseteq[n-k]\biggr{\\}}\enspace.$

The proof of those equations only uses the fact, that the price schedule of
SJA is submodular and symmetric, thus it is applicable in our more general
sense. Next, it is immediate, that
$\pi_{I^{c}}(D_{[k]})=\Lambda(p_{k+1}-p_{k},\dots,p_{n}-p_{n-1})$. The central
symmetry around the point $\frac{1}{2}\cdot{\mathbf{1}}$, where ${\mathbf{1}}$
is the all ones vector, shows that $\pi_{I}(D_{[k]})$ is congruent to
$\Lambda(1-(p_{k}-p_{k-1}),\dots,1-(p_{2}-p_{1}),1-p_{1})$. ∎

In Section 5, we will further discuss the computation of the SJA-prices. It is
interesting to note, that for $n>4$ items, the SJA-prices are not strictly
increasing and that they are critical with respect to a selling candidate
${\mathcal{I}}_{k,n}$ for some $k<n-1$; see Table 1. That is, gaps do occur.

For the remainder of this section, we want to compare SJA to other submodular
and symmetric auctions and strengthen the result of Proposition 19. A direct
conclusion of Theorem 17 says that any submodular and critical price schedule
for ${\mathcal{I}}_{k,n}$ is automatically symmetric. The next lemma
complements this statement.

######  Lemma 23.

Let $p=\\{p_{k}\\}_{k\in[n]}$ be a submodular and symmetric price schedule
with $p_{1}<1$. Then there exists $k\in\\{0,\dots,n-1\\}$ such that $p$ admits
${\mathcal{I}}_{k,n}$.

###### Proof.

For the sake of contradiction, let us assume there is a number $\ell<n$ such
that $\operatorname{vol}D_{[\ell]}>0$ but $\operatorname{vol}D_{[\ell-1]}=0$.
Since $\operatorname{vol}D_{[\ell]}>0$, we can apply Lemma 12 and conclude
that $p_{\ell}<p_{\ell+1}$. Next, we want to show that $p_{\ell}\leq
p_{\ell-1}$. Let $x\in[0,1]^{n}$ with $x_{i}=1$ for $i\in[\ell-1]$ and
$x_{i}=0$ otherwise. Since $\operatorname{vol}D_{[\ell-1]}=0$, there is some
$\ell^{\prime}$ such that

$\sum_{i\in[\ell-1]}x_{i}-p_{\ell-1}\ \leq\
\sum_{i\in[\ell^{\prime}]}x_{i}-p_{\ell^{\prime}}\enspace.$

If $\ell^{\prime}<\ell-1$ we get $p_{\ell-1}\leq
p_{\ell^{\prime}}+(\ell-1-\ell^{\prime})p_{1}$ by submodularity, which results
in

$\sum_{i\in[\ell-1]}x_{i}-p_{\ell-1}\ =\ \ell-1-p_{\ell-1}\ \geq\
\ell^{\prime}-p_{\ell^{\prime}}+(\ell-1-\ell^{\prime})(1-p_{1})\ >\
\ell^{\prime}-p_{\ell^{\prime}}\ =\
\sum_{i\in[\ell^{\prime}]}x_{i}-p_{\ell^{\prime}}\enspace.$

Therefore $\ell^{\prime}>\ell-1$. But then
$\sum_{i\in[\ell^{\prime}]}x_{i}=\ell-1=\sum_{i\in[\ell-1]}x_{i}$, whence
$p_{\ell^{\prime}}\leq p_{\ell-1}$. Applying Lemma 12 again, from
$\ell^{\prime}>\ell-1$ we obtain $p_{\ell}\leq p_{\ell-1}$. Finally, the
submodularity of $p$ implies $p_{\ell+1}\leq p_{\ell}+p_{\ell}-p_{\ell-1}\leq
p_{\ell}$, and this contradicts $p_{\ell}<p_{\ell+1}$.

Further, we need to show that $\operatorname{vol}D_{[n]}>0$. We do this by
showing that the point $x=(p_{1},\dots,p_{1})$ is in $D_{[n]}$. This is enough
because also $x^{\prime}\in D_{[n]}$ if $x_{i}^{\prime}\geq x_{i}$ for all
$i\in[n]$. By submodularity we get $p_{n}\leq p_{\ell}+(n-\ell)\cdot p_{1}$
for all $\ell<n$. Therefore

$\sum_{i\in[n]}x_{i}-p_{n}\ =\ n\cdot p_{1}-p_{n}\ \geq\ \ell\cdot
p_{1}-p_{\ell}+(n-\ell)(p_{1}-p_{1})\ \geq\
\sum_{i\in[\ell]}x_{i}-p_{\ell}\enspace,$

which proves that $x\in D_{[n]}$. ∎

We call a submodular auction _degenerate_ if at least one of the submodularity
conditions is satisfied with equality, i.e., there are bundles which are
tight. By Proposition 19 SJA is a candidate for the optimal auction. The next
results shows, that it is the only candidate among all submodular and
symmetric auctions which are nondegenerate.

######  Theorem 24.

Let $M$ be a deterministic, submodular and symmetric auction for $n$ items
which is not degenerate. If $M$ satisfies the necessary critical point
conditions (1)–(4) of Proposition 16, then it is the SJA.

###### Proof.

Let $(p_{1},\dots,p_{n})$ be the vector of SJA-prices for $n$ items and let
$k\in\\{1,\dots,n-1\\}$ be chosen such that ${\mathcal{I}}_{k,n}$ is the
selling candidate of SJA. Let $(q_{1},\dots,q_{n})$ be the price schedule of
$M$. Assume that $q\neq p$. We will show, that $q$ then infringes one of the
critical conditions. If $q_{1}=1$, then $\operatorname{vol}_{D_{[1]}}=0$ and
by submodularity, $q_{i}>1$ for $i>1$. Therefore $\delta(\\{1\\})<0$ and thus
condition (2) is not satisfied. Hence we assume $q_{1}<1$. Now we can apply
Lemma 23 and find some $k^{\prime}\in\\{0,\dots,n-1\\}$ such that $q$ admits
${\mathcal{I}}_{k^{\prime},n}$. Since $q\neq p$, we know $k^{\prime}<k$. For
$q$ to satisfy condition (1), it needs to be critical with respect to
${\mathcal{I}}_{k^{\prime},n}$. Therefore, the prices $q_{i}$ need to be
defined such that $\delta_{n}({[i]})=0$ for all $i\leq k^{\prime}$. Since SJA
is critical with respect to ${\mathcal{I}}_{k,n}$, this is also true for
$p_{i}$. As in the proof of Theorem 17, there is at most one solution to
$\delta_{n}({[i]})=0$ for all $i\leq k^{\prime}$. Hence $q_{i}=p_{i}$ for
$i\leq k^{\prime}$.

Next, we claim $q_{n}>p_{k^{\prime}+1}$: For any two integers $1\leq a\leq
b\leq n$, we define the polytope

$P_{a}^{b}\ =\ \biggl{\\{}x\in[0,1]^{n}\biggm{|}\sum_{i\in I}x_{i}\leq
p_{\ell}\text{ for all }\ell\in\\{a,\dots,b\\}\text{ and
}I\in\binom{[n]}{\ell}\biggr{\\}}\enspace.$

Moreover, we define the halfspace
$H_{r}=\\{x\in{\mathbb{R}}^{n}\mid\sum_{i\in[n]}x_{i}\leq r\\}$. Let us assume
for now that $k^{\prime}>0$. With this notation and using the proof of Theorem
17, as well as the fact that $q_{i}=p_{i}$ for $i\leq k^{\prime}$, $q_{n}$ is
the unique solution to

(15) $\operatorname{vol}_{n}\left(P_{1}^{k^{\prime}}\cap
H_{q_{n}}\right)=\frac{1}{n+1}\enspace.$

Similarly, $p_{n}$ is the unique solution to
$\operatorname{vol}_{n}(P_{1}^{k^{\prime}}\cap P_{k^{\prime}+1}^{k}\cap
H_{p_{n}})=\frac{1}{n+1}$. By Lemma 12, we get
$p_{k^{\prime}}<p_{k^{\prime}+1}<\dots<p_{k}<p_{n}$. Therefore, assuming
$q_{n}\leq p_{k^{\prime}+1}$ implies $P_{1}^{k^{\prime}}\cap
P_{k^{\prime}+1}^{k}\cap H_{q_{n}}=P_{1}^{k^{\prime}}\cap H_{q_{n}}$ and thus
$p_{n}=q_{n}$. But this is a contradiction to $p_{n}>p_{k}$. Note that for
$k^{\prime}=0$, we can not use the proof of Theorem 17 to guarantee that there
is at most one solution to 15. But since $q_{1}<1$ and
$\operatorname{vol}D_{\\{1\\}}=0$ we have $q_{n}<1$, which is enough to show
that 15 has at most one solution, namely $q_{n}=\tfrac{n!}{n+1}$.

Finally, we show that $q$ does not satisfy condition (2). Since for $q$ we
have $\operatorname{vol}_{n}D_{k^{\prime}+1}=0$, we can assume
$q_{k^{\prime}+1}=q_{n}$. Hence $q_{k^{\prime}+1}>p_{k^{\prime}+1}$. But since
$p_{k^{\prime}+1}$ is chosen such that
$\operatorname{vol}_{n}(P_{1}^{k^{\prime}}\cap
H_{p_{k^{\prime}+1}})=1-\frac{k^{\prime}+1}{n+1}$, we get that
$\operatorname{vol}_{n}(P_{1}^{k^{\prime}}\cap
H_{q_{k^{\prime}+1}})>1-\frac{k^{\prime}+1}{n+1}$, which implies
$\delta_{n}([k^{\prime}+1])<0$ for $q$. ∎

Note that SJA can be degenerate. This is the case if the gap is at least $2$;
in that case the condition $p_{n}+p_{n-2}\leq p_{n-1}+p_{n-1}$ is tight. Hence
our computations show, that SJA is nondegenerate for $n\leq 7$ and $n=12$, but
degenerate for $8\leq n\leq 11$; see Table 1. Still SJA is a strong candidate
for the optimal auction. Indeed, it is optimal if no other degenerate auction
satisfies the necessary critical point conditions (1)–(4) of Proposition 16.

######  Corollary 25.

SJA is optimal among all deterministic, submodular and symmetric auctions,
unless other critical degenerate auctions exist.

###### Proof.

The set of all deterministic, submodular and symmetric auctions is given by
the set of submodular and symmetric price schedules. This set is bounded and
closed, hence it is compact. Since the expected revenue is a continuous
function depending on the price schedule, there is an optimal price schedule
which maximizes the expected revenue. If there is no critical price schedule
other than SJA, that must be optimal. ∎

In general, neither symmetry nor submodularity are forced by optimality. This
is what the following example shows. However, in contrast to our general
assumption above, the example employs a distribution for the valuations of the
buyer which is not uniform.

######  Example 26 (Babaioff et al. [2, Example 5.2]).

Let us consider a price schedule for $n=3$ items, where the valuations are
drawn independently from the discrete distribution $f$ given by:

$v$ | 0 | 1 | 2 | 5 | 6
---|---|---|---|---|---
$f(v)$ | 0.1 | 0.1 | 0.4 | 0.1 | 0.3

Then one optimal price schedule is defined by
$p_{\\{1\\}}=p_{\\{2\\}}=p_{\\{3\\}}=6$, $p_{\\{1,2\\}}=p_{\\{1,3\\}}=7$,
$p_{\\{2,3\\}}=8$ and $p_{\\{1,2,3\\}}=9$. This price schedule is neither
symmetric nor submodular, but has a better expected revenue than any symmetric
or submodular price schedule.

##  4\. Volume Formulae

In Section 3 we have proven that critical price schedules are characterized by
the volumes of polytopes that appear as the regions of a tropical
hypersurface, and that the projections of these polytopes are SIM-bodies. The
latter have been recognized as generalized permutahedra in Section 2. This
opens up several paths for computing and analyzing volumes of SIM-bodies, all
of which have their merits. Giannakopoulos and Koutsoupias proposed to
recursively evaluate integrals [17, (12)]. Throughout we fix parameters
$\alpha_{1}\geq\dots\geq\alpha_{n}\geq 0$ and abbreviate
$\Lambda=\Lambda(\alpha_{1},\dots,\alpha_{n})$.

### Dragon marriage

A substantial part of Postnikov’s work [26] deals with rewriting generalized
permutahedra in order to obtain various formulae for volumes and counting
lattice points. Here we follow the approach in [26, §9]. With this, for
$I\in\tbinom{[n+1]}{k}$ and $k\geq 1$, we set

(16) $y_{I}\ =\
\begin{cases}\sum_{i=0}^{k-2}(-1)^{i+k}\binom{k-2}{i}\alpha_{n-i},&\text{ if
}n+1\in I\\\ 0,&\text{ otherwise}\enspace.\end{cases}$

Note that the value $y_{I}$ only depends on the cardinality of $I$ and the
parameters $\alpha_{i}$. We write standard simplices as
$\Delta_{I}=\operatorname{conv}\\{e_{i}\mid i\in I\\}$. The following is a
description of the SIM-bodies in terms of “nested sets” in the sense of [26,
§7].

######  Proposition 27.

For $\alpha_{1}\geq\dots\geq\alpha_{n}\geq 0$ we have

(17) $\Lambda(\alpha_{1},\dots,\alpha_{n})\ =\ P_{n+1}\\{z_{I}\\}\ =\
\sum_{I\subseteq[n+1]}y_{I}\Delta_{I}\enspace,$

where $y_{I}$ is defined as in (16), and $z_{I}$ as in (2).

###### Proof.

Verify that $\sum_{J\subseteq I}y_{J}=z_{I}$ for $\emptyset\neq
I\subseteq[n+1]$. With Proposition 3 the claim follows from [26, Remark 6.4].
∎

######  Remark 28.

Note that the decomposition (17) is not necessarily a Minkowski sum of
standard simplices, as the parameters $y_{I}$ may be negative. For instance,
with $n=3$ and $(\alpha_{1},\alpha_{2},\alpha_{3})=(4,3,1)$, we obtain
$y_{[4]}=\alpha_{3}-2\alpha_{2}+\alpha_{1}=-1$.

Let $\Phi_{n}=\\{d\in[n]^{n}\mid d_{1}\leq\dots\leq d_{n}\\}$ be the set of
weakly ascending integer vectors of length $n$, whose entries lie in the set
$[n]$. For $d\in\Phi_{n}$ we let $M_{d}$ denote the number of labeled
bipartite graphs with left degree vector $(d_{1},\dots,d_{n})$, sorted in
weakly ascending order, which satisfy Hall’s condition; i.e., they include a
perfect matching.

######  Corollary 29.

For $\alpha_{1}\geq\dots\geq\alpha_{n}\geq 0$ the volume of
$\Lambda=\Lambda(\alpha_{1},\dots,\alpha_{n})$ equals

$\operatorname{vol}_{n}(\Lambda)\ =\ \frac{1}{n!}\sum_{d\in\Phi_{n}}M_{d}\
\omega_{d_{1}}\cdots\omega_{d_{n}}\enspace,$

where

$\omega_{k}\ =\
\sum_{i=0}^{k-1}(-1)^{i+k-1}\binom{k-1}{i}\alpha_{n-i}\enspace.$

In particular, the normalized volume $n!\cdot\operatorname{vol}_{n}(\Lambda)$
is an integral polynomial which is homogeneous of degree $n$ in the
parameters.

###### Proof.

It suffices to consider the generic case $\alpha_{1}>\dots>\alpha_{n}>0$, from
which the degenerate cases follow by continuity. By Proposition 27 and [26,
Corollary 9.4] we have

(18) $\operatorname{vol}_{n}(\Lambda)\ =\
\frac{1}{n!}\sum_{(J_{1},...,J_{n})}y_{J_{1}}\cdots y_{J_{n}}\enspace,$

where the sum is taken over ordered collections of nonempty subsets
$J_{1},\dots,J_{n}\subseteq[n+1]$ such that, for pairwise distinct
$i_{1},\dots,i_{k}$, we have

(19) $\\#\bigl{(}J_{i_{1}}\cup\dots\cup J_{i_{k}}\bigr{)}\ \geq\ k+1\enspace.$

The volume formula (18) can be simplified by removing zero terms arising from
the case distinction in (16); moreover, $y_{I}=y_{I^{\prime}}$ whenever $I$
and $I^{\prime}$ share the same cardinality. We have $\omega_{k}=y_{I}$ if $I$
contains $n+1$ and exactly $k$ additional elements in $[n]$.

For $d_{i}=\\#J_{i}-1$ the product $\omega_{d_{1}}\cdots\omega_{d_{n}}$ equals
$y_{J_{1}}\cdots y_{J_{n}}$, if each $J_{i}\subseteq[n+1]$ satisfies $n+1\in
J_{i}$. From $J_{1},\dots,J_{n}$ with weakly ascending cardinalities we obtain
a bipartite graph by taking $J_{i}\setminus\\{n+1\\}$ as the set of right
neighbors of the left node $i$. Now the requirement (19) on
$J_{1},\dots,J_{n}$ translates into
$\\#((J_{i_{1}}\setminus\\{n+1\\})\cup\dots\cup(J_{i_{k}}\setminus\\{n+1\\}))\geq
k$, which is Hall’s condition. ∎

The inequality (19) is the _dragon marriage condition_ [26, Proposition 5.4].
There are many other ways to compute volumes of SIM-bodies: for instance, via
integration [17, Equation (12)].

######  Example 30.

Let us compute the volume of the SIM-body $\Lambda(4,3,1)$ via Corollary 29.
We have $\omega_{1}=1,\omega_{2}=2,\omega_{3}=-1$ and thus

$\displaystyle\operatorname{vol}_{3}(\Lambda(4,3,1))$ $\displaystyle=\
\frac{1}{6}\Big{(}M_{(1,1,1)}+2M_{(1,1,2)}-M_{(1,1,3)}+4M_{(1,2,2)}-2M_{(1,2,3)}+M_{(1,3,3)}$
$\displaystyle\qquad+8M_{(2,2,2)}-4M_{(2,2,3)}+2M_{(2,3,3)}-M_{(3,3,3)}\Big{)}$
$\displaystyle=\ \frac{1}{6}\Big{(}6+2\cdot 36-18+4\cdot 63-2\cdot 54+9+8\cdot
24-4\cdot 27+2\cdot 9-1\Big{)}$ $\displaystyle=\ \frac{157}{3}\enspace.$

The formula [17, (12)] gives
$v(a,b):=\operatorname{vol}_{2}(\Lambda(a,b))=\frac{1}{2}a^{2}+ab-\frac{1}{2}b^{2}$
and

$\displaystyle\operatorname{vol}_{3}(\Lambda(a,b,c))$ $\displaystyle=\
\int_{0}^{c}v(a,b)dt+\int_{c}^{b}v(a,b+c-t)dt+\int_{b}^{a}v(a+b-t,c)dt$
$\displaystyle=\
\frac{1}{6}(c^{3}+3c^{2}(b-2a)-3c(2b^{2}-2ba-a^{2})-2b^{3}+3b^{2}a+3ba^{2}+a^{3})\enspace.$

Substituting $a=4$, $b=3$ and $c=1$ recovers
$\operatorname{vol}_{3}(\Lambda(4,3,1))=\frac{157}{3}$.

### Lawrence’s method

We can exploit that the regular SIM-bodies are simple polytopes. Let
$P=\\{x\in{\mathbb{R}}^{n}\mid Ax\leq b\\}$ be a rational simple $n$-polytope
with vertex set $V$ such that $(A\ b)$ is facet defining. We assume that the
rows of $A\in{\mathbb{Z}}^{m\times n}$ are the primitive (outward) facet
normals. Then each vertex $v$ is incident with exactly $n$ facets, i.e., there
is an invertible $n{\times}n$-submatrix $A_{v}$ of $A$ such that
$A_{v}v=b_{v}$, where $b_{v}$ is the subvector of $b$ corresponding to the
rows of $A_{v}$. Let $c\in{\mathbb{Z}}^{n}$ be a linear objective function
which is not constant on any edge of $P$. That is, $c$ induces an acyclic
orientation on the vertex-edge graph of $P$. We consider the vector
$\gamma^{v}:={A_{v}}^{-\top}c$, where
${A_{v}}^{-\top}={({A_{v}}^{\top})}^{-1}$ is the inverse transpose. The vector
$c$ is _generic_ for $P$ if it is not constant on edges and additionally
$\gamma_{v}\neq 0$ for all vertices $v$ of $P$. For such data Lawrence [21]
showed

(20) $\operatorname{vol}_{n}(P)\ =\ \frac{1}{n!}\cdot\sum_{v\in
V}\frac{\langle c,v\rangle^{n}}{|\det
A_{v}|\prod_{i=1}^{n}\gamma_{i}^{v}}\enspace.$

See also [7, §3].

A rational polytope $P$ is called _Delzant_ if the primitive edge directions
at each vertex form a lattice basis. This property is equivalent to the
condition that the projective toric variety associated with the normal fan of
$P$ does not have any singularities, i.e., it is smooth in the sense of
differential geometry; see [9, Theorem 2.4.3]. Since a lattice basis obviously
needs to form a basis, a smooth polytope is necessarily simple, but the
converse does not hold, in general. We will show that the SIM-bodies have that
property. Note that Lawrence formula is particularly useful for Delzant
polytopes since then $|\det A_{v}|=1$ in (20), which simplifies the
computation; this will be used in Section 5. We define

$A_{k}=\left[\begin{array}[]{c|c}C_{k}&0\\\ \hline\cr
0&-I_{n-k}\end{array}\right],\quad C_{k}=\left[\begin{array}[]{cccc}1&&&0\\\
1&1&&\\\ \vdots&&\ddots&\\\ 1&1&\dots&1\end{array}\right],\quad
b_{\alpha^{(k)}}=\left(\begin{array}[]{c}\alpha_{1}\\\
\alpha_{1}+\alpha_{2}\\\ \vdots\\\ \alpha_{1}+\dots+\alpha_{k}\\\ 0\\\
\vdots\\\ 0\end{array}\right),$

where $A_{k}\in{\mathbb{R}}^{n\times n}$, $C_{k}\in{\mathbb{R}}^{k\times k}$,
and $I_{n-k}$ is the identity matrix in ${\mathbb{R}}^{(n-k)\times(n-k)}$. By
Proposition 4 each vertex $v$ of $\Lambda$ can be written as
$\sigma(\alpha^{(k)})$, where
$\alpha^{(k)}=(\alpha_{1},\dots,\alpha_{k},0,\dots,0)$, and
$\sigma\in\operatorname{Sym}(n)$ is a permutation. It follows from Proposition
3 that $A_{k}\alpha^{(k)}=b_{\alpha^{(k)}}$. Note that the matrix $A_{k}$ only
depends on $k$, not on the parameters $\alpha_{i}$.

######  Proposition 31.

Any proper SIM-body is a Delzant polytope.

###### Proof.

This follows from $\det(A_{k})=\pm 1$. ∎

Now (20) specializes as follows.

######  Lemma 32.

For $\alpha_{1}\geq\dots\geq\alpha_{n}\geq 0$ the volume of
$\Lambda=\Lambda(\alpha_{1},\dots,\alpha_{n})$ equals

(21) $\operatorname{vol}_{n}(\Lambda)\ =\
\frac{1}{n!}\cdot\sum_{k\in[n]}\sum_{\sigma\in\operatorname{Sym}(n)}\frac{{\langle\sigma(c),\alpha^{(k)}\rangle}^{n}}{(n-k)!\prod_{i=1}^{n}({A_{k}}^{-\top}\sigma(c))_{i}}\enspace,$

for any generic objective function $c$.

###### Proof.

Again it suffices to consider the generic case
$\alpha_{1}>\dots>\alpha_{n}>0$, from which the degenerate cases follow by
continuity. Let $P_{\sigma}$ be the permutation matrix corresponding to
$\sigma$, i.e., $v=P_{\sigma}\alpha^{(k)}$. Then we obtain
$A_{v}=A_{k}P_{\sigma}^{-1}$ and $b_{v}=b_{\alpha^{(k)}}$. In (21) we can
leave out the origin, which is a vertex, since it does not contribute to the
final volume. The factor $(n-k)!$ in the denominator comes from the fact, that
all permutations which permute the $0$-entries of $\alpha^{(k)}$ count the
same vertex. Moreover, the scalar product in the numerator satisfies $\langle
c,P_{\sigma}\alpha^{(k)}\rangle=\langle P_{\sigma}^{-1}c,\alpha^{(k)}\rangle$,
and $P_{\sigma}^{-1}c=\sigma^{-1}(c)$. Finally, notice that iterating over all
permutations $\sigma$ or their inverses is the same. ∎

This leads us to identifying those linear objective functions which are
generic.

######  Lemma 33.

An objective function $c$ is generic for $\Lambda$ if and only if the
coefficients of $c$ are nonzero and pairwise distinct. In particular,
$c=(1,2,\dots,n)$ is generic.

###### Proof.

The edge directions of $\Lambda$ are $e_{i}-e_{j}$ for $i\neq j$ or $e_{i}$.
Consequently, $c$ is not constant on any edge of $\Lambda$ if and only if
$c_{i}\neq c_{j}$ for $i\neq j$ and $c_{i}\neq 0$. In that case, a routine
computation yields $({A_{k}}^{-\top}\sigma(c))_{i}\neq 0$ for all $i$, $k$ and
$\sigma$. ∎

While the volume formula (21) is fairly compact, it can be rewritten to
improve the efficiency of evaluation. Our goal is to get rid of the factor
$(n-k)!$ in the denominator by enumerating each vertex only once. To this end
we gather some useful observations. First, the objective function
$c=(1,2,\dots,n)$ does not depend on the parameters $\alpha_{i}$. Second, we
compute

${A_{k}}^{-\top}=\left[\begin{array}[]{c|c}{C_{k}}^{-\top}&0\\\ \hline\cr
0&-I_{n-k}\end{array}\right]\,,\qquad{C_{k}}^{-\top}=\left[\begin{array}[]{ccccc}1&-1&&&0\\\
&1&-1&&\\\ &&\ddots&\ddots&\\\ &&&1&-1\\\ 0&&&&1\end{array}\right]\enspace.$

We fix some $k\in[n]$. Recall from the proof of Lemma 32 permuting the vector
$\alpha^{(k)}$ gives the same as permuting the objective function $c$ by the
inverse permutation. Then two permutations $\sigma_{1},\sigma_{2}$ correspond
to the same vertex if and only if the first $k$ coordinates of
$\sigma_{1}^{-1}(c)$ and $\sigma_{2}^{-1}(c)$ are the same. This allows us to
first choose $k$ entries of $c=(1,2,\dots,n)$ and then go through all $k!$
permutations of those vectors. We arrive at the following.

######  Proposition 34.

For $\alpha_{1}\geq\dots\geq\alpha_{n}\geq 0$ the volume of
$\Lambda=\Lambda(\alpha_{1},\dots,\alpha_{n})$ equals

$\operatorname{vol}_{n}(\Lambda)\ =\
\frac{1}{n!}\sum_{k\in[n]}\sum_{L\in\binom{[n]}{k}}\sum_{\sigma\in\operatorname{Sym}(k)}\frac{{\langle\sigma(L),\alpha^{[k]}\rangle}^{n}}{\sigma(L)_{k}\cdot\prod_{i\in[k-1]}\left(\sigma(L)_{i}-\sigma(L)_{i+1}\right)\cdot\prod_{i\notin
L}(-i)}\enspace,$

where $\alpha^{[k]}=(\alpha_{1},\dots,\alpha_{k})$, and we sort
$L\in\binom{[n]}{k}$ ascendingly to obtain a vector in ${\mathbb{R}}^{k}$.

### Lorentzian polynomials

In this section we will exhibit yet another representation of the SIM-bodies
which is similar to (17), but here we obtain a proper Minkowski sum
decomposition. This will reveal interesting structural properties of the
volume polynomials. To this and we set $\beta_{k}:=\alpha_{k}-\alpha_{k+1}$
and $\alpha_{n+1}:=0$. As the parameters $\alpha_{i}$ are strictly decreasing,
the new parameters $\beta_{i}$ are strictly positive.

######  Proposition 35.

We have

(22) $\Lambda(\alpha_{1},\dots,\alpha_{n})\ =\
\sum_{i=1}^{n}\beta_{i}\,Q(i,n)\enspace,$

where

$Q(k,n)\ :=\ \Biggl{\\{}x\in[0,1]^{n}\Biggm{|}\sum_{i=1}^{n}x_{i}\leq
k\Biggr{\\}}\enspace.$

###### Proof.

We will first check the inclusion from right to left. Let
$x=\sum_{k=1}^{n}q^{(k)}$ with $q^{(k)}\in\beta_{k}\,Q(k,n)$. For $j,k\in[n]$
we have $q^{(k)}_{j}\leq\beta_{k}$ and $\sum_{i=1}^{n}q^{(k)}_{i}\leq
k\beta_{k}$. Thus each set $J\subseteq[n]$ satisfies $\sum_{j\in
J}q^{(k)}_{j}\leq\beta_{k}\cdot\min\\{k,\\#J\\}$. We get

$\displaystyle\sum_{j\in J}x_{j}\ =\ \sum_{j\in J}\sum_{k=1}^{n}q^{(k)}_{j}$
$\displaystyle\leq\ \sum_{k=1}^{n}\beta_{k}\cdot\min\\{k,\\#J\\}$
$\displaystyle=\ \sum_{k=1}^{n}(\alpha_{k}-\alpha_{k+1})\cdot\min\\{k,\\#J\\}\
=\ \sum_{k=1}^{\\#J}\alpha_{k}\enspace,$

and thus $x\in\Lambda$.

For the reverse inclusion consider an arbitrary point $x\in\Lambda$. This can
be written as a convex combination of the vertices. As the origin is a vertex
of $\Lambda$, we obtain a function $\gamma:[n]\times S_{n}\rightarrow[0,1]$
with $\sum_{k=1}^{n}\sum_{\sigma\in S_{n}}\gamma(k,\sigma)\leq 1$ such that

$x\ =\ \sum_{k=1}^{n}\sum_{\sigma\in
S_{n}}\gamma(k,\sigma)\sigma\left(\sum_{i=1}^{k}\alpha_{i}e_{i}\right)\enspace.$

Note that $\gamma$ is not unique, since $x$ can be written as a convex
combination in more than one way. Permutations are linear, and so we get:

$\displaystyle x$ $\displaystyle=\ \sum_{\sigma\in
S_{n}}\sum_{k=1}^{n}\sum_{i=1}^{k}\gamma(k,\sigma)\alpha_{i}\sigma(e_{i})\ =\
\sum_{\sigma\in
S_{n}}\sum_{k=1}^{n}\sum_{i=1}^{k}\gamma(k,\sigma)\left(\sum_{j=i}^{n}\alpha_{j}-\alpha_{j+1}\right)\sigma(e_{i})$
$\displaystyle=\ \sum_{\sigma\in
S_{n}}\sum_{j=1}^{n}(\alpha_{j}-\alpha_{j+1})\sum_{i=1}^{j}\sum_{k=i}^{n}\gamma(k,\sigma)\sigma(e_{i})$
$\displaystyle=\ \sum_{j=1}^{n}\beta_{j}\left[\sum_{\sigma\in
S_{n}}\sum_{k=1}^{j}\gamma(k,\sigma)\sigma\left(\sum_{i=1}^{k}e_{i}\right)+\sum_{\sigma\in
S_{n}}\sum_{k=j+1}^{n}\gamma(k,\sigma)\sigma\left(\sum_{i=1}^{j}e_{i}\right)\right]\enspace.$

Since $\sum_{k=1}^{n}\sum_{\sigma\in S_{n}}\gamma(k,\sigma)\leq 1$, the vector
enclosed in brackets $[...]$ is contained in the polytope
$\operatorname{conv}\\{\bigcup_{k=1}^{j}{\mathcal{P}}(\sum_{i=1}^{k}e_{i})\cup\\{{\mathbf{0}}\\}\\}=Q(j,n)$,
which finishes the proof. ∎

Following Brändén and Huh [4] a homogeneous real polynomial with positive
coefficients is _Lorentzian_ if all its iterated partial derivatives all the
way down to degree two yield quadratic forms of Lorentzian signature
$({-}{+}{+}\cdots{+})$. It turns out that the volume polynomials of the SIM-
bodies belong to this class, up to a linear substitution.

######  Theorem 36.

The polynomial

$\lambda(\beta_{1},\dots,\beta_{n})\ =\
\operatorname{vol}_{n}\Big{(}\Lambda\left(\,\beta_{1}+\dots+\beta_{n},\,\beta_{2}+\dots+\beta_{n},\,\dots,\,\beta_{n}\,\right)\Big{)}$

is Lorentzian.

###### Proof.

Recall that $\alpha_{1}\geq\dots\geq\alpha_{n}\geq 0$ if and only if
$\beta_{1},\dots,\beta_{n}\geq 0$. Proposition 35 shows that
$\Lambda\left(\sum_{i=1}^{n}\beta_{i},\sum_{i=2}^{n}\beta_{i},\dots,\beta_{n}\right)=\sum_{i=1}^{n}\beta_{i}Q(i,n)$,
and the claim follows from [4, Theorem 4.1]. ∎

######  Example 37.

The normalized volume of a 3-dimensional SIM-body reads

$\displaystyle\operatorname{vol}_{3}($
$\displaystyle\Lambda(\alpha_{1},\alpha_{2},\alpha_{3}))\ =$
$\displaystyle\alpha_{1}^{3}+3\alpha_{1}^{2}\alpha_{2}+3\alpha_{1}^{2}\alpha_{3}+3\alpha_{1}\alpha_{2}^{2}+6\alpha_{1}\alpha_{2}\alpha_{3}-6\alpha_{1}\alpha_{3}^{2}-2\alpha_{2}^{3}-6\alpha_{2}^{2}\alpha_{3}+3\alpha_{2}\alpha_{3}^{2}+\alpha_{3}^{3}\enspace.$

Substituting $\beta_{3}=\alpha_{3}$, $\beta_{2}=\alpha_{2}-\beta_{3}$,
$\beta_{1}=\alpha_{1}-\beta_{2}-\beta_{3}$ results in

$\displaystyle\lambda($ $\displaystyle\beta_{1},\beta_{2},\beta_{3})\ =$
$\displaystyle\beta_{1}^{3}+6\beta_{1}^{2}\beta_{2}+9\beta_{1}^{2}\beta_{3}+12\beta_{1}\beta_{2}^{2}+36\beta_{1}\beta_{2}\beta_{3}+18\beta_{1}\beta_{3}^{2}+5\beta_{2}^{3}+18\beta_{2}^{2}\beta_{3}+18\beta_{2}\beta_{3}^{2}+6\beta_{3}^{3}\enspace.$

##  5\. Computing the SJA-Prices

Giannakopoulos and Koutsoupias listed the SJA-prices for up to six items [17,
p. 146]. Here we extend that computation to $n\leq 12$ items using polymake
[16] and HomotopyContinuation.jl [6], and we also compute the resulting
revenues. While some of our computations employ numerical methods, our results
for $n\leq 10$ are fully certified and thus correct, within their margins of
error, which are also given explicitly. We employ the volume computations for
SIM-bodies as laid out in Section 4.

Consider the SJA of $n$ items, and $p_{k}^{(n)}$ is the price at which any
bundle of cardinality $k$ is sold, where $k\in[n]$. When $n$ is clear from the
context, we abbreviate $p_{k}=p_{k}^{(n)}$. By Theorem 17 and Lemma 21, the
SJA-prices satisfy the critical conditions

(23) $1-\frac{k}{n+1}\ =\
\operatorname{vol}_{k}\Lambda(p_{1},p_{2}-p_{1},\dots,p_{k}-p_{k-1})\quad\text{for
}k\in[n]\enspace,$

and this is a system of $n$ rational polynomial equations in the $n$ prices.
We abbreviate the volume polynomial as
$v_{k}:=\operatorname{vol}_{k}\Lambda(\alpha_{1},\dots,\alpha_{n})$. Notice
that the price polynomial $v_{k}(p_{1},p_{2}-p_{1},\dots,p_{k}-p_{k-1})$ does
not depend on $n$; yet the constant term $1-\frac{k}{n+1}$ does.

######  Example 38.

For $n=3$ the polynomial equations (23) read

$\displaystyle 1-\frac{1}{4}\ =$ $\displaystyle\ p_{1}$ $\displaystyle
1-\frac{2}{4}\ =$ $\displaystyle\ -p_{1}^{2}+2p_{1}p_{2}-\frac{1}{2}p_{2}^{2}$
$\displaystyle 1-\frac{3}{4}\ =$ $\displaystyle\
\frac{1}{2}p_{1}^{3}-\frac{3}{2}p_{1}^{2}p_{3}-3p_{1}p_{2}^{2}+6p_{1}p_{2}p_{3}-\frac{3}{2}p_{1}p_{3}^{2}+p_{2}^{3}-\frac{3}{2}p_{2}^{2}p_{3}+\frac{1}{6}p_{3}^{3}\enspace.$

The first step is to compute the (coefficients) of the volume polynomials
$v_{k}$. Here we followed two approaches. First, we computed the volume
polynomial of a proper SIM-body in polymake via Proposition 34. Then we
applied the linear substitution as in (23) to obtain the price polynomials.
Interestingly, because of cancellation effects caused by the substitution, the
support of the price polynomials seems to be considerably smaller than the
support of the volume polynomials. Therefore, we also computed the price
polynomials directly, by exploiting [17, Equation (12)] and implementing the
integration of polynomials in a way tailored to SJA. That second method is
superior for large $n$.

The SJA-prices arise as solutions to the system (23) of price polynomials, but
they are constrained by the submodularity condition (8). Here it reads

(24) $p_{k}-p_{k-1}\ \leq\ p_{k-1}-p_{k-2}\quad\text{for }k\in[n]\enspace,$

and we use the convention $p_{0}=0$ and $p_{-1}=-1$. It follows from Theorem
17 that the polynomial system (23) has at most one real solution which
satisfies (24); see also [17, Lemma 6.2]. Note that (23) is valid only for
weakly increasing prices, i.e., $p_{1}\leq p_{2}\leq\dots\leq p_{n}$. However
if during computation we get a price $p_{k}<p_{k-1}$, we can accommodate for
it by normalizing the prices on the fly and setting $p_{k-1}=p_{k}$. This way,
equation (23) reads
$v_{k}(p_{1},p_{2}-p_{1},\dots,p_{k}-p_{k-2},0)=1-\tfrac{k}{n+1}$. This step
may be necessary multiple times. Combining (23) with (24) then yields the
Algorithm 1 for computing the SJA-prices; its correctness follows from Theorem
17.

input: integer $n\geq 1$

output: SJA-prices $p=(p_{1},\dots,p_{n})$ or $\emptyset$, if
${\mathcal{I}}_{n-1,n}$ is not solvable

for $k\in[n]$ do

$i\leftarrow 1$

while $i<k$ do

$w(x)$ $\leftarrow$
$v_{k}(p_{1},p_{2}-p_{1},\dots,p_{k-i}-p_{k-i-1},x-p_{k-i},0,\dots,0)$

$\xi$ $\leftarrow$ solution to $w(x)=1-\frac{k}{n+1}$ with $x-p_{k-1}\leq
p_{k-1}-p_{k-2}$

if $\xi$ does not exist then return $\emptyset$

if $\xi\geq p_{k-1}$ then

$p_{k}$ $\leftarrow$ $\xi$

break

$i$ $\leftarrow$ $i+1$

for $j\in[i-1]$ do

$p_{k-j}$ $\leftarrow$ $p_{k}$

return $p=(p_{1},\dots,p_{n})$

Algorithm 1 Finding the SJA price schedule

The Algorithm 1 cannot be applied naively. It rather requires an extra layer
of considerations which we discuss now. The nontrivial steps of the procedure
is finding the real zeros of a polynomial with real coefficients, which is, of
course, classical. Yet Algorithm 1 pretends that those computations are exact.
The multivariate volume polynomial of the SIM-bodies and its linear
substitution, the volume polynomial $v_{k}$, have rational coefficients; so
there is no issue with an exact representation. Yet the univariate polynomial
$w(x)=v_{k}(p_{1},p_{2}-p_{1},\dots,p_{k-i}-p_{k-i-1},x-p_{k-i},0,\dots,0)$
depends on the prices $p_{1},\dots,p_{k-1}$, which are algebraic numbers. A
naive approach would be to apply numerical methods to find the first price,
substitute and iterate the process. However, the increasing degrees of the
price polynomials amplify even a small initial error enormously. Therefore,
instead of this iterative approach we applied HomotopyContinuation.jl to the
entire polynomial system (23), as this can return exact certificates [5]. In
this way we were able to compute numerical approximations with at least 15
exact decimal digits (precision at 53 bits) for all $n\leq 10$. For $n=11$ the
HomotopyContinuation.jl computation died for lack of main memory, with more
than 130 GB required. We could apply the (nonexact) iterative method for
$n=11$ and $n=12$. Our results are compiled in Table 1.

Finally, the expected revenue (9) of the SJA reads

(25) $\operatorname{Rev}(p)\ =\
\sum_{k\in[n]}p_{k}\cdot\binom{n}{k}\cdot\operatorname{vol}_{n}\left(D_{[k]}\right)\enspace.$

To compute the volume of the region $D_{[k]}$ recall from Lemma 22 that this
is a product of SIM-bodies. The computation of (25) for $n\leq 12$ can be
found in Table 2.

The computations were made on an Intel(R) Xeon(R) Processor E5-2630 v4 @ 2.20
GHz with openSUSE Leap 15.2, Linux 5.3.18-lp152.36 in about 30 minutes and are
certified until $n=10$. The memory requirement did not exceed 36 GB.

Table 1. SJA-prices for $n\leq 12$ items, where $p_{k}^{(n)}$ indicates the price of selling a bundle of $k$ items in an $n$ item setting, and “–” says that the corresponding bundle is not sold. Values for $n\leq 10$ certified by HomotopyContinuation.jl [5]. $n$ | $p^{(n)}_{1}$ | $p^{(n)}_{2}$ | $p^{(n)}_{3}$ | $p^{(n)}_{4}$ | $p^{(n)}_{5}$ | $p^{(n)}_{6}$ | $p^{(n)}_{7}$ | $p^{(n)}_{8}$ | $p^{(n)}_{9}$ | $p^{(n)}_{10}$ | $p^{(n)}_{11}$ | $p^{(n)}_{12}$
---|---|---|---|---|---|---|---|---|---|---|---|---
$1$ | $1/2$ |  |  |  |  |  |  |  |  |  |  |
$2$ | $2/3$ | 0.862 |  |  |  |  |  |  |  |  |  |
$3$ | $3/4$ | 1.146 | 1.226 |  |  |  |  |  |  |  |  |
$4$ | $4/5$ | 1.317 | 1.581 | 1.601 |  |  |  |  |  |  |  |
$5$ | $5/6$ | 1.431 | 1.817 | – | 1.986 |  |  |  |  |  |  |
$6$ | $6/7$ | 1.512 | 1.986 | 2.286 | – | 2.377 |  |  |  |  |  |
$7$ | $7/8$ | 1.573 | 2.113 | 2.500 | 2.739 | – | 2.775 |  |  |  |  |
$8$ | $8/9$ | 1.621 | 2.211 | 2.667 | 2.991 | – | – | 3.178 |  |  |  |
$9$ | $9/10$ | 1.659 | 2.290 | 2.800 | 3.192 | 3.466 | – | – | 3.584 |  |  |
$10$ | $10/11$ | 1.690 | 2.355 | 2.909 | 3.356 | 3.696 | 3.932 | – | – | 3.995 |  |
$11$ | $11/12$ | 1.715 | 2.409 | 3.000 | 3.493 | 3.888 | 4.188 | 4.392 | – | – | 4.408 |
$12$ | $12/13$ | 1.737 | 2.454 | 3.077 | 3.609 | 4.051 | 4.404 | 4.670 | 4.848 | 4.937 | – | 5.013
Table 2. Expected revenues $\operatorname{Rev}=\operatorname{Rev}(p_{1}^{(n)},\dots,p_{n}^{(n)})$ of the SJA for $n=1,\dots,12$. $n$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
---|---|---|---|---|---|---|---|---|---|---|---|---
$\operatorname{Rev}$ | 0.25 | 0.549 | 0.875 | 1.220 | 1.576 | 1.943 | 2.318 | 2.699 | 3.086 | 3.478 | 3.883 | 4.336

##  6\. Conclusion

The revenue optimization of auctions with multiple items is notoriously
difficult. In the present paper this is reflected in metric intricacies
concerning special classes of generalized permutahedra and ensuing algebraic
questions. We believe that answers to the following open questions will lead
to a better understanding.

As already suggested by Giannakopoulos and Koutsoupias, the SJA seems to be
the only immediate candidate for an optimal auction in the submodular and
symmetric setting. A major technical obstacle in any attempt to confirm or
refute the corresponding [17, Conjecture 4.3] seems to be the following.

######  Question 39.

How large is the gap of SJA for $n$ items?

From Table 1 we see that the gap equals two for $n=11$, and it is one for
$n=12$. So as a function of $n$ the gap is not monotone.

There may be more to say from the point of view of tropical geometry. The
support of the tropical polynomial $u$ in (6) is formed by the vertices of the
unit cube. The prices, which enter as the coefficients of $u$, give rise to a
regular subdivision, ${\mathcal{S}}(u)$, on $[0,1]^{n}$ which is dual to the
tropical hypersurface ${\mathcal{T}}(u)$; see [19, §1.2]. In this way, finding
optimal prices becomes a nonlinear optimization problem over the secondary
cone of ${\mathcal{S}}(u)$.

######  Question 40.

What can be learned from this dual point of view? Does it help to understand
submodular auctions which are degenerate?

## References

  * [1] Moshe Babaioff, Nicole Immorlica, Brendan Lucier, and S. Matthew Weinberg, _A simple and approximately optimal mechanism for an additive buyer_ , J. ACM 67 (2020), no. 4, 24:1–24:40.
  * [2] Moshe Babaioff, Noam Nisan, and Aviad Rubinstein, _Optimal deterministic mechanisms for an additive buyer_ , Proceedings of the 2018 ACM Conference on Economics and Computation, Ithaca, NY, USA, June 18-22, 2018 (Éva Tardos, Edith Elkind, and Rakesh Vohra, eds.), ACM, 2018, p. 429.
  * [3] Elizabeth Baldwin and Paul Klemperer, _Understanding preferences: “Demand Types”, and the existence of equilibrium with indivisibilities_, Econometrica 87 (2019), no. 3, 867–893.
  * [4] Petter Brändén and June Huh, _Lorentzian polynomials_ , Ann. of Math. (2) 192 (2020), no. 3, 821–891.
  * [5] Paul Breiding, Kemal Rose, and Sascha Timme, _Certifying zeros of polynomial systems using interval arithmetic_ , 2021, Preprint arXiv:2011.05000.
  * [6] Paul Breiding and Sascha Timme, _HomotopyContinuation.jl : a package for homotopy continuation in Julia_, Mathematical software – ICMS 2018 (James Davenport, Manuel Kauers, George Labahn, and Josef Urban, eds.), Lecture Notes in Computer Science, vol. 10931, Springer, 2018.
  * [7] Benno Büeler, Andreas Enge, and Komei Fukuda, _Exact volume computation for polytopes: a practical study_ , Polytopes—combinatorics and computation (Oberwolfach, 1997), DMV Sem., vol. 29, Birkhäuser, Basel, 2000, pp. 131–154.
  * [8] Xi Chen et al., _The complexity of optimal multidimensional pricing for a unit-demand buyer_ , Games and Econ. Behav. 110 (2018), 139–164.
  * [9] David A. Cox, John B. Little, and Henry K. Schenck, _Toric varieties_ , Graduate Studies in Mathematics, vol. 124, American Mathematical Society, Providence, RI, 2011.
  * [10] Robert Alexander Crowell and Ngoc Mai Tran, _Tropical geometry and mechanism design_ , 2018, Preprint arXiv:1606.04880.
  * [11] Vladimir I. Danilov and Gleb A. Koshevoy, _Cores of cooperative games, superdifferentials of functions, and the Minkowski difference of sets_ , J. Math. Anal. Appl. 247 (2000), no. 1, 1–14.
  * [12] Constantinos Daskalakis, Alan Deckelbaum, and Christos Tzamos, _The complexity of optimal mechanism design_ , Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2014, pp. 1302–1318.
  * [13] by same author, _Strong duality for a multiple-good monopolist_ , Econometrica 85 (2017), no. 3, 735–767.
  * [14] Jeffrey Samuel Doker, _Geometry of Generalized Permutohedra_ , ProQuest LLC, Ann Arbor, MI, 2011, Thesis (Ph.D.)–University of California, Berkeley.
  * [15] András Frank and Kazuo Murota, _Discrete decreasing minimization, part i: Base-polyhedra with applications in network optimization_ , 2019, Preprint arXiv:1808.07600.
  * [16] Ewgenij Gawrilow and Michael Joswig, _polymake : a framework for analyzing convex polytopes_, Polytopes—combinatorics and computation (Oberwolfach, 1997), DMV Sem., vol. 29, Birkhäuser, Basel, 2000, pp. 43–73. MR MR1785292 (2001f:52033)
  * [17] Yiannis Giannakopoulos and Elias Koutsoupias, _Duality and optimality of auctions for uniform distributions_ , SIAM J. Comput. 47 (2018), no. 1, 121–165.
  * [18] Sergiu Hart and Noam Nisan, _Approximate revenue maximization with multiple items_ , J. Econ. Theory 172 (2017), 313–347.
  * [19] Michael Joswig, _Essentials of tropical combinatorics_ , Graduate Studies in Mathematics, American Mathematical Society, Providence, RI, 2022.
  * [20] Michael Joswig and Thorsten Theobald, _Polyhedral and algebraic methods in computational geometry_ , Springer, 2013.
  * [21] Jim Lawrence, _Polytope volume computation_ , Math. Comp. 57 (1991), no. 195, 259–271.
  * [22] Xinye Li and Andrew Chi-Chih Yao, _On revenue maximization for selling multiple independently distributed items_ , Proc. Natl. Acad. Sci. USA 110 (2013), no. 28, 11232–11237.
  * [23] Diane Maclagan and Bernd Sturmfels, _Introduction to tropical geometry_ , Graduate Studies in Mathematics, vol. 161, American Mathematical Society, Providence, RI, 2015.
  * [24] Alejandro M. Manelli and Daniel R. Vincent, _Bundling as an optimal selling mechanism for a multiple-good monopolist_ , Journal of Economic Theory 127 (2006), no. 1, 1–35.
  * [25] Roger B. Myerson, _Optimal auction design_ , Math. Oper. Res. 6 (1981), no. 1, 58–73.
  * [26] Alexander Postnikov, _Permutohedra, associahedra, and beyond_ , Int. Math. Res. Not. IMRN (2009), no. 6, 1026–1106.
  * [27] Richard Rado, _An inequality_ , J. London Math. Soc. 27 (1952), 1–6.
  * [28] Jean-Charles Rochet, _The taxation principle and multi-time Hamilton-Jacobi equations_ , J. Math. Econ. 14 (1985), no. 2, 113–128.
  * [29] Neil J. A. Sloane et al., _The on-line encyclopedia of integer sequences (OEIS)_ , https://oeis.org/.
  * [30] John Thanassoulis, _Haggling over substitutes_ , J. Econ. Theory 117 (2004), no. 2, 217–245.
  * [31] Ngoc Mai Tran and Josephine Yu, _Product-mix auctions and tropical geometry_ , Math. Oper. Res. 44 (2019), no. 4, 1396–1411.
  * [32] William Vickrey, _Counterspeculation, auctions, and competitive sealed tenders_ , J. Finance 16 (1961), no. 1, 8–37.
  * [33] Günter M. Ziegler, _Lectures on polytopes_ , Graduate Texts in Mathematics, vol. 152, Springer-Verlag, New York, 1995.