Wikipedia:Reference desk/Archives/Computing/2021 January 17

Welcome to the Wikipedia Computing Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

January 17

Can a first place team be eliminated?

In the baseball elimination problem, it is possible for a team to be eliminated despite the fact that there are teams with worse records that have not been eliminated. This table, taken from Programming Assignment 3: Baseball Elimination, is an example:

Division standings

team	wins	loss	left	Atl	Phi	NY	Mon
Atlanta	83	71	8	-	1	6	1
Philadelphia	80	79	3	1	-	0	2
New York	78	78	6	6	0	-	0
Montreal	77	82	3	1	2	0	-

"Montreal is mathematically eliminated since it can finish with at most 80 wins and Atlanta already has 83 wins. This is the simplest reason for elimination. However, there can be more complicated reasons. For example, Philadelphia is also mathematically eliminated. It can finish the season with as many as 83 wins, which appears to be enough to tie Atlanta. But this would require Atlanta to lose all of its remaining games, including the 6 against New York, in which case New York would finish with 84 wins. We note that New York is not yet mathematically eliminated despite the fact that it has fewer wins than Philadelphia."

With all that being said, could the same logic hold for a team in first place? Can a first place team be eliminated due to scheduling constraints in the division? It would appear that the answer is yes, but I'm curious if there is another factor here that I am missing. The method for determining which team is in first is probably relevant here. You can either consider which team has the highest win percentage, or which team has the most total wins. I have a half baked intuition that the answer to my question is no, if we use the former method, but I really don't know how to approach this problem. --Puzzledvegetable^{Is it teatime already?} 18:33, 17 January 2021 (UTC)

I don't know about baseball, but it's possible in European football competitions. Suppose the top-ranked team A has played all its matches already, but two teams B and C who still have to face each other both have one point less than A and at least one of them has a better goal difference than A. It's guaranteed that either B or C will beat A. If the match of B vs. C leads to a winner, that winner gains 3 points, enough to beat A by 2 points, and if B vs. C leads to a draw, both get 1 point and the team with the best goal difference beats A. PiusImpavidus (talk) 16:56, 18 January 2021 (UTC)

Many European football leagues use head-to-head points and head-to-head goal difference as the first tie-breakers, and not overall goal difference. If one of B and C leads over A in head-to-head then A isn't necessarily eliminated. A draw between B and C gives a three-way tie where all matches between the three teams will be counted. Team A may be ahead there, but you can of course make scenarios where that will not be possible. If all teams have the same number of matches left then the leader cannot be eliminated already.PrimeHunter (talk) 20:37, 18 January 2021 (UTC)

This isn't strictly a question about the rules of baseball or the leagues in which individual teams are ranked; it's a question of mathematics. This is purely a question of applied mathematics in the form of directed graph flow theory. The answer might not be obvious - in fact, the explanatory page linked earlier splits the problem into a "trivial" and a "non-trivial" case; but the short answer here is "yes, it is possible." It is possible to construct a graph such that the first place team would be "mathematically eliminated" (as defined in the problem-set-up).

We can do this by starting with a directed-graph representation of a losing team; then we deform that graph representation by adding or subtracting other games (vertices) that do not change the characteristic, until we find a configuration in which the originally-losing-team is in first place.

I assert (without proof) that you will find nearly trivial cases if you explore smaller graphs - e.g. the first or second game in a league that only plays five or ten games in the season. It's more mental effort if you're looking at the 65th-game-in-the-season in an 80-game-season (even though the problem is mathematically no more or less tractable - and after all, isn't that why we use a computer for this task?)

I think the follow-on question, which becomes much less theoretical, is whether that scenario realistically represents a plausible game schedule for any real-world baseball league, and I think the answer to that is "probably not," for most of the cases that sprung to my mind.

If you want to foray out of the world of theoretical computer science, and into applied graph theory, we might further decorate graph nodes to afford ourselves additional constraints on the schedule (e.g. we might replace integer g with an object, and impart some constraint satisfaction on that object as we traverse the graph). And if we wanted to return back from applied to theoretical math, we might attempt to reduce the decoration back to a single integer by way of a coordinate rotation in high dimensional space.

Isn't graph theory so much more fun when we leave it to proper mathematicians, instead of letting it become overrun by social scientists masquerading as computer scientists?

Nimur (talk) 18:17, 18 January 2021 (UTC)

I am not seeing much pseudo-code here. How is this a computing and not mathematics problem? Elizium23 (talk) 19:57, 18 January 2021 (UTC)

If there is any difference between problems of mathematics, and problems of computing, it's chiefly a historical accident, says Prof. Dr. Dijkstra. Nimur (talk) 20:31, 18 January 2021 (UTC)

Nimur, it is not a problem of mathematics for me to install, configure and run BIND9. Mathematics problems such as this can be solved with computers, but general-purpose computers can do much more outside that realm. I'm just asking because we have a dedicated Reference Desk for mathematics questions, and the watchers there may be well-equipped to answer this question. I am not well-equipped, and I have worked in IT for 30 years and hold 3 certifications. Elizium23 (talk) 20:39, 18 January 2021 (UTC)