Skip to main content
added 138 characters in body
Source Link
alex
  • 976
  • 4
  • 14
  • 26

$k$ people play the following game: person $i$ independently picks a subset $S_i$ of $\{ 1,2,\ldots,n \}$ according to some distribution $p$ on the $2^n$ subsets; each person uses the same distribution $p$. If some $S_i$ is contained in $\cup_{j \neq i} S_j$, they all lose; else, they all win. What distribution $p$ maximizes the probability of winning?

I am actually only interested in the case where $n/k$ is an integer, in which case I would conjecture that the optimal distribution is for each person to pick a random subset with $n/k$ elements. I can prove this only for $k=2$, in which case it follows straightforwardly from Sperner's theorem.

Edit: JBL points out in the comments that its also easy to confirm the $n=k$ case of the conjecture in the previous paragraph.

$k$ people play the following game: person $i$ independently picks a subset $S_i$ of $\{ 1,2,\ldots,n \}$ according to some distribution $p$ on the $2^n$ subsets; each person uses the same distribution $p$. If some $S_i$ is contained in $\cup_{j \neq i} S_j$, they all lose; else, they all win. What distribution $p$ maximizes the probability of winning?

I am actually only interested in the case where $n/k$ is an integer, in which case I would conjecture that the optimal distribution is for each person to pick a random subset with $n/k$ elements. I can prove this only for $k=2$, in which case it follows straightforwardly from Sperner's theorem.

$k$ people play the following game: person $i$ independently picks a subset $S_i$ of $\{ 1,2,\ldots,n \}$ according to some distribution $p$ on the $2^n$ subsets; each person uses the same distribution $p$. If some $S_i$ is contained in $\cup_{j \neq i} S_j$, they all lose; else, they all win. What distribution $p$ maximizes the probability of winning?

I am actually only interested in the case where $n/k$ is an integer, in which case I would conjecture that the optimal distribution is for each person to pick a random subset with $n/k$ elements. I can prove this only for $k=2$, in which case it follows straightforwardly from Sperner's theorem.

Edit: JBL points out in the comments that its also easy to confirm the $n=k$ case of the conjecture in the previous paragraph.

upper case title
Link
Charles Matthews
  • 12.6k
  • 35
  • 64

a A probability question related to extremal combinatorics

added 32 characters in body
Source Link
alex
  • 976
  • 4
  • 14
  • 26

$k$ people play the following game: person $i$ independently picks a random subset $S_i$ of $\{ 1,2,\ldots,n \}$ according to some distribution which is$p$ on the $2^n$ subsets; each person uses the same for all personsdistribution $p$. If some $S_i$ is contained in $\cup_{j \neq i} S_j$, they all lose; else, they all win. What distribution $p$ maximizes the probability of winning?

I am actually only interested in the case where $n/k$ is an integer, in which case I would conjecture that the optimal distribution is for each person to pick a random subset with $n/k$ elements. I can prove this only for $k=2$, in which case it follows straightforwardly from Sperner's theorem.

$k$ people play the following game: person $i$ independently picks a random subset $S_i$ of $\{ 1,2,\ldots,n \}$ according to some distribution which is the same for all persons. If some $S_i$ is contained in $\cup_{j \neq i} S_j$, they all lose; else, they all win. What distribution maximizes the probability of winning?

I am actually only interested in the case where $n/k$ is an integer, in which case I would conjecture that the optimal distribution is for each person to pick a random subset with $n/k$ elements. I can prove this only for $k=2$, in which case it follows straightforwardly from Sperner's theorem.

$k$ people play the following game: person $i$ independently picks a subset $S_i$ of $\{ 1,2,\ldots,n \}$ according to some distribution $p$ on the $2^n$ subsets; each person uses the same distribution $p$. If some $S_i$ is contained in $\cup_{j \neq i} S_j$, they all lose; else, they all win. What distribution $p$ maximizes the probability of winning?

I am actually only interested in the case where $n/k$ is an integer, in which case I would conjecture that the optimal distribution is for each person to pick a random subset with $n/k$ elements. I can prove this only for $k=2$, in which case it follows straightforwardly from Sperner's theorem.

added 14 characters in body
Source Link
alex
  • 976
  • 4
  • 14
  • 26
Loading
Source Link
alex
  • 976
  • 4
  • 14
  • 26
Loading