Friendly frogs, stable marriage, and the magic of invariance

Maria Deijfen; Alexander E. Holroyd; James B. Martin

doi:10.48550/arXiv.1604.03161

Friendly frogs, stable marriage, and the magic of invariance

Maria Deijfen, Alexander E. Holroyd, James B. Martin

Research output: Contribution to journal › Article (Academic Journal) › peer-review

6 Citations (Scopus)

Abstract

We introduce a two-player game involving two tokens located at points of a fixed set. The players take turns to move a token to an unoccupied point in such a way that the distance between the two tokens is decreased. Optimal strategies for this game and its variants are intimately tied to Gale-Shapley stable marriage. We focus particularly on the case of random infinite sets, where we use invariance, ergodicity, mass transport, and deletion-tolerance to determine game outcomes.

Original language	English
Number of pages	17
Journal	American Mathematical Monthly
Volume	124
Issue number	5
DOIs	https://doi.org/10.48550/arXiv.1604.03161 https://doi.org/10.4169/amer.math.monthly.124.5.387
Publication status	Published - 13 Dec 2017

Keywords

math.PR

Access to Document

Handle.net

Persistent link

Paul R. Halmos-Lester R. Ford Award
Holroyd, A. E. (Recipient), Deijfen, M. (Recipient) & Martin, J. (Recipient), 2018
Prize: Prizes, Medals, Awards and Grants

Cite this

@article{07a33780daaa4a559c8ebbd7601ae201,

title = "Friendly frogs, stable marriage, and the magic of invariance",

abstract = " We introduce a two-player game involving two tokens located at points of a fixed set. The players take turns to move a token to an unoccupied point in such a way that the distance between the two tokens is decreased. Optimal strategies for this game and its variants are intimately tied to Gale-Shapley stable marriage. We focus particularly on the case of random infinite sets, where we use invariance, ergodicity, mass transport, and deletion-tolerance to determine game outcomes. ",

keywords = "math.PR",

author = "Maria Deijfen and Holroyd, \{Alexander E.\} and Martin, \{James B.\}",

year = "2017",

month = dec,

day = "13",

doi = "10.48550/arXiv.1604.03161",

language = "English",

volume = "124",

journal = "American Mathematical Monthly",

issn = "0002-9890",

publisher = "Taylor \& Francis Group",

number = "5",

}

TY - JOUR

T1 - Friendly frogs, stable marriage, and the magic of invariance

AU - Deijfen, Maria

AU - Holroyd, Alexander E.

AU - Martin, James B.

PY - 2017/12/13

Y1 - 2017/12/13

N2 - We introduce a two-player game involving two tokens located at points of a fixed set. The players take turns to move a token to an unoccupied point in such a way that the distance between the two tokens is decreased. Optimal strategies for this game and its variants are intimately tied to Gale-Shapley stable marriage. We focus particularly on the case of random infinite sets, where we use invariance, ergodicity, mass transport, and deletion-tolerance to determine game outcomes.

AB - We introduce a two-player game involving two tokens located at points of a fixed set. The players take turns to move a token to an unoccupied point in such a way that the distance between the two tokens is decreased. Optimal strategies for this game and its variants are intimately tied to Gale-Shapley stable marriage. We focus particularly on the case of random infinite sets, where we use invariance, ergodicity, mass transport, and deletion-tolerance to determine game outcomes.

KW - math.PR

U2 - 10.48550/arXiv.1604.03161

DO - 10.48550/arXiv.1604.03161

M3 - Article (Academic Journal)

SN - 0002-9890

VL - 124

JO - American Mathematical Monthly

JF - American Mathematical Monthly

IS - 5

ER -

Friendly frogs, stable marriage, and the magic of invariance

Abstract

Keywords

Access to Document

Handle.net

Fingerprint

Prizes

Paul R. Halmos-Lester R. Ford Award

Cite this