Leta1,…,am,c1,…,ckbe independent random points in Rnthat are identically distributed spherically symmetrical in Rnand letX≔{x∈Rn|aTix⩽1,i=1,…,m} be the associated random polyhedron form⩾n⩾2. We consider multiple objective linear programming problems maxx∈XcT1x, maxx∈XcT2x,…,maxx∈XcTkxwith 1⩽k⩽n. For distributions with algebraically decreasing tail in the unit ball, we investigate the asymptotic expected number of vertices in the efficient frontier ofXwith respect toc1,…,ckfor fixedn,kandm→∞. This expected number of efficient vertices is the most significant indicator for the average-case complexity of the multiple objective linear programming problem.