using PyMongeAmpere by Quentin Mérigot: https://github.com/mrgt/PyMongeAmpere.
We consider the monopolist's problem in a semi-discrete setting: given
the monopolist is looking for
that maximizes her profits, i.e. that solves (SDPAP):
$$ \min_{v \in \mathbb R^N} \sum_{i=1}^N (c_i -v_i)\ \mu\left( \text{Lag}_i(v) \right) $$where the cell $\text{Lag}_i(v) := \left\{ x \in X : b(x,y_i)-v_i \ge b(x,y_j)- v_j, \ \forall j=0,\ldots,N \right\}$ is the set of agents' types $x$ that choose, in response to the price schedule $v$, to buy a product of type $y_i$ at the price $v_i$ (because it maximizes their quasi-linear utility).
We restrict in what follows to the bilinear valuation function $b(x,y) = x \cdot y$, so that $\left(\text{Lag}_i(v)\right)_i$ are the cells of a Laguerre-Voronoi or power diagram. We further restrict to the dimension $d=2$.
Let
for $k = 1, \ldots, \text{multi}$, let
(obtained by solving a semi-discrete optimal transport problem, here in dimension 2 with PyMongeAmpere by Quentin Mérigot);
(computed here from PyMongeAmpere by Quentin Mérigot);
return $(\tilde v, \tilde L)$.
% matplotlib notebook
% run QuadUnifSquare.py --n 3 --multi 1
# n -> (2^n+1)^2 products' types, multi -> number of successive optimizations
DATA Number of products' types: 81, distribution of agents' types: uniform on a square, cost: quadratic OPTIMIZATION 1 Initial function value: -1.324290 Optimization method: L-BFGS-B, status: 0, success: True, nit: 61, CONVERGENCE: REL_REDUCTION_OF_F_<=_FACTR*EPSMCH Final function value: -1.508670
% matplotlib notebook
% run QuadUnifSquare.py --n 4 --multi 3
# n -> (2^n+1)^2 products' types, multi -> number of successive optimizations
DATA Number of products' types: 289, distribution of agents' types: uniform on a square, cost: quadratic OPTIMIZATION 1 Initial function value: -1.330908 Optimization method: L-BFGS-B, status: 0, success: True, nit: 223, CONVERGENCE: REL_REDUCTION_OF_F_<=_FACTR*EPSMCH Final function value: -1.513311 OPTIMIZATION 2 Initial function value: -1.439223 Optimization method: L-BFGS-B, status: 0, success: True, nit: 176, CONVERGENCE: REL_REDUCTION_OF_F_<=_FACTR*EPSMCH Final function value: -1.512956 OPTIMIZATION 3 Initial function value: -1.478573 Optimization method: L-BFGS-B, status: 0, success: True, nit: 189, CONVERGENCE: REL_REDUCTION_OF_F_<=_FACTR*EPSMCH Final function value: -1.513380
% matplotlib notebook
% run QuadUnifSquare.py --n 5 --multi 3
# n -> (2^n+1)^2 products' types, multi -> number of successive optimizations
$X=[1,2]^2$, $\mu$ Gaussian, $Y$ a regular grid of $[0,2]^2$, $c(y) =\frac{1}{2} |y|^2$
Run (shift+enter) the cell below. One can choose $N$ via the argument $n$ ($N = (2^n+1)^2$), the standard deviation $\sigma$ of $\mu$, and the argument multi.
% matplotlib notebook
% run QuadGaussianSquare.py --n 3 --sigma 5 --multi 3
# n -> (2^n+1)^2 products' types, sigma -> standard deviation, multi -> number of successive optimizations
$X$ the disk inscribed in $[1,2]^2$, $\mu$ Gaussian, $Y$ a regular grid of $[0,2]^2$, $c(y) =\frac{1}{2} |y|^2$
Run (shift+enter) the cell below. One can choose $N$ via the argument $n$ ($N = (2^n+1)^2$), the standard deviation $\sigma$ of $\mu$, and the argument multi.
% matplotlib notebook
% run QuadGaussianDisk.py --n 4 --sigma 10 --multi 3
# n -> (2^n+1)^2 products' types, sigma -> standard deviation, multi -> number of successive optimizations
% matplotlib notebook
% run ChineseUnifSquare.py --n 5 --multi 1
# n -> (2^n+1)^2 products' types, multi -> number of successive optimizations
% matplotlib notebook
% run ChineseUnifSquare.py --n 3 --multi 3
# n -> (2^n+1)^2 products' types, multi -> number of successive optimizations