  We introduce the multiset partition algebra $\mathcal{MP}_k(\xi)$ over
$F[\xi]$, where $F$ is a field of characteristic $0$ and $k$ is a positive
integer. When $\xi$ is specialized to a positive integer $n$, we establish the
Schur-Weyl duality between the actions of resulting algebra $\mathcal{MP}_k(n)$
and the symmetric group $S_n$ on $\text{Sym}^k(F^n)$. The construction of
$\mathcal{MP}_k(\xi)$ generalizes to any vector $\lambda$ of non-negative
integers yielding the algebra $\mathcal{MP}_{\lambda}(\xi)$ over $F[\xi]$ so
that there is Schur-Weyl duality between the actions of
$\mathcal{MP}_{\lambda}(n)$ and $S_n$ on $\text{Sym}^{\lambda}(F^n)$. We find
the generating function for the multiplicity of each irreducible representation
of $S_n$ in $\text{Sym}^\lambda(F^n)$, as $\lambda$ varies, in terms of a
plethysm of Schur functions. As consequences we obtain an indexing set for the
irreducible representations of $\mathcal{MP}_k(n)$, and the generating function
for the multiplicity of an irreducible polynomial representation of $GL_n(F)$
when restricted to $S_n$. We show that $\mathcal{MP}_\lambda(\xi)$ embeds
inside the partition algebra $\mathcal{P}_{|\lambda|}(\xi)$. Using this
embedding, over $F$, we prove that $\mathcal{MP}_{\lambda}(\xi)$ is a cellular
algebra, and $\mathcal{MP}_{\lambda}(\xi)$ is semisimple when $\xi$ is not an
integer or $\xi$ is an integer such that $\xi\geq 2|\lambda|-1$. We give an
insertion algorithm based on Robinson-Schensted-Knuth correspondence realizing
the decomposition of $\mathcal{MP}_{\lambda}(n)$ as
$\mathcal{MP}_{\lambda}(n)\times \mathcal{MP}_{\lambda}(n)$-module.
