{
"type": "Article",
"authors": [
{
"type": "Person",
"familyNames": [
"Rassias"
],
"givenNames": [
"Michael",
"T."
]
}
],
"identifiers": [],
"references": [
{
"type": "Article",
"id": "bib-bib1",
"authors": [],
"title": "\nV. Conitzer,\nEliciting single-peaked preferences using comparison queries.\nJ. Artificial Intelligence Res.35, 161–191 (2009)\n"
},
{
"type": "Article",
"id": "bib-bib2",
"authors": [],
"title": "\nC. H. Coombs.\nPsychological scaling without a unit of measurement.\nPsychological Review57, 145 (1950)\n"
},
{
"type": "Article",
"id": "bib-bib3",
"authors": [],
"title": "\nE. Elkind, M. Lackner and D. Peters.\nStructured preferences.\nIn Trends in Computational Social Choice,\nedited by U. Endriss,\nChapter 10,\nAI Access, 187–207 (2017)\n"
},
{
"type": "Article",
"id": "bib-bib4",
"authors": [],
"title": "\nH. Moulin,\nAxioms of Cooperative Decision Making.\nCambridge University Press, Cambridge (1991)\n"
},
{
"type": "Article",
"id": "bib-bib5",
"authors": [],
"title": "\nT. Walsh,\nGenerating single peaked votes.\narXiv:1503.02766 (2015)\n",
"url": "http://arxiv.org/abs/1503.02766"
},
{
"type": "Article",
"id": "bib-bib6",
"authors": [],
"title": "\nB. Cooper and C. Wallace,\nGroup selection and the evolution of altruism.\nOxford Economic Papers56, 307–330 (2004)\n"
},
{
"type": "Article",
"id": "bib-bib7",
"authors": [],
"title": "\nR. Povey,\nPunishment and the potency of group selection,\nJ. Evolutionary Economics24 (2014)\n"
},
{
"type": "Article",
"id": "bib-bib8",
"authors": [],
"title": "\nG. R. Price,\nSelection and covariance,\nNature227, 520–521 (1970)\n"
},
{
"type": "Article",
"id": "bib-bib9",
"authors": [],
"title": "\nG. R. Price,\nExtension of covariance selection mathematics,\nAnn. Human Genetics35, 485–490 (1972)\n"
},
{
"type": "Article",
"id": "bib-bib10",
"authors": [],
"title": "\nE. Sober and D. S. Wilson,\nUnto Others,\nHarvard University Press, Cambridge, Massachusetts (1999)\n"
},
{
"type": "Article",
"id": "bib-bib11",
"authors": [],
"title": "\nC. Ballester, A. Calvó-Armengol and Y. Zenou,\nWho’s who in networks. Wanted: the key player.\nEconometrica74, 1403–1417 (2006)\n"
},
{
"type": "Article",
"id": "bib-bib12",
"authors": [],
"title": "\nM. O. Jackson and Y. Zenou,\nGames on networks.\nIn Handbook of Game Theory. Vol. 4,\nedited by H. P. Young and S. Zamir,\nHandbooks in Economics, 91–157,\nElsevier/North-Holland, Amsterdam (2015)\n"
},
{
"type": "Article",
"id": "bib-bib13",
"authors": [],
"title": "\nY. Sun, W. Zhao and J. Zhou,\nStructural interventions in networks.\narXiv:2101.12420 (2021)\n",
"url": "http://arxiv.org/abs/2101.12420"
},
{
"type": "Article",
"id": "bib-bib14",
"authors": [],
"title": "\nG. Ashkenazi-Golan, I. Krasikov, C. Rainer and E. Solan,\nAbsorption paths and equilibria in quitting games.\narXiv:2012.04369 (2021)\n",
"url": "http://arxiv.org/abs/2012.04369"
},
{
"type": "Article",
"id": "bib-bib15",
"authors": [],
"title": "\nJ. Flesch, F. Thuijsman and K. Vrieze,\nCyclic Markov equilibria in stochastic games.\nInternat. J. Game Theory26, 303–314 (1997)\n"
},
{
"type": "Article",
"id": "bib-bib16",
"authors": [],
"title": "R. S. Simon,\nThe structure of non-zero-sum stochastic games.\nAdv. in Appl. Math.38, 1–26 (2007)\n"
},
{
"type": "Article",
"id": "bib-bib17",
"authors": [],
"title": "\nR. S. Simon,\nA topological approach to quitting games.\nMath. Oper. Res.37, 180–195 (2012)\n"
},
{
"type": "Article",
"id": "bib-bib18",
"authors": [],
"title": "\nE. Solan,\nThree-player absorbing games.\nMath. Oper. Res.24, 669–698 (1999)\n"
},
{
"type": "Article",
"id": "bib-bib19",
"authors": [],
"title": "\nE. Solan,\nThe dynamics of the Nash correspondence and n-player stochastic games.\nInt. Game Theory Rev.3, 291–299 (2001)\n"
},
{
"type": "Article",
"id": "bib-bib20",
"authors": [],
"title": "\nE. Solan and O. N. Solan,\nQuitting games and linear complementarity problems.\nMath. Oper. Res.45, 434–454 (2020)\n"
},
{
"type": "Article",
"id": "bib-bib21",
"authors": [],
"title": "E. Solan and N. Vieille,\nQuitting games.\nMath. Oper. Res.26, 265–285 (2001)\n"
},
{
"type": "Article",
"id": "bib-bib22",
"authors": [],
"title": "\nE. Solan and N. Vieille,\nQuitting games – an example.\nInternat. J. Game Theory31, 365–381 (2002)\n"
},
{
"type": "Article",
"id": "bib-bib23",
"authors": [],
"title": "\nP. Hagelstein, D. Herden and A. Stokolos,\nA theorem of Besicovitch and a generalization of the Birkhoff ergodic theorem.\nProc. Amer. Math. Soc. Ser. B8, 52–59 (2021)\n"
},
{
"type": "Article",
"id": "bib-bib24",
"authors": [],
"title": "\nD. Tanny,\nA zero-one law for stationary sequences.\nZ. Wahrscheinlichkeitstheorie und Verw. Gebiete30, 139–148 (1974)\n"
},
{
"type": "Article",
"id": "bib-bib25",
"authors": [],
"title": "\nD. Volný and B. Weiss,\nCoboundaries in L0∞.\nAnn. Inst. H. Poincaré Probab. Statist.40, 771–778 (2004)\n"
},
{
"type": "Article",
"id": "bib-bib26",
"authors": [],
"title": "\nA. Kiro, Y. Smilansky and U. Smilansky,\nThe distribution of path lengths on directed weighted graphs.\nIn Analysis as a Tool in Mathematical Physics,\nOper. Theory Adv. Appl. 276,\nBirkhäuser/Springer, Cham, 351–372 (2020)\n"
},
{
"type": "Article",
"id": "bib-bib27",
"authors": [],
"title": "\nY. Smilansky,\nUniform distribution of Kakutani partitions generated by substitution schemes.\nIsrael J. Math.240, 667–710 (2020)\n"
}
],
"title": "Solved and unsolved problems",
"meta": {},
"content": [
{
"type": "Paragraph",
"id": "p1",
"content": [
"The present column is devoted to Game Theory."
]
},
{
"type": "Heading",
"id": "S1",
"depth": 1,
"content": [
"I Six new problems – solutions solicited"
]
},
{
"type": "Paragraph",
"id": "S1.p1",
"content": [
"Solutions will appear in a subsequent issue."
]
},
{
"type": "Heading",
"id": "S1.SSx1",
"depth": 2,
"content": [
"245"
]
},
{
"type": "Paragraph",
"content": [
"We consider a setting where there is a set of ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "m",
"meta": {
"altText": "m"
}
},
" candidates"
]
},
{
"type": "MathBlock",
"id": "S1.Ex1",
"mathLanguage": "mathml",
"text": "C={c1,…,cm},m≥2,",
"meta": {
"altText": "C=\\{c_{1},\\dots,c_{m}\\},\\quad m\\geq 2,"
}
},
{
"type": "Paragraph",
"content": [
"and a set of ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "n",
"meta": {
"altText": "n"
}
},
" voters ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "[n]={1,…,n}",
"meta": {
"altText": "[n]=\\{1,\\dots,n\\}"
}
},
".\nEach voter ranks all candidates from the most preferred one to the least preferred one; we write ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "a≻ib",
"meta": {
"altText": "a\\succ_{i}b"
}
},
" if voter ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "i",
"meta": {
"altText": "i"
}
},
" prefers candidate ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "a",
"meta": {
"altText": "a"
}
},
" to candidate ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "b",
"meta": {
"altText": "b"
}
},
".\nA collection of all voters’ rankings is called a ",
{
"type": "Emphasis",
"content": [
"preference profile"
]
},
".\nWe say that a preference profile is ",
{
"type": "Emphasis",
"content": [
"single-peaked"
]
},
" if there is a total order ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "⊲",
"meta": {
"altText": "\\vartriangleleft"
}
},
" on the candidates (called the ",
{
"type": "Emphasis",
"content": [
"axis"
]
},
") such that for each voter ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "i",
"meta": {
"altText": "i"
}
},
" the following holds: if ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "i",
"meta": {
"altText": "i"
}
},
"’s most preferred candidate is ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "c",
"meta": {
"altText": "c"
}
},
" and ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "a⊲b⊲c",
"meta": {
"altText": "a\\vartriangleleft b\\vartriangleleft c"
}
},
" or ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "c⊲b⊲a",
"meta": {
"altText": "c\\vartriangleleft b\\vartriangleleft a"
}
},
", then ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "b≻ia",
"meta": {
"altText": "b\\succ_{i}a"
}
},
".\nThat is, each ranking has a single ‘peak’, and then ‘declines’ in either direction from that peak."
]
},
{
"type": "Paragraph",
"content": [
"(i) In general, if we aggregate voters’ preferences over candidates, the resulting majority relation may have cycles: e.g., if ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "a≻1b≻1c",
"meta": {
"altText": "a\\succ_{1}b\\succ_{1}c"
}
},
", ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "b≻2c≻2a",
"meta": {
"altText": "b\\succ_{2}c\\succ_{2}a"
}
},
" and ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "c≻3a≻3b",
"meta": {
"altText": "c\\succ_{3}a\\succ_{3}b"
}
},
", then a strict majority (2 out of 3) voters prefer ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "a",
"meta": {
"altText": "a"
}
},
" to ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "b",
"meta": {
"altText": "b"
}
},
", a strict majority prefer ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "b",
"meta": {
"altText": "b"
}
},
" to ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "c",
"meta": {
"altText": "c"
}
},
", yet a strict majority prefer ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "c",
"meta": {
"altText": "c"
}
},
" to ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "a",
"meta": {
"altText": "a"
}
},
".\nArgue that this cannot happen if the preference profile is single-peaked.\nThat is, prove that if a profile is single-peaked, a strict majority of voters prefer ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "a",
"meta": {
"altText": "a"
}
},
" to ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "b",
"meta": {
"altText": "b"
}
},
", and a strict majority of voters prefer ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "b",
"meta": {
"altText": "b"
}
},
" to ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "c",
"meta": {
"altText": "c"
}
},
", then a strict majority of voters prefer ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "a",
"meta": {
"altText": "a"
}
},
" to ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "c",
"meta": {
"altText": "c"
}
},
"."
]
},
{
"type": "Paragraph",
"content": [
"(ii) Suppose that ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "n",
"meta": {
"altText": "n"
}
},
" is odd and voters’ preferences are known to be single-peaked with respect to an axis ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "⊲",
"meta": {
"altText": "\\vartriangleleft"
}
},
".\nConsider the following voting rule: we ask each voter ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "i",
"meta": {
"altText": "i"
}
},
" to report their top candidate ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "t(i)",
"meta": {
"altText": "t(i)"
}
},
", find a median voter ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "i*",
"meta": {
"altText": "i^{*}"
}
},
", i.e."
]
},
{
"type": "MathBlock",
"id": "S1.Ex2",
"mathLanguage": "mathml",
"text": "|{i:t(i)⊲t(i*)}|<n2and|{i:t(i*)⊲t(i)}|<n2,",
"meta": {
"altText": "\\lvert\\{i:t(i)\\vartriangleleft t(i^{*})\\}\\rvert<\\frac{n}{2}\\quad\\text{and}\\quad\\lvert\\{i:t(i^{*})\\vartriangleleft t(i)\\}\\rvert<\\frac{n}{2},"
}
},
{
"type": "Paragraph",
"content": [
"and output ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "t(i*)",
"meta": {
"altText": "t(i^{*})"
}
},
".\nArgue that under this voting rule no voter can benefit from voting dishonestly, if a voter ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "i",
"meta": {
"altText": "i"
}
},
" reports some candidate ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "a≠t(i)",
"meta": {
"altText": "a\\neq t(i)"
}
},
" instead of ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "t(i)",
"meta": {
"altText": "t(i)"
}
},
", this either does not change the outcome or results in an outcome that ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "i",
"meta": {
"altText": "i"
}
},
" likes less than the outcome of the truthful voting."
]
},
{
"type": "Paragraph",
"content": [
"(iii) We say that a preference profile is ",
{
"type": "Emphasis",
"content": [
"1D-Euclidean"
]
},
" if each candidate ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "cj",
"meta": {
"altText": "c_{j}"
}
},
" and each voter ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "i",
"meta": {
"altText": "i"
}
},
" can be associated with a point in ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "ℝ",
"meta": {
"altText": "\\mathbb{R}"
}
},
" so that the preferences are determined by distances, i.e. there is an embedding ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "x:C∪[n]→ℝ",
"meta": {
"altText": "x\\colon C\\cup[n]\\to\\mathbb{R}"
}
},
" such that for all ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "a,b∈C",
"meta": {
"altText": "a,b\\in C"
}
},
" and ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "i∈[n]",
"meta": {
"altText": "i\\in[n]"
}
},
" we have ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "a≻ib",
"meta": {
"altText": "a\\succ_{i}b"
}
},
" if and only if ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "|x(i)-x(a)|<|x(i)-x(b)|",
"meta": {
"altText": "\\lvert x(i)-x(a)\\rvert<\\lvert x(i)-x(b)\\rvert"
}
},
".\nArgue that a 1D-Euclidean profile is necessarily single-peaked.\nShow that the converse is not true, i.e. there exists a single-peaked profile that is not 1D-Euclidean."
]
},
{
"type": "Paragraph",
"content": [
"(iv) Let ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "P",
"meta": {
"altText": "P"
}
},
" be a single-peaked profile, and let ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "L",
"meta": {
"altText": "L"
}
},
" be the set of candidates ranked last by at least one voter.\nProve that ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "|L|≤2",
"meta": {
"altText": "\\lvert L\\rvert\\leq 2"
}
},
"."
]
},
{
"type": "Paragraph",
"content": [
"(v) Consider an axis ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "c1⊲…⊲cm",
"meta": {
"altText": "c_{1}\\vartriangleleft\\dots\\vartriangleleft c_{m}"
}
},
".\nProve that there are exactly ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "2m-1",
"meta": {
"altText": "2^{m-1}"
}
},
" distinct votes that are single-peaked with respect to this axis.\nExplain how to sample from the uniform distribution over these votes."
]
},
{
"type": "Paragraph",
"content": [
"These problems are based on references [",
{
"type": "Cite",
"target": "bib-bib4",
"content": [
"4"
]
},
"] (parts (i) and (ii)), [",
{
"type": "Cite",
"target": "bib-bib2",
"content": [
"2"
]
},
"] (part (iii)) and [",
{
"type": "Cite",
"target": "bib-bib1",
"content": [
"1"
]
},
", ",
{
"type": "Cite",
"target": "bib-bib5",
"content": [
"5"
]
},
"] (part (v)); part (iv) is folklore.\nSee also the survey [",
{
"type": "Cite",
"target": "bib-bib3",
"content": [
"3"
]
},
"]."
]
},
{
"type": "Paragraph",
"id": "S1.SSx1.p8",
"content": [
{
"type": "Emphasis",
"content": [
"Edith Elkind (University of Oxford, UK)"
]
}
]
},
{
"type": "Heading",
"id": "S1.SSx2",
"depth": 2,
"content": [
"246"
]
},
{
"type": "Paragraph",
"id": "S1.SSx2.p1",
"content": [
"Consider a standard prisoners’ dilemma game described by the following strategic form, with ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "\\beta>0>\\gamma\" display=\"inline\">δ>β>0>γ",
"meta": {
"altText": "\\delta>\\beta>0>\\gamma"
}
},
":"
]
},
{
"type": "Figure",
"id": "S1-SSx2-fig1",
"content": [
{
"type": "ImageObject",
"contentUrl": "246-1.png",
"mediaType": "image/png",
"meta": {
"inline": false
}
}
]
},
{
"type": "Paragraph",
"id": "S1.SSx2.p2",
"content": [
"Assume that any given agent either plays ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "C",
"meta": {
"altText": "C"
}
},
" or ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "D",
"meta": {
"altText": "D"
}
},
" and that agents reproduce at a rate determined by their payoff from the strategic form of the game plus a constant ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "f",
"meta": {
"altText": "f"
}
},
".\nSuppose that members of an infinite population are assorted into finite groups of size ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "n",
"meta": {
"altText": "n"
}
},
".\nLet ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "q",
"meta": {
"altText": "q"
}
},
" denote the proportion of agents playing strategy ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "C",
"meta": {
"altText": "C"
}
},
" (“altruists”) in the population as a whole and ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "qi",
"meta": {
"altText": "q_{i}"
}
},
" denote the proportion of agents playing ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "C",
"meta": {
"altText": "C"
}
},
" in group ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "i",
"meta": {
"altText": "i"
}
},
".\nWe assume that currently ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "q∈(0,1)",
"meta": {
"altText": "q\\in(0,1)"
}
},
"."
]
},
{
"type": "Paragraph",
"content": [
"The process of assortment is abstract, but we assume that it has finite expectation ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "E[qi]=q",
"meta": {
"altText": "E[q_{i}]=q"
}
},
" and variance ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "Var[qi]=σ2",
"meta": {
"altText": "\\operatorname{Var}[q_{i}]=\\sigma^{2}"
}
},
".\nMembers within each group are then randomly paired off to play one iteration of the prisoners’ dilemma against another member of their group.\nAll agents then return to the overall population."
]
},
{
"type": "Paragraph",
"content": []
},
{
"type": "List",
"items": [
{
"type": "ListItem",
"content": [
{
"type": "Paragraph",
"id": "S1.I1.i1.p1",
"content": [
"Find a condition relating ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "q",
"meta": {
"altText": "q"
}
},
", ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "σ2",
"meta": {
"altText": "\\sigma^{2}"
}
},
", ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "β",
"meta": {
"altText": "\\beta"
}
},
", ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "γ",
"meta": {
"altText": "\\gamma"
}
},
", ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "δ",
"meta": {
"altText": "\\delta"
}
},
" and ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "n",
"meta": {
"altText": "n"
}
},
" under which the proportion of altruists in the overall population rises after a round of play."
]
}
]
},
{
"type": "ListItem",
"content": [
{
"type": "Paragraph",
"id": "S1.I1.i2.p1",
"content": [
"Now interpret this game as one where each player can confer a benefit ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "b",
"meta": {
"altText": "b"
}
},
" upon the other player by individually incurring a cost ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "c",
"meta": {
"altText": "c"
}
},
", with ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "c>0\" display=\"inline\">b>c>0",
"meta": {
"altText": "b>c>0"
}
},
", so that ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "β=b-c",
"meta": {
"altText": "\\beta=b-c"
}
},
", ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "δ=b",
"meta": {
"altText": "\\delta=b"
}
},
" and ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "γ=-c",
"meta": {
"altText": "\\gamma=-c"
}
},
".\nProve that, as long as\n(i) there is some positive assortment in group formation and\n(ii) the ratio ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "cb",
"meta": {
"altText": "\\frac{c}{b}"
}
},
" is low enough, then the proportion of altruists in the overall population will rise after a round of play."
]
}
]
}
],
"order": "Ascending"
},
{
"type": "Paragraph",
"id": "S1.SSx2.p4",
"content": [
{
"type": "Emphasis",
"content": [
"Richard Povey (Hertford College and St Hilda’s College, University of Oxford, UK)"
]
}
]
},
{
"type": "Heading",
"id": "S1.SSx3",
"depth": 2,
"content": [
"247"
]
},
{
"type": "Paragraph",
"id": "S1.SSx3.p1",
"content": [
"Consider a village consisting of n farmers who live along a circle of length ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "n",
"meta": {
"altText": "n"
}
},
".\nThe farmers live at positions ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "1,2,…,n",
"meta": {
"altText": "1,2,\\ldots,n"
}
},
".\nEach of them is friends with the person to the left and right of them, and each friendship has capacity ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "m",
"meta": {
"altText": "m"
}
},
" where ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "m",
"meta": {
"altText": "m"
}
},
" is a non-negative integer.\nAt the end of the year, each farmer does either well (her wealth is ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "+1",
"meta": {
"altText": "+1"
}
},
" dollars) or not well (her wealth is ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "-1",
"meta": {
"altText": "-1"
}
},
" dollars) with equal probability.\nFarmers’ wealth realizations are independent of each other.\nHence, for a large circle the share of farmers in each state is on average ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "1",
"meta": {
"altText": "1"
}
},
"."
]
},
{
"type": "Paragraph",
"id": "S1.SSx3.p2",
"content": [
"The farmers share risk by transferring money to their direct neighbors.\nThe goal of risk-sharing is to create as many farmers with OK wealth (0 dollars) as possible.\nTransfers have to be in integer dollars and cannot exceed the capacity of each link (which is ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "m",
"meta": {
"altText": "m"
}
},
")."
]
},
{
"type": "Paragraph",
"content": [
"A few examples with a village of size ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "n=4",
"meta": {
"altText": "n=4"
}
},
" serve to illustrate risk-sharing."
]
},
{
"type": "Paragraph",
"content": []
},
{
"type": "List",
"items": [
{
"type": "ListItem",
"content": [
{
"type": "Paragraph",
"content": [
"Consider the case where farmers 1 to 4 have wealth"
]
},
{
"type": "MathBlock",
"id": "S1.Ex3",
"mathLanguage": "mathml",
"text": "(+1,-1,+1,-1).",
"meta": {
"altText": "(+1,-1,+1,-1)."
}
},
{
"type": "Paragraph",
"content": [
"In that case, we can share risk completely with farmer ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "1",
"meta": {
"altText": "1"
}
},
" sending a dollar to agent ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "2",
"meta": {
"altText": "2"
}
},
" and farmer ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "3",
"meta": {
"altText": "3"
}
},
" sending a dollar to farmer ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "4",
"meta": {
"altText": "4"
}
},
".\nThis works for any ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "m≥1",
"meta": {
"altText": "m\\geq 1"
}
},
"."
]
}
]
},
{
"type": "ListItem",
"content": [
{
"type": "Paragraph",
"content": [
"Consider the case where farmers ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "1",
"meta": {
"altText": "1"
}
},
" to ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "4",
"meta": {
"altText": "4"
}
},
" have wealth"
]
},
{
"type": "MathBlock",
"id": "S1.Ex4",
"mathLanguage": "mathml",
"text": "(+1,+1,-1,-1).",
"meta": {
"altText": "(+1,+1,-1,-1)."
}
},
{
"type": "Paragraph",
"content": [
"In that case, we can share risk completely with farmer ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "1",
"meta": {
"altText": "1"
}
},
" sending a dollar to farmer ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "2",
"meta": {
"altText": "2"
}
},
", farmer ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "2",
"meta": {
"altText": "2"
}
},
" sending two dollars to farmer ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "3",
"meta": {
"altText": "3"
}
},
" and farmer ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "3",
"meta": {
"altText": "3"
}
},
" sending one dollar to farmer ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "4",
"meta": {
"altText": "4"
}
},
".\nIn this case, we need ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "m≥2",
"meta": {
"altText": "m\\geq 2"
}
},
".\nIf ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "m=1",
"meta": {
"altText": "m=1"
}
},
", we can only share risk among half the people in the village."
]
}
]
}
],
"order": "Unordered"
},
{
"type": "Paragraph",
"content": [
"Show that for any wealth realization an optimal risk-sharing arrangement can be found as the solution to a maximum flow problem."
]
},
{
"type": "Paragraph",
"id": "S1.SSx3.p4",
"content": [
{
"type": "Emphasis",
"content": [
"Tanya Rosenblat (School of Information and Department of Economics, University of Michigan, USA)"
]
}
]
},
{
"type": "Heading",
"id": "S1.SSx4",
"depth": 2,
"content": [
"248"
]
},
{
"type": "Paragraph",
"id": "S1.SSx4.p1",
"content": [
"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.\nAssume that for any realization of wealth levels the best possible risk-sharing arrangement is implemented and denote the expected share of unmatched farmers with ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "U(n,m)",
"meta": {
"altText": "U(n,m)"
}
},
".\nShow that ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "U(n,m)→12m+1",
"meta": {
"altText": "U(n,m)\\to\\frac{1}{2m+1}"
}
},
" as ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "n→∞",
"meta": {
"altText": "n\\to\\infty"
}
},
"."
]
},
{
"type": "Paragraph",
"id": "S1.SSx4.p2",
"content": [
{
"type": "Emphasis",
"content": [
"Tanya Rosenblat (School of Information and Department of Economics, University of Michigan, USA)"
]
}
]
},
{
"type": "Heading",
"id": "S1.SSx5",
"depth": 2,
"content": [
"249"
]
},
{
"type": "Paragraph",
"id": "S1.SSx5.p1",
"content": [
"In a ",
{
"type": "Emphasis",
"content": [
"combinatorial auction"
]
},
" there are ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "m",
"meta": {
"altText": "m"
}
},
" items for sale to ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "n",
"meta": {
"altText": "n"
}
},
" buyers.\nEach buyer ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "i",
"meta": {
"altText": "i"
}
},
" has some valuation function ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "vi(⋅)",
"meta": {
"altText": "v_{i}(\\cdot)"
}
},
" which takes as input a set ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "S",
"meta": {
"altText": "S"
}
},
" of items and outputs that bidder’s value for that set.\nThese functions will always be monotone (",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "vi(S∪T)≥vi(S)",
"meta": {
"altText": "v_{i}(S\\cup T)\\geq v_{i}(S)"
}
},
" for all ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "S,T",
"meta": {
"altText": "S,T"
}
},
"), and satisfy ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "vi(∅)=0",
"meta": {
"altText": "v_{i}(\\emptyset)=0"
}
},
"."
]
},
{
"type": "Claim",
"id": "Thmtheorem1",
"label": "Definition 1(Walrasian equilibrium).",
"title": [
{
"type": "Strong",
"content": [
"Definition 1"
]
},
{
"type": "Strong",
"content": []
},
"(Walrasian equilibrium)",
{
"type": "Strong",
"content": [
"."
]
}
],
"content": [
{
"type": "Paragraph",
"content": [
"A price vector ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "p→∈ℝ≥0m",
"meta": {
"altText": "\\vec{p}\\in\\mathbb{R}_{\\geq 0}^{m}"
}
},
" and a list ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "B1,…,Bn",
"meta": {
"altText": "B_{1},\\ldots,B_{n}"
}
},
" of subsets of ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "[m]",
"meta": {
"altText": "[m]"
}
},
" form a ",
{
"type": "Emphasis",
"content": [
"Walrasian equilbrium"
]
},
" for ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "v1,…,vn",
"meta": {
"altText": "v_{1},\\ldots,v_{n}"
}
},
" if the following two properties hold:"
]
},
{
"type": "Paragraph",
"content": []
},
{
"type": "List",
"items": [
{
"type": "ListItem",
"content": [
{
"type": "Paragraph",
"id": "S1.I3.i1.p1",
"content": [
"Each ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "Bi∈argmaxS{vi(S)-∑j∈Spj}",
"meta": {
"altText": "B_{i}\\in\\arg\\max_{S}\\{v_{i}(S)-\\sum_{j\\in S}p_{j}\\}"
}
},
"."
]
}
]
},
{
"type": "ListItem",
"content": [
{
"type": "Paragraph",
"id": "S1.I3.i2.p1",
"content": [
"The sets ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "Bi",
"meta": {
"altText": "B_{i}"
}
},
" are disjoint, and ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "⋃iBi=[m]",
"meta": {
"altText": "\\mathop{\\bigcup}_{i}B_{i}=[m]"
}
},
"."
]
}
]
}
],
"order": "Unordered"
}
]
},
{
"type": "Paragraph",
"content": [
"Prove that a Walrasian equilibrium exists for ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "v1,…,vn",
"meta": {
"altText": "v_{1},\\ldots,v_{n}"
}
},
" if and only if there exists an integral",
{
"type": "Note",
"id": "idm1112",
"noteType": "Footnote",
"content": [
{
"type": "Paragraph",
"id": "footnote1",
"content": [
"That is, a point such that each ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "",
"meta": {
"altText": "x_{i,S}\\in\\{0,1\\}"
}
},
"."
]
}
]
},
" optimum to the following linear program:"
]
},
{
"type": "MathBlock",
"id": "S1.Ex5X",
"mathLanguage": "mathml",
"text": "maximize∑i∑Svi(S)⋅xi,S",
"meta": {
"altText": "\\displaystyle\\text{maximize}\\ \\sum_{i}\\sum_{S}v_{i}(S)\\cdot x_{i,S}"
}
},
{
"type": "MathBlock",
"id": "S1.Ex5Xa",
"mathLanguage": "mathml",
"text": "such that,for alli,∑Sxi,S=1,for allj,∑S∋j∑ixi,S≤1,for alli,S,xi,S≥0.",
"meta": {
"altText": "\\displaystyle\\begin{aligned} \\text{such that},\\,&\\text{for all}\\ i,&\\sum_{S}x_{i,S}&=1,\\\\\n&\\text{for all}\\ j,&\\sum_{S\\ni j}\\sum_{i}x_{i,S}&\\leq 1,\\\\[-3.0pt]\n&\\text{for all}\\ i,S,&x_{i,S}&\\geq 0.\\end{aligned}"
}
},
{
"type": "Paragraph",
"content": [
{
"type": "Emphasis",
"content": [
"Hint."
]
},
"\nTake the dual, and start from there."
]
},
{
"type": "Paragraph",
"id": "S1.SSx5.p3",
"content": [
{
"type": "Emphasis",
"content": [
"Matt Weinberg (Computer Science, Princeton University, USA)"
]
}
]
},
{
"type": "Heading",
"id": "S1.SSx6",
"depth": 2,
"content": [
"250"
]
},
{
"type": "Paragraph",
"content": [
"Consider a game played on a network and a finite set of players ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "𝒩={1,2,…,n}",
"meta": {
"altText": "\\mathcal{N}=\\{1,2,\\ldots,n\\}"
}
},
".\nEach node in the network represents a player and edges capture their relationships.\nWe use ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "𝐆=(gij)1≤i,j≤n",
"meta": {
"altText": "\\mathbf{G}=(g_{ij})_{1\\leq i,j\\leq n}"
}
},
" to represent the adjacency matrix of a undirected graph/network, i.e. ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "gij=gji∈{0,1}",
"meta": {
"altText": "g_{ij}=g_{ji}\\in\\{0,1\\}"
}
},
".\nWe assume ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "gii=0",
"meta": {
"altText": "g_{ii}=0"
}
},
".\nThus, ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "𝐆",
"meta": {
"altText": "\\mathbf{G}"
}
},
" is a zero-diagonal, squared and symmetric matrix.\nEach player, indexed by ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "i",
"meta": {
"altText": "i"
}
},
", chooses an action ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "xi∈ℝ",
"meta": {
"altText": "x_{i}\\in\\mathbb{R}"
}
},
" and obtains the following payoff:"
]
},
{
"type": "MathBlock",
"id": "S1.Ex6",
"mathLanguage": "mathml",
"text": "πi(x1,x2,…,xn)=xi-12xi2+δ∑j∈𝒩gijxixj.",
"meta": {
"altText": "\\pi_{i}(x_{1},x_{2},\\ldots,x_{n})=x_{i}-{\\frac{1}{2}}x_{i}^{2}+\\delta\\sum_{j\\in\\mathcal{N}}g_{ij}x_{i}x_{j}."
}
},
{
"type": "Paragraph",
"content": [
"The parameter ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "0\" display=\"inline\">δ>0",
"meta": {
"altText": "\\delta>0"
}
},
" captures the strength of the direct links between different players.\nFor simplicity, we assume ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "0<δ<1n-1",
"meta": {
"altText": "0<\\delta<\\frac{1}{n-1}"
}
},
"."
]
},
{
"type": "Paragraph",
"content": [
"A Nash equilibrium is a profile ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "𝐱*=(x1*,…,xn*)",
"meta": {
"altText": "\\mathbf{x}^{*}=(x_{1}^{*},\\ldots,x_{n}^{*})"
}
},
" such that, for any ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "i=1,…,n",
"meta": {
"altText": "i=1,\\ldots,n"
}
},
","
]
},
{
"type": "MathBlock",
"id": "S1.Ex7",
"mathLanguage": "mathml",
"text": "πi(x1*,…,xn*)≥πi(x1*,…,xi-1*,xi,xi+1*,…,xn*)for anyxi∈ℝ.",
"meta": {
"altText": "\\pi_{i}(x_{1}^{*},\\ldots,x_{n}^{*})\\geq\\pi_{i}(x_{1}^{*},\\ldots,x_{i-1}^{*},x_{i},x_{i+1}^{*},\\ldots,x_{n}^{*})\\quad\\text{for any}\\ x_{i}\\in\\mathbb{R}."
}
},
{
"type": "Paragraph",
"content": [
"In other words, at a Nash equilibrium, there is no profitable deviation for any player ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "i",
"meta": {
"altText": "i"
}
},
" choosing ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "xi*",
"meta": {
"altText": "x_{i}^{*}"
}
},
"."
]
},
{
"type": "Paragraph",
"content": [
"Let ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "𝐰=(w1,w2,…,wn)′",
"meta": {
"altText": "\\mathbf{w}=(w_{1},w_{2},\\ldots,w_{n})^{\\prime}"
}
},
", ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "0\" display=\"inline\">wi>0",
"meta": {
"altText": "w_{i}>0"
}
},
" for all ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "i",
"meta": {
"altText": "i"
}
},
" (the transpose of a vector ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "𝐰",
"meta": {
"altText": "\\mathbf{w}"
}
},
" is denoted by ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "𝐰′",
"meta": {
"altText": "\\mathbf{w}^{\\prime}"
}
},
"), and ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "𝐈n",
"meta": {
"altText": "\\mathbf{I}_{n}"
}
},
" the ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "n×n",
"meta": {
"altText": "n\\times n"
}
},
" identity matrix.\nDefine the ",
{
"type": "Emphasis",
"content": [
"weighted"
]
},
" Katz–Bonacich centrality vector as"
]
},
{
"type": "MathBlock",
"id": "S1.Ex8",
"mathLanguage": "mathml",
"text": "𝐛(𝐆,𝐰)=[𝐈n-δ𝐆]-1𝐰.",
"meta": {
"altText": "\\mathbf{b}(\\mathbf{G,w})=[\\mathbf{I}_{n}-\\delta\\mathbf{G}]^{-1}\\mathbf{w}."
}
},
{
"type": "Paragraph",
"content": [
"Here ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "𝐌≔[𝐈-δ𝐆]-1",
"meta": {
"altText": "\\mathbf{M}\\coloneqq[\\mathbf{I}-\\delta\\mathbf{G}]^{-1}"
}
},
" denote the inverse Leontief matrix associated with network ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "𝐆",
"meta": {
"altText": "\\mathbf{G}"
}
},
", while ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "mij",
"meta": {
"altText": "m_{ij}"
}
},
" denote its ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "ij",
"meta": {
"altText": "ij"
}
},
" entry, which is equal to the discounted number of walks from ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "i",
"meta": {
"altText": "i"
}
},
" to ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "j",
"meta": {
"altText": "j"
}
},
" with decay factor ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "δ",
"meta": {
"altText": "\\delta"
}
},
".\nLet ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "𝟏n=(1,1,…,1)′",
"meta": {
"altText": "\\mathbf{1}_{n}=(1,1,\\ldots,1)^{\\prime}"
}
},
" be a vector of ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "1",
"meta": {
"altText": "1"
}
},
"s.\nThen the ",
{
"type": "Emphasis",
"content": [
"unweighted"
]
},
" Katz–Bonacich centrality vector can be defined as"
]
},
{
"type": "MathBlock",
"id": "S1.Ex9",
"mathLanguage": "mathml",
"text": "𝐛(𝐆,𝟏)=[𝐈-δ𝐆]-1𝟏n.",
"meta": {
"altText": "\\mathbf{b}(\\mathbf{G,1})=[\\mathbf{I}-\\delta\\mathbf{G}]^{-1}\\mathbf{1}_{n}."
}
},
{
"type": "Paragraph",
"content": []
},
{
"type": "List",
"items": [
{
"type": "ListItem",
"content": [
{
"type": "Paragraph",
"id": "S1.I4.i1.p1",
"content": [
"Show that this network game has a unique Nash equilibrium ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "𝐱*(𝐆)",
"meta": {
"altText": "\\mathbf{x}^{*}(\\mathbf{G})"
}
},
".\nCan you link this equilibrium to the Katz–Bonacich centrality vector defined above?"
]
}
]
},
{
"type": "ListItem",
"content": [
{
"type": "Paragraph",
"id": "S1.I4.i2.p1",
"content": [
"Let ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "x*(𝐆)=∑i=1nxi*(𝐆)",
"meta": {
"altText": "x^{*}(\\mathbf{G})=\\sum_{i=1}^{n}x_{i}^{*}(\\mathbf{G})"
}
},
" denote the sum of actions (total activity) at the unique Nash equilibrium in part 1.\nNow suppose that you can remove a single node, say ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "i",
"meta": {
"altText": "i"
}
},
", from the network.\nWhich node do you want to remove such that the sum of effort at the new Nash equilibrium is reduced the most? (Note that, after the deletion of node ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "i",
"meta": {
"altText": "i"
}
},
", we remove all the links of node ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "i",
"meta": {
"altText": "i"
}
},
", and the remaining network, denoted by ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "𝐆-i",
"meta": {
"altText": "\\mathbf{G}_{-i}"
}
},
", can be obtained by deleting the ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "i",
"meta": {
"altText": "i"
}
},
"-th row and ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "i",
"meta": {
"altText": "i"
}
},
"-th column of ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "𝐆",
"meta": {
"altText": "\\mathbf{G}"
}
},
".)"
]
},
{
"type": "Paragraph",
"content": [
"Mathematically, you need to solve the ",
{
"type": "Emphasis",
"content": [
"key player problem"
]
}
]
},
{
"type": "MathBlock",
"id": "S1.Ex10",
"mathLanguage": "mathml",
"text": "maxi∈𝒩(x*(𝐆)-x*(𝐆-i)).",
"meta": {
"altText": "\\max_{i\\in\\mathcal{N}}\\bigl(x^{*}(\\mathbf{G})-x^{*}(\\mathbf{G}_{-i})\\bigr)."
}
},
{
"type": "Paragraph",
"content": [
"In other words, you want to find a player who, once removed, leads to the highest reduction in total action in the remaining network."
]
},
{
"type": "Paragraph",
"id": "S1.I4.i2.p3",
"content": [
{
"type": "Emphasis",
"content": [
"Hint."
]
},
"\nYou may come up with an index ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "ci",
"meta": {
"altText": "c_{i}"
}
},
" for each ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "i",
"meta": {
"altText": "i"
}
},
" such that the key player is the one with the highest ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "ci",
"meta": {
"altText": "c_{i}"
}
},
".\nThis ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "ci",
"meta": {
"altText": "c_{i}"
}
},
" should be expressed using the Katz–Bonacich centrality vector defined above."
]
}
]
},
{
"type": "ListItem",
"content": [
{
"type": "Paragraph",
"id": "S1.I4.i3.p1",
"content": [
"Now instead of deleting a single node, we can delete any pair of nodes from the network.\nCan you identify the key pair, that is, the pair of nodes that, once removed, reduces total activity the most?"
]
}
]
}
],
"order": "Ascending"
},
{
"type": "Paragraph",
"id": "S1.SSx6.p5",
"content": [
{
"type": "Emphasis",
"content": [
"Yves Zenou (Monash University, Australia) and\nJunjie Zhou (National University of Singapore)"
]
}
]
},
{
"type": "Heading",
"id": "S2",
"depth": 1,
"content": [
"II Open problem"
]
},
{
"type": "Paragraph",
"content": [
"Equilibrium in Quitting Games"
]
},
{
"type": "Paragraph",
"content": [
{
"type": "Emphasis",
"content": [
"by Eilon Solan (School of Mathematical Sciences, Tel Aviv University, Israel)",
{
"type": "Note",
"id": "idm2088",
"noteType": "Footnote",
"content": [
{
"type": "Paragraph",
"id": "footnote2",
"content": [
"The author thanks János Flesch, Ehud Lehrer, and Abraham Neyman for commenting on earlier versions of the text, and acknowledges the support of the Israel Science Foundation, Grant #217/17."
]
}
]
}
]
}
]
},
{
"type": "Paragraph",
"id": "S2.p2",
"content": [
"Alaya, Black, and Catherine are involved in an endurance match, where each player has to decide if and when to quit, and the outcome depends on the set of players whose choice is larger than the minimum of the three choices.\nFormally, each of the three has to select an element of ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "ℕ∪{∞}",
"meta": {
"altText": "\\mathbb{N}\\cup\\{\\infty\\}"
}
},
": the choice ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "∞",
"meta": {
"altText": "\\infty"
}
},
" corresponds to the decision to never quit, and the choice ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "n∈ℕ",
"meta": {
"altText": "n\\in\\mathbb{N}"
}
},
" corresponds to the decision to quit the match in round ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "n",
"meta": {
"altText": "n"
}
},
".\nDenote by ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "nA",
"meta": {
"altText": "n_{A}"
}
},
" (resp. ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "nB",
"meta": {
"altText": "n_{B}"
}
},
", ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "nC",
"meta": {
"altText": "n_{C}"
}
},
") Alaya’s (resp. Black’s, Catherine’s) choice, and by ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "n*≔min{nA,nB,nC}",
"meta": {
"altText": "n_{*}\\coloneqq\\min\\{n_{A},n_{B},n_{C}\\}"
}
},
".\nAs a result of their choices, the players receive payoffs, which are determined by the set ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "n_{*}\\bigr\\}\" display=\"inline\">{i∈{A,B,C}:ni>n*}",
"meta": {
"altText": "\\bigl\\{i\\in\\{A,B,C\\}\\colon n_{i}>n_{*}\\bigr\\}"
}
},
" and on whether ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "n*<∞",
"meta": {
"altText": "n_{*}<\\infty"
}
},
".\nAs a concrete example, suppose that if ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "n*=∞",
"meta": {
"altText": "n_{*}=\\infty"
}
},
", the payoff of each player is 0, and if ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "n*<∞",
"meta": {
"altText": "n_{*}<\\infty"
}
},
", the payoffs are given by the table in Figure ",
{
"type": "Cite",
"target": "S2-F1",
"content": [
"1"
]
},
"."
]
},
{
"type": "Figure",
"id": "S2-F1",
"caption": [
{
"type": "Paragraph",
"content": [
"The payoffs to the players in the game when ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "n*<∞",
"meta": {
"altText": "n_{*}<\\infty"
}
},
".\nIn red, purple, and green the choices and payoffs of respectively Alaya, Black, and Catherine.\nAlaya chooses a row, Black a column, and Catherine a matrix."
]
}
],
"content": [
{
"type": "ImageObject",
"contentUrl": "eq-quitting-games.png",
"mediaType": "image/png",
"meta": {
"inline": false
}
}
]
},
{
"type": "Paragraph",
"id": "S2.p3",
"content": [
"Each entry in the figure represents one possible outcome.\nFor example, when ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "n*=nA=nB<nC",
"meta": {
"altText": "n_{*}=n_{A}=n_{B}(1,0,1)",
"meta": {
"altText": "(1,0,1)"
}
},
": the left-most number in each entry is the payoff to Alaya, the middle number is the payoff to Black, and the right-most number is the payoff to Catherine.\nThis game is an instance of a class of games that are known as ",
{
"type": "Emphasis",
"content": [
"quitting games"
]
},
"."
]
},
{
"type": "Paragraph",
"content": [
"How should the players act in this game?\nTo provide an answer, we formalize the concepts of ",
{
"type": "Emphasis",
"content": [
"strategy"
]
},
" and ",
{
"type": "Emphasis",
"content": [
"equilibrium"
]
},
".\nAs the choice of each participant may be random, a ",
{
"type": "Emphasis",
"content": [
"strategy"
]
},
" for a player is a probability distribution over ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "ℕ∪{∞}",
"meta": {
"altText": "\\mathbb{N}\\cup\\{\\infty\\}"
}
},
".\nDenote a strategy of Alaya (resp. Black, Catherine) by ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "σA",
"meta": {
"altText": "\\sigma_{A}"
}
},
" (resp. ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "σB",
"meta": {
"altText": "\\sigma_{B}"
}
},
", ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "σC",
"meta": {
"altText": "\\sigma_{C}"
}
},
"), and by ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "γi(σA,σB,σC)",
"meta": {
"altText": "\\gamma_{i}(\\sigma_{A},\\sigma_{B},\\sigma_{C})"
}
},
" the expected payoff to player ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "i",
"meta": {
"altText": "i"
}
},
" under the vector of strategies ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "(σA,σB,σC)",
"meta": {
"altText": "(\\sigma_{A},\\sigma_{B},\\sigma_{C})"
}
},
".\nA vector of strategies ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "(σA*,σB*,σC*)",
"meta": {
"altText": "(\\sigma^{*}_{A},\\sigma^{*}_{B},\\sigma^{*}_{C})"
}
},
" is an ",
{
"type": "Emphasis",
"content": [
"equilibrium"
]
},
" if no player can increase her or his expected payoff by adopting another strategy while the other two stick to their strategies:"
]
},
{
"type": "MathBlock",
"id": "S2.Ex11",
"mathLanguage": "mathml",
"text": "γA(σA*,σB*,σC*)≥γA(σA,σB*,σC*)",
"meta": {
"altText": "\\gamma_{A}(\\sigma^{*}_{A},\\sigma^{*}_{B},\\sigma^{*}_{C})\\geq\\gamma_{A}(\\sigma_{A},\\sigma^{*}_{B},\\sigma^{*}_{C})"
}
},
{
"type": "Paragraph",
"content": [
"for every strategy ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "σA",
"meta": {
"altText": "\\sigma_{A}"
}
},
" of Alaya, and analogous inequalities hold for Black and Catherine."
]
},
{
"type": "Paragraph",
"content": [
"The three-player quitting game with payoffs as described above was studied by Flesch, Thuijsman, and Vrieze [",
{
"type": "Cite",
"target": "bib-bib15",
"content": [
"15"
]
},
"] who proved that the following vector of strategies ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "(σA*,σB*,σC*)",
"meta": {
"altText": "(\\sigma^{*}_{A},\\sigma^{*}_{B},\\sigma^{*}_{C})"
}
},
" is an equilibrium:"
]
},
{
"type": "MathBlock",
"id": "S2.Ex12",
"mathLanguage": "mathml",
"text": "123456789…∞σA*:120014001800…0σB*:012001400180…0σC*:001200140018…0",
"meta": {
"altText": "\\begin{array}{cccccccccccc}&1&2&3&4&5&6&7&8&9&\\ldots&\\infty\\\\\n\\hline\\cr\\sigma^{*}_{A}:&\\frac{1}{2}&0&0&\\frac{1}{4}&0&0&\\frac{1}{8}&0&0&\\ldots&0\\\\\n\\sigma^{*}_{B}:&0&\\frac{1}{2}&0&0&\\frac{1}{4}&0&0&\\frac{1}{8}&0&\\ldots&0\\\\\n\\sigma^{*}_{C}:&0&0&\\frac{1}{2}&0&0&\\frac{1}{4}&0&0&\\frac{1}{8}&\\ldots&0\\\\\n\\end{array}"
}
},
{
"type": "Paragraph",
"content": [
"Under ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "(σA*,σB*,σC*)",
"meta": {
"altText": "(\\sigma^{*}_{A},\\sigma^{*}_{B},\\sigma^{*}_{C})"
}
},
", with probability 1 the minimum ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "n*",
"meta": {
"altText": "n_{*}"
}
},
" is the choice of exactly one player: ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "n*=nA",
"meta": {
"altText": "n_{*}=n_{A}"
}
},
" with probability ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "47",
"meta": {
"altText": "\\frac{4}{7}"
}
},
", ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "n*=nB",
"meta": {
"altText": "n_{*}=n_{B}"
}
},
" with probability ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "27",
"meta": {
"altText": "\\frac{2}{7}"
}
},
", and ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "n*=nC",
"meta": {
"altText": "n_{*}=n_{C}"
}
},
" with probability ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "17",
"meta": {
"altText": "\\frac{1}{7}"
}
},
".\nIt follows that the vector of expected payoffs under ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "(σA*,σB*,σC*)",
"meta": {
"altText": "(\\sigma^{*}_{A},\\sigma^{*}_{B},\\sigma^{*}_{C})"
}
},
" is"
]
},
{
"type": "MathBlock",
"id": "S2.Ex13",
"mathLanguage": "mathml",
"text": "γ(σA*,σB*,σC*)=47⋅(1,3,0)+27⋅(0,1,3)+17⋅(3,0,1)=(1,2,1).",
"meta": {
"altText": "\\begin{split}\\gamma(\\sigma^{*}_{A},\\sigma^{*}_{B},\\sigma^{*}_{C})&=\\frac{4}{7}\\cdot(1,3,0)+\\frac{2}{7}\\cdot(0,1,3)+\\frac{1}{7}\\cdot(3,0,1)\\\\\n&=(1,2,1).\\end{split}"
}
},
{
"type": "Paragraph",
"content": [
"Can a player profit by adopting a strategy different than ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "σA*",
"meta": {
"altText": "\\sigma^{*}_{A}"
}
},
", ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "σB*",
"meta": {
"altText": "\\sigma^{*}_{B}"
}
},
", or ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "σC*",
"meta": {
"altText": "\\sigma^{*}_{C}"
}
},
", assuming the other two stick to their prescribed strategies?\nIt is a bit tedious, but not too difficult, to verify that this is not the case, hence ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "(σA*,σB*,σC*)",
"meta": {
"altText": "(\\sigma^{*}_{A},\\sigma^{*}_{B},\\sigma^{*}_{C})"
}
},
" is indeed an equilibrium."
]
},
{
"type": "Paragraph",
"id": "S2.p6",
"content": [
"In fact, Flesch, Thuijsman, and Vrieze [",
{
"type": "Cite",
"target": "bib-bib15",
"content": [
"15"
]
},
"] proved that under ",
{
"type": "Emphasis",
"content": [
"all"
]
},
" equilibria of the game, with probability 1 the minimum ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "n*",
"meta": {
"altText": "n_{*}"
}
},
" coincides with the choice of exactly one player.\nMoreover, a vector of strategies is an equilibrium if and only if the set ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "ℕ",
"meta": {
"altText": "\\mathbb{N}"
}
},
" can be partitioned into blocks of consecutive numbers, and up to circular permutations of the players, the support of the strategy of Alaya (which is a probability distribution over ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "ℕ∪{∞}",
"meta": {
"altText": "\\mathbb{N}\\cup\\{\\infty\\}"
}
},
") is contained in blocks number ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "1,4,7,…",
"meta": {
"altText": "1,4,7,\\ldots"
}
},
", and the total probability that ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "nA",
"meta": {
"altText": "n_{A}"
}
},
" is in block ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "3k-2",
"meta": {
"altText": "3k-2"
}
},
" is ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "12k",
"meta": {
"altText": "\\frac{1}{2^{k}}"
}
},
" (for each ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "k∈ℕ",
"meta": {
"altText": "k\\in\\mathbb{N}"
}
},
"), the support of the strategy of Black (resp. Catherine) is contained in blocks number ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "2,5,8,…",
"meta": {
"altText": "2,5,8,\\ldots"
}
},
" (resp. ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "3,6,9,…",
"meta": {
"altText": "3,6,9,\\ldots"
}
},
"), and the total probability that ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "nB",
"meta": {
"altText": "n_{B}"
}
},
" (resp. ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "nC",
"meta": {
"altText": "n_{C}"
}
},
") is in block ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "3k-1",
"meta": {
"altText": "3k-1"
}
},
" (resp. ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "3k",
"meta": {
"altText": "3k"
}
},
") is ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "12k",
"meta": {
"altText": "\\frac{1}{2^{k}}"
}
},
" (for each ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "k∈ℕ",
"meta": {
"altText": "k\\in\\mathbb{N}"
}
},
")."
]
},
{
"type": "Paragraph",
"content": [
"Does an equilibrium exist if the payoffs are not given by the table in Figure ",
{
"type": "Cite",
"target": "S2-F1",
"content": [
"1"
]
},
", but rather by other numbers?\nSolan [",
{
"type": "Cite",
"target": "bib-bib19",
"content": [
"19"
]
},
"] showed that this is not the case.\nHe studied a three-player quitting game that differs from the game of [",
{
"type": "Cite",
"target": "bib-bib15",
"content": [
"15"
]
},
"]\nin three payoffs:"
]
},
{
"type": "Paragraph",
"content": []
},
{
"type": "List",
"items": [
{
"type": "ListItem",
"content": [
{
"type": "Paragraph",
"id": "S2.I1.i1.p1",
"content": [
"the payoffs in the entry ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "n*=nA=nB<nC",
"meta": {
"altText": "n_{*}=n_{A}=n_{B}(1+η,0,1)",
"meta": {
"altText": "(1+\\eta,0,1)"
}
},
","
]
}
]
},
{
"type": "ListItem",
"content": [
{
"type": "Paragraph",
"id": "S2.I1.i2.p1",
"content": [
"the payoffs in the entry ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "n*=nA=nC<nB",
"meta": {
"altText": "n_{*}=n_{A}=n_{C}(0,1,1+η)",
"meta": {
"altText": "(0,1,1+\\eta)"
}
},
",\n"
]
}
]
},
{
"type": "ListItem",
"content": [
{
"type": "Paragraph",
"id": "S2.I1.i3.p1",
"content": [
"the payoffs in the entry ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "n*=nB=nC<nA",
"meta": {
"altText": "n_{*}=n_{B}=n_{C}(1,1+η,0)",
"meta": {
"altText": "(1,1+\\eta,0)"
}
},
";"
]
}
]
}
],
"order": "Unordered"
},
{
"type": "Paragraph",
"content": [
"and showed that provided ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "η",
"meta": {
"altText": "\\eta"
}
},
" is sufficiently small, the game has no equilibrium.\nFor example, the strategy vector ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "(σA*,σB*,σC*)",
"meta": {
"altText": "(\\sigma^{*}_{A},\\sigma^{*}_{B},\\sigma^{*}_{C})"
}
},
" described above is no longer an equilibrium, because Catherine is better off selecting ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "nC=1",
"meta": {
"altText": "n_{C}=1"
}
},
" with probability 1, thereby obtaining expected payoff ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "12⋅1+12⋅(1+η)=1+η2",
"meta": {
"altText": "\\frac{1}{2}\\cdot 1+\\frac{1}{2}\\cdot(1+\\eta)=1+\\frac{\\eta}{2}"
}
},
", which is higher than her expected payoff under ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "(σA*,σB*,σC*)",
"meta": {
"altText": "(\\sigma^{*}_{A},\\sigma^{*}_{B},\\sigma^{*}_{C})"
}
},
" (that is still 1)."
]
},
{
"type": "Paragraph",
"content": [
"Yet in Solan’s variation [",
{
"type": "Cite",
"target": "bib-bib19",
"content": [
"19"
]
},
"], for every ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "0\" display=\"inline\">ε>0",
"meta": {
"altText": "\\varepsilon>0"
}
},
" there is an ",
{
"type": "Emphasis",
"content": [
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "ε",
"meta": {
"altText": "\\varepsilon"
}
},
"-equilibrium"
]
},
": a vector of strategies such that no player can profit more than ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "ε",
"meta": {
"altText": "\\varepsilon"
}
},
" by deviating to another strategy, in other words,"
]
},
{
"type": "MathBlock",
"id": "S2.Ex14",
"mathLanguage": "mathml",
"text": "γA(σA*,σB*,σC*)≥γA(σA,σB*,σC*)-ε,",
"meta": {
"altText": "\\gamma_{A}(\\sigma^{*}_{A},\\sigma^{*}_{B},\\sigma^{*}_{C})\\geq\\gamma_{A}(\\sigma_{A},\\sigma^{*}_{B},\\sigma^{*}_{C})-\\varepsilon,"
}
},
{
"type": "Paragraph",
"content": [
"for every strategy ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "σA",
"meta": {
"altText": "\\sigma_{A}"
}
},
" of Alaya, and analogous inequalities hold for Black and Catherine.\nIndeed, given a positive integer ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "m",
"meta": {
"altText": "m"
}
},
", consider the following variation of ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "(σA*,σB*,σC*)",
"meta": {
"altText": "(\\sigma^{*}_{A},\\sigma^{*}_{B},\\sigma^{*}_{C})"
}
},
", denoted ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "(σ^A,σ^B,σ^C)",
"meta": {
"altText": "(\\hat{\\sigma}_{A},\\hat{\\sigma}_{B},\\hat{\\sigma}_{C})"
}
},
", where the set ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "ℕ",
"meta": {
"altText": "\\mathbb{N}"
}
},
" is partitioned into blocks of size ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "m",
"meta": {
"altText": "m"
}
},
": block ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "k",
"meta": {
"altText": "k"
}
},
" contains the integers ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "{(k-1)m+1,(k-1)m+2,…,km}",
"meta": {
"altText": "\\{(k-1)m+1,(k-1)m+2,\\ldots,km\\}"
}
},
", for each ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "k∈ℕ",
"meta": {
"altText": "k\\in\\mathbb{N}"
}
},
".\n",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "σ^A",
"meta": {
"altText": "\\hat{\\sigma}_{A}"
}
},
" is the probability distribution that assigns to each integer in block ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "3k-2",
"meta": {
"altText": "3k-2"
}
},
" the probability ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "1m⋅2k",
"meta": {
"altText": "\\frac{1}{m\\cdot 2^{k}}"
}
},
", for every ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "k∈ℕ",
"meta": {
"altText": "k\\in\\mathbb{N}"
}
},
".\nSimilarly, ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "σ^B",
"meta": {
"altText": "\\hat{\\sigma}_{B}"
}
},
" (resp. ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "σ^C",
"meta": {
"altText": "\\hat{\\sigma}_{C}"
}
},
") is the probability distribution that assigns to each integer in block ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "3k-1",
"meta": {
"altText": "3k-1"
}
},
" (resp. ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "3k",
"meta": {
"altText": "3k"
}
},
") the probability ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "1m⋅2k",
"meta": {
"altText": "\\frac{1}{m\\cdot 2^{k}}"
}
},
", for every ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "k∈ℕ",
"meta": {
"altText": "k\\in\\mathbb{N}"
}
},
".\nAs mentioned above, the strategy vector ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "(σ^A,σ^B,σ^C)",
"meta": {
"altText": "(\\hat{\\sigma}_{A},\\hat{\\sigma}_{B},\\hat{\\sigma}_{C})"
}
},
" is an equilibrium of the game whose payoff function is given in Figure ",
{
"type": "Cite",
"target": "S2-F1",
"content": [
"1"
]
},
", and one can verify that provided ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "m≥1ε",
"meta": {
"altText": "m\\geq\\frac{1}{\\varepsilon}"
}
},
", it is an ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "ε",
"meta": {
"altText": "\\varepsilon"
}
},
"-equilibrium of Solan’s variation [",
{
"type": "Cite",
"target": "bib-bib19",
"content": [
"19"
]
},
"]."
]
},
{
"type": "Paragraph",
"id": "S2.p9",
"content": [
"It follows from [",
{
"type": "Cite",
"target": "bib-bib18",
"content": [
"18"
]
},
"]\nthat an ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "ε",
"meta": {
"altText": "\\varepsilon"
}
},
"-equilibrium exists in ",
{
"type": "Emphasis",
"content": [
"every"
]
},
" three-player quitting game, for every ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "0\" display=\"inline\">ε>0",
"meta": {
"altText": "\\varepsilon>0"
}
},
", regardless of the payoffs.\nOne of the most challenging problems in game theory to date is the following."
]
},
{
"type": "Heading",
"id": "S2.SSx1",
"depth": 2,
"content": [
"251*"
]
},
{
"type": "Paragraph",
"id": "S2.SSx1.p1",
"content": [
"Does an ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "ε",
"meta": {
"altText": "\\varepsilon"
}
},
"-equilibrium exist in quitting games that include more than three players, for every ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "0\" display=\"inline\">ε>0",
"meta": {
"altText": "\\varepsilon>0"
}
},
"?"
]
},
{
"type": "Paragraph",
"id": "S2.SSx1.p2",
"content": [
"For partial results, see\n[",
{
"type": "Cite",
"target": "bib-bib21",
"content": [
"21"
]
},
", ",
{
"type": "Cite",
"target": "bib-bib22",
"content": [
"22"
]
},
", ",
{
"type": "Cite",
"target": "bib-bib16",
"content": [
"16"
]
},
", ",
{
"type": "Cite",
"target": "bib-bib17",
"content": [
"17"
]
},
", ",
{
"type": "Cite",
"target": "bib-bib20",
"content": [
"20"
]
},
", ",
{
"type": "Cite",
"target": "bib-bib14",
"content": [
"14"
]
},
"],\nwhich use different tools to study the problem: dynamical systems, algebraic topology, and linear complementarity problems.\nThe open problem is a step in solving several other well-known open problems in game theory: the existence of ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "ε",
"meta": {
"altText": "\\varepsilon"
}
},
"-equilibria in stopping games, the existence of uniform equilibria in stochastic games, and the existence of ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "ε",
"meta": {
"altText": "\\varepsilon"
}
},
"-equilibria in repeated games with Borel-measurable payoffs."
]
},
{
"type": "Paragraph",
"content": [
"It is interesting to note that if we defined"
]
},
{
"type": "MathBlock",
"id": "S2.Ex15",
"mathLanguage": "mathml",
"text": "n*≔max{𝟏{nA<∞}⋅nA,𝟏{nB<∞}⋅nB,𝟏{nC<∞}⋅nC},",
"meta": {
"altText": "n_{*}\\coloneqq\\max\\{\\mathbf{1}_{\\{n_{A}<\\infty\\}}\\cdot n_{A},\\mathbf{1}_{\\{n_{B}<\\infty\\}}\\cdot n_{B},\\mathbf{1}_{\\{n_{C}<\\infty\\}}\\cdot n_{C}\\},"
}
},
{
"type": "Paragraph",
"content": [
"then an ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "ε",
"meta": {
"altText": "\\varepsilon"
}
},
"-equilibrium need not exist for small ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "0\" display=\"inline\">ε>0",
"meta": {
"altText": "\\varepsilon>0"
}
},
".\nIndeed, with this definition, the three-player game in which the payoff of player ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "i",
"meta": {
"altText": "i"
}
},
" is 1 if ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "n_{i}=n_{*}>n_{j}\" display=\"inline\">∞>ni=n*>nj",
"meta": {
"altText": "\\infty>n_{i}=n_{*}>n_{j}"
}
},
" for each ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "j≠i",
"meta": {
"altText": "j\\neq i"
}
},
", and 0 otherwise, has no ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "ε",
"meta": {
"altText": "\\varepsilon"
}
},
"-equilibrium for ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "ε∈(0,23)",
"meta": {
"altText": "\\varepsilon\\in(0,\\frac{2}{3})"
}
},
"."
]
},
{
"type": "Heading",
"id": "S3",
"depth": 1,
"content": [
"III Solutions"
]
},
{
"type": "Heading",
"id": "S3.SSx1",
"depth": 2,
"content": [
"237"
]
},
{
"type": "Paragraph",
"id": "S3.SSx1.p1",
"content": [
"We take for our probability space ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "(X,m)",
"meta": {
"altText": "(X,m)"
}
},
": the unit interval ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "X=[0,1]",
"meta": {
"altText": "X=[0,1]"
}
},
" equipped with Lebesgue measure ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "m",
"meta": {
"altText": "m"
}
},
" defined on ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "ℬ(X)",
"meta": {
"altText": "\\mathcal{B}(X)"
}
},
", the Borel subsets of ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "X",
"meta": {
"altText": "X"
}
},
" and let ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "(X,m,T)",
"meta": {
"altText": "(X,m,T)"
}
},
" be an invertible measure preserving transformation, that is ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "T:X0→X0",
"meta": {
"altText": "T\\colon X_{0}\\to X_{0}"
}
},
" is a bimeasurable bijection of some Borel set ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "X0∈ℬ(X)",
"meta": {
"altText": "X_{0}\\in\\mathcal{B}(X)"
}
},
" of full measure so that and ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "m(TA)=m(T-1A)=m(A)",
"meta": {
"altText": "m(TA)=m(T^{-1}A)=m(A)"
}
},
" for every ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "A∈ℬ(X)",
"meta": {
"altText": "A\\in\\mathcal{B}(X)"
}
},
"."
]
},
{
"type": "Paragraph",
"id": "S3.SSx1.p2",
"content": [
"Suppose also that ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "T",
"meta": {
"altText": "T"
}
},
" is ergodic in the sense that the only ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "T",
"meta": {
"altText": "T"
}
},
"-invariant Borel sets have either zero- or full measure (",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "A∈ℬ(X)",
"meta": {
"altText": "A\\in\\mathcal{B}(X)"
}
},
", ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "TA=A⇒m(A)=0,1",
"meta": {
"altText": "TA=A\\Rightarrow m(A)=0,1"
}
},
")."
]
},
{
"type": "Paragraph",
"content": [
"Birkhoff’s ergodic theorem says that for every integrable function ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "f:X→ℝ",
"meta": {
"altText": "f\\colon X\\to\\mathbb{R}"
}
},
","
]
},
{
"type": "MathBlock",
"id": "S3.Ex16",
"mathLanguage": "mathml",
"text": "1n∑k=0n-1f∘Tk→n→∞𝔼(f)≔∫Xf𝑑ma.s.",
"meta": {
"altText": "\\frac{1}{n}\\sum_{k=0}^{n-1}f\\circ T^{k}\\xrightarrow[n\\to\\infty]{}\\mathbb{E}(f)\\coloneqq\\int_{X}\\,f\\,dm\\ \\text{a.s.}"
}
},
{
"type": "Paragraph",
"content": [
"The present exercise is concerned with the possibility of generalizing this.\nThroughout, ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "(X,m,T)",
"meta": {
"altText": "(X,m,T)"
}
},
" is an arbitrary ergodic, measure preserving transformation as above."
]
},
{
"type": "Claim",
"id": "Thmwarmup1",
"label": "Warm-up 1.",
"title": [
{
"type": "Strong",
"content": [
"Warm-up 1"
]
},
{
"type": "Strong",
"content": [
"."
]
}
],
"content": [
{
"type": "Paragraph",
"content": [
"Show that if ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "f:X→ℝ",
"meta": {
"altText": "f\\colon X\\to\\mathbb{R}"
}
},
" is measurable, and"
]
},
{
"type": "MathBlock",
"id": "S3.Ex17",
"mathLanguage": "mathml",
"text": "0,\" display=\"block\">m([lim¯n→∞|∑k=0n-1f∘Tk|<∞])>0,",
"meta": {
"altText": "m\\Biggl(\\Biggl[\\varlimsup_{n\\to\\infty}\\Biggl|\\sum_{k=0}^{n-1}f\\circ T^{k}\\Biggr|<\\infty\\Biggr]\\Biggr)>0,"
}
},
{
"type": "Paragraph",
"content": [
"then ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "1n∑k=0n-1f∘Tk",
"meta": {
"altText": "\\frac{1}{n}\\sum_{k=0}^{n-1}f\\circ T^{k}"
}
},
" converges in ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "ℝ",
"meta": {
"altText": "\\mathbb{R}"
}
},
" a.s."
]
}
]
},
{
"type": "Paragraph",
"id": "S3.SSx1.p4",
"content": [
"Warm-up 1 is [",
{
"type": "Cite",
"target": "bib-bib23",
"content": [
"23"
]
},
", Lemma 1].\nFor a multidimensional version, see [",
{
"type": "Cite",
"target": "bib-bib23",
"content": [
"23"
]
},
", Conjecture 3]."
]
},
{
"type": "Claim",
"id": "Thmwarmup2",
"label": "Warm-up 2.",
"title": [
{
"type": "Strong",
"content": [
"Warm-up 2"
]
},
{
"type": "Strong",
"content": [
"."
]
}
],
"content": [
{
"type": "Paragraph",
"id": "Thmwarmup2.p1",
"content": [
"Show that if ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "f:X→ℝ",
"meta": {
"altText": "f\\colon X\\to\\mathbb{R}"
}
},
" is as in Warm-up 1, there exist ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "g,h:X→ℝ",
"meta": {
"altText": "g,h\\colon X\\to\\mathbb{R}"
}
},
" measurable with ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "h",
"meta": {
"altText": "h"
}
},
" bounded so that ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "f=h+g-g∘Tn",
"meta": {
"altText": "f=h+g-g\\circ T^{n}"
}
},
"."
]
}
]
},
{
"type": "Paragraph",
"id": "S3.SSx1.p5",
"content": [
"Warm-up 2 is established by adapting the proof of [",
{
"type": "Cite",
"target": "bib-bib25",
"content": [
"25"
]
},
", Theorem A]."
]
},
{
"type": "Claim",
"id": "Thmproblemx1",
"label": "Problem.",
"title": [
{
"type": "Strong",
"content": [
"Problem"
]
},
{
"type": "Strong",
"content": [
"."
]
}
],
"content": [
{
"type": "Paragraph",
"content": [
"Show that there is a measurable function ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "f:X→ℝ",
"meta": {
"altText": "f\\colon X\\to\\mathbb{R}"
}
},
" satisfying ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "𝔼(|f|)=∞",
"meta": {
"altText": "\\mathbb{E}(\\lvert f\\rvert)=\\infty"
}
},
" so that"
]
},
{
"type": "MathBlock",
"id": "S3.Ex18",
"mathLanguage": "mathml",
"text": "1n∑k=0n-1f∘Tk",
"meta": {
"altText": "\\frac{1}{n}\\mathop{\\smash[b]{\\sum_{k=0}^{n-1}}}f\\circ T^{k}"
}
},
{
"type": "Paragraph",
"content": [
"converges in ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "ℝ",
"meta": {
"altText": "\\mathbb{R}"
}
},
" a.s."
]
}
]
},
{
"type": "Paragraph",
"id": "S3.SSx1.p6",
"content": [
"The existence of such ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "f",
"meta": {
"altText": "f"
}
},
" for a specially constructed ergodic measure preserving transformation is shown in [",
{
"type": "Cite",
"target": "bib-bib24",
"content": [
"24"
]
},
", Example b].\nThe point here is to prove it for an arbitrary ergodic measure preserving transformation of ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "(X,m)",
"meta": {
"altText": "(X,m)"
}
},
"."
]
},
{
"type": "Paragraph",
"id": "S3.SSx1.p7",
"content": [
{
"type": "Emphasis",
"content": [
"Jon Aaronson (Tel Aviv University, Israel)"
]
}
]
},
{
"type": "Heading",
"id": "S3.SSx1.SSSx1",
"depth": 3,
"content": [
"Solution by the proposer"
]
},
{
"type": "Paragraph",
"id": "S3.SSx1.SSSx1.p1",
"content": [
"We’ll fix sequences ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "0\" display=\"inline\">εk,Mk>0",
"meta": {
"altText": "\\varepsilon_{k},M_{k}>0"
}
},
", ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "Nk∈ℕ",
"meta": {
"altText": "N_{k}\\in\\mathbb{N}"
}
},
" (",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "k≥1",
"meta": {
"altText": "k\\geq 1"
}
},
").\nFor each ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "0\" display=\"inline\">ε,M>0",
"meta": {
"altText": "\\varepsilon,M>0"
}
},
", ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "N≥1",
"meta": {
"altText": "N\\geq 1"
}
},
", we’ll construct a small coboundary ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "f(ε,M,N)",
"meta": {
"altText": "f^{(\\varepsilon,M,N)}"
}
},
".\nThe desired function will be of the form ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "F≔∑k≥1f(εk,Mk,Nk)",
"meta": {
"altText": "F\\coloneqq\\sum_{k\\geq 1}f^{(\\varepsilon_{k},M_{k},N_{k})}"
}
},
" for a suitable choice of ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "0\" display=\"inline\">εk,Mk>0",
"meta": {
"altText": "\\varepsilon_{k},M_{k}>0"
}
},
", ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "Nk∈ℕ",
"meta": {
"altText": "N_{k}\\in\\mathbb{N}"
}
},
" (",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "k≥1",
"meta": {
"altText": "k\\geq 1"
}
},
")."
]
},
{
"type": "Paragraph",
"content": [
"To construct ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "f(ε,M,N)",
"meta": {
"altText": "f^{(\\varepsilon,M,N)}"
}
},
", choose, using Rokhlin’s lemma, a set ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "B∈ℬ",
"meta": {
"altText": "B\\in\\nobreak\\mathcal{B}"
}
},
" such that ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "{TkB:|k|≤2N}",
"meta": {
"altText": "\\{T^{k}B:\\lvert k\\rvert\\leq 2N\\}"
}
},
" are disjoint and ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "m(A)=ε",
"meta": {
"altText": "m(A)=\\varepsilon"
}
},
" where ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "A≔⨃|k|≤2NTkB",
"meta": {
"altText": "A\\coloneqq\\text{⨃}_{\\lvert k\\rvert\\leq 2N}T^{k}B"
}
},
".\nLet"
]
},
{
"type": "MathBlock",
"id": "S3.Ex19",
"mathLanguage": "mathml",
"text": "f=f(ε,M,N)≔M∑k=12N(-1)k1TkB.",
"meta": {
"altText": "f=f^{(\\varepsilon,M,N)}\\coloneqq M\\sum_{k=1}^{2N}(-1)^{k}1_{T_{k}B}."
}
},
{
"type": "Paragraph",
"content": [
"It follows that"
]
},
{
"type": "MathBlock",
"id": "S3.Ex20X",
"mathLanguage": "mathml",
"text": "Snf(x)∈{0,M,-M}for alln≥1,x∈X;",
"meta": {
"altText": "\\displaystyle S_{n}f(x)\\in\\{0,M,-M\\}\\quad\\text{for all}\\ n\\geq 1,\\,x\\in X;"
}
},
{
"type": "MathBlock",
"id": "S3.Ex20Xa",
"mathLanguage": "mathml",
"text": "Snf(x)=0for all 1≤n≤N,x∉A;",
"meta": {
"altText": "\\displaystyle S_{n}f(x)=0\\quad\\text{for all}\\ 1\\leq n\\leq N,\\,x\\notin A;"
}
},
{
"type": "MathBlock",
"id": "S3.Ex20Xb",
"mathLanguage": "mathml",
"text": "\\frac{M\\varepsilon}{3}.\" display=\"inline\">E(|f|)=Mm(⨃j=12NTjB)=Mε2N4N+1>Mε3.",
"meta": {
"altText": "\\displaystyle E(\\lvert f\\rvert)=Mm\\Biggl(\\text{⨃}_{j=1}^{2N}T^{j}B\\Biggr)=\\frac{M\\varepsilon 2N}{4N+1}>\\frac{M\\varepsilon}{3}."
}
},
{
"type": "Paragraph",
"content": [
"Set ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "εk≔15k",
"meta": {
"altText": "\\varepsilon_{k}\\coloneqq\\frac{1}{5^{k}}"
}
},
", ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "Mk=6k",
"meta": {
"altText": "M_{k}=6^{k}"
}
},
", ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "Nk=7k",
"meta": {
"altText": "N_{k}=7^{k}"
}
},
", and define ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "F(k)≔f(εk,Mk,Nk)",
"meta": {
"altText": "F^{(k)}\\coloneqq f^{(\\varepsilon_{k},M_{k},N_{k})}"
}
},
" as above."
]
},
{
"type": "Paragraph",
"content": [
"Since"
]
},
{
"type": "MathBlock",
"id": "S3.Ex21",
"mathLanguage": "mathml",
"text": "∑k≥1m([F(k)≠0])≤∑k≥1εk<∞,",
"meta": {
"altText": "\\sum_{k\\geq 1}m([F^{(k)}\\neq 0])\\leq\\sum_{k\\geq 1}\\varepsilon_{k}<\\infty,"
}
},
{
"type": "Paragraph",
"content": [
"this is a finite sum and so"
]
},
{
"type": "MathBlock",
"id": "S3.Ex22",
"mathLanguage": "mathml",
"text": "F≔∑k≥1F(k):X→ℝ.",
"meta": {
"altText": "F\\coloneqq\\sum_{k\\geq 1}F^{(k)}\\colon X\\to\\mathbb{R}."
}
},
{
"type": "Claim",
"claimType": "Proof",
"label": "Proof that E(|F|)=∞.",
"title": [
"Proof that ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "E(|F|)=∞",
"meta": {
"altText": "E(\\lvert F\\rvert)=\\infty"
}
},
"."
],
"content": [
{
"type": "Paragraph",
"content": [
"For each ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "K≥1",
"meta": {
"altText": "K\\geq 1"
}
},
","
]
},
{
"type": "MathBlock",
"id": "S3.Ex23",
"mathLanguage": "mathml",
"text": "K]}\\\\\n&\\geq\\Biggl(\\lvert F^{(K)}\\rvert-\\sum_{1\\leq j\\leq K-1}\\lvert F^{(j)}\\rvert\\Biggr)1_{[F^{(k)}=0\\ \\forall\\,k>K]}\\\\\n&\\geq\\Biggl(M_{K}-\\sum_{1\\leq j\\leq K-1}M_{j}\\Biggr)1_{[F^{(K)}\\neq 0\\ \\&\\ F^{(k)}=0\\ \\forall\\,k>K]}\\\\\n&\\geq\\smash{\\frac{4}{5}}M_{K}1_{[F^{(K)}\\neq 0\\ \\&\\ F^{(k)}=0\\ \\forall\\,k>K]}\\end{split}\" display=\"block\">|F|≥|F(K)+∑1≤j≤K-1F(j)|1[F(k)=0∀k>K]≥(|F(K)|-∑1≤j≤K-1|F(j)|)1[F(k)=0∀k>K]≥(MK-∑1≤j≤K-1Mj)1[F(K)≠0&F(k)=0∀k>K]≥45MK1[F(K)≠0&F(k)=0∀k>K]",
"meta": {
"altText": "\\begin{split}\\lvert F\\rvert&\\geq\\Biggl|F^{(K)}+\\sum_{1\\leq j\\leq K-1}F^{(j)}\\Biggr|1_{[F^{(k)}=0\\ \\forall\\,k>K]}\\\\\n&\\geq\\Biggl(\\lvert F^{(K)}\\rvert-\\sum_{1\\leq j\\leq K-1}\\lvert F^{(j)}\\rvert\\Biggr)1_{[F^{(k)}=0\\ \\forall\\,k>K]}\\\\\n&\\geq\\Biggl(M_{K}-\\sum_{1\\leq j\\leq K-1}M_{j}\\Biggr)1_{[F^{(K)}\\neq 0\\ \\&\\ F^{(k)}=0\\ \\forall\\,k>K]}\\\\\n&\\geq\\smash{\\frac{4}{5}}M_{K}1_{[F^{(K)}\\neq 0\\ \\&\\ F^{(k)}=0\\ \\forall\\,k>K]}\\end{split}"
}
},
{
"type": "Paragraph",
"content": [
"and"
]
},
{
"type": "MathBlock",
"id": "S3.Ex24",
"mathLanguage": "mathml",
"text": "K]).\" display=\"block\">E(|F|)≥45MKm([F(K)≠0&F(k)=0∀k>K]).",
"meta": {
"altText": "E(\\lvert F\\rvert)\\geq\\frac{4}{5}M_{K}m([F^{(K)}\\neq 0\\ \\&\\ F^{(k)}=0\\ \\forall\\,k>K])."
}
},
{
"type": "Paragraph",
"content": [
"Next,"
]
},
{
"type": "MathBlock",
"id": "S3.Ex25",
"mathLanguage": "mathml",
"text": "K]^{c}=\\mathop{\\smash[b]{\\bigcup_{k\\geq K+1}\\bigcup_{1\\leq j\\leq 2N_{k}}}}T^{k}B_{k}\" display=\"block\">ℰK≔[F(k)=0∀k>K]c=⋃k≥K+1⋃1≤j≤2NkTkBk",
"meta": {
"altText": "\\mathcal{E}_{K}\\coloneqq[F^{(k)}=0\\ \\forall\\,k>K]^{c}=\\mathop{\\smash[b]{\\bigcup_{k\\geq K+1}\\bigcup_{1\\leq j\\leq 2N_{k}}}}T^{k}B_{k}"
}
},
{
"type": "Paragraph",
"content": [
"whence"
]
},
{
"type": "MathBlock",
"id": "S3.Ex26",
"mathLanguage": "mathml",
"text": "m(ℰK)≤∑k≥K+1εk2=12∑k≥K+115k=εK40.",
"meta": {
"altText": "m(\\mathcal{E}_{K})\\leq\\sum_{k\\geq K+1}\\frac{\\varepsilon_{k}}{2}=\\frac{1}{2}\\sum_{k\\geq K+1}\\frac{1}{5^{k}}=\\frac{\\varepsilon_{K}}{40}."
}
},
{
"type": "Paragraph",
"content": [
"It follows that"
]
},
{
"type": "MathBlock",
"id": "S3.Ex27",
"mathLanguage": "mathml",
"text": "\\frac{\\varepsilon_{K}}{3}-\\frac{\\varepsilon_{K}}{40}=\\frac{37\\varepsilon_{K}}{120},\" display=\"block\">m([F(K)≠0]∖ℰK)=m(⨃j=12NKTjBK∖ℰK)>εK3-εK40=37εK120,",
"meta": {
"altText": "m([F^{(K)}\\neq 0]\\setminus\\mathcal{E}_{K})=m\\Biggl(\\mathop{\\smash[b]{\\text{⨃}_{j=1}^{2N_{K}}}}T^{j}B_{K}\\setminus\\mathcal{E}_{K}\\Biggr)>\\frac{\\varepsilon_{K}}{3}-\\frac{\\varepsilon_{K}}{40}=\\frac{37\\varepsilon_{K}}{120},"
}
},
{
"type": "Paragraph",
"content": [
"whence"
]
},
{
"type": "MathBlock",
"id": "S3.Ex28",
"mathLanguage": "mathml",
"text": "\\frac{37\\varepsilon_{K}M_{K}}{150}\\xrightarrow[K\\to\\infty]{}\\infty.\" display=\"block\">E(|F|)≥45MKm([F(K)≠0]∖ℰK)>37εKMK150→K→∞∞.",
"meta": {
"altText": "E(\\lvert F\\rvert)\\geq\\frac{4}{5}M_{K}m([F^{(K)}\\neq 0]\\setminus\\mathcal{E}_{K})>\\frac{37\\varepsilon_{K}M_{K}}{150}\\xrightarrow[K\\to\\infty]{}\\infty."
}
},
{
"type": "Paragraph",
"content": [
"∎"
]
}
]
},
{
"type": "Claim",
"claimType": "Proof",
"label": "Proof that SnF=o(n) a.s..",
"title": [
"Proof that ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "SnF=o(n)",
"meta": {
"altText": "S_{n}F=o(n)"
}
},
" a.s.."
],
"content": [
{
"type": "Paragraph",
"content": [
"There is a function ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "κ:X→ℕ",
"meta": {
"altText": "\\kappa\\colon X\\to\\mathbb{N}"
}
},
" so that for a.s. ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "x∈X",
"meta": {
"altText": "x\\in X"
}
},
", ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "x∈Akc",
"meta": {
"altText": "x\\in A_{k}^{c}"
}
},
" for all ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "k≥κ(x)",
"meta": {
"altText": "k\\geq\\kappa(x)"
}
},
".\nSuppose that ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "k≥κ(x)",
"meta": {
"altText": "k\\geq\\kappa(x)"
}
},
" and ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "2Nk≤n<2Nk+1",
"meta": {
"altText": "2N_{k}\\leq n<2N_{k+1}"
}
},
", then"
]
},
{
"type": "MathBlock",
"id": "S3.Ex29",
"mathLanguage": "mathml",
"text": "|SnF(x)|=|∑j=1kSnF(j)(x)|≤∑j=1kMj<65⋅(67)k⋅Nk",
"meta": {
"altText": "\\lvert S_{n}F(x)\\rvert=\\Biggl|\\mathop{\\smash[b]{\\sum_{j=1}^{k}}}S_{n}F^{(j)}(x)\\Biggr|\\leq\\mathop{\\smash[b]{\\sum_{j=1}^{k}}}M_{j}<\\frac{6}{5}\\cdot\\biggl(\\frac{6}{7}\\biggr)^{k}\\cdot N_{k}"
}
},
{
"type": "Paragraph",
"content": [
"and"
]
},
{
"type": "MathBlock",
"id": "S3.Ex30",
"mathLanguage": "mathml",
"text": "|SnF(x)|n→n→∞0a.s.",
"meta": {
"altText": "\\smash{\\frac{\\lvert S_{n}F(x)\\rvert}{n}}\\xrightarrow[n\\to\\infty]{}0\\ \\text{a.s.}"
}
},
{
"type": "Paragraph",
"content": [
"∎"
]
}
]
},
{
"type": "Heading",
"id": "S3.SSx2",
"depth": 2,
"content": [
"238"
]
},
{
"type": "Paragraph",
"content": [
"Let ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "(Ω,ℱ,ℙ)",
"meta": {
"altText": "(\\Omega,\\mathcal{F},\\mathbb{P})"
}
},
" be a probability space and ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "{Xn:n≥1}",
"meta": {
"altText": "\\{X_{n}:n\\geq 1\\}"
}
},
" be a sequence of independent and identically distributed (i.i.d.) random variables on ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "Ω",
"meta": {
"altText": "\\Omega"
}
},
".\nAssume that there exists a sequence of positive numbers ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "{bn:n≥1}",
"meta": {
"altText": "\\{b_{n}:n\\geq 1\\}"
}
},
" such that ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "bnn≤bn+1n+1",
"meta": {
"altText": "\\frac{b_{n}}{n}\\leq\\frac{b_{n+1}}{n+1}"
}
},
" for every ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "n≥1",
"meta": {
"altText": "n\\geq 1"
}
},
", ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "limn→∞bnn=∞",
"meta": {
"altText": "\\lim_{n\\to\\infty}\\frac{b_{n}}{n}=\\infty"
}
},
", and ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "∑n=1∞ℙ(|Xn|≥bn)<∞",
"meta": {
"altText": "\\sum_{n=1}^{\\infty}\\mathbb{P}(\\lvert X_{n}\\rvert\\geq b_{n})<\\infty"
}
},
".\nProve that, if ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "Sn≔∑j=1nXj",
"meta": {
"altText": "S_{n}\\coloneqq\\sum_{j=1}^{n}X_{j}"
}
},
" for each ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "n≥1",
"meta": {
"altText": "n\\geq 1"
}
},
", then"
]
},
{
"type": "MathBlock",
"id": "S3.Ex31",
"mathLanguage": "mathml",
"text": "limn→∞Snbn=0almost surely.",
"meta": {
"altText": "\\lim_{n\\to\\infty}\\frac{S_{n}}{b_{n}}=0\\ \\text{almost surely}."
}
},
{
"type": "Paragraph",
"content": [
{
"type": "Emphasis",
"content": [
"Comment."
]
},
"\nThe desired statement says that, if such a sequence ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "{bn:n≥1}",
"meta": {
"altText": "\\{b_{n}:n\\geq 1\\}"
}
},
" exists, then ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "{Xn:n≥1}",
"meta": {
"altText": "\\{X_{n}:n\\geq 1\\}"
}
},
" satisfies the (generalized) Strong Law of Large Numbers (SLLN) when averaged by ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "{bn:n≥1}",
"meta": {
"altText": "\\{b_{n}:\\nobreak n\\geq\\nobreak 1\\}"
}
},
".\nIf ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "Xn∈L1(ℙ)",
"meta": {
"altText": "X_{n}\\in L^{1}(\\mathbb{P})"
}
},
" for every ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "n≥1",
"meta": {
"altText": "n\\geq 1"
}
},
", then the desired statement follows trivially from Kolmogorov’s SLLN, since in which case, with probability one,"
]
},
{
"type": "MathBlock",
"id": "S3.Ex32",
"mathLanguage": "mathml",
"text": "limn→∞Snn=𝔼[X1],",
"meta": {
"altText": "\\smash{\\lim_{n\\to\\infty}\\frac{S_{n}}{n}}=\\mathbb{E}[X_{1}],"
}
},
{
"type": "Paragraph",
"content": [
"and hence"
]
},
{
"type": "MathBlock",
"id": "S3.Ex33",
"mathLanguage": "mathml",
"text": "Snbn=Snn⋅nbn",
"meta": {
"altText": "\\smash[t]{\\frac{S_{n}}{b_{n}}=\\frac{S_{n}}{n}\\cdot\\frac{n}{b_{n}}}"
}
},
{
"type": "Paragraph",
"content": [
"must converge to 0 under the assumptions on ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "{bn:n≥1}",
"meta": {
"altText": "\\{b_{n}:n\\geq 1\\}"
}
},
".\nTherefore, the desired statement can be viewed as an alternative to Kolmogorov’s SLLN for i.i.d. random variables that are not integrable."
]
},
{
"type": "Paragraph",
"id": "S3.SSx2.p2",
"content": [
{
"type": "Emphasis",
"content": [
"Linan Chen (McGill University, Montreal, Quebec, Canada)"
]
}
]
},
{
"type": "Heading",
"id": "S3.SSx2.SSSx1",
"depth": 3,
"content": [
"Solution by the proposer"
]
},
{
"type": "Paragraph",
"content": [
"As explained above, we will need to prove the desired statement without assuming integrability of ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "Xn",
"meta": {
"altText": "X_{n}"
}
},
"’s.\nFor every ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "n≥1",
"meta": {
"altText": "n\\geq 1"
}
},
", we truncate ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "Xn",
"meta": {
"altText": "X_{n}"
}
},
" at the level ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "bn",
"meta": {
"altText": "b_{n}"
}
},
" by defining ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "Yn=Xn",
"meta": {
"altText": "Y_{n}=X_{n}"
}
},
" if ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "|Xn|<bn",
"meta": {
"altText": "\\lvert X_{n}\\rvertYn=0",
"meta": {
"altText": "Y_{n}=0"
}
},
" if ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "|Xn|≥bn",
"meta": {
"altText": "\\lvert X_{n}\\rvert\\geq b_{n}"
}
},
".\nThen, ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "{Yn:n≥1}",
"meta": {
"altText": "\\{Y_{n}:n\\geq 1\\}"
}
},
" is again a sequence of independent random variables.\nIt follows from the assumption on ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "{bn:n≥1}",
"meta": {
"altText": "\\{b_{n}:n\\geq 1\\}"
}
},
" that\n"
]
},
{
"type": "MathBlock",
"id": "S3.Ex34",
"mathLanguage": "mathml",
"text": "∑n=1∞ℙ(Xn≠Yn)=∑n=1∞ℙ(|Xn|≥bn)<∞,",
"meta": {
"altText": "\\sum_{n=1}^{\\infty}\\mathbb{P}(X_{n}\\neq Y_{n})=\\sum_{n=1}^{\\infty}\\mathbb{P}(\\lvert X_{n}\\rvert\\geq b_{n})<\\infty,"
}
},
{
"type": "Paragraph",
"content": [
"which, by the Borel–Cantelli lemma, implies that the sequence of the truncated random variables ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "{Yn:n≥1}",
"meta": {
"altText": "\\{Y_{n}:n\\geq 1\\}"
}
},
" is ",
{
"type": "Emphasis",
"content": [
"equivalent"
]
},
" to the original sequence ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "{Xn:n≥1}",
"meta": {
"altText": "\\{X_{n}:n\\geq 1\\}"
}
},
" in the sense that"
]
},
{
"type": "MathBlock",
"id": "S3.E1X",
"mathLanguage": "mathml",
"text": "ℙ(Xn≠Yninfinitely often)=0,or equivalently,",
"meta": {
"altText": "\\displaystyle\\mathbb{P}(X_{n}\\neq Y_{n}\\ \\text{infinitely often})=0,\\,\\text{or equivalently},"
}
},
{
"type": "MathBlock",
"id": "S3.E1Xa",
"mathLanguage": "mathml",
"text": "ℙ(Xn=Yneventually always)=1.",
"meta": {
"altText": "\\displaystyle\\mathbb{P}(X_{n}=Y_{n}\\ \\text{eventually always})=1."
}
},
{
"type": "Paragraph",
"content": [
"Next, by setting ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "b0=0",
"meta": {
"altText": "b_{0}=0"
}
},
", we have that"
]
},
{
"type": "MathBlock",
"id": "S3.Ex35",
"mathLanguage": "mathml",
"text": "∑n=1∞ℙ(|Xn|≥bn)=∑n=1∞∑k=n+1∞ℙ(bk-1≤|X1|<bk)=∑k=2∞∑n=1k-1ℙ(bk-1≤|X1|<bk)=∑k=2∞(k-1)ℙ(bk-1≤|X1|<bk)=∑k=1∞kℙ(bk-1≤|X1|<bk)-1,",
"meta": {
"altText": "\\begin{split}\\sum_{n=1}^{\\infty}\\mathbb{P}(\\lvert X_{n}\\rvert\\geq b_{n})&=\\sum_{n=1\\vphantom{k}}^{\\infty}\\sum_{k=n+1}^{\\infty}\\mathbb{P}(b_{k-1}\\leq\\lvert X_{1}\\rvert{bn:n≥1}",
"meta": {
"altText": "\\{b_{n}:n\\geq 1\\}"
}
},
" implies that"
]
},
{
"type": "MathBlock",
"id": "S3.E2",
"mathLanguage": "mathml",
"text": "∑k=1∞kℙ(bk-1≤|X1|<bk)<∞.",
"meta": {
"altText": "\\sum_{k=1}^{\\infty}k\\mathbb{P}(b_{k-1}\\leq\\lvert X_{1}\\rvert{Yn:n≥1}",
"meta": {
"altText": "\\{Y_{n}:n\\geq 1\\}"
}
},
".\nTo be specific, we want to show that if ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "Tn≔∑j=1nYj",
"meta": {
"altText": "T_{n}\\coloneqq\\sum_{j=1}^{n}Y_{j}"
}
},
" for each ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "n≥1",
"meta": {
"altText": "n\\geq 1"
}
},
", then ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "limn→∞Tnbn=0",
"meta": {
"altText": "\\lim_{n\\to\\infty}\\frac{T_{n}}{b_{n}}=0"
}
},
" almost surely.\nWe will achieve this goal in two steps."
]
},
{
"type": "Paragraph",
"content": [
"Step 1 is to treat the convergence of ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "𝔼[Tn]bn",
"meta": {
"altText": "\\frac{\\mathbb{E}[T_{n}]}{b_{n}}"
}
},
".\nTo this end, we derive an upper bound for this term as"
]
},
{
"type": "MathBlock",
"id": "S3.Ex36",
"mathLanguage": "mathml",
"text": "𝔼[|Tn|]bn≤1bn∑j=1n𝔼[|Yj|]=1bn∑j=1n∫{|X1|<bj}|X1|𝑑ℙ=1bn∑j=1n∑k=1j∫{bk-1≤|X1|<bk}|X1|𝑑ℙ≤1bn∑k=1n(n-k+1)bkℙ(bk-1≤|X1|<bk)≤2nbn∑k=1nbkℙ(bk-1≤|X1|<bk).",
"meta": {
"altText": "\\begin{split}\\frac{\\mathbb{E}[\\lvert T_{n}\\rvert]}{b_{n}}&\\leq\\frac{1}{b_{n}}\\sum_{j=1}^{n}\\mathbb{E}[\\lvert Y_{j}\\rvert]=\\frac{1}{b_{n}}\\sum_{j=1}^{n}\\int_{\\{\\lvert X_{1}\\rvert∑k=1∞bkℙ(bk-1≤|X1|<bk)(bk/k)=∑k=1∞kℙ(bk-1≤|X1|<bk)<∞,",
"meta": {
"altText": "\\sum_{k=1}^{\\infty}\\frac{b_{k}\\mathbb{P}(b_{k-1}\\leq\\lvert X_{1}\\rvertlimn→∞nbn∑k=1nbkℙ(bk-1≤|X1|<bk)=0.",
"meta": {
"altText": "\\lim_{n\\to\\infty}\\frac{n}{b_{n}}\\sum_{k=1}^{n}b_{k}\\mathbb{P}(b_{k-1}\\leq\\lvert X_{1}\\rvertlimn→∞𝔼[|Tn|]bn=0",
"meta": {
"altText": "\\lim_{n\\to\\infty}\\frac{\\mathbb{E}[\\lvert T_{n}\\rvert]}{b_{n}}=0"
}
},
"."
]
},
{
"type": "Paragraph",
"content": [
"Step 2 is to establish the convergence of ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "Tn-𝔼[Tn]bn",
"meta": {
"altText": "\\frac{T_{n}-\\mathbb{E}[T_{n}]}{b_{n}}"
}
},
", for which we will use a martingale convergence argument.\nWe note that if"
]
},
{
"type": "MathBlock",
"id": "S3.Ex39",
"mathLanguage": "mathml",
"text": "Mn≔∑j=1nYj-𝔼[Yj]bj",
"meta": {
"altText": "M_{n}\\coloneqq\\sum_{j=1}^{n}\\frac{Y_{j}-\\mathbb{E}[Y_{j}]}{b_{j}}"
}
},
{
"type": "Paragraph",
"content": [
"for each ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "n≥1",
"meta": {
"altText": "n\\geq 1"
}
},
", then ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "{Mn:n≥1}",
"meta": {
"altText": "\\{M_{n}:n\\geq 1\\}"
}
},
" is a martingale (with respect to the natural filtration) and for each ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "n≥1",
"meta": {
"altText": "n\\geq 1"
}
},
","
]
},
{
"type": "MathBlock",
"id": "S3.Ex40",
"mathLanguage": "mathml",
"text": "𝔼[Mn2]≤∑j=1n𝔼[Yj2]bj2=∑j=1n1bj2∫{|X1|<bj}X12𝑑ℙ≤∑j=1n∑k=1jbk2bj2ℙ(bk-1≤|X1|<bk)≤∑k=1n(∑j=kn1j2)k2ℙ(bk-1≤|X1|<bk)≤C∑k=1nkℙ(bk-1≤|X1|<bk),",
"meta": {
"altText": "\\begin{split}\\mathbb{E}[M_{n}^{2}]&\\leq\\sum_{j=1}^{n}\\frac{\\mathbb{E}[Y_{j}^{2}]}{b_{j}^{2}}=\\sum_{j=1}^{n}\\frac{1}{b_{j}^{2}}\\int_{\\{\\lvert X_{1}\\rvertbnn",
"meta": {
"altText": "\\frac{b_{n}}{n}"
}
},
" is increasing in ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "n",
"meta": {
"altText": "n"
}
},
", and the last inequality is due to the fact that there exists constant ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "0\" display=\"inline\">C>0",
"meta": {
"altText": "C>0"
}
},
" such that ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "∑j=k∞1j2≤Ck",
"meta": {
"altText": "\\sum_{j=k}^{\\infty}\\frac{1}{j^{2}}\\leq\\frac{C}{k}"
}
},
" for every ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "k≥1",
"meta": {
"altText": "k\\geq 1"
}
},
".\nHence, (",
{
"type": "Cite",
"target": "S3-E2",
"content": [
"2"
]
},
") implies that ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "{Mn:n≥1}",
"meta": {
"altText": "\\{M_{n}:n\\geq 1\\}"
}
},
" is bounded in ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "L2(ℙ)",
"meta": {
"altText": "L^{2}(\\mathbb{P})"
}
},
".\nA standard martingale convergence result implies that ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "limn→∞Mn",
"meta": {
"altText": "\\lim_{n\\to\\infty}M_{n}"
}
},
" exists in ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "ℝ",
"meta": {
"altText": "\\mathbb{R}"
}
},
" almost surely",
{
"type": "Note",
"id": "idm7392",
"noteType": "Footnote",
"content": [
{
"type": "Paragraph",
"id": "footnote3",
"content": [
"One can also use Kolmogorov’s maximal inequality to prove the almost sure existence of the limit of ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "",
"meta": {
"altText": "M_{n}"
}
},
"."
]
}
]
},
", which, by Kronecker’s lemma again, leads to"
]
},
{
"type": "MathBlock",
"id": "S3.Ex41",
"mathLanguage": "mathml",
"text": "limn→∞Tn-𝔼[Tn]bn=0almost surely.",
"meta": {
"altText": "\\lim_{n\\to\\infty}\\frac{T_{n}-\\mathbb{E}[T_{n}]}{b_{n}}=0\\ \\text{almost surely}."
}
},
{
"type": "Paragraph",
"content": [
"Finally, we write ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "Snbn",
"meta": {
"altText": "\\frac{S_{n}}{b_{n}}"
}
},
" as"
]
},
{
"type": "MathBlock",
"id": "S3.Ex42",
"mathLanguage": "mathml",
"text": "Snbn=Sn-Tnbn+Tn-𝔼[Tn]bn+𝔼[Tn]bn,",
"meta": {
"altText": "\\frac{S_{n}}{b_{n}}=\\frac{S_{n}-T_{n}}{b_{n}}+\\frac{T_{n}-\\mathbb{E}[T_{n}]}{b_{n}}+\\frac{\\mathbb{E}[T_{n}]}{b_{n}},"
}
},
{
"type": "Paragraph",
"content": [
"where the last two terms have been proven to converge to 0 almost surely, and (",
{
"type": "Cite",
"target": "S3-E1",
"content": [
"1"
]
},
") implies that, with probability one, the limit of the first term is also 0.\nWe have completed the proof."
]
},
{
"type": "Heading",
"id": "S3.SSx3",
"depth": 2,
"content": [
"239"
]
},
{
"type": "Paragraph",
"content": [
"In Beetown, the bees have a strict rule: all clubs must have exactly ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "k",
"meta": {
"altText": "k"
}
},
" members.\nClubs are not necessarily disjoint.\nLet ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "b(k)",
"meta": {
"altText": "b(k)"
}
},
" be the smallest number of clubs that the ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "n≥k2",
"meta": {
"altText": "n\\geq k^{2}"
}
},
" bees can form, such that no matter how they divide themselves into two teams to play beeball, there will always be a club all of whose membees are on the same team.\nProve that"
]
},
{
"type": "MathBlock",
"id": "S3.Ex43",
"mathLanguage": "mathml",
"text": "2k-1≤b(k)≤Ck2⋅2k",
"meta": {
"altText": "2^{k-1}\\leq b(k)\\leq Ck^{2}\\cdot 2^{k}"
}
},
{
"type": "Paragraph",
"content": [
"for some constant ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "0\" display=\"inline\">C>0",
"meta": {
"altText": "C>0"
}
},
"."
]
},
{
"type": "Paragraph",
"id": "S3.SSx3.p2",
"content": [
{
"type": "Emphasis",
"content": [
"Rob Morris (IMPA, Rio de Janeiro, Brasil)"
]
}
]
},
{
"type": "Heading",
"id": "S3.SSx3.SSSx1",
"depth": 3,
"content": [
"Solution by the proposer"
]
},
{
"type": "Paragraph",
"id": "S3.SSx3.SSSx1.p1",
"content": [
"This is an old result of Erdős, and a classic application of the probabilistic method.\nLet us think of the two teams as being red and blue, so that a club is ‘monochromatic’ if all of its membees are on the same team."
]
},
{
"type": "Paragraph",
"id": "S3.SSx3.SSSx1.p2",
"content": [
"First, for the lower bound, we need to show that if ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "m<2k-1",
"meta": {
"altText": "m<2^{k-1}"
}
},
", then for any collection of ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "m",
"meta": {
"altText": "m"
}
},
" clubs there exists a colouring with no monochromatic club.\nTo do so, we choose the teams randomly, and observe that the expected number of monochromatic clubs is less than ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "1",
"meta": {
"altText": "1"
}
},
".\nTo be precise, let ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "Pr(bis red)=12",
"meta": {
"altText": "\\Pr(b\\ \\text{is red})=\\frac{1}{2}"
}
},
", independently for each bee ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "b",
"meta": {
"altText": "b"
}
},
", and let ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "S",
"meta": {
"altText": "S"
}
},
" count the number of monochromatic clubs.\nThen, by linearity of expectation,\n",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "𝔼[S]=m⋅2-k+1<1",
"meta": {
"altText": "\\mathbb{E}[S]=m\\cdot 2^{-k+1}<1"
}
},
",\nsince each club is monochromatic with probability exactly ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "2-k+1",
"meta": {
"altText": "2^{-k+1}"
}
},
".\nBut this implies that ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "0\" display=\"inline\">Pr(S=0)>0",
"meta": {
"altText": "\\Pr(S=0)>0"
}
},
", so there exists a colouring with no monochromatic club, as required."
]
},
{
"type": "Paragraph",
"id": "S3.SSx3.SSSx1.p3",
"content": [
"For the upper bound, we choose the clubs randomly.\nTo be precise, choose ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "N=k2",
"meta": {
"altText": "N=k^{2}"
}
},
" bees, and choose each club uniformly and independently from the ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "k",
"meta": {
"altText": "k"
}
},
"-subsets of these ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "N",
"meta": {
"altText": "N"
}
},
" bees.\nThe idea is that, for any colouring of the bees, the expected number of monochromatic clubs is at least ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "k2",
"meta": {
"altText": "k^{2}"
}
},
", so the probability of having no monochromatic club should be at most ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "e-k2",
"meta": {
"altText": "e^{-k^{2}}"
}
},
".\nSince there are ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "2k2",
"meta": {
"altText": "2^{k^{2}}"
}
},
" colourings of these bees, the expected number of colourings with no monochromatic clubs is less than ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "1",
"meta": {
"altText": "1"
}
},
", so there must exist a choice for which it is zero."
]
},
{
"type": "Paragraph",
"content": [
"To spell out the details, fix a colouring, and suppose that ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "x",
"meta": {
"altText": "x"
}
},
" of the ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "N",
"meta": {
"altText": "N"
}
},
" chosen bees are red.\nThe probability that a random club is monochromatic is"
]
},
{
"type": "MathBlock",
"id": "S3.Ex44",
"mathLanguage": "mathml",
"text": "((xk)+(N-xk))(Nk)-1≥2⋅(N/2k)(Nk)-1≥2-k-c",
"meta": {
"altText": "\\biggl(\\biggl(\\mkern-1.0mu \\genfrac{}{}{0.0pt}{0}{x}{k}\\mkern-1.0mu \\biggr)+\\biggl(\\mkern-1.0mu \\genfrac{}{}{0.0pt}{0}{N-x}{k}\\mkern-1.0mu \\biggr)\\biggr)\\biggl(\\mkern-1.0mu \\genfrac{}{}{0.0pt}{0}{N}{k}\\mkern-1.0mu \\biggr)^{-1}\\geq 2\\cdot\\biggl(\\mkern-1.0mu \\genfrac{}{}{0.0pt}{0}{N/2}{k}\\mkern-1.0mu \\biggr)\\biggl(\\mkern-1.0mu \\genfrac{}{}{0.0pt}{0}{N}{k}\\mkern-1.0mu \\biggr)^{-1}\\geq 2^{-k-c}"
}
},
{
"type": "Paragraph",
"content": [
"for some constant ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "0\" display=\"inline\">c>0",
"meta": {
"altText": "c>0"
}
},
", where in the final inequality we used the fact that ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "N≥k2",
"meta": {
"altText": "N\\geq k^{2}"
}
},
"."
]
},
{
"type": "Paragraph",
"content": [
"Now, let ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "T",
"meta": {
"altText": "T"
}
},
" count the number of colourings of the ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "N",
"meta": {
"altText": "N"
}
},
" bees with no monochromatic club, and observe that if there are ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "m=k22k+c",
"meta": {
"altText": "m=k^{2}2^{k+c}"
}
},
" clubs, then"
]
},
{
"type": "MathBlock",
"id": "S3.Ex45",
"mathLanguage": "mathml",
"text": "𝔼[T]≤∑colouringsof the N bees(1-2-k-c)m≤ 2k2e-k2<1.",
"meta": {
"altText": "\\mathbb{E}[T]\\,\\leq\\sum_{\\begin{subarray}{c}\\text{colourings}\\\\\n\\text{of the $N$ bees}\\end{subarray}}\\big(1-2^{-k-c}\\big)^{m}\\leq\\,2^{k^{2}}e^{-k^{2}}<1."
}
},
{
"type": "Paragraph",
"content": [
"It follows that there exists a choice of ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "m",
"meta": {
"altText": "m"
}
},
" clubs such that ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "T=0",
"meta": {
"altText": "T=0"
}
},
", as required."
]
},
{
"type": "Heading",
"id": "S3.SSx4",
"depth": 2,
"content": [
"240"
]
},
{
"type": "Paragraph",
"id": "S3.SSx4.p1",
"content": [
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "N",
"meta": {
"altText": "N"
}
},
" agents are in a room with a server, and each agent is looking to get served, at which point the agent leaves the room.\nAt any discrete time step, each agent may choose to either shout or stay quiet, and an agent gets served in that round if (and only if) that agent is the only one to have shouted.\nThe agents are indistinguishable to each other at the start, but at each subsequent step, every agent gets to see who has shouted and who has not.\nIf all the agents are required to use the same randomised strategy, show that the minimum time to clear the room in expectation is ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "N+(2+o(1))log2N",
"meta": {
"altText": "N+(2+o(1))\\log_{2}N"
}
},
"."
]
},
{
"type": "Paragraph",
"id": "S3.SSx4.p2",
"content": [
{
"type": "Emphasis",
"content": [
"Bhargav Narayanan (Rutgers University, Piscataway, USA)"
]
}
]
},
{
"type": "Heading",
"id": "S3.SSx4.SSSx1",
"depth": 3,
"content": [
"Solution by the proposer"
]
},
{
"type": "Paragraph",
"id": "S3.SSx4.SSSx1.p1",
"content": [
"Here is a simple strategy that works in expected time ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "N+(2+o(1))log2N",
"meta": {
"altText": "N+(2+o(1))\\log_{2}N"
}
},
".\nThe agents all toss independent fair coins to decide whether to shout or not in each of the first ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "k=(2+o(1))log2N",
"meta": {
"altText": "k=(2+o(1))\\log_{2}N"
}
},
" rounds.\nIt is easy to see that with high probability, after these ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "k",
"meta": {
"altText": "k"
}
},
" rounds, every agent (still in the room) has a unique ‘history’, i.e. no two agents have the exact same sequence of turns (shouting/staying quiet).\nNow the agents are all distinguishable, and we are done in ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "N",
"meta": {
"altText": "N"
}
},
" more steps; for example, the agents can interpret each others histories as numbers in binary, and can get served in increasing order.\nBelow, we show that no strategy can do significantly better."
]
},
{
"type": "Paragraph",
"content": [
"At any time, we can partition all the agents into clusters based on their history so far: two agents go into the same cluster if they have chosen to do the same thing in all previous rounds.\nBy the requirement that the agents all have the same randomised strategy, we know that at any time, all the agents in the same cluster must have the same strategy.\nLet ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "X",
"meta": {
"altText": "X"
}
},
" be the number of times an agent from a cluster of size at least 2 gets served and leaves the room, and let ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "Y",
"meta": {
"altText": "Y"
}
},
" be the number of times either"
]
},
{
"type": "Paragraph",
"content": []
},
{
"type": "List",
"items": [
{
"type": "ListItem",
"content": [
{
"type": "Paragraph",
"id": "S3.I1.i1.p1",
"content": [
"exactly two agents from the same cluster, and nobody else, ask to be served, or"
]
}
]
},
{
"type": "ListItem",
"content": [
{
"type": "Paragraph",
"id": "S3.I1.i2.p1",
"content": [
"nobody asks to be served at all."
]
}
]
}
],
"order": "Ascending"
},
{
"type": "Paragraph",
"content": [
"An easy computation shows that"
]
},
{
"type": "MathBlock",
"id": "S3.Ex46",
"mathLanguage": "mathml",
"text": "ℙ(Bin(m,p)=1)≤ℙ(Bin(m,p)=0)+ℙ(Bin(m,p)=2)",
"meta": {
"altText": "\\mathbb{P}(\\operatorname{Bin}(m,p)=1)\\leq\\mathbb{P}(\\operatorname{Bin}(m,p)=0)+\\mathbb{P}(\\operatorname{Bin}(m,p)=2)"
}
},
{
"type": "Paragraph",
"content": [
"for all ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "1\" display=\"inline\">m>1",
"meta": {
"altText": "m>1"
}
},
" and any ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "0≤p≤1",
"meta": {
"altText": "0\\leq p\\leq 1"
}
},
"; consequently, it is easy to see that ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "Y",
"meta": {
"altText": "Y"
}
},
" stochastically dominates ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "X",
"meta": {
"altText": "X"
}
},
".\nSo, if for some strategy,"
]
},
{
"type": "MathBlock",
"id": "S3.Ex47",
"mathLanguage": "mathml",
"text": "2(\\log_{2}N)^{2}\\bigr)>\\frac{1}{\\log_{2}N},\" display=\"block\">ℙ(X>2(log2N)2)>1log2N,",
"meta": {
"altText": "\\mathbb{P}\\bigl(X>2(\\log_{2}N)^{2}\\bigr)>\\frac{1}{\\log_{2}N},"
}
},
{
"type": "Paragraph",
"content": [
"then the expected time to clear the room, which is at least ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "N+Y",
"meta": {
"altText": "N+\\nobreak Y"
}
},
", is at least ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "N+2log2N",
"meta": {
"altText": "N+2\\log_{2}N"
}
},
" in expectation.\nSo we may assume that ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "X<2(log2N)2",
"meta": {
"altText": "X<2(\\log_{2}N)^{2}"
}
},
" with high probability for any strategy under consideration."
]
},
{
"type": "Paragraph",
"id": "S3.SSx4.SSSx1.p3",
"content": [
"Let ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "S",
"meta": {
"altText": "S"
}
},
" be the set of agents who leave the room only when they belong to their own singleton cluster.\nAs we just observed, the number of such agents ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "|S|=M=N-X",
"meta": {
"altText": "\\lvert S\\rvert=M=N-X"
}
},
" may be assumed to be at least ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "N-2(log2N)2",
"meta": {
"altText": "N-2(\\log_{2}N)^{2}"
}
},
".\nThe key observation is this: if someone leaves the room in a particular step, the cluster structure of ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "S",
"meta": {
"altText": "S"
}
},
" does not change in that step.\nTo see this, note that when an agent not from ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "S",
"meta": {
"altText": "S"
}
},
" leaves the room, that agent shouts and everyone in ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "S",
"meta": {
"altText": "S"
}
},
" does not, so there is no change to the cluster structure of ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "S",
"meta": {
"altText": "S"
}
},
".\nOn the other hand, when an agent from ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "S",
"meta": {
"altText": "S"
}
},
" leaves the room, that agent is, by definition, already in their own singleton cluster, and every other agent in ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "S",
"meta": {
"altText": "S"
}
},
" does not shout in this step; again, there is no change in the cluster structure of ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "S",
"meta": {
"altText": "S"
}
},
"."
]
},
{
"type": "Paragraph",
"id": "S3.SSx4.SSSx1.p4",
"content": [
"But we know that at the end of the process, which let us say takes ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "N+Δ",
"meta": {
"altText": "N+\\Delta"
}
},
" rounds, ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "S",
"meta": {
"altText": "S"
}
},
" has been split from a single cluster into ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "M",
"meta": {
"altText": "M"
}
},
" singleton clusters.\nNothing changes in the cluster structure of ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "S",
"meta": {
"altText": "S"
}
},
" in the ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "N",
"meta": {
"altText": "N"
}
},
" rounds when someone leaves the room, so ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "S",
"meta": {
"altText": "S"
}
},
" gets broken down into singleton clusters in the remaining ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "Δ",
"meta": {
"altText": "\\Delta"
}
},
" steps."
]
},
{
"type": "Paragraph",
"id": "S3.SSx4.SSSx1.p5",
"content": [
"Consider these ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "Δ",
"meta": {
"altText": "\\Delta"
}
},
" steps where nobody leaves the room.\nDeterministically, in the first ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "log2M-1",
"meta": {
"altText": "\\log_{2}M-1"
}
},
" of these steps, we can produce at most ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "M2",
"meta": {
"altText": "\\frac{M}{2}"
}
},
" singletons in ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "S",
"meta": {
"altText": "S"
}
},
".\nThe remaining ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "M2",
"meta": {
"altText": "\\frac{M}{2}"
}
},
" agents in ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "S",
"meta": {
"altText": "S"
}
},
" are all in clusters of size at least 2.\nDivide all these cluster into sub-clusters each of size 2 (by ignoring agents if necessary).\nThe result is at least ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "M6",
"meta": {
"altText": "\\frac{M}{6}"
}
},
" 2-clusters that we still need to break down into singletons (the worst case being when the ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "M2",
"meta": {
"altText": "\\frac{M}{2}"
}
},
" agents are each in a cluster of size 3).\nThe probability that a 2-cluster breaks down into two singletons at any given time step, with any strategy, is at most ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "12",
"meta": {
"altText": "\\frac{1}{2}"
}
},
".\nSo in any strategy, we need at least another ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "log2M-log2log2M",
"meta": {
"altText": "\\log_{2}M-\\log_{2}\\log_{2}M"
}
},
" time steps, say, for all these 2-clusters to separate into singletons.\nThus, ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "Δ≥2log2M-log2log2M",
"meta": {
"altText": "\\Delta\\geq 2\\log_{2}M-\\log_{2}\\log_{2}M"
}
},
" with high probability, which with our previous bound on ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "M",
"meta": {
"altText": "M"
}
},
", tells us that any strategy takes at least ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "N+(2-o(1))log2N",
"meta": {
"altText": "N+(2-o(1))\\log_{2}N"
}
},
" steps to clear the room."
]
},
{
"type": "Heading",
"id": "S3.SSx5",
"depth": 2,
"content": [
"241"
]
},
{
"type": "Paragraph",
"id": "S3.SSx5.p1",
"content": [
"Consider the following sequence of partitions of the unit interval ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "I",
"meta": {
"altText": "I"
}
},
": First, define ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "π1",
"meta": {
"altText": "\\pi_{1}"
}
},
" to be the partition of ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "I",
"meta": {
"altText": "I"
}
},
" into two intervals, a red interval of length ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "13",
"meta": {
"altText": "\\frac{1}{3}"
}
},
" and a blue one of length ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "23",
"meta": {
"altText": "\\frac{2}{3}"
}
},
".\nNext, for any ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "1\" display=\"inline\">m>1",
"meta": {
"altText": "m>1"
}
},
", define ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "πm+1",
"meta": {
"altText": "\\pi_{m+1}"
}
},
" to be the partition derived from ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "πm",
"meta": {
"altText": "\\pi_{m}"
}
},
" by splitting all intervals of maximal length in ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "πm",
"meta": {
"altText": "\\pi_{m}"
}
},
", each into two intervals, a red one of ratio ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "13",
"meta": {
"altText": "\\frac{1}{3}"
}
},
" and a blue one of ratio ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "23",
"meta": {
"altText": "\\frac{2}{3}"
}
},
", just as in the first step.\nFor example ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "π2",
"meta": {
"altText": "\\pi_{2}"
}
},
" consists of three intervals of lengths ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "13",
"meta": {
"altText": "\\frac{1}{3}"
}
},
" (red), ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "29",
"meta": {
"altText": "\\frac{2}{9}"
}
},
" (red) and ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "49",
"meta": {
"altText": "\\frac{4}{9}"
}
},
" (blue), the last two are the result of splitting the blue interval in ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "π1",
"meta": {
"altText": "\\pi_{1}"
}
},
".\nThe figure above illustrates ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "π1,…,π4",
"meta": {
"altText": "\\pi_{1},\\ldots,\\pi_{4}"
}
},
", from top to bottom."
]
},
{
"type": "Figure",
"id": "S3-SSx5-fig1",
"licenses": [
{
"type": "CreativeWork",
"url": "https://creativecommons.org/licenses/by/4.0/legalcode",
"content": [
{
"type": "Paragraph",
"content": []
}
]
}
],
"content": [
{
"type": "ImageObject",
"contentUrl": "38-kakutaniredandblue.svg",
"mediaType": "image/svg+xml",
"meta": {
"inline": false
}
}
]
},
{
"type": "Paragraph",
"content": [
"Let ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "m∈ℕ",
"meta": {
"altText": "m\\in\\mathbb{N}"
}
},
" and consider the ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "m",
"meta": {
"altText": "m"
}
},
"-th partition ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "πm",
"meta": {
"altText": "\\pi_{m}"
}
},
"."
]
},
{
"type": "Paragraph",
"content": []
},
{
"type": "List",
"items": [
{
"type": "ListItem",
"content": [
{
"type": "Paragraph",
"id": "S3.I2.i1.p1",
"content": [
"Choose an interval in ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "πm",
"meta": {
"altText": "\\pi_{m}"
}
},
" uniformly at random.\nLet ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "Rm",
"meta": {
"altText": "R_{m}"
}
},
" be the probability you chose a red interval.\nDoes the sequence ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "(Rm)m∈ℕ",
"meta": {
"altText": "(R_{m})_{m\\in\\mathbb{N}}"
}
},
" converge? If so, what is the limit?"
]
}
]
},
{
"type": "ListItem",
"content": [
{
"type": "Paragraph",
"id": "S3.I2.i2.p1",
"content": [
"Choose a point in ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "I",
"meta": {
"altText": "I"
}
},
" uniformly at random.\nLet ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "Am",
"meta": {
"altText": "A_{m}"
}
},
" be the probability that the point is colored red.\nDoes the sequence ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "(Am)m∈ℕ",
"meta": {
"altText": "(A_{m})_{m\\in\\mathbb{N}}"
}
},
" converge? If so, what is the limit?"
]
}
]
}
],
"order": "Ascending"
},
{
"type": "Paragraph",
"id": "S3.SSx5.p3",
"content": [
{
"type": "Emphasis",
"content": [
"Yotam Smilansky (Rutgers University, NJ, USA)"
]
}
]
},
{
"type": "Heading",
"id": "S3.SSx5.SSSx1",
"depth": 3,
"content": [
"Solution by the proposer"
]
},
{
"type": "Paragraph",
"id": "S3.SSx5.SSSx1.p1",
"content": [
"The proposed solution is based on path counting results [",
{
"type": "Cite",
"target": "bib-bib26",
"content": [
"26"
]
},
"] on an appropriately defined graph, and can be generalized to higher dimensions and to more complicated sequences of partitions [",
{
"type": "Cite",
"target": "bib-bib27",
"content": [
"27"
]
},
"]."
]
},
{
"type": "Paragraph",
"id": "S3.SSx5.SSSx1.p2",
"content": [
"Let ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "G",
"meta": {
"altText": "G"
}
},
" be a weighted graph with a single vertex and two directed loops: a red one of length ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "-log(13)",
"meta": {
"altText": "-\\log(\\frac{1}{3})"
}
},
" and a blue one of length ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "-log(23)",
"meta": {
"altText": "-\\log(\\frac{2}{3})"
}
},
", and consider directed walks along the edges of ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "G",
"meta": {
"altText": "G"
}
},
" that originate at the vertex and terminate on a point of a colored loop.\nThe first important observation is that there is a 1-1 correspondence between colored intervals in ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "πm",
"meta": {
"altText": "\\pi_{m}"
}
},
" and walks of length ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "ℓm",
"meta": {
"altText": "\\ell_{m}"
}
},
" on ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "G",
"meta": {
"altText": "G"
}
},
", where ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "(ℓm)m∈ℕ",
"meta": {
"altText": "(\\ell_{m})_{m\\in\\mathbb{N}}"
}
},
" is the increasing sequence of lengths of closed orbits on ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "G",
"meta": {
"altText": "G"
}
},
".\nIn the following illustration, the top is partition ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "π1",
"meta": {
"altText": "\\pi_{1}"
}
},
" and the corresponding two walks of length ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "ℓ1=-log(23)",
"meta": {
"altText": "\\ell_{1}=-\\log(\\frac{2}{3})"
}
},
", and the bottom is partition ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "π2",
"meta": {
"altText": "\\pi_{2}"
}
},
" and the corresponding three walks of length ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "ℓ2=-2log(23)",
"meta": {
"altText": "\\ell_{2}=-2\\log(\\frac{2}{3})"
}
},
"."
]
},
{
"type": "Figure",
"id": "S3-SSx5-SSSx1-fig1",
"licenses": [
{
"type": "CreativeWork",
"url": "https://creativecommons.org/licenses/by/4.0/legalcode",
"content": [
{
"type": "Paragraph",
"content": []
}
]
}
],
"content": [
{
"type": "ImageObject",
"contentUrl": "38-kakutanicoloredpaths.svg",
"mediaType": "image/svg+xml",
"meta": {
"inline": false
}
}
]
},
{
"type": "Paragraph",
"id": "S3.SSx5.SSSx1.p3",
"content": [
"In general, a splitting of an interval corresponds to an extension of a walk that terminates at the vertex to two new walks, one that extends onto the red loop and the other onto the blue.\nTherefore, ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "Rm",
"meta": {
"altText": "R_{m}"
}
},
" is the relative part of walks of length ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "ℓm",
"meta": {
"altText": "\\ell_{m}"
}
},
" that terminate on the red loop.\nFor ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "Am",
"meta": {
"altText": "A_{m}"
}
},
", consider random walks on ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "G",
"meta": {
"altText": "G"
}
},
" and prescribe probabilities to the two outgoing loops: a walk along ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "G",
"meta": {
"altText": "G"
}
},
" is extended onto the red loop when reaching the vertex with probability ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "13",
"meta": {
"altText": "\\frac{1}{3}"
}
},
", and onto the blue loop with probability ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "23",
"meta": {
"altText": "\\frac{2}{3}"
}
},
".\nThese are chosen because ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "13",
"meta": {
"altText": "\\frac{1}{3}"
}
},
" of a split interval is colored red and ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "23",
"meta": {
"altText": "\\frac{2}{3}"
}
},
" colored blue.\nIt follows that ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "Am",
"meta": {
"altText": "A_{m}"
}
},
" is the probability that a walker is located on the red loop after walking a walk of length ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "ℓm",
"meta": {
"altText": "\\ell_{m}"
}
},
"."
]
},
{
"type": "Paragraph",
"id": "S3.SSx5.SSSx1.p4",
"content": [
"The second observation is that in order to compute the asymptotic behavior of ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "Rm",
"meta": {
"altText": "R_{m}"
}
},
" and ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "Am",
"meta": {
"altText": "A_{m}"
}
},
", one can apply the well-known Wiener–Ikehara theorem, originally devised to approach the prime number theorem.\nThe theorem states that if there exists ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "λ∈ℝ",
"meta": {
"altText": "\\lambda\\in\\mathbb{R}"
}
},
" for which the Laplace transform of a counting function is analytic for ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "\\lambda\" display=\"inline\">ℜ(s)>λ",
"meta": {
"altText": "\\Re(s)>\\lambda"
}
},
", has a simple pole at ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "s=λ",
"meta": {
"altText": "s=\\lambda"
}
},
" and no other singular points on the vertical line ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "ℜ(s)=λ",
"meta": {
"altText": "\\Re(s)=\\lambda"
}
},
", then the main term of the growth rate is ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "ceλx",
"meta": {
"altText": "ce^{\\lambda x}"
}
},
", with ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "c",
"meta": {
"altText": "c"
}
},
" the residue of the Laplace transform at ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "s=λ",
"meta": {
"altText": "s=\\lambda"
}
},
"."
]
},
{
"type": "Paragraph",
"content": [
"A direct computation shows that the Laplace transform for the number of walks that terminate on the red loop is"
]
},
{
"type": "MathBlock",
"id": "S3.Ex48",
"mathLanguage": "mathml",
"text": "1s⋅1-(13)s1-(13)s-(23)s.",
"meta": {
"altText": "\\frac{1}{s}\\cdot\\frac{1-\\bigl(\\frac{1}{3}\\bigr)^{s}}{1-\\bigl(\\frac{1}{3}\\bigr)^{s}-\\bigl(\\frac{2}{3}\\bigr)^{s}}."
}
},
{
"type": "Paragraph",
"content": [
"Inspecting the term ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "1-(13)s-(23)s",
"meta": {
"altText": "1-\\bigl(\\frac{1}{3}\\bigr)^{s}-\\bigl(\\frac{2}{3}\\bigr)^{s}"
}
},
" one sees that ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "s=1",
"meta": {
"altText": "s=1"
}
},
" is a simple root of maximal real part, and so to apply the Wiener–Ikehara theorem it suffices to establish that there are no other roots of the form ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "1+it",
"meta": {
"altText": "1+it"
}
},
".\nIndeed, a careful but elementary inspection shows that otherwise, the loops of ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "G",
"meta": {
"altText": "G"
}
},
" must have commensurable lengths, or equivalently ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "log23∈ℚ",
"meta": {
"altText": "\\log_{2}3\\in\\mathbb{Q}"
}
},
", which is of course false.\nThe Laplace transform of the total number of walks is similar but has numerator ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "2-(13)s-(23)s",
"meta": {
"altText": "2-\\bigl(\\frac{1}{3}\\bigr)^{s}-\\bigl(\\frac{2}{3}\\bigr)^{s}"
}
},
", and so ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "Rm",
"meta": {
"altText": "R_{m}"
}
},
" tends to the ratio of the residues of these two transforms at ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "s=1",
"meta": {
"altText": "s=1"
}
},
", that is,\n",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "limm→∞Rm=23",
"meta": {
"altText": "\\lim_{m\\to\\infty}R_{m}=\\frac{2}{3}"
}
},
".\nSimilarly, the Laplace transform for ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "Am",
"meta": {
"altText": "A_{m}"
}
},
" is"
]
},
{
"type": "MathBlock",
"id": "S3.Ex49",
"mathLanguage": "mathml",
"text": "13s⋅1-(13)s1-(13)s+1-(23)s+1,",
"meta": {
"altText": "\\frac{\\frac{1}{3}}{s}\\cdot\\frac{1-\\bigl(\\frac{1}{3}\\bigr)^{s}}{1-\\bigl(\\frac{1}{3}\\bigr)^{s+1}-\\bigl(\\frac{2}{3}\\bigr)^{s+1}},"
}
},
{
"type": "Paragraph",
"content": [
"with the same poles but shifted by ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "-1",
"meta": {
"altText": "-1"
}
},
".\nIt follows that ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "Am",
"meta": {
"altText": "A_{m}"
}
},
" converges to the residue at ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "s=0",
"meta": {
"altText": "s=0"
}
},
", namely"
]
},
{
"type": "MathBlock",
"id": "S3.Ex50",
"mathLanguage": "mathml",
"text": "limm→∞Am=-13log13-13log13-23log23.",
"meta": {
"altText": "\\lim_{m\\to\\infty}A_{m}=\\frac{-\\frac{1}{3}\\log\\frac{1}{3}}{-\\frac{1}{3}\\log\\frac{1}{3}-\\frac{2}{3}\\log\\frac{2}{3}}."
}
},
{
"type": "Paragraph",
"id": "S3.SSx5.SSSx1.p6",
"content": [
"Note that the limit of ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "Rm",
"meta": {
"altText": "R_{m}"
}
},
" is simply the length of the blue interval in ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "π1",
"meta": {
"altText": "\\pi_{1}"
}
},
", and the limit of ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "Am",
"meta": {
"altText": "A_{m}"
}
},
" can be viewed as the relative contribution of the red interval to the partition entropy of ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "π1",
"meta": {
"altText": "\\pi_{1}"
}
},
".\nThis interpretation leads me to suspect that there may exist a more direct and illuminating approach to these problems, possibly based on tools from probability and dynamics, and I would be very happy to discuss any ideas or suggestions."
]
},
{
"type": "Heading",
"id": "S3.SSx6",
"depth": 2,
"content": [
"242"
]
},
{
"type": "Paragraph",
"content": [
"Prove that there exist ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "c<1",
"meta": {
"altText": "c<1"
}
},
" and ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "0\" display=\"inline\">ε>0",
"meta": {
"altText": "\\varepsilon>0"
}
},
" such that if ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "A1,…,Ak",
"meta": {
"altText": "A_{1},\\dots,A_{k}"
}
},
" are increasing events of independent boolean random variables with ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "Pr(Ai)<ε",
"meta": {
"altText": "\\Pr(A_{i})<\\varepsilon"
}
},
" for all ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "i",
"meta": {
"altText": "i"
}
},
", then"
]
},
{
"type": "MathBlock",
"id": "S3.Ex51",
"mathLanguage": "mathml",
"text": "Pr(exactly one ofA1,…,Akoccurs)≤c.",
"meta": {
"altText": "\\Pr(\\text{exactly one of}\\ A_{1},\\dots,A_{k}\\ \\text{occurs})\\leq c."
}
},
{
"type": "Paragraph",
"content": [
"(What is the smallest ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "c",
"meta": {
"altText": "c"
}
},
" that you can prove?)"
]
},
{
"type": "Paragraph",
"id": "S3.SSx6.p2",
"content": [
"Here ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "A⊂{0,1}n",
"meta": {
"altText": "A\\subset\\{0,1\\}^{n}"
}
},
" is an “increasing event” if whenever ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "x∈A",
"meta": {
"altText": "x\\in A"
}
},
", then the vector obtained by changing any coordinates of ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "x",
"meta": {
"altText": "x"
}
},
" from ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "0",
"meta": {
"altText": "0"
}
},
" to ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "1",
"meta": {
"altText": "1"
}
},
" still lies in ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "A",
"meta": {
"altText": "A"
}
},
"."
]
},
{
"type": "Paragraph",
"id": "S3.SSx6.p3",
"content": [
"A useful fact is the Harris inequality, which states that for increasing events ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "A",
"meta": {
"altText": "A"
}
},
" and ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "B",
"meta": {
"altText": "B"
}
},
" of boolean random variables, ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "Pr(A∩B)≥Pr(A)Pr(B)",
"meta": {
"altText": "\\Pr(A\\cap B)\\geq\\Pr(A)\\Pr(B)"
}
},
"."
]
},
{
"type": "Paragraph",
"id": "S3.SSx6.p4",
"content": [
"I learned of this problem from Jeff Kahn."
]
},
{
"type": "Paragraph",
"id": "S3.SSx6.p5",
"content": [
{
"type": "Emphasis",
"content": [
"Yufei Zhao (MIT, Cambridge, USA)"
]
}
]
},
{
"type": "Heading",
"id": "S3.SSx6.SSSx1",
"depth": 3,
"content": [
"Solution by the proposer"
]
},
{
"type": "Paragraph",
"id": "S3.SSx6.SSSx1.p1",
"content": [
"We will show that the claim is true for every ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "0\" display=\"inline\">ε>0",
"meta": {
"altText": "\\varepsilon>0"
}
},
" and ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "c=1+ε2",
"meta": {
"altText": "c=\\frac{1+\\varepsilon}{2}"
}
},
"."
]
},
{
"type": "Paragraph",
"id": "S3.SSx6.SSSx1.p2",
"content": [
"If ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "Pr(A1∪⋯∪Ak)≤c",
"meta": {
"altText": "\\Pr(A_{1}\\cup\\cdots\\cup A_{k})\\leq c"
}
},
", then the conclusion is automatic.\nSo let us assume that ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "c\" display=\"inline\">Pr(A1∪⋯∪Ak)>c",
"meta": {
"altText": "\\Pr(A_{1}\\cup\\cdots\\cup A_{k})>c"
}
},
".\nSince ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "Pr(Ai)<ε",
"meta": {
"altText": "\\Pr(A_{i})<\\varepsilon"
}
},
" for each ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "i",
"meta": {
"altText": "i"
}
},
", there exists some ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "j",
"meta": {
"altText": "j"
}
},
" such that ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "Pr(A1∪⋯∪Aj)",
"meta": {
"altText": "\\Pr(A_{1}\\cup\\cdots\\cup A_{j})"
}
},
" lies within ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "ε2",
"meta": {
"altText": "\\frac{\\varepsilon}{2}"
}
},
" of ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "12",
"meta": {
"altText": "\\frac{1}{2}"
}
},
".\nLet ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "B=A1∪⋯∪Aj",
"meta": {
"altText": "B=A_{1}\\cup\\cdots\\cup A_{j}"
}
},
" and ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "C=Aj+1∪⋯∪Ak",
"meta": {
"altText": "C=A_{j+1}\\cup\\cdots\\cup A_{k}"
}
},
".\nWe write ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "B¯",
"meta": {
"altText": "\\overline{B}"
}
},
" and ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "C¯",
"meta": {
"altText": "\\overline{C}"
}
},
" for the complementary events."
]
},
{
"type": "Paragraph",
"content": [
"If exactly one of ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "A1,…,Ak",
"meta": {
"altText": "A_{1},\\dots,A_{k}"
}
},
" occurs, then exactly one of ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "B",
"meta": {
"altText": "B"
}
},
" and ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "C",
"meta": {
"altText": "C"
}
},
" can occur.\nSo"
]
},
{
"type": "MathBlock",
"id": "S3.Ex52",
"mathLanguage": "mathml",
"text": "Pr(exactly one ofA1,…,Akoccurs)≤Pr(B∩C¯)+Pr(B¯∩C)≤Pr(B)Pr(C¯)+Pr(B¯)Pr(C)≤max{Pr(B),Pr(B¯)}≤1+ε2",
"meta": {
"altText": "\\begin{split}\\Pr(\\text{exactly one of}\\ A_{1},\\dots,A_{k}\\ \\text{occurs})&\\leq\\Pr(B\\cap\\overline{C})+\\Pr(\\overline{B}\\cap C)\\\\\n&\\leq\\Pr(B)\\Pr(\\overline{C})+\\Pr(\\overline{B})\\Pr(C)\\\\\n&\\leq\\max\\{\\Pr(B),\\Pr(\\overline{B})\\}\\\\\n&\\leq\\frac{1+\\varepsilon}{2}\\end{split}"
}
},
{
"type": "Paragraph",
"content": [
"where the second inequality is due to Harris’ inequality."
]
},
{
"type": "Paragraph",
"id": "S3.SSx6.SSSx1.p4",
"content": [
{
"type": "Emphasis",
"content": [
"Remark."
]
},
"\nIt is conjectured that for any ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "\\frac{1}{e}\" display=\"inline\">c>1e",
"meta": {
"altText": "c>\\frac{1}{e}"
}
},
" there exists some ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "0\" display=\"inline\">ε>0",
"meta": {
"altText": "\\varepsilon>0"
}
},
" for which the statement is true.\nHere ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "1e",
"meta": {
"altText": "\\frac{1}{e}"
}
},
" is optimal, since if ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "Ai",
"meta": {
"altText": "A_{i}"
}
},
" are independent Bernoulli random variables with mean ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "1k",
"meta": {
"altText": "\\frac{1}{k}"
}
},
", then the number of occurrences is asymptotically Poisson with mean 1, with so that the probability of single occurrence is ",
{
"type": "MathFragment",
"mathLanguage": "mathml",
"text": "1e+o(1)",
"meta": {
"altText": "\\frac{1}{e}+o(1)"
}
},
"."
]
},
{
"type": "Paragraph",
"id": "S3.SSx6.SSSx1.p5",
"content": [
{
"type": "Emphasis",
"content": [
"We are eager to receive your solutions to the proposed problems, and any ideas that you may have on open problems.\nSend your solutions\nto Michael Th. Rassias (Institute of Mathematics, University of Zürich, Winterthurerstrasse 190, 8057 Zürich, Switzerland; ",
{
"type": "Link",
"target": "mailto:michail.rassias@math.uzh.ch",
"content": [
"michail.rassias@math.uzh.ch"
]
},
")."
]
}
]
},
{
"type": "Paragraph",
"id": "S3.SSx6.SSSx1.p6",
"content": [
{
"type": "Emphasis",
"content": [
"We also solicit your suggestions for new problems together with their solutions, for the next “Solved and unsolved problems” column, which will be devoted to Topology/Geometry."
]
}
]
}
]
}