Re: [iccrg] Pareto frontier

That's a very useful answer, thanks a lot Keith!

Cheers,
Michael

> On 8 Jan 2020, at 16:40, Keith Winstein <keithw@cs.stanford.edu> wrote:
> 
> Hi Michael,
> 
> Formally speaking, given a set of feasible allocations (each the result of some strategy), the Pareto frontier is the subset of allocations that aren't strictly dominated by any other allocation. It's fashionable to show this by drawing the convex hull through the frontier -- see, e.g., the plots in the Wikipedia article on "Pareto efficiency." But the frontier is really the set of points, not the line drawn to connect them.
> 
> It's okay that the set considered is finite -- the Pareto frontier does not have to be taken only after evaluating the full (typically infinite) set of all possible strategies. (Of course it's important to compare with the right prior work or alternative strategies, but that's just true any time you want to have a comparative evaluation -- it doesn't come from the definition of Pareto frontier.) And in congestion control, it's not like we usually have access to a tight upper bound. If you look at, e.g., Figure 7 of https://cs.nyu.edu/~anirudh/contest-ccr.pdf (3,000 different congestion-control schemes run across the same time-varying emulated network path), there's a substantial gap between the apparent frontier-of-schemes-tested and the best known upper bound ("Omniscient"). Maybe there exists some scheme that comes very close to "Omniscient" and would remove most other points from the frontier, or maybe there isn't -- one can't know this just by plotting a frontier of a finite set of evaluated strategies.
> 
> Also, maybe the schemes on the frontier will still be on the frontier when evaluated over a different emulated network, or over a real-world Internet path, or maybe they won't -- one won't necessarily know this either. (Our Pantheon paper, https://pantheon.stanford.edu/static/pantheon/documents/pantheon-paper.pdf, tries to show how challenging it can be to match the real-world results of a variety of congestion-control schemes in an emulator.)
> 
> I assume when somebody says their scheme sits "outside the Pareto frontier", they mean that it strictly dominated some of the schemes that *had been* on the Pareto frontier before it was added to the set of available schemes. One does have to be cautious about how far you interpret these snapshot results -- some of my own results for schemes that strictly dominated other schemes have not held up when you run the experiment with different network paths, buffering regimes, workloads, figures of merit (dimensions of the "allocation"), etc. I talked about this a bit here: https://youtu.be/pzPy6VUuY-k?t=2474 .
> 
> But these problems belong, I think, more to the realm of computer networking and the hardness of reasoning about how to make resource allocation decisions under uncertainty in a decentralized manner, than in the concept of Pareto efficiency.
> 
> Sincerely,
> Keith
> 
> On Wed, Jan 8, 2020 at 5:53 AM Michael Welzl <michawe@ifi.uio.no> wrote:
> Hi,
> 
> Recently, it has become common in some congestion control papers, when showing plots with various congestion control mechanisms and a "better" arrow, to also draw a line through the presumably best mechanisms and call it a Pareto frontier.
> 
> I find it a bit of a stretch to just call this line a Pareto frontier - it MAY be one, but that's not proven, so I'm not sure this is a correct thing to state, strictly speaking. Anyway, I've recently seen cases where mechanism XY beats the others, as shown in the diagram, where it "sits comfortably outside the Pareto frontier".
> 
> Now, either I totally misunderstand something, or I never got the idea of Pareto efficiency, OR such a statement is utter nonsense.
> (because being better than the mechanisms on the Pareto frontier simply means that this line is indeed *NOT* the Pareto frontier, and it was wrong to call it that in the first place).
> 
> Can someone enlighten me please?
> 
> Cheers,
> Michael
> 
> _______________________________________________
> iccrg mailing list
> iccrg@irtf.org
> https://www.irtf.org/mailman/listinfo/iccrg