Consider the context of solving a multi-objective simulation optimization problem with one or more continuous objective functions to global optimality on a compact feasible set. For a simple algorithm that consists of selecting a finite set of feasible points using a space-filling design, expending the same number of simulation replications at each point to estimate the objective values, and returning the discretized estimated efficient and Pareto sets, we (i) introduce a mathematically tractable performance indicator for assessing the optimality gap of the discretized estimated efficient set, (ii) derive finite-time probabilistic upper bounds on the optimality gap, and (iii) determine how to trade off the number of feasible points with the number of simulation replications per point to ensure the optimality gap converges to zero in probability at a fast rate. Thus, we identify both an upper bound on the convergence rate for simple algorithms and a lower bound on the convergence rate for other algorithms that exploit structure. In addition, if the optimality gap is measured under the infinity norm, then the required total simulation budget grows slightly faster than logarithmically in the number of objectives. We demonstrate our results through numerical examples having one, two, or three objectives.