Go Back  FlyerTalk Forums > Miles&Points > Airlines and Mileage Programs > Delta Air Lines | SkyMiles
Reload this Page >

Class Action Federal Lawsuit Aginst Delta RE: Best Fares Available

Old Sep 9, 14, 6:54 am
FlyerTalk Forums Expert How-Tos and Guides
Last edit by: mbwmbw
All files are available for download at: http://mbw.name/Files/FlyerTalk/Delta_Class_Action/

Furthermore, each document has been linked to the download location.

For a full download of the complaint and attachments click here.

Date Filed # Docket Text
08/07/2014 1 COMPLAINT with Jury Demand; against Delta Airlines, Inc. by Darla Opper. ( Filing Fee PAID $400 receipt number 0757-1939172) (Attachments: # 1 Exhibit A, # 2 Exhibit B, # 3 Exhibit C, # 4 Exhibit D, # 5 Exhibit E, # 6 Exhibit F, # 7 Exhibit G, # 8 Civil Cover Sheet, # 9 Summons)(Shah, James)
08/07/2014 NOTICE Regarding assignment of this matter to Chief Judge William C Griesbach ;Consent/refusal forms for Magistrate Judge Duffin to be filed within 21 days;the consent/refusal form is available on our web site ;pursuant to Civil Local Rule 7.1 a disclosure statement is to be filed upon the first filing of any paper and should be filed now if not already filed (jcl)
08/07/2014 2 DISCLOSURE Statement by Darla Opper. (Shah, James)
08/08/2014 Summons Issued as to Delta Airlines, Inc. (mec)
08/20/2014 3 Refusal to Jurisdiction by US Magistrate Judge by Darla Opper. (Shah, James)
08/25/2014 4 SUMMONS Returned Executed by Darla Opper. Delta Airlines Inc served on 8/14/2014, answer due 9/4/2014. (Shah, James)
08/29/2014 5 Unopposed MOTION for Extension of Time by Delta Airlines Inc. (Smith, Renee)
08/29/2014 6 DISCLOSURE Statement by Delta Airlines Inc. (Smith, Renee)
09/02/2014 TEXT ONLY ORDER GRANTING 5 Unopposed MOTION for Extension of Time filed by Delta Airlines Inc., signed by Chief Judge William C Griesbach on 09/02/2014. The deadline for filing its responsive pleading is extended 14 days, until September 18, 2014. (cc: all counsel)(Griesbach, William)
09/18/2014 7 MOTION to Dismiss by Delta Airlines Inc. (Balassa, Gabor)
09/18/2014 8 BRIEF in Support filed by Delta Airlines Inc re 7 MOTION to Dismiss . (Attachments: # 1 Exhibit A - Best Fare Guarantee, # 2 Exhibit B - Best Fare Guarantee Claim Form, # 3 Exhibit C - Tabatabai v. West Coast Life Ins. Co, # 4 Exhibit D - Marine Travelift, Inc. v. Marine Lift Sys., Inc, # 5 Exhibit E - Tilstra v. Bou-Matic, LLC, # 6 Exhibit F - PNC Bank, N.A. v. Van Hoornaar, # 7 Exhibit G - NIIJII Entmt, LLC v. Troha) (Balassa, Gabor)
10/03/2014 9 Unopposed MOTION for Extension of Time by Darla Opper. (Shah, James)

Print Wikipost

Class Action Federal Lawsuit Aginst Delta RE: Best Fares Available

Old Sep 9, 14, 8:54 pm
  #91  
 
Join Date: Jun 2004
Location: ATL
Programs: Delta PlM, 1M
Posts: 6,272
Originally Posted by sethb View Post
I'm assuming input data is all published fares. So if the airline publishes a fare AAA-CCC (which routes through BBB), that's considered a single step for the algorithm. So there would be three fares to look at: AAA-BBB, BBB-CCC, and AAA-CCC. When finding the cheapest AAA-CCC involving two or fewer hops, it would look at all three (and also AAA-XXX and XXX-CCC, etc.)
Yes, but the issue I am saying is that the published AAA-CCC fares need to be validated across all possible routes (not just 2 legs). That in itself will be a shortest path calc. And same for AAA-BBB fares ...

The answer is 25387776. Question was, "how many Angels can dance on the head of a pin"? :-)
exwannabe is offline  
Old Sep 9, 14, 8:58 pm
  #92  
FlyerTalk Evangelist
 
Join Date: Jun 2004
Location: MSP
Programs: DL PM, MM, NR; HH Diamond, Bonvoy Gold, Hyatt Explorist, IHG Spire, others
Posts: 11,977
There are some published fares, including direct flights and connections. Those are all input to the program. It is then an easy algorithm to find all least-cost routings between cities.
sethb is offline  
Old Sep 9, 14, 9:28 pm
  #93  
FlyerTalk Evangelist
 
Join Date: Sep 2007
Location: BOS
Programs: DL DM 2MM, Marriott LT Titanium, Hertz PC
Posts: 14,174
To the plaintiff: Thanks for ruining EF access for the rest of us who weren't out to make some point trying to stick it to DL.
rylan is offline  
Old Sep 9, 14, 9:47 pm
  #94  
 
Join Date: Dec 2007
Posts: 1,688
Originally Posted by sethb View Post
There are some published fares, including direct flights and connections. Those are all input to the program. It is then an easy algorithm to find all least-cost routings between cities.
I'll admit it...I was wrong. ...The problem is actually NP-hard, not NP-complete. But everything else I said is still true. If you have an algorithm to solve an NP-hard problem in polynomial time, you have proven that P=NP and that wins you the $1 million. (An NP-complete problem can be verified in polynomial time, but that's not the case here.)

The problem with your logic is that you're still assuming that the price of the ticket only increases as fare components are added. This is not true. You cannot reliably price a ticket until the entire ticket is known, or even make claims such as "the ticket will be at least $X." For example, adding a fare component can change which location is considered the destination vs. the stop over. Adding a fare component can change whether or not the ticket qualifies as round/circle trip. Adding a fare component can exceed a minimum stay requirement or fulfill a Saturday stay requirement.

See this article: http://www.msri.org/people/members/s...s/airfares.pdf

Obviously, if you bound the problem by saying "I only want to see non-stop fares" or "I won't leave the US to connect on an otherwise domestic itinerary" or "my itinerary must be complete within X days" then you can solve the problem in a reasonable period of time. But, that doesn't mean its not still NP-hard. It just means you've reduced the problem to a degree where all of the possibilities can be checked.
DaDaDan is offline  
Old Sep 9, 14, 11:03 pm
  #95  
FlyerTalk Evangelist
 
Join Date: Jul 2003
Posts: 20,218
Originally Posted by sethb View Post
There are some published fares, including direct flights and connections. Those are all input to the program. It is then an easy algorithm to find all least-cost routings between cities.
A "published" fare, does not mean an "available" fare. Ultimately, you need to query the GDS systems to see what's actually available in the fare buckets. You can cache the data, but how stale do you let the cached inventory to get before you refresh it? What if some of the published fares you are searching haven't had their bucket availability instantiated in your cache yet?
xliioper is offline  
Old Sep 10, 14, 1:40 am
  #96  
 
Join Date: Oct 2012
Location: NYC
Programs: AA DULtArer
Posts: 5,522
Originally Posted by exwannabe View Post
No. The "shortest path" problem is with some pre-assigned value to any leg. It does not depend on distance, or any assumptions of an additive metric.

Seth is still technically wrong though. The said logic does work to search for fare breaks, but not solve the entire married fare problem.

Example. A-B-C or A-C (only routes). Shortest path algs would be able to easily search A-B(stop)B-C vs A-C. But the A-C fare itself could route via B with different metrics I would guess that a simple solution of the married fare problem would actually be quadratic in routes.

This is still a useless conversation. In practice the problem is trivial. If DL starts flying 1000000000 routes a day, then let's come back here.
this doesn't address this

once I've found a way to get from AAA to BBB for $222, any route that's already over $222 doesn't need to be extended, because it already lost.
at all, but you are right that this thread is basically useless 1s and 0s
LaserSailor is offline  
Old Sep 10, 14, 5:40 am
  #97  
 
Join Date: Dec 2007
Posts: 1,688
Originally Posted by LaserSailor View Post
this doesn't address this

once I've found a way to get from AAA to BBB for $222, any route that's already over $222 doesn't need to be extended, because it already lost.
at all, but you are right that this thread is basically useless 1s and 0s
As I noted above, the problem is that extending a route can lower its price.

And delta doesn't need to fly 1000000000 routes a day to cause this issue. Even with Delta's current route structure, and limiting yourself just to DL-marketed flights, there are already sufficiently many ways to get from A to B that you cannot practically check them all.
DaDaDan is offline  
Old Sep 10, 14, 7:08 am
  #98  
 
Join Date: Nov 2010
Location: BDL/HPN/JFK/FLL
Programs: DL Diamond Ham Sandwich
Posts: 1,051
Originally Posted by DaDaDan View Post
As I noted above, the problem is that extending a route can lower its price.

And delta doesn't need to fly 1000000000 routes a day to cause this issue. Even with Delta's current route structure, and limiting yourself just to DL-marketed flights, there are already sufficiently many ways to get from A to B that you cannot practically check them all.
No DaDaDan extending broken fare routes can not lower the price. This problem requires solving the "what is the lowest AAA-ZZZ fare available" and then looking for combinations of fares that get you from AAA to BBB without going over that price.

So:
(1) Lowest available "married segment" fare to destination
(2) Find fares (married or individual flight) from origin airport that are lower than fare found in (1)
(3) Find fares (married or individual flight) from connecting airport found in (2) which combine to be less than the currently best fare or combination of fares
(4) For each fare or combinations of fares found in (3) iterate (3) until at destination

The reality is that you could stop at a couple connections for practical purposes...
mother- is offline  
Old Sep 10, 14, 8:29 am
  #99  
 
Join Date: Dec 2007
Posts: 1,688
Originally Posted by mother- View Post
No DaDaDan extending broken fare routes can not lower the price. This problem requires solving the "what is the lowest AAA-ZZZ fare available" and then looking for combinations of fares that get you from AAA to BBB without going over that price.

So:
(1) Lowest available "married segment" fare to destination
(2) Find fares (married or individual flight) from origin airport that are lower than fare found in (1)
(3) Find fares (married or individual flight) from connecting airport found in (2) which combine to be less than the currently best fare or combination of fares
(4) For each fare or combinations of fares found in (3) iterate (3) until at destination

The reality is that you could stop at a couple connections for practical purposes...
Taking a step back, all the claims about this actually being very simple are contradicted by the folks in the industry who have actually had to design these algorithms, as discussed in the article I posted above.

The reality of course is that you can generate algorithms that are very good. They definitely find very good fares. And they probably find the best fare. But, they can't be certain of it.


Separately, looking at your algorithm, I don't think it is comprehensive. If the problem is to fly AAA to BBB, there are also round trip fares from AAA to NNN that allow an open jaw where the "return" can be to BBB. If you price AAA-NNN alone, as suggested in your Step 2, the price could be a high OW fare, at which point your algorithm will stop exploring this option. Only by adding the segment NNN-BBB, do you find that it qualifies as a RT with OJ.

This is at least one way where searching fares progressively fails. At least one other one is creating an itinerary that, by adding a leg, qualifies for RTW pricing.
DaDaDan is offline  
Old Sep 10, 14, 9:11 am
  #100  
 
Join Date: Nov 2010
Location: BDL/HPN/JFK/FLL
Programs: DL Diamond Ham Sandwich
Posts: 1,051
Originally Posted by DaDaDan View Post
Separately, looking at your algorithm, I don't think it is comprehensive. If the problem is to fly AAA to BBB, there are also round trip fares from AAA to NNN that allow an open jaw where the "return" can be to BBB. If you price AAA-NNN alone, as suggested in your Step 2, the price could be a high OW fare, at which point your algorithm will stop exploring this option. Only by adding the segment NNN-BBB, do you find that it qualifies as a RT with OJ.

This is at least one way where searching fares progressively fails. At least one other one is creating an itinerary that, by adding a leg, qualifies for RTW pricing.
(With the caveat that I'm really only thinking about domestic flights and not all the crazy extra fees and complexity for Intl)
I think that once again you're not talking about broken fares but fares from origin to destination, and that type of fare (married segments if connecting) is exactly the logic that would be in step 1 of what I outlined, and is what Delta.com already does.

And
mother- is offline  
Old Sep 10, 14, 9:19 am
  #101  
 
Join Date: Dec 2007
Posts: 1,688
Originally Posted by mother- View Post
(With the caveat that I'm really only thinking about domestic flights and not all the crazy extra fees and complexity for Intl)
I think that once again you're not talking about broken fares but fares from origin to destination, and that type of fare (married segments if connecting) is exactly the logic that would be in step 1 of what I outlined, and is what Delta.com already does.

And
The linked article notes a case where there was a massive last minute fare sale on flights to London from the East Coast that allowed open jaw returns to major US cities. E.g., NYC-LHR-BOS was allowed. In this scenario, it would be very possible that a flight NYC-LHR-BOS (qualifying as RT with OJ) is cheaper than a last minute OW fare NYC-BOS or even NYC-BOS. The algorithm above would not find this because the cheaper fare is filed as a RT fare NYC-LHR, but the algorithm only looks for:

1. NYC-BOS fares
2. Fares to other airports that are lower (just NYC-LHR is an expensive OW fare and not cheaper)


(Btw, I know you excluded international fares. I used LHR just because it is referenced in the article. The same facts could apply domestically as well. There aren't as many cases in practice since most RT are just 2xOW domestically these days. But, that hasn't always been the case. And there's nothing stopping an occasional violation of this norm.)

Last edited by DaDaDan; Sep 10, 14 at 9:30 am Reason: Spelling
DaDaDan is offline  
Old Sep 10, 14, 10:37 am
  #102  
FlyerTalk Evangelist
 
Join Date: Jun 2004
Location: MSP
Programs: DL PM, MM, NR; HH Diamond, Bonvoy Gold, Hyatt Explorist, IHG Spire, others
Posts: 11,977
Originally Posted by LBJ View Post
A "published" fare, does not mean an "available" fare. Ultimately, you need to query the GDS systems to see what's actually available in the fare buckets. You can cache the data, but how stale do you let the cached inventory to get before you refresh it? What if some of the published fares you are searching haven't had their bucket availability instantiated in your cache yet?
Any algorithm assumes its input data exists and is correct.

Here's a least-cost all-routes algorithm:

There are N cities. Create an NxN matrix; the entries are the airline's published fare from AAA to BBB, with 0 on the diagonal (it's free to say in the same place). Call that M1 (cheapest route with 1 or fewer fares).

Do a "matrix multiply" using min over plus (standard matrix multiply is plus over times) M1 x M1. Call the result M2, it's the cheapest route with 2 or fewer fares.

Do that again, M2 x M2. Call the result M4, it's the cheapest result with 4 or fewer fares.

Continue until Mn, where n>=N. That takes ceiling(log2(N)) steps. The result is the cheapest routes from any city to any other. Total time is clearly polynomial in N.

For those looking at broken round-trips, hidden cities, etc., those technically aren't allowed by the airlines. But if they are to be allowed in this problem, it's easy to include them. When the airline quotes a fare from AAA to BBB, check the routing, and include that as the fare from AAA to any CCC along the route if lower than already found.

The real-world problem is a bit harder, because we need to consider connections, minimum time, etc. However, that's still feasible: let each node be an airport at a time, where the times are arrival+MCT for each flight. Waiting at an airport is free. It's still polynomial in the number of flights.
sethb is offline  
Old Sep 10, 14, 5:42 pm
  #103  
 
Join Date: Dec 2007
Posts: 1,688
Originally Posted by sethb View Post
Here's a least-cost all-routes algorithm:

There are N cities. Create an NxN matrix; the entries are the airline's published fare from AAA to BBB, with 0 on the diagonal (it's free to say in the same place). Call that M1 (cheapest route with 1 or fewer fares).

Do a "matrix multiply" using min over plus (standard matrix multiply is plus over times) M1 x M1. Call the result M2, it's the cheapest route with 2 or fewer fares.

Do that again, M2 x M2. Call the result M4, it's the cheapest result with 4 or fewer fares.

Continue until Mn, where n>=N. That takes ceiling(log2(N)) steps. The result is the cheapest routes from any city to any other. Total time is clearly polynomial in N.

For those looking at broken round-trips, hidden cities, etc., those technically aren't allowed by the airlines. But if they are to be allowed in this problem, it's easy to include them. When the airline quotes a fare from AAA to BBB, check the routing, and include that as the fare from AAA to any CCC along the route if lower than already found.

The real-world problem is a bit harder, because we need to consider connections, minimum time, etc. However, that's still feasible: let each node be an airport at a time, where the times are arrival+MCT for each flight. Waiting at an airport is free. It's still polynomial in the number of flights.
So, I'll start by reiterating the fact that your assertion contradicts the published accounts of folks who have actually built fare engines. Now, maybe they were wrong, and you're right. But it's been published by mathematical research groups. So, I tend to believe them.


More specifically, you've made several assumptions here that are not true in practice:

1. There is only one published fare between two city pairs (or at least the cheapest fare is trivial to observe).

This allows you to reduce the problem to the shortest distance problem where we know in advance the distance between any two locations.

This is not true in our case. There are many published fares for any route, and the ability to use one may depend on a number of conditions, including conditions dependent on other fare components. E.g., it must be part of a round trip, requires Saturday stay, etc. Each fare must be checked and all conditions validated against the attributes of the entire ticket.

You also have to determine availability on any particular flight segment.

This means you need to determine the time complexity not just in number of segments (as you have done) but also in number of fare rules filed and in flights offered. In order to determine the minimum price between two points, you need to check every fare rule and every flight's availability. As connections are added, the universe of relevant fare rules and feasible flights whose availability must be checked grows.

Even ignoring the availability issue, it grows very quickly.

[Edited to add: So apparently in FT land, the symbol for exponentiation is ^. Please interpret accordingly!]

Assume:
F = number of fares filed per city pair
C = number of cities
n = number of segments

I want to fly AAA-BBB.

For a non-stop flight (n=1), there are F fare rules to check.

For exactly one connection, AAA-ZZZ-BBB, there are F fare rules to check for AAA-ZZZ and F fares to check for ZZZ-BBB. So, for one connection city (n=2), there are F^2 fares to check times C-2 cities (you cannot connect in AAA or BBB).

For exactly two connections, AAA-YYY-ZZZ-BBB, you check F^3 fares times (C-2)^2 connection points. This assumes that you allow connections such as AAA-YYY-AAA-BBB, which in theory is necessary. For example, you could be flying on a RT fare AAA-YYY with an OJ return ending at BBB, and the segment from your "destination" YYY to BBB requires a connection at AAA. This could price lower than the OW fare AAA-BBB.

Ok, for arbitrarily many F, C, and n, you have:

summation(1,N) of [F(C-2)^(n-1)]^n

This definitely grows faster than polynomial time.

As an example:

F will vary by city pair, but let's say it is 15 fare rules per city pair
C is something like 1500 commercial airports in the world
Let's assume N is 5 segments.

This yields 2.5 x 10^69 fares to calculate. If you assume you can check 10 fares per second, that's 7.8 x 10^60 years.

And it gets worse...

2. Any stay in a city is just like any other.

This assumption again reduces the complexity, but does not hold in practice. Your stay in any city can be termed a connection, a stopover, or a destination. Which category it falls into depends on the timing of the flights into and out of the city, the remaining segments on the ticket, the fare rule you're using, and in some cases your option.


3. Taxes, fees, carrier-imposed surcharges, etc. are irrelevant.

These can only be calculated knowing the entire ticket and all of its attributes, including small things like point of sale, plating carrier, etc., some of which you can manipulate to get a lower price.

Last edited by DaDaDan; Sep 10, 14 at 5:55 pm
DaDaDan is offline  
Old Sep 10, 14, 6:24 pm
  #104  
Original Poster
 
Join Date: Feb 2012
Location: Los Angeles, CA
Programs: DL DM, UA 1K, AA EXP, US G, SPG P, HH D, MR G, NEXUS/GE, DL AMEX Reserve
Posts: 2,035
I never knew we had so many mathematical and computer science wizs on here .
mbwmbw is offline  
Old Sep 10, 14, 6:43 pm
  #105  
 
Join Date: Dec 2007
Posts: 1,688
Originally Posted by mbwmbw View Post
I never knew we had so many mathematical and computer science wizs on here .
I think I got my equation wrong actually, but it's still in the "impossible" range. So wizz-1 for me.

Should be:

Summation(1,N) of [F^n (c-2)^(n-1)]

Still takes 1.2 x 10^10 years to calculate.
DaDaDan is offline  

Thread Tools
Search this Thread