The present column is devoted to Geometry/Topology.

I Six new problems – solutions solicited

Solutions will appear in a subsequent issue.

252

Prove that the space of unordered couples of distinct points of a circle is the (open) Möbius band. More formally, consider

(S1×S1){(x,x)xS1}(S^{1}\times S^{1})\setminus\{(x,x)\mid x\in S^{1}\}

and the equivalence relation on this space (x,y)(y,x)(x,y)\equiv(y,x); prove that the quotient topological space is the (open) Möbius band.

Costante Bellettini (Department of Mathematics, University College London, UK)

253

In the Euclidean plane, let γ1\gamma_{1} and γ2\gamma_{2} be two concentric circles of radius respectively r1r_{1} and r2r_{2}, with r1<r2r_{1}<r_{2}. Show that the locus γ\gamma of points PP such that the polar line of PP with respect to γ2\gamma_{2} is tangent to γ1\gamma_{1} is a circle of radius r22/r1{r_{2}^{2}}/{r_{1}}.

Acknowledgement

I want to thank the professors who guided me in the first part of my career for giving me the ideas for these problems.

Paola Bonacini (Mathematics and Computer Science Department, University of Catania, Italy)

254

Let AR3A\subseteq\mathbb{R}^{3} be a connected open subset of Euclidean space, and suppose that the following conditions hold:

  1. Every smooth irrotational vector field on AA admits a potential (i.e., it is the gradient of a smooth function).

  2. The closure A\overline{A} of AA is a smooth compact submanifold of R3\mathbb{R}^{3} (of course, with non-empty boundary).

Show that AA is simply connected. Does this conclusion hold even if we drop condition (2) on AA?

Roberto Frigerio (Dipartimento di Matematica, Università di Pisa, Italy)

255

A regulus is a surface in R3\mathbb{R}^{3} that is formed as follows: We consider pairwise skew lines 1,2,3R3\ell_{1},\ell_{2},\ell_{3}\subset\mathbb{R}^{3} and take the union of all lines that intersect each of 1\ell_{1}, 2\ell_{2}, and 3\ell_{3}. Prove that, for every regulus UU, there exists an irreducible polynomial fR[x,y,z]f\in\mathbb{R}[x,y,z] of degree two that vanishes on UU.

Adam Sheffer (Department of Mathematics, Baruch College, City University of New York, NY, USA)

256

(Enumerative Geometry). How many lines pass through 44 generic lines in a 33-dimensional complex projective space CP3\mathbb{C}\mathbb{P}^{3}?

Mohammad F. Tehrani (Department of Mathematics, University of Iowa, USA)

257

I learned about the following problem from Shmuel Weinberger. It can be viewed as a topological analogue of Arrow’s Impossibility Theorem.

(a) A group of nn friends have decided to spend their summer cottaging together on an undeveloped island, which happens to be a perfect copy of the closed 2-disk D2D^{2}. Their first task is to decide where on this island to build their cabin. Being democratically-minded, the friends decide to vote on the question. Each friend chooses his or her favourite point on D2D^{2}. The friends want a function that will take as input their nn votes, and give as output a suitable point on D2D^{2} to build. They believe, to be reasonable and fair, their “choice” function should have the following properties:

  • (Continuity) It should be continuous as a function (D2)nD2(D^{2})^{n}\to D^{2}. This means, if one friend changes their vote by a small amount, the output will change only a small amount.

  • (Symmetry) The nn friends should be indistinguishable from each other. If two friends swap votes, the final choice should be unaffected.

  • (Unanimity) If all nn friends chose the same point xx, then xx should be the final choice.

For which values of nn does such a choice function exist?

(b) The friends’ second task is to decide where along the shoreline of the island they will build their dock. The shoreline happens to be a perfect copy of the circle S1S^{1}. Again, they decide to take the problem to a vote. For which values of nn does a continuous, symmetric, and unanimous choice function (S1)nS1(S^{1})^{n}\to S^{1} exist?

These are special cases of the following general problem in topological social choice theory: given a topological space XX, for what values of nn does XX admit a social choice function that is continuous, symmetric, and unanimous? In other words, when is there a function A ⁣:XnXA\colon X^{n}\to X satisfying

  • AA is continuous,

  • A(x1,,xn)A(x_{1},\ldots,x_{n}) is independent of the ordering of x1,,xnx_{1},\ldots,x_{n}, and

  • A(x,x,x,,x)=xA(x,x,x,\ldots,x)=x for all xXx\in X?

Jenny Wilson (Department of Mathematics, University of Michigan, USA)

II Open problem

Embeddings of contact domains

by Yakov Eliashberg (Department of Mathematics, Stanford University, USA)

One of the cornerstones of symplectic topology, Gromov’s non-squeezing theorem, see [6 M. Gromov, Pseudo holomorphic curves in symplectic manifolds. Invent. Math. 82, 307–347 (1985) ], asserts that for n>1n>1 the ball of radius R>1R>1 in the standard symplectic space (R2n,ω=1ndxjdyj)(\mathbb{R}^{2n},\omega=\sum_{1}^{n}dx_{j}\wedge dy_{j}) does not admit a symplectic embedding into the domain

{x12+y12<1}R2n,\{x_{1}^{2}+y_{1}^{2}<1\}\subset\mathbb{R}^{2n},

while there is no volume constraints to do that. Since that time, the theory of symplectic embedding has made a lot of progress (see F. Schlenk’s survey [8 F. Schlenk, Symplectic embedding problems, old and new.  Bull. Amer. Math. Soc. (N.S.) 55, 139–182 (2018) ] for recent results).

The (non-)embedding results in contact geometry, which is an odd-dimensional analogue of symplectic geometry, are rarer; below, we discuss a few open problems.

Recall that a contact structure ξ\xi on an (2n+1)(2n+1)-dimensional manifold MM is a completely non-integrable hyperplane field. If ξ\xi is defined by a Pfaffian equation α=0\alpha=0 for a differential 11-form α\alpha (and such a form can always be found locally, and if ξ\xi is co-orientable even globally) then the complete non-integrability can be expressed by the condition that αdαn\alpha\wedge d\alpha^{n} is a non-vanishing (2n+1)(2n+1)-form on MM.

In this set of problems, we will restrict our attention to domains in the contact manifold X:R2n×S1X\coloneq\mathbb{R}^{2n}\times S^{1}, S1=R/ZS^{1}=\mathbb{R}/\mathbb{Z}, endowed with the contact structure

ξ:{dz+121nxjdyjyjdxj=0}.\xi\coloneq\biggl\{dz+\frac{1}{2}\sum_{1}^{n}x_{j}\,dy_{j}-y_{j}\,dx_{j}=0\biggr\}.

Given a bounded domain UR2nU\subset\mathbb{R}^{2n}, we set

U^:U×S1R2n×S1=X,\hat{U}\coloneq U\times S^{1}\subset\mathbb{R}^{2n}\times S^{1}=X,

and refer to U^\hat{U} as a quantized domain UU. We say that a domain U^1\hat{U}_{1} admits a contact embedding into a domain U^2\hat{U}_{2} if there is a contact isotopy ft ⁣:U^1Xf_{t}\colon\hat{U}_{1}\to X, starting with the inclusion f0 ⁣:U^1Xf_{0}\colon\hat{U}_{1}\hookrightarrow X such that f1(U^1)U^2f_{1}(\hat{U}_{1})\subset\hat{U}_{2}. Note that any Hamiltonian isotopy which moves U1U_{1} into U2U_{2} lifts to a contact isotopy moving U^1\hat{U}_{1} into U^2\hat{U}_{2}. Hence we will refer to the problem of contact embeddings between the domains U^1\hat{U}_{1} and U^2\hat{U}_{2} as a quantized version of the corresponding symplectic embedding problem of U1U_{1} to U2U_{2}.

Denote by B2n(R)B^{2n}(R) the 2n2n-dimensional open ball of radius RR and by P(r1,,rk)P(r_{1},\dots,r_{k}) the polydisk B2(r1)××B2(rn)R2nB^{2}(r_{1})\times\dots\times B^{2}(r_{n})\subset\mathbb{R}^{2n}, where 0<r1r2rn0<r_{1}\leq r_{2}\leq\dots\leq r_{n}. It was shown in [3 Y. Eliashberg, S. S. Kim and L. Polterovich, Geometry of contact transformations and domains: orderability versus squeezing. Geom. Topol. 10, 1635–1747 (2006) ] that if πr12<k<πr22\pi r_{1}^{2}<k<\pi r^{2}_{2} for any integer k1k\geq 1, then B^2n(r2)\hat{B}^{2n}(r_{2}) does not admit a contact embedding into B^2n(r1)\hat{B}^{2n}(r_{1}). Another theorem from [3 Y. Eliashberg, S. S. Kim and L. Polterovich, Geometry of contact transformations and domains: orderability versus squeezing. Geom. Topol. 10, 1635–1747 (2006) ] states that if πR2<1\pi R^{2}<1, then B^2n(R)\hat{B}^{2n}(R) admits a contact embedding into B^2n(r)\hat{B}^{2n}(r) for any r>0r>0. The former result was improved in [2 S.-F. Chiu, Nonsqueezing property of contact balls. Duke Math. J. 166, 605–655 (2017) , 5 M. Fraser, Contact non-squeezing at large scale in ℝ2⁢n×S1. Internat. J. Math. 27, 1650107 (2016) ] to show that for any r1<r2r_{1}<r_{2} with πr22>1\pi r_{2}^{2}>1 there is no contact embedding of B^2n(r2)\hat{B}^{2n}(r_{2}) into B^2n(r1)\hat{B}^{2n}(r_{1}). Recall that Gromov’s symplectic widthWidthGr(U)\mathrm{Width}_{\mathrm{Gr}}(U) of a domain UR2nU\subset\mathbb{R}^{2n} can be defined as the supremum of πρ2\pi\rho^{2} such that B2n(ρ)B^{2n}(\rho) can be symplectically embedded into the domain UU. The above results can be slightly generalized to the following statement, see [3 Y. Eliashberg, S. S. Kim and L. Polterovich, Geometry of contact transformations and domains: orderability versus squeezing. Geom. Topol. 10, 1635–1747 (2006) ].

If, for two domains U1,U2R2nU_{1},U_{2}\subset\mathbb{R}^{2n}, we have

WidthGr(U2)>WidthGr(U1)andWidthGr(U2)>1,\mathrm{Width}_{\mathrm{Gr}}(U_{2})>\mathrm{Width}_{\mathrm{Gr}}(U_{1})\quad\textrm{and}\quad\mathrm{Width}_{\mathrm{Gr}}(U_{2})>1,

then the quantized domain U^2\hat{U}_{2} does not admit a contact embedding into U^1\hat{U}_{1}.

Very little is known about embeddings of contact domains beyond the above results. Let us formulate a couple of concrete problems concerning quantized versions of some relatively old embedding results in symplectic topology. As we already mentioned above, many new obstructions to symplectic embeddings were found in recent years. It is unknown whether any of them hold in the quantized versions.

258*

Contact packing problem. Suppose that πR2>πr2>1\pi R^{2}>\pi r^{2}>1. Is there a maximal number of quantized balls B^2n(r)\hat{B}^{2n}(r) which admit a contact packing into B^2n(R)\hat{B}^{2n}(R)? And if the answer is “yes”, then what is this number?

Here we say that B^2n(R)\hat{B}^{2n}(R) admits a contact packing by kk quantized balls B^2n(r)\hat{B}^{2n}(r) if the disjoint union

B^2n(r)B^2n(r)kX\underbrace{\hat{B}^{2n}(r)\sqcup\dots\sqcup\hat{B}^{2n}(r)}_{k}\subset X

admits a contact embedding into B^2n(R)\hat{B}^{2n}(R). Note that the corresponding symplectic packing problem was intensively studied beginning with the seminal paper by Gromov [6 M. Gromov, Pseudo holomorphic curves in symplectic manifolds. Invent. Math. 82, 307–347 (1985) ], where he proved that the packing of the ball B2n(R)B^{2n}(R) with 2 disjoint balls B2n(r)B^{2n}(r) is possible if and only if R2>2r2R^{2}>2r^{2}. For n=2n=2, the problem was significantly advanced by D. McDuff and L. Polterovich in [7 D. McDuff and L. Polterovich, Symplectic packings and algebraic geometry. Invent. Math. 115, 405–434 (1994) ], and then completely solved by P. Biran in [1 P. Biran, Symplectic packing in dimension 4. Geom. Funct. Anal. 7, 420–437 (1997) ]. In the contact case, Problem 258* is completely open.

259*

Rotating quantized polydisks. For r<Rr<R, consider the standard contact inclusion (x,y)(y,x)(x,y)\mapsto(-y,x). Let j^=j×Id\hat{j}=j\times\mathrm{Id}, ψ^=ψ×Id\hat{\psi}=\psi\times\mathrm{Id} be the corresponding contact inclusion P^(r,r)P^(R,R)\hat{P}(r,r)\to\hat{P}(R,R), and consider the contactomorphism ψ×Id ⁣:X=R2n×S1R2n×S1=X\psi\times\mathrm{Id}\colon X=\mathbb{R}^{2n}\times S^{1}\to\mathbb{R}^{2n}\times S^{1}=X. When are the embeddings j^,ψ^j^ ⁣:P^(r,r)P^(R,R)\hat{j},\hat{\psi}\circ\hat{j}\colon\hat{P}(r,r)\hookrightarrow\hat{P}(R,R) contact isotopic?

Note that a theorem of Floer–Hofer–Wysocki, see [4 A. Floer, H. Hofer and K. Wysocki, Applications of symplectic homology. I. Math. Z. 217, 577–606 (1994) ], states that when 2r2>R22r^{2}>R^{2} the symplectic embeddings j,ψ ⁣:P(r,r)P(R,R)j,\psi\colon P(r,r)\to\mathbb{P}(R,R) are not symplectically isotopic.

III Solutions

245

We consider a setting where there is a set of mm candidates

C={c1,,cm},m2,C=\{c_{1},\dots,c_{m}\},\quad m\geq 2,

and a set of nn voters [n]={1,,n}[n]=\{1,\dots,n\}. Each voter ranks all candidates from the most preferred one to the least preferred one; we write aiba\succ_{i}b if voter ii prefers candidate aa to candidate bb. A collection of all voters’ rankings is called a preference profile. We say that a preference profile is single-peaked if there is a total order \vartriangleleft on the candidates (called the axis) such that for each voter ii the following holds: if ii’s most preferred candidate is cc and abca\vartriangleleft b\vartriangleleft c or cbac\vartriangleleft b\vartriangleleft a, then biab\succ_{i}a. That is, each ranking has a single “peak”, and then “declines” in either direction from that peak.

(i) In general, if we aggregate voters’ preferences over candidates, the resulting majority relation may have cycles: e.g., if a1b1ca\succ_{1}b\succ_{1}c, b2c2ab\succ_{2}c\succ_{2}a and c3a3bc\succ_{3}a\succ_{3}b, then a strict majority (2 out of 3) voters prefer aa to bb, a strict majority prefer bb to cc, yet a strict majority prefer cc to aa. Argue that this cannot happen if the preference profile is single-peaked. That is, prove that if a profile is single-peaked, a strict majority of voters prefer aa to bb, and a strict majority of voters prefer bb to cc, then a strict majority of voters prefer aa to cc.

(ii) Suppose that nn is odd and voters’ preferences are known to be single-peaked with respect to an axis \vartriangleleft. Consider the following voting rule: we ask each voter ii to report their top candidate t(i)t(i), find a median voter ii^{*}, i.e.,

{i:t(i)t(i)}<n2and{i:t(i)t(i)}<n2,\lvert\{i:t(i)\vartriangleleft t(i^{*})\}\rvert<\frac{n}{2}\quad\textrm{and}\quad\lvert\{i:t(i^{*})\vartriangleleft t(i)\}\rvert<\frac{n}{2},

and output t(i)t(i^{*}). Argue that under this voting rule no voter can benefit from voting dishonestly, if a voter ii reports some candidate at(i)a\neq t(i) instead of t(i)t(i), this either does not change the outcome or results in an outcome that ii likes less than the outcome of the truthful voting.

(iii) We say that a preference profile is 1D-Euclidean if each candidate cjc_{j} and each voter ii can be associated with a point in R\mathbb{R} so that the preferences are determined by distances, i.e., there is an embedding x ⁣:C[n]Rx\colon C\cup[n]\to\mathbb{R} such that for all a,bCa,b\in C and i[n]i\in[n], we have aiba\succ_{i}b if and only if x(i)x(a)<x(i)x(b)\lvert x(i)-x(a)\rvert<\lvert x(i)-x(b)\rvert. Argue that a 1D-Euclidean profile is necessarily single-peaked. Show that the converse is not true, i.e., there exists a single-peaked profile that is not 1D-Euclidean.

(iv) Let PP be a single-peaked profile, and let LL be the set of candidates ranked last by at least one voter. Prove that L2\lvert L\rvert\leq 2.

(v) Consider an axis c1cmc_{1}\vartriangleleft\dots\vartriangleleft c_{m}. Prove that there are exactly 2m12^{m-1} distinct votes that are single-peaked with respect to this axis. Explain how to sample from the uniform distribution over these votes.

These problems are based on references [12 H. Moulin, Axioms of Cooperative Decision Making. Cambridge University Press, Cambridge (1991) ] (parts (i) and (ii)), [10 C. H. Coombs. Psychological scaling without a unit of measurement. Psychological Review 57, 145 (1950) ] (part (iii)) and [9 V. Conitzer, Eliciting single-peaked preferences using comparison queries. J. Artificial Intelligence Res. 35, 161–191 (2009) , 13 T. Walsh, Generating single peaked votes. arXiv:1503.02766 (2015) ] (part (v)); part (iv) is folklore. See also the survey [11 E. Elkind, M. Lackner and D. Peters. Structured preferences. In Trends in Computational Social Choice, edited by U. Endriss, Chapter 10, AI Access, 187–207 (2017) ].

Edith Elkind (University of Oxford, UK)

Solution by the proposer

(i) We can restrict the voters’ preferences to the set {a,b,c}\{a,b,c\}; the reader can check that a restriction of a single-peaked profile to a subset of candidates remains single-peaked. We consider three cases depending on how aa, bb and cc are ordered by the axis \vartriangleleft.

  1. abca\vartriangleleft b\vartriangleleft c or cbac\vartriangleleft b\vartriangleleft a. Then all voters who prefer aa over bb have aa as their top choice and hence prefer aa to cc.

  2. bacb\vartriangleleft a\vartriangleleft c or cabc\vartriangleleft a\vartriangleleft b. All voters who prefer cc over aa have cc as their top choice and hence prefer aa to bb; therefore, these voters are in minority.

  3. acba\vartriangleleft c\vartriangleleft b or bcab\vartriangleleft c\vartriangleleft a. This is impossible: all voters who prefer bb to cc have bb as their top choice, so we have a strict majority preferring bb over aa, a contradiction.

(ii) Suppose the winner under truthful voting is aa. Consider a voter ii. If t(i)=at(i)=a, then ii cannot improve the outcome by lying. So suppose t(i)at(i)\vartriangleleft a (the case at(i)a\vartriangleleft t(i) is symmetric). If ii reports aa or some candidate bb with bab\vartriangleleft a, this does not change what the top choice of the median voter is, and hence does not change the outcome. If ii reports a candidate cc with t(i)ct(i)\vartriangleleft c, then the median voter may shift to the right, i.e., further away from ii’s true top choice; as ii’s preferences are single-peaked, this does not improve the outcome from her perspective.

(iii) Ordering the candidates by their position, i.e., placing aa before bb on the axis \vartriangleleft if x(a)<x(b)x(a)<x(b) results in an axis witnessing that the input profile is single-peaked. To show that the converse is not true, consider the following four votes:

b1c1a1d,\displaystyle b\succ_{1}c\succ_{1}a\succ_{1}d,
c2b2a2d,\displaystyle c\succ_{2}b\succ_{2}a\succ_{2}d,
b3c3d3a,\displaystyle b\succ_{3}c\succ_{3}d\succ_{3}a,
c4b4d4a.\displaystyle c\succ_{4}b\succ_{4}d\succ_{4}a.

This profile is single-peaked on abcda\vartriangleleft b\vartriangleleft c\vartriangleleft d. Now, suppose for contradiction that it is 1D-Euclidean, i.e., it admits an embedding xx. Consider the positions of the four voters x(1),x(2),x(3),x(4)x(1),x(2),x(3),x(4). Assume without loss of generality that x(b)<x(c)x(b)<x(c). Then we have

x(1),x(3)<12(x(b)+x(c))x(1),x(3)<\frac{1}{2}(x(b)+x(c))

(as voters 1 and 3 prefer bb to cc) and

x(2),x(4)>12(x(b)+x(c))x(2),x(4)>\frac{1}{2}(x(b)+x(c))

(as voters 2 and 4 prefer bb to cc). But now consider the point 12(x(a)+x(d))\frac{1}{2}(x(a)+x(d)). Voters 1 and 2 have to be on one side of this point and voters 3 and 4 have to be on the other side of this point, because of their preferences over aa vs. dd. But this is clearly impossible!

(iv) Assume without loss of generality that PP is single-peaked with respect to the axis c1cmc_{1}\vartriangleleft\dots\vartriangleleft c_{m}. Clearly, PP may contain a vote that ranks c1c_{1} last or a vote that ranks cmc_{m} last. But it cannot contain a vote that ranks some cic_{i} with 1<i<m1<i<m last: if the top candidate in that vote is a cjc_{j} with j<ij<i, then this voter prefers cic_{i} to cmc_{m}, and if the top candidate in that vote is a ckc_{k} with k>ik>i, then this voter prefers cic_{i} to c1c_{1}.

(v) Induction. For m=2m=2, we have 2=2212=2^{2-1} orders, i.e., c1c2c_{1}\succ\nobreak c_{2} and c2c1c_{2}\succ\nobreak c_{1}. Now suppose the claim has been proved for all m<mm^{\prime}<\nobreak m. A vote that is single-peaked on c1cmc_{1}\vartriangleleft\dots\vartriangleleft c_{m} may have c1c_{1} in the last position, with candidates in top m1m-1 positions forming a single-peaked vote with respect to c2cmc_{2}\vartriangleleft\dots\vartriangleleft c_{m} (2m22^{m-2} options) or it may have cmc_{m} in the last position, with candidates in top m1m-\nobreak 1 positions forming a single-peaked vote with respect to c1cm1c_{1}\vartriangleleft\dots\vartriangleleft c_{m-1} (2m22^{m-2} options). For sampling, we can build the vote bottom-up. At the first step, we fill the last position with c1c_{1} or cmc_{m}, with probability 12\frac{1}{2} each. Once kk positions have been filled, 1km11\leq k\leq m-1, the not-yet-ranked candidates form a contiguous segment c1cjc_{1}\vartriangleleft\nobreak\dots\vartriangleleft c_{j} of the axis. We then fill position k+1k+1 from the bottom with cic_{i} or cjc_{j}, with equal probability. This sampling is uniform, because the probability of generating a specific ranking is exactly 2m+12^{-m+1}: we make m1m-1 choice, and with probability 12\frac{1}{2} each choice is consistent with the target ranking.

246

Consider a standard prisoners’ dilemma game described by the following strategic form, with δ>β>0>γ\delta>\beta>0>\gamma:

Assume that any given agent either plays CC or DD and that agents reproduce at a rate determined by their payoff from the strategic form of the game plus a constant ff. Suppose that members of an infinite population are assorted into finite groups of size nn. Let qq denote the proportion of agents playing strategy CC (“altruists”) in the population as a whole and qiq_{i} denote the proportion of agents playing CC in group ii. We assume that currently q(0,1)q\in(0,1).

The process of assortment is abstract, but we assume that it has finite expectation E[qi]=qE[q_{i}]=q and variance Var[qi]=σ2\operatorname{Var}[q_{i}]=\sigma^{2}. Members within each group are then randomly paired off to play one iteration of the prisoners’ dilemma against another member of their group. All agents then return to the overall population.

  1. Find a condition relating qq, σ2\sigma^{2}, β\beta, γ\gamma, δ\delta and nn under which the proportion of altruists in the overall population rises after a round of play.

  2. Now interpret this game as one where each player can confer a benefit bb upon the other player by individually incurring a cost cc, with b>c>0b>c>0, so that β=bc\beta=b-c, δ=b\delta=b and γ=c\gamma=-c. Prove that, as long as (i) there is some positive assortment in group formation and (ii) the ratio cb\frac{c}{b} is low enough, then the proportion of altruists in the overall population will rise after a round of play.

Richard Povey (Hertford College and St Hilda’s College, University of Oxford, UK)

Solution by the proposer

(a) We can firstly see that the number of altruists (type CC) and non-altruists (type DD) in group ii after a round of play will be given by

niqi=(β(nqi1n1)+γ(n(1qi)n1)+f)nqi,\displaystyle n_{i}^{\prime}q_{i}^{\prime}=\biggl(\beta\biggl(\frac{nq_{i}-1}{n-1}\biggr)+\gamma\biggl(\frac{n(1-q_{i})}{n-1}\biggr)+f\biggr)nq_{i},
ni(1qi)=(δ(nqin1)+f)n(1qi).\displaystyle n_{i}^{\prime}(1-q_{i}^{\prime})=\biggl(\delta\biggl(\frac{nq_{i}}{n-1}\biggr)+f\biggr)n(1-q_{i}).

Summing these two equalities yields

ni=βqi(n(nqi1)n1)+γqi(n2(1qi)n1)+δ(1qi)(n2qin1)+fn.\begin{split}n_{i}^{\prime}&=\beta q_{i}\biggl(\frac{n(nq_{i}-1)}{n-1}\biggr)+\gamma q_{i}\biggl(\frac{\smash{n^{2}}(1-q_{i})}{n-1}\biggr)\\ &\qquad+\delta(1-q_{i})\biggl(\frac{\smash{n^{2}}q_{i}}{n-1}\biggr)+fn.\end{split}

Given an infinite population and hence an infinite number of groups, the new proportion of altruists in the overall population will be

q=E[niqi]E[ni]=(β(nE[qi2]E[qi]n1)+nγ(E[qi]E[qi2]n1)+fE[qi])(βqi(nE[qi2]E[qi]n1)+nγ(E[qi]E[qi2]n1)+nδ(E[qi]E[qi2]n1)+f)1.\begin{split}q^{\prime}&=\frac{E[n_{i}^{\prime}q_{i}^{\prime}]}{E[n_{i}^{\prime}]}\\ &=\biggl(\beta\biggl(\frac{nE[q_{i}^{2}]-E[q_{i}]}{n-1}\biggr)+n\gamma\biggl(\frac{E[q_{i}]-E[q_{i}^{2}]}{n-1}\biggr)+fE[q_{i}]\biggr)\\ &\qquad\cdot\biggl(\beta q_{i}\biggl(\frac{nE[q_{i}^{2}]-E[q_{i}]}{n-1}\biggr)+n\gamma\biggl(\frac{E[q_{i}]-E[q_{i}^{2}]}{n-1}\biggr)\\ &\qquad\qquad+n\delta\biggl(\frac{E[q_{i}]-E[q_{i}^{2}]}{n-1}\biggr)+f\biggr)^{-1}.\end{split}

Substituting in E[qi2]=σ2+E[qi]2E[q_{i}^{2}]=\sigma^{2}+E[q_{i}]^{2} and E[qi]=qE[q_{i}]=q gives us

q=(β(nσ2+nq2qn1)+nγ(q(1q)σ2n1)+fq)(β(nσ2+nq2qn1)+nγ(q(1q)σ2n1)+nδ(q(1q)σ2n1)+f)1.\begin{split}q^{\prime}&=\biggl(\beta\biggl(\frac{n\sigma^{2}+nq^{2}-q}{n-1}\biggr)+n\gamma\biggl(\frac{q(1-q)-\sigma^{2}}{n-1}\biggr)+fq\biggr)\\ &\qquad\cdot\biggl(\beta\biggl(\frac{n\sigma^{2}+nq^{2}-q}{n-1}\biggr)+n\gamma\biggl(\frac{q(1-q)-\sigma^{2}}{n-1}\biggr)\\ &\qquad\qquad+n\delta\biggl(\frac{q(1-q)-\sigma^{2}}{n-1}\biggr)+f\biggr)^{-1}.\end{split}

Assuming ff is high enough to make the denominator positive, it then follows that

qq>0    (1q)(β(nσ2+nq2qn1)+nγ(q(1q)σ2n1))nqδ(q(1q)σ2n1)>0.\begin{split}&q^{\prime}-q>0\\[-3.0pt] &\quad\iff(1-q)\biggl(\beta\biggl(\frac{\smash{n\sigma^{2}+nq^{2}}-q}{n-1}\biggr)+n\gamma\biggl(\frac{q(1-q)-\smash{\sigma^{2}}}{n-1}\biggr)\biggr)\\ &\hskip 50.0pt-nq\delta\smash[b]{\biggl(\frac{q(1-q)-\smash{\sigma^{2}}}{n-1}\biggr)}>0.\end{split}

After some further rearrangement, we can derive the following:

qq>0    σ2q(1q)>1(n1n)(β(1q)(βγ)+qδ).\begin{split}&q^{\prime}-q>0\\[-3.0pt] &\quad\iff\frac{\smash{\sigma^{2}}}{q(1-q)}>1-\biggl(\frac{n-1}{n}\biggr)\biggl(\frac{\beta}{(1-q)(\beta-\gamma)+q\delta}\biggr).\end{split}

Since the right-hand side of (1) must be strictly between 00 and 11, this has the intuitive interpretation that the inter-group variance σ2\sigma^{2} must be sufficiently high relative to the intra-group variance1This is the variance of the Bernoulli variable B(q)B(q) which takes a value of 11 of a single individual drawn from the population is an altruist and 00 otherwise, which is q(1q)q(1-q). so that, although altruists do less well relative to non-altruists within each group, the concentration of altruists together within particular groups is sufficiently strong to confer enough of an evolutionary advantage to offset this and to enable altruists to do better evolutionarily than non-altruists in the overall population.2This result was first proved in a general evolutionary context by George R. Price [16 G. R. Price, Selection and covariance, Nature 227, 520–521 (1970) , 17 G. R. Price, Extension of covariance selection mathematics, Ann. Human Genetics 35, 485–490 (1972) ].

(b) In the case where β=bc\beta=b-c, δ=b\delta=b and γ=c\gamma=-c, condition (1) can be rearranged to give

cb<(σ2q(1q))(nn1)1n1.\frac{c}{b}<\biggl(\frac{\sigma^{2}}{q(1-q)}\biggr)\biggl(\frac{n}{n-1}\biggr)-\frac{1}{n-1}.

With random assortment, qiq_{i} would be equal to Xin\frac{X_{i}}{n} where XiX_{i}, the number of altruists in group ii would have a binomial distribution: XiB(n,q)X_{i}\sim B(n,q). Therefore

σ2=Var[Xin]=q(1q)nn2=q(1q)n.\sigma^{2}=\operatorname{Var}\biggl[\frac{X_{i}}{n}\biggr]=\frac{q(1-q)n}{n^{2}}=\frac{q(1-q)}{n}.

With perfect positive correlation between group members, we would get

σ2=Var[Xin]=q(1q)n2n2=q(1q).\sigma^{2}=\operatorname{Var}\biggl[\frac{X_{i}}{n}\biggr]=\frac{q(1-q)n^{2}}{n^{2}}=q(1-q).

With some positive assortment generating positive covariance between group members, we may therefore without loss of generality suppose that

σ2=q(1q)n+q(1q)ε(n2n)n2=q(1q)n+εq(1q)(n1)n,\begin{split}\sigma^{2}&=\frac{q(1-q)n+q(1-q)\varepsilon(n^{2}-n)}{n^{2}}\\ &=\frac{q(1-q)}{n}+\frac{\varepsilon q(1-q)(n-1)}{n},\end{split}

where ε(0,1)\varepsilon\in(0,1). Plugging this into (2) and simplifying, we get cb<ε\frac{c}{b}<\varepsilon. So we can see that for any ε>0\varepsilon>0 there always exists a value of cb\frac{c}{b} low enough for altruists to expand as a proportion of the overall population.3The literature on this model has further established the results that multiple periods of isolation in finite groups acts to amplify inter-group variance, so that even with random assortment into groups altruism can evolve [14 B. Cooper and C. Wallace, Group selection and the evolution of altruism. Oxford Economic Papers 56, 307–330 (2004) ]. It has also been found that use of punishment strategies in dynamic interactions can act to weaken this group selection mechanism [15 R. Povey, Punishment and the potency of group selection, J. Evolutionary Economics 24 (2014) ]. For an accessible book-length treatment of the topic of group selection in the biological and social sciences, see [18 E. Sober and D. S. Wilson, Unto Others, Harvard University Press, Cambridge, Massachusetts (1999) ].

247

Consider a village consisting of n farmers who live along a circle of length nn. The farmers live at positions 1,2,,n1,2,\ldots,n. Each of them is friends with the person to the left and right of them, and each friendship has capacity mm where mm is a non-negative integer. At the end of the year, each farmer does either well (her wealth is +1+1 dollars) or not well (her wealth is 1-1 dollars) with equal probability. Farmers’ wealth realizations are independent of each other. Hence, for a large circle the share of farmers in each state is on average 11.

The farmers share risk by transferring money to their direct neighbors. The goal of risk-sharing is to create as many farmers with OK wealth (0 dollars) as possible. Transfers have to be in integer dollars and cannot exceed the capacity of each link (which is mm).

A few examples with a village of size n=4n=4 serve to illustrate risk-sharing.

  • Consider the case where farmers 1 to 4 have wealth

    (+1,1,+1,1).(+1,-1,+1,-1).

    In that case, we can share risk completely with farmer 11 sending a dollar to agent 22 and farmer 33 sending a dollar to farmer 44. This works for any m1m\geq 1.

  • Consider the case where farmers 11 to 44 have wealth

    (+1,+1,1,1).(+1,+1,-1,-1).

    In that case, we can share risk completely with farmer 11 sending a dollar to farmer 22, farmer 22 sending two dollars to farmer 33 and farmer 33 sending one dollar to farmer 44. In this case, we need m2m\geq 2. If m=1m=1, we can only share risk among half the people in the village.

Show that for any wealth realization an optimal risk-sharing arrangement can be found as the solution to a maximum flow problem.

Tanya Rosenblat (School of Information and Department of Economics, University of Michigan, USA)

Solution by the proposer

We augment the village graph by adding two auxiliary nodes. The source nodess is connected to all the farmers with positive wealth (+1+1) and each of these links has capacity 11. The sink nodett is connected to all the farmers with negative wealth (1-1) and each of these links also capacity 11. We now look for the maximum flow from ss to tt: this is equal to the number of luck/unlucky farmer pairs who can be matched under the best risk-sharing arrangement.

248

This exercise is a continuation of Problem 247 where we studied risk-sharing among farmers who live on a circle village and are friends with their direct neighbors to the left and right with friendships of a certain capacity. Assume that for any realization of wealth levels the best possible risk-sharing arrangement is implemented and denote the expected share of unmatched farmers with U(n,m)U(n,m). Show that U(n,m)12m+1U(n,m)\to\frac{1}{2m+1} as nn\to\infty.

Tanya Rosenblat (School of Information and Department of Economics, University of Michigan, USA)

Solution by the proposer

The solution proceeds in two stages. In Problem 247, we already established that the problem can be understood as a maximum flow problem. We first formulate a particular algorithm that implements this flow. We then use this algorithm to express U(n,m)U(n,m) in closed form.

Risk-sharing as a Maximum Flow Problem

We next describe a matching algorithm which is to run for mm rounds. The claim is that this algorithm implements the maximum flow in the augmented graph for any mm. For the purpose of this algorithm, we call a black agent an agent with positive shock and a white agent an agent with a negative shock.

Step I: Index all agents from 11 to nn clockwise (11 is the neighbor of nn on a circle). Set the counter ii to 11.

Step II: If agents ii and i+1i+1 are of different colors, label them “matched” and move the counter clockwise to i+2i+2. If agent i+1i+1 has the same color as agent ii, then declare agent ii “unmatched” and move the counter clockwise to agent i+1i+1. Repeat this step until the counter has reached the first agent again.

Step III: Define a new circle by ordering all the unmatched agents on a circle without disturbing the order of the agents. Essentially, this implies that all the matched agents are simply removed from the circle and any gaps are plugged by connected the closest unmatched agents with each other. Repeat steps I and II for this new circle. Repeat this algorithm mm times.

Lemma 1. The above matching algorithm implements the maximum flow.

Proof. The Ford–Fulkerson algorithm computes the maximum flow by looking for open paths which can carry positive flow and then constructing a graph with augmented capacities in which the next path is found, etc. Once no more open path exists the max flow has been implemented. The above algorithm implements Ford–Fulkerson using a particular order of selecting open paths. Therefore, it implements the max flow.

Closed form solutions. We next prove the following lemma.

Lemma 2. Assume we have a circle of size nn where the probability that an agent has a neighbor of the same color is α\alpha. Then the share of unmatched agents after one round of the above algorithm converges to α2α\frac{\alpha}{2-\alpha} as nn\to\infty.

Proof. In each instance of step I of the algorithm, it produces an unmatched agent with probability α\alpha and a pair of matched agents with probability 1α1-\alpha. The sum of unmatched and matched agents has to be nn. Therefore the share of unmatched agents converges to

αα+2(1α)=α2α.\smash{\frac{\alpha}{\alpha+2(1-\alpha)}}=\smash{\frac{\alpha}{2-\alpha}}.

The final step in the proof of the result is to derive the probability αm\alpha_{m} that an agent is followed by a same-color agent in round mm. We know that in round 11 shocks are i.i.d.; therefore α1=12\alpha_{1}=\frac{1}{2}. We start by proving a recursive formula for calculating αm\alpha_{m}.

Lemma 3. If the sequential probability is αm\alpha_{m} in round mm, then the sequential probability in round m+1m+1 satisfies

αm+1=2αm32αm.\alpha_{m+1}=\smash[b]{\frac{2-\alpha_{m}}{3-2\alpha_{m}}}.

Proof. Consider an agent ii on whom the counter rested at some point in the algorithm and who stays unmatched in the current round. This must be because he has a neighbor i+1i+1 of the same color (without loss of generality assume both are black). With probability αm\alpha_{m} agent i+2i+2 is also black and therefore agent i+1i+1 will survive into round m+1m+1 as well and be of the same color as agent ii (black). With probability 1αm1-\alpha_{m} agent i+2i+2 is white. In this case agents i+1i+1 and i+2i+2 can be matched. Matching can continue for the subsequent pairs of agents (i+3,i+4)(i+3,i+4), (i+5,i+6)(i+5,i+6), etc.; it will only stop if for any of these pairs agents have the same color. This will happen with probability αm\alpha_{m}. To figure out it if this process will stop at a “white pair” or a “black pair” (let’s call it the “blocking pair”) it is crucial to know whether agent i+2i+2, i+4i+4, i+6i+6, etc. (i.e., the agent just prior to the blocking pair) is white or black.

We know that agent i+2i+2 is white. What is the probability that agent i+4i+4 is the same color (provided (i+3,i+4)(i+3,i+4) is not a blocking pair)? This can only happen if the pair (i+3,i+4)(i+3,i+4) is a black agent followed by a white agent. If it is a white agent followed by a black agent then i+4i+4 has a different color from i+2i+2. So the probability of a color change is

αm(1αm)αm(1αm)+(1αm)2=αm.\frac{\alpha_{m}(1-\alpha_{m})}{\alpha_{m}(1-\alpha_{m})+(1-\alpha_{m})^{2}}=\alpha_{m}.

Assume that the probability that the agent prior to the blocking pair is of the same color as i+2i+2 is qq. With probability αm\alpha_{m} the pair (i+3,i+4)(i+3,i+4) is a blocking pair and with probability 1αm1-\alpha_{m} the pair is not blocking. In that case agent i+4i+4 has a different color from agent i+2i+2 with probability αm\alpha_{m}. Because of the recursive nature of the problem, the probability that the agent prior to the blocking pair has the same color as i+4i+4 is qq. Therefore we know that

q=αm+(1αm)[(1αm)q+(1q)αm].q=\alpha_{m}+(1-\alpha_{m})[(1-\alpha_{m})q+(1-q)\alpha_{m}].

This allows us to calculate qq as

q=αm(2αm)1(1αm)(12αm)=2αm32αm.q=\frac{\alpha_{m}(2-\alpha_{m})}{1-(1-\alpha_{m})(1-2\alpha_{m})}=\frac{2-\alpha_{m}}{3-2\alpha_{m}}.

So we know that the agent prior to the blocking pair is white with probability qq. The blocking pair is therefore a black blocking pair with probability q(1αm)+(1q)αmq(1-\alpha_{m})+(1-q)\alpha_{m}. Therefore the total probability that the next unmatched agent after agent ii is of the same color (black in this case) is

αm+1=αm+(1αm)[q(1αm)+(1q)αm]=q=2αm32αm.\begin{split}\alpha_{m+1}&=\alpha_{m}+(1-\alpha_{m})[q(1-\alpha_{m})+(1-q)\alpha_{m}]\\ &=q=\frac{2-\alpha_{m}}{3-2\alpha_{m}}.\end{split}

We can check that αm=112m\alpha_{m}=1-\frac{1}{2m} satisfies both the initial condition and the recursive equation 3. This implies that

αm2αm=2m12m+1.\frac{\alpha_{m}}{2-\alpha_{m}}=\frac{2m-1}{2m+1}.

Finally, note that the share of unmatched agents (for nn\to\infty) can be calculated by taking the product of the share of unmatched agents in each round:

limnU(n,m)=i=1mαi2αi=12m+1.\lim_{n\to\infty}U(n,m)=\smash{\prod_{i=1}^{m}\frac{\alpha_{i}}{2-\alpha_{i}}}=\frac{1}{2m+1}.

249

In a combinatorial auction there are mm items for sale to nn buyers. Each buyer ii has some valuation function vi()v_{i}(\cdot) which takes as input a set SS of items and outputs that bidder’s value for that set. These functions will always be monotone (vi(ST)vi(S)v_{i}(S\cup T)\geq v_{i}(S) for all S,TS,T), and satisfy vi()=0v_{i}(\emptyset)=0.

Definition 1 (Walrasian equilibrium). A price vector pR0m\vec{p}\in\mathbb{R}_{\geq 0}^{m} and a list B1,,BnB_{1},\ldots,B_{n} of subsets of [m][m] form a Walrasian equilbrium for v1,,vnv_{1},\ldots,v_{n} if the following two properties hold:

  • Each BiargmaxS{vi(S)jSpj}B_{i}\in\arg\max_{S}\{v_{i}(S)-\sum_{j\in S}p_{j}\}.

  • The sets BiB_{i} are disjoint, and iBi=[m]\mathop{\bigcup}_{i}B_{i}=[m].

Prove that a Walrasian equilibrium exists for v1,,vnv_{1},\ldots,v_{n} if and only if there exists an integral4That is, a point such that each xi,S{0,1}x_{i,S}\in\{0,1\}. optimum to the following linear program:

maximize iSvi(S)xi,S\displaystyle\textrm{maximize}\ \sum_{i}\sum_{S}v_{i}(S)\cdot x_{i,S}
such that,for all i,Sxi,S=1,for all j,Sjixi,S1,for all i,S,xi,S0.\displaystyle\begin{aligned} \textrm{such that},\,&\textrm{for all}\ i,&\sum_{S}x_{i,S}&=1,\\ &\textrm{for all}\ j,&\sum_{S\ni j}\sum_{i}x_{i,S}&\leq 1,\\[-3.0pt] &\textrm{for all}\ i,S,&x_{i,S}&\geq 0.\end{aligned}

Hint. Take the dual, and start from there.

Matt Weinberg (Computer Science, Princeton University, USA)

Solution by the proposer

First, we take the dual of the given LP. We use the dual variable pjp_{j} for the constraints involving items, and the dual variable uiu_{i} for the constraints involving bidders. Then the dual problem is

minimize iui+jpj\displaystyle\textrm{minimize}\ \sum_{i}u_{i}+\sum_{j}p_{j}
such that,for all i,S,ui+jSpjvi(S),for all j,pj0.\displaystyle\begin{aligned} \textrm{such that},\,&\textrm{for all}\ i,S,&u_{i}+\sum_{j\in S}p_{j}&\geq v_{i}(S),\\[-3.0pt] &\textrm{for all}\ j,&p_{j}&\geq 0.\end{aligned}

Walrasian equilibrium implies integral optimum

Now, assume that a Walrasian equilibrium exists, and let it be p1,,pmp_{1},\ldots,p_{m} and B1,,BnB_{1},\ldots,B_{n}. Then consider the integral solution to the LP that sets xi,Bi=1x_{i,B_{i}}=1 for all ii, and all other variables to 00. This solution is clearly feasible for the LP, and has objective value equal to ivi(Bi)\sum_{i}v_{i}(B_{i}).

Consider also the dual solution ui:vi(Bi)jBipju_{i}\coloneq v_{i}(B_{i})-\sum_{j\in B_{i}}p_{j}, with pjp_{j} as given in the Walrasian equilibrium. We claim this is a feasible solution to the dual. To see this, observe first that each pj0p_{j}\geq 0. Also, because BiargmaxS{vi(S)jSpj}B_{i}\in\arg\max_{S}\{v_{i}(S)-\sum_{j\in S}p_{j}\} by definition of Walrasian equilibrium, we have that

ui:vi(Bi)jBipjvi(S)jSpjfor all S.u_{i}\coloneq v_{i}(B_{i})-\sum_{j\in B_{i}}p_{j}\geq v_{i}(S)-\sum_{j\in S}p_{j}\quad\textrm{for all}\ S.

Therefore, all dual constraints are satisfied, and this is a feasible dual. Moreover, observe that the value of the dual objective is

iui+jpj=i(vi(Bi)jBipj)+jpj=ivi(Bi).\sum_{i}u_{i}+\sum_{j}p_{j}=\sum_{i}\Bigl(v_{i}(B_{i})-\sum_{j\in B_{i}}p_{j}\Bigr)+\sum_{j}p_{j}=\sum_{i}v_{i}(B_{i}).

The last equality follows because each item is in exactly one bundle BiB_{i}. So we have proved that if (p,B)(\vec{p},\vec{B}) is a Walrasian equilibrium, then there is an integral feasible point for the LP with objective value ivi(Bi)\sum_{i}v_{i}(B_{i}), and also a feasible dual solution with value ivi(Bi)\sum_{i}v_{i}(B_{i}). By LP duality, both feasible solutions are in fact optimal. Therefore, there is an integral optimum for the LP.

Integral optimum implies Walrasian equilibrium

Now, assume that the LP has an integral optimum. Observe that for this integral solution, there must exist disjoint sets B1,,BnB_{1},\ldots,B_{n} such that for each ii, xi,Bi=1x_{i,B_{i}}=1 and all other variables are 00. The LP value for this solution is ivi(Bi)\sum_{i}v_{i}(B_{i}). Moreover, observe that if any item jiBij\notin\cup_{i}B_{i}, we can add jj to an arbitrary BiB_{i} without decreasing ivi(Bi)\sum_{i}v_{i}(B_{i}) (because each vi()v_{i}(\cdot) is monotone). Therefore, if there is an integral optimum to the LP, there exist disjoint B1,,BnB_{1},\ldots,B_{n} such that iBi=[m]\cup_{i}B_{i}=[m] and ivi(Bi)\sum_{i}v_{i}(B_{i}) is the optimal solution to the LP.

By Strong LP Duality, there also exists a feasible dual solution p1,,pm,u1,,unp_{1},\ldots,p_{m},u_{1},\ldots,u_{n} such that iui+jpj=ivi(Bi)\sum_{i}u_{i}+\sum_{j}p_{j}=\sum_{i}v_{i}(B_{i}). We will claim that (p,B)(\vec{p},\vec{B}) form a Walrasian equilibrium.

For a proof by contradiction, assume that this is not the case. Then there must be some bidder ii such that BiargmaxS{vi(S)jSpj}B_{i}\notin\arg\max_{S}\{v_{i}(S)-\sum_{j\in S}p_{j}\}. In particular, this means that there exists some BiB^{\prime}_{i} such that vi(Bi)jBi>vi(Bi)jBiv_{i}(B^{\prime}_{i})-\sum_{j\in B^{\prime}_{i}}>v_{i}(B_{i})-\sum_{j\in B_{i}}. Because uiu_{i} is a feasible solution for the dual, we then conclude that

uivi(Bi)jBi>vi(Bi)