This reminds me of "Mr. & Mrs. Everywhere" from the book "Stands on Zanzibar" written by John Brunner in 1968.