We give an explicit counterexample to the Bunkbed Conjecture introduced by Kasteleyn in 1985. The counterexample is given by a planar graph on 7222 vertices, and is built on the recent work of Hollom (2024).
@article{gladkov2024bunkbedconjecturefalse,title={The bunkbed conjecture is false},author={Gladkov, Nikita and Pak, Igor and Zimin, Aleksandr},year={2024},eprint={2410.02545},archiveprefix={arXiv},primaryclass={math.CO},url={https://www.quantamagazine.org/maths-bunkbed-conjecture-has-been-debunked-20241101/},doi={10.48550/arXiv.2410.02545},}
Bond percolation does not simulate site percolation
We show that a site percolation is a stronger model than a bond percolation. We use the van den Berg – Kesten (vdBK) inequality to prove that site percolation on a neighborhood of a vertex of degree 3 cannot be simulated even approximately by bond percolation, and develop a decision tree technique to prove the same for a neighborhood of a vertex of degree 2. This technique can be used to obtain inequalities for connectedness probabilities, including a conjectured inequality of Erik Aas.
@article{gladkov2024bondpercolationdoessimulate,title={Bond percolation does not simulate site percolation},author={Gladkov, Nikita and Zimin, Aleksandr},year={2024},eprint={2404.08873},archiveprefix={arXiv},primaryclass={math.PR},doi={10.48550/arXiv.2404.08873},}
Optimal Transport
On multistochastic Monge–Kantorovich problem, bitwise operations, and fractals
Nikita A
Gladkov, Alexander V
Kolesnikov, and Alexander P
Zimin
Calculus of Variations and Partial Differential Equations, 2019
The multistochastic \((n,k)\)-Monge–Kantorovich problem on a product space \(\prod_{i=1}^n X_i\)is an extension of the classical Monge–Kantorovich problem. This problem is considered on the space of measures with fixed projections onto \(X_{i_1} \times \ldots \times X_{i_k}\)for all k-tuples \(\{i_1, \ldots, i_k\} ⊂\{1, \ldots, n\}\)for a given \(1 \le k < n\). In our paper we study well-posedness of the primal and the corresponding dual problem. Our central result describes a solution \(\pi\)to the following important model case \(n=3, k=2, X_i = [0,1]\), the cost function \(c(x,y,z) = xyz\), and the corresponding two–dimensional projections are Lebesgue measures on \([0,1]^2\). We prove, in particular, that the mapping \((x,y) \to x ⊕y\), where \(⊕\)is the bitwise addition (xor- or Nim-addition) on \([0,1] ≅\mathbb{Z}_2^{∞}\), is the corresponding optimal transportation. In particular, the support of \(\pi\)is the Sierpiński tetrahedron.
In addition, we describe a solution to the corresponding dual problem.
@article{gladkov2019multistochastic,title={On multistochastic Monge--Kantorovich problem, bitwise operations, and fractals},author={Gladkov, Nikita A and Kolesnikov, Alexander V and Zimin, Alexander P},journal={Calculus of Variations and Partial Differential Equations},volume={58},pages={1--33},year={2019},publisher={Springer},doi={10.1007/s00526-019-1610-4},}
The multistochastic Monge–Kantorovich problem
Nikita A.
Gladkov, Alexander V.
Kolesnikov, and Alexander P.
Zimin
Journal of Mathematical Analysis and Applications, 2022
The multistochastic Monge–Kantorovich problem on the product \(X = \prod_{i=1}^n X_i\,\,\)of \(n\)spaces is a generalization of the multimarginal Monge–Kantorovich problem. For a given integer number \(1 \le k< n\,\,\)we consider the minimization problem \(∫c d \pi \to \inf\,\,\)on the space of measures with fixed projections onto every \(X_{i_1} \times …\times X_{i_k}\,\,\)for arbitrary set of \(k\,\,\)indices \(\{i_1, …, i_k\} ⊂\{1, …, n\}\,\,\). In this paper we study basic properties of the multistochastic problem, including well-posedness, existence of a dual solution, boundedness and continuity of a dual solution.
@article{GLADKOV2022125666,title={The multistochastic Monge–Kantorovich problem},journal={Journal of Mathematical Analysis and Applications},volume={506},number={2},pages={125666},year={2022},issn={0022-247X},doi={https://doi.org/10.1016/j.jmaa.2021.125666},author={Gladkov, Nikita A. and Kolesnikov, Alexander V. and Zimin, Alexander P.},keywords={Optimal transportation, Monge-Kantorovich problem, Multistochastic Monge-Kantorovich problem, Multimarginal transportation problem, Dual linear program, Fractals},}
An Explicit Solution for a Multimarginal Mass Transportation Problem
We construct an explicit solution for the multimarginal transportation problem on the unit cube \([0, 1]^3\,\,\)with the cost function xyz and one-dimensional uniform projections. We show that the primal problem is concentrated on a set with non-constant local dimension and admits many solutions, whereas the solution to the corresponding dual problem is unique (up to addition of constants).
@article{10.1137/18M122707X,author={Gladkov, Nikita A. and Zimin, Alexander P.},title={An Explicit Solution for a Multimarginal Mass Transportation Problem},journal={SIAM Journal on Mathematical Analysis},volume={52},number={4},pages={3666-3696},year={2020},doi={10.1137/18M122707X},}
On existence of measure with given marginals supported on a hyperplane
Let \(\{\mu_k\}_{k=1}^N\)be absolutely continuous probability measures on the real line such that every measure \(\mu_k\)is supported on the interval \([l_k, r_k]\)and the density function of \(\mu_k\)is nonincreasing on that interval for all \(k\). We prove that if \(\Bbb{E}(\mu_1) + …+ \Bbb{E}(\mu_N) = C\)and if \(r_k - l_k \le C - (l_1 + …+ l_N)\)for all \(k\), then there exists a transport plan with given marginals supported on the hyperplane \(\{x_1 + …+ x_N = C\}\). This transport plan is an optimal solution of the multimarginal Monge-Kantorovich problem for the repulsive harmonic cost function \(\sum_{i, j = 1}^N-(x_i - x_j)^2\)
@article{zimin2020existence,title={On existence of measure with given marginals supported on a hyperplane},author={Zimin, Alexander P.},year={2020},eprint={2010.07263},archiveprefix={arXiv},primaryclass={math.PR},doi={10.48550/arXiv.2010.07263},}
Economic Applications
Sorting with Teams
Job
Boerma, Aleh
Tsyvinski, and Alexander P.
Zimin
We fully solve a sorting problem with heterogeneous firms and multiple heterogeneous workers whose skills are imperfect substitutes. We show that optimal sorting, which we call mixed and countermonotonic, is comprised of two regions. In the first region, mediocre firms sort with mediocre workers and coworkers such that the output losses are equal across all these teams (mixing). In the second region, a high skill worker sorts with low skill coworkers and a high productivity firm (countermonotonicity). We characterize the equilibrium wages and firm values. Quantitatively, our model can generate the dispersion of earnings within and across US firms.
@article{boerma2023sortingteams,title={Sorting with Teams},author={Boerma, Job and Tsyvinski, Aleh and Zimin, Alexander P.},year={2023},eprint={2109.02730},archiveprefix={arXiv},primaryclass={econ.GN},url={https://arxiv.org/abs/2109.02730},doi={10.48550/arXiv.2109.02730},}
We characterize optimal policies in a multidimensional nonlinear taxation model with bunching. We develop an empirically relevant model with cognitive and manual skills, firm heterogeneity, and labor market sorting. The analysis of optimal policy is based on two main results. We first derive an optimality condition − a general ABC formula − that states that the entire schedule of benefits of taxes second order stochastically dominates the entire schedule of tax distortions. Second, we use Legendre transforms to represent our problem as a linear program. This linearization allows us to solve the model quantitatively and to precisely characterize the regions and patterns of bunching. At an optimum, 9.8 percent of workers is bunched both locally and nonlocally. We introduce two notions of bunching – blunt bunching and targeted bunching. Blunt bunching constitutes 30 percent of all bunching, occurs at the lowest regions of cognitive and manual skills, and lumps the allocations of these workers resulting in a significant distortion. Targeted bunching constitutes 70 percent of all bunching and recognizes the workers’ comparative advantage. The planner separates workers on their dominant skill and bunches them on their weaker skill, thus mitigating distortions along the dominant skill dimension. Tax wedges are particularly high for low skilled workers who are bluntly bunched and are also high along the dimension of comparative disadvantage for somewhat more skilled workers who are targetedly bunched.
@article{NBERw30015,title={Bunching and Taxing Multidimensional Skills},author={Boerma, Job and Tsyvinski, Aleh and Zimin, Alexander P},institution={National Bureau of Economic Research},type={Working Paper},series={Working Paper Series},number={30015},year={2022},month=may,doi={10.3386/w30015},}
Beckmann’s approach to multi-item multi-bidder auctions
Alexander
Kolesnikov, Fedor
Sandomirskiy, Aleh
Tsyvinski, and Alexander P.
Zimin
We consider the problem of revenue-maximizing Bayesian auction design with several i.i.d. bidders and several items. We show that the auction- design problem can be reduced to the problem of continuous optimal trans- portation introduced by Beckmann (1952). We establish the strong duality between the two problems and demonstrate the existence of solutions. We then develop a new numerical approximation scheme that combines multi-to- single-agent reduction and the majorization theory insights to characterize the solution.
@article{BeckmannAuctions,doi={10.48550/ARXIV.2203.06837},author={Kolesnikov, Alexander and Sandomirskiy, Fedor and Tsyvinski, Aleh and Zimin, Alexander P.},keywords={Theoretical Economics (econ.TH), Computer Science and Game Theory (cs.GT), Functional Analysis (math.FA), Optimization and Control (math.OC), FOS: Economics and business, FOS: Economics and business, FOS: Computer and information sciences, FOS: Computer and information sciences, FOS: Mathematics, FOS: Mathematics},title={Beckmann's approach to multi-item multi-bidder auctions},publisher={arXiv},year={2022},copyright={arXiv.org perpetual, non-exclusive license},}
