Another way to say "Lobster is often eaten with steak." is "Steak is often served as a complement to lobster."