Other applied ML AAAI 2023

Six routes, one budget, a million possible plans. Try it by hand.

Constrained Market Share Maximization by Signal-Guided Optimization

Bo Hui¹
Yuchen Fang^{2 *}
Tian Xia¹
Sarp Aykent¹
Wei-Shinn Ku¹

Affiliations at the time of publication¹Auburn University, ²Beijing University of Posts and Telecommunications
^*Footnote as printed: “These authors contributed equally.”

The paper turns an airline’s budget limit into a penalty signal whose weight rises while a flight plan costs too much and falls while it is under budget, so the frequencies on every route can be improved together by gradient steps through a trained market-share predictor.

On the top 1,000 US routes it reports more optimised passengers than both baselines that finished, for all three airlines.

Read the paper (opens in a new tab) Try the idea

Figure 1Illustration

Cost against the budget99 of 100 toy cost units

1 left. Press any route on the map, or a plus, and see what the budget says.

A to Bcost 5 per flight8

B to Ccost 4 per flight2

C to Dcost 4 per flight1

A to Ccost 6 per flight7

B to Dcost 5 per flight1

D to Ecost 3 per flight0

This plan1,038toy passengers

Best within budget1,038toy passengers

Whole-number plans1,000,000ten levels, six routes

A made-up six-route market computed in your browser. Chips show flights and toy share; press a route to add a flight, Shift-click to take one awaytap a route to add a flight, a minus takes one away. Not the paper’s data and not its prediction model; its numbers are not results.

01 The problem

Every extra route multiplies the choices, and no route moves alone.

An airline decides how many flights to run on each route, and the paper asks for the plan with the largest overall market share that stays inside a budget. It names two difficulties: the number of possible plans, and predicting the share a plan would win. It gives two reasons why “traditional combinatorial optimization algorithms [...] cannot be used to solve this problem”: “the market share is nondeterministic, and two routes are usually not independent from each other”.

Figure 2Illustration

Count the plans as the network grows

Routes n in the paper’s formula 6

Highest frequency on a route yours to pick: the paper prints no value 9

One plan

Whole-number plans, (f^max + 1)ⁿ

“if there are n routes and the maximum frequency is f^max, we need to find an optimal solution from (f^max + 1)ⁿ options under constraint. Enumerating and evaluating all solutions on such a complicated network is prohibitive.”
Introduction, page 4330

IllustrationExact whole-number arithmetic on the paper’s formula: a count of plans, not a running time. The paper defines f^max as the observed maximum on each route and prints no value, so the highest frequency here is yours to pick. MeasuredTables 1 to 4, the two search baselines that do not finish at 1,000 routes. Brute Force: “N/A” and “Timeout” at both sizes. Normal Greedy: 47, 34 and 42 seconds at 10 routes, “Timeout” at 1,000.

Figure 3Illustration

Add one flight and watch the other routes

Add one flight to

A to B B to C C to D A to C B to D D to E

In this toy market

Routes feed each other Pretend they are independent

“people may choose to drive from New York to Philadelphia since the distance between these two cities is short [...] there is a flow between these two routes.”
The paper’s own example, page 4333: an itinerary through Los Angeles, New York, Philadelphia and Miami, whose first and last flights are not adjacent

IllustrationThe plan here is an even one, and the feeder bonus between connecting routes is the toy’s own rule. The paper learns route-to-route influence with attention (section 05) and prints no such numbers; these are not results.

How the other approaches handle it. At 1,000 routes Brute Force and Normal Greedy print “Timeout”; the earlier gradient method “solves the problem in only one space”. Open the comparison, in the paper’s words.

Measured, Tables 1 to 4

Approach	What it does	What the paper says limits it	Printed cells
Enumerate Brute Force	“we enumerate all feasible solutions under the observed maximum flight frequency and budget constraints”	“the running time is prohibitively long”	“N/A” and “Timeout” at 10 routes and at 1,000 routes.
Greedy Normal Greedy, Group Greedy	Normal: “compares the marginal improvement in the market share of all strategies and selects the strategy that brings the biggest improvement”. Group: “randomly splits flight routes into multiple groups and then utilizes the normal greedy on these groups”.	Of GroupGreedy (An et al. 2016): “the scalability of this work is far from satisfactory”.	Normal Greedy: the highest cell for Airline1 at 10 routes (31016), 34 to 47 s, “Timeout” at 1,000. Group Greedy: 19 to 20 s at 10 routes, 194 to 282 s at 1,000.
Gradient in one space AGA, Li et al. 2021	“a gradient-based white-box optimization algorithm, which adds a regularization term to the original Lagrange function and solves the new function by a heuristic search method”	It “solves the problem in only one space” and “may be trapped in a stationary point and the global optimal solution is not guaranteed”.	The lowest runtime in all six cells (14 to 15 s, 26 to 27 s); fewer optimised passengers than the paper’s method in all six cells.
Signal-guided this paper	The budget becomes “a penalty signal”; frequencies move on the faster timescale, the signal’s coefficient on the slower one.	The paper states no limitation of its own method. This page adds: what it proves is convergence to a fixed point, not a guaranteed best plan.	The highest cell in five of six passenger cells; the second lowest runtime in all six.

Quotations are from the Introduction, the Baselines paragraph and the results text (pages 4330, 4334 and 4335). “Highest”, “lowest” and the counts are computed by this page from Tables 1 to 4, which section 04 shows whole. The second half of the problem, predicting the share at all, is section 05: the paper calls accurate prediction “demanding”.

02 The idea

Let the budget push back: a penalty that grows while the plan costs too much.

The paper does not enumerate plans. It treats the frequencies as numbers that a gradient can move, and subtracts from the predicted passengers a penalty signal: a coefficient λ times the amount by which the plan’s cost exceeds the budget. Earlier methods, it says, “manually set” that coefficient. Algorithm 1 moves it: up while the plan is over budget, down while it is under, and more slowly than the frequencies move.

Figure 4Illustration

Run the loop, then take the signal away.

Press Run and watch the overspend swing and settle, while the six bars land on the line at λ.
Switch to No signal and run again: nothing pushes back, and every route climbs to its limit.
Switch to Set it by hand and hunt for the λ whose plan just fits the budget. Then let Algorithm 1 find it.

Who sets the signal coefficient λ

No signal Set it by hand Signal-guided (Algorithm 1)

Budget toy cost units 100

Break the two-timescale rule OURS

This broken variant is ours. The paper states the rule (Assumption 1) and does not test breaking it.

The planarrow width is flights; chips show flights and toy share

What this figure does with scripts on

It runs the paper’s Algorithm 1 on the map beside it, starting from this plan. The plan first overshoots the budget, then swings around it and settles on it, while the signal coefficient rises and falls with the overspend. You can take the signal away, in which case every route climbs to its limit, or set the coefficient by hand and hunt for the value whose plan just fits.

The three rules under the figure say what the loop does, and section 03 lists every step of one pass.

What one more unit of cost buys on each routeextra toy passengers per extra toy cost unit, against the line at λ

The run, pass by passpoint to read a pass; click, or focus and use the arrow keys, to show it on the map and the barstap a pass to show it on the map and the bars

Pass

Cost of budget99.0 of 100toy cost units

Signal coefficient λ0.00per toy cost unit

Carried1,038toy passengers

Plans compared on the toy market at the chosen budget
Plan	Flights, A to B through D to E	Cost, toy cost units	Toy passengers
Starting plan
Your best by hand Figure 1
This run, rounded down
Best of all 1,000,000 plans ours

Checking every plan is only possible because the toy is tiny. The paper reports brute force as timing out at 10 routes (Table 2) and never measures the gap to the best plan.

IllustrationA hand-built market with five made-up airports, six routes and fixed rivals. The loop is the paper’s Algorithm 1; the market it runs on is ours. It is not the paper’s trained predictor, not its data, and its numbers are not results.

How to read it. The paper’s Figure 3 plots passengers and cost minus budget for its top airline over 2,000 iterations. Its text gives one value, passengers converging “at about 1.1 million”, and reports that “the cost can be larger than the budget in the optimization process” while the final cost is under the budget. The curves here are the toy’s: one settling run on six routes is an example of the behaviour the paper’s theorem describes, not evidence for it.

How the toy market works. A route wins share as your flights outweigh the rival’s, and gains a bonus when connecting routes have flights. The paper does not use a formula like this: it predicts share with a trained attention network (section 05). Algorithm 1 only needs the predictor’s output and the slope of the objective, which is why a two-line market can stand in for it here.

What the toy had to choose for itself

The paper prints no step sizes. The toy uses shrinking steps that satisfy the three printed conditions of Assumption 1: both keep moving, both shrink fast enough, and the signal’s step shrinks faster than the frequencies’ step.

Algorithm 1, line 7 takes the logarithm of the penalised objective, and the paper does not say what happens when that objective is not positive. The toy guards the logarithm with a floor of its own; the status line says so if the guard ever acts.

“Settled” here means that, to the end of the run, the cost stays within 1 toy cost unit of the budget and no route moves by more than a hundredth of a flight per pass. The paper does not print its convergence test.

The signal is one subtraction

The paper’s Lagrange function is the predicted passengers minus λ times the budget gap, where the gap is the plan’s cost minus the budget. It calls the budget term “a penalty signal” and λ “a coefficient of the penalty signal”. Eq. 3 and 4, page 4332

The overspend moves the coefficient

λ starts at 0. Each pass adds a small step times the budget gap, then projects the result “into the range [0, ∞]”: up while the plan is over budget, down while it is under, never below zero. The running text says only that λ “is increased until the constraint is satisfied”; the fall while under budget is what line 8 computes. Algorithm 1, lines 2 and 8; Eq. 6 and 7; page 4332 moves slowly

Frequencies move on the faster clock

The step sizes “ensure that the frequency update is performed on a faster timescale than that of the coefficient λ of the penalty signal”, and Assumption 1 asks that their ratio tends to zero. Frequencies are relaxed to real numbers, kept between 0 and the route’s maximum, and rounded down at the end. Eq. 5, 6 and 8; page 4332 moves fast

03 One pass of the loop, step by step

Follow one pass: predict, score, push the frequencies, then nudge the signal.

Algorithm 1 is nine lines. This drawing lays one pass of it over two lanes: the frequencies above, which move fast, and the signal’s coefficient below, which moves slowly. The signal reaches the frequencies in exactly one place, the penalised objective; the frequencies reach the signal through the budget gap. The live values come from the run on the bench above, at the pass where its overspend is largest. Every box opens.

Figure 5Illustration

Step through one pass of Algorithm 1

Start from the airline’s given frequencies, with no penalty

Line 1 initialises the search with the airline’s frequencies, which the paper does not define in a sentence; this page reads them as the original frequencies of the paper’s Figure 2(a). They are treated from here on as real numbers, and the signal coefficient starts at zero. Algorithm 1, lines 1 and 2

plan
λ
Ask the frozen predictor what share this plan would win

The frequencies go into the pre-trained model together with the airline’s other features and the competing carriers’ inputs. The model returns the airline’s share on every route. In the paper this is a structure-aware attention network; here it is the toy market. Algorithm 1, line 4; the paper’s Figure 1

plan
toy share
Score the plan twice: passengers won, and budget broken

Passengers: demand times share, summed over routes. Budget gap: cost per flight times flights, summed, minus the budget. Positive means overspent. Algorithm 1, lines 5 and 6

o
cost
c
Let the budget push back: subtract the penalty signal

The penalty signal is the signal coefficient times the budget gap. Subtract it from the passengers. Over budget, the objective is docked; under budget, it gets a small bonus. Eq. 3 and 5

λ × c
L
Fast move: every frequency steps uphill on the penalised objective

Each route’s frequency moves in the direction that raises the logarithm of the penalised objective: up if an extra flight wins more passengers than the signal charges for it, down otherwise. Then it is kept between 0 and the route’s maximum. Algorithm 1, line 7; Eq. 6 and 7 moves fast

Route Gain per flight Charge, λ × cost Move
Slow move: the overspend itself raises the signal

The signal coefficient grows by a small step times the budget gap: up while the plan is overspent, down while it is under, never below zero. Its step shrinks faster than the frequencies’ step. That separation is what “two-timescale” means. Algorithm 1, line 8; Assumption 1 moves slowly

λ
steps
Repeat until nothing moves, then round down

The paper proves that, under Assumption 1 plus the stability and bounded-noise assumptions it cites, the pair converges almost surely to a fixed point, and argues (Lemma 1) that this point respects the budget. It reports that along the way “the cost can be larger than the budget”. The settled frequencies are rounded down to whole flights. Theorem 1 and Lemma 1, pages 4332 and 4333; Convergence, page 4336

Convergence here means a fixed point, which the proof calls “a local saddle point”. The paper does not claim the best possible plan.

settled
rounded

Select any box in the drawing to read what it does. Arrow keys move between boxes.

Predictor Θ

fixed “Pre-trained structure-aware attention model”, the paper’s Figure 1

In: frequencies, features, competitors
Out: share on every route

Trained once with an L1 loss on ten years of data except the last month, then only read: 4 attention layers, hidden size 64. The loop uses it through its output and through the gradient of the objective, nothing else.

In the toy: the two-line market of Figure 4 stands in for it.

The paper does not say how accurate it is for plans far from the data it was tested on.

Frequencies f

moves fast “parametrized frequencies”, pages 4331 to 4332

In: the last pass’s move
Out: one real number per route

The paper treats them “as learnable parameters in a pre-trained neural network model”, moved by gradient, “which is different from existing black-box search methods”. They are relaxed to real numbers during the search.

Toy, this pass:

The paper does not say what the highest frequency on any route is.

Features X

fixed Dataset paragraph, page 4334; Eq. 1; Algorithm 1

In: the last month’s data
Out: five numbers per route

In the experiments: “the ticket price, delay ratio, cancel ratio, divert ratio, and seat availability”. Equation (1) and Algorithm 1 change only the frequencies, so on this page’s reading the features stay fixed while the frequencies are searched.

In the toy: there are none.

The paper does not say whether changing frequencies would in turn change prices or delays.

Competitors

fixed “Competing Carriers' frequencies, ticket prices, and other features”, the paper’s Figure 1

In: the last month’s data
Out: inputs of the predictor

An input of the predictor. Equation (1) optimises only carrier k’s frequencies, so on this page’s reading these inputs stay fixed during the search.

In the toy: one fixed rival strength per route, made up.

The paper does not study competitors reacting to the new plan.

Embed

fixed Eq. 11, page 4333

In: a route’s frequency and features
Out: one hidden vector per route

The frequency is concatenated with the route’s other features and passed through one fully connected layer.

In the toy: no counterpart.

Not reproduced here: the printed dimensions of this layer do not add up, so the page describes it in words.

Structure-aware attention

fixed Eq. 12 to 14, page 4333

In: every route’s vector
Out: a vector that has looked at all routes

Every route gathers from every route. The weight is a learned similarity plus a prior from the route network: routes become nodes, linked when one ends where the next begins, and the prior is a Gaussian kernel of the hop distance. Section 05 opens this up.

In the toy: a feeder bonus from routes one or two connections away.

The paper does not print the value of the kernel’s width (it defines it as the standard deviation of all pairwise shortest path lengths) or any learned weights.

Share ratio

fixed Eq. 16, page 4334

In: predicted passengers of each airline
Out: a share between 0 and 1

The model predicts the airline’s passengers on the route, clips negative values, and divides by the predicted passengers of all airlines on that route.

In the toy: your pull over your pull plus the rival’s.

DB1B “releases 10% of tickets sold in the US every month”; the paper does not say whether its passenger counts are raw counts from that sample or scaled up.

Share m

moves fast m = Θ(f, ·), Eq. 2

In: the predictor’s output
Out: one share per route

“The market share m_r,k is estimated by a pre-trained prediction model.” It changes every pass because the frequencies do.

Toy, this pass:

The paper reports no field test of any predicted share for a new plan.

Passengers o

moves fast o(f), Eq. 4, page 4332

In: share m, demand d
Out: one passenger count

The demand, “the passenger demand for Route r”, times the share, summed over routes. This is the quantity the Metrics paragraph calls “optimized passengers”, reported in Tables 1 and 3.

Toy, this pass:

The paper does not say where the demand comes from.

Two timescales

Eq. 6 and Assumption 1, Eq. 8

Fast: the frequencies, step η₂
Slow: the coefficient λ, step η₁

The step sizes ensure that “the frequency update is performed on a faster timescale than that of the coefficient λ of the penalty signal”. Assumption 1 asks that both steps shrink, not too fast, and that η₁ divided by η₂ tends to zero.

Toy, this pass:

The paper does not print its step sizes or their schedule. The toy’s are ours.

Gradient step

moves fast Eq. 7; Algorithm 1, line 7

In: L, and its slope for each route
Out: a move for each route

The gradient of log(o − λc), “obtained using the log-likelihood trick”. A route moves up when an extra flight wins more than λ times its cost.

Toy, this pass:

The paper does not say what happens when o − λc is not positive. The toy’s guard is its own.

Keep in range

moves fast projection Γ_f, Eq. 6

In: the moved frequencies
Out: frequencies inside their limits

The paper writes: “we project the frequency solution onto a compact and convex set”. Equation 5 bounds each frequency between 0 and the route’s observed maximum; reading the set as that box is ours.

Toy, this pass:

The paper does not write out the set it projects onto.

Settled?

“while not convergence”, Algorithm 1, line 3

No: another pass
Yes: round down

The loop repeats until convergence. The paper’s Figure 3 runs to 2,000 iterations on its horizontal axis.

Toy, this run:

The paper does not print its convergence test or how many iterations its tables used.

Round down

continuous relaxation, page 4332

In: settled real numbers
Out: whole flights

“We relax flight frequencies to real numbers during the maximization and round down the real numbers to integers at the end of the maximization process.”

Toy, this run:

The paper does not report what rounding costs in passengers or leaves unspent.

Penalised objective L

“Lagrange function”, Eq. 3

In: o from above, λ and c from below
Out: one number to climb

o minus λ times c. The paper calls the budget term “a penalty signal” and λ “a coefficient of the penalty signal”. This box is the only place where the signal acts on the frequencies.

Toy, this pass:

The paper gives no ablation of this part: no run with λ fixed or without the logarithm.

Budget gap c

moves fast c(f), Eq. 4; Algorithm 1, line 6

In: frequencies, cost per flight, budget
Out: cost minus budget

The paper’s “cost per flight on Route r for airline k” times the flights, summed, minus “the budget of airline k”. Positive means over budget. It changes as fast as the frequencies do; only the coefficient it feeds moves slowly.

Toy, this pass:

The paper does not give the costs, the budgets, their source or their unit.

Signal coefficient λ

moves slowly “Lagrange multiplier”; Algorithm 1, lines 2 and 8

In: the budget gap
Out: how hard the signal pushes

It starts at 0. “Previous methods manually set the Lagrange multiplier”; here line 8 updates it from the overspend on every pass.

Toy, this pass:

The paper does not name the previous methods it means.

Keep at or above zero

moves slowly projection Γ_λ, Eq. 6

In: the updated λ
Out: λ, never negative

The paper projects “the Lagrange multiplier into the range [0, ∞]”. A negative coefficient would reward overspending.

Toy, this run:

Nothing further is said about this step in the paper.

Live values are read at pass 0

IllustrationDrawn for this page from Algorithm 1 and Equations 1 to 8. It is not the paper’s Figure 1. Live values are the toy’s, from the bench above: not the paper’s data, and its numbers are not results.

How to read it. Our reading of Equations (3) to (7): the budget never blocks a move. It only enters as one subtraction, in the box between the lanes. Solid thick wires carry the frequency update, dashed wires the signal’s; only λ itself moves slowly. Hairlines with a pin are inputs this page reads as fixed, because Equation (1) and Algorithm 1 change only the frequencies and λ.

04 The evidence

At 1,000 routes the paper prints the most optimised passengers for all three airlines. At 10 routes greedy takes one, and a gradient baseline is faster throughout.

The experiments use the DB1B origin and destination survey of the US Bureau of Transportation Statistics: the 1,000 routes with the most passengers, the top 3 airlines, which the paper does not name, and the last month held out. Two problem sizes, four baselines, two measures. Every value in the chart and the four tables below is a printed cell; anything this page computes from them is marked as computed.

Figure 6Measured, Tables 1 to 4

Pick a size and a measure, then read every printed cell

Problem size

Top 10 routes Top 1,000 routes

Measure

Optimised passengers Runtime in seconds

Airlines, as the paper labels them

Ours, the paper’s method (diamond, bold)
baseline
the row the paper labels Ground Truth, continued as a dashed line
no number printed: the paper’s word is shown

computed from the cells Top 1,000 routes, optimised passengers, larger is better. Highest: Ours for all three airlines (1089126, 1074594, 873283). Brute Force and Normal Greedy print “N/A”.

The paper writes that “the maximum market share obtained by our method almost doubles the ground truth”. Computed from Table 3, Ours divided by the row labelled Ground Truth is 2.17, 1.90 and 1.95.

Read these cells with four things in mind

Optimised passengers are demand times the share that the paper’s own predictor expects for a plan. The paper reports no plan that was flown.
The paper does not define its “Ground Truth” row. This page calls it the row the paper labels Ground Truth and says no more.
The paper gives no hardware, no timeout threshold, no seeds and no error bars.
Group Greedy uses 2 groups at 10 routes and 20 groups at 1,000 routes.

The four tables as printed

Table 1, page 4335: “Optimization results for the top-10 routes.” Optimised passengers, larger is better.
Methods	Airline1	Airline2	Airline3
Ground Truth	25851	19553	19543
Brute Force	N/A	N/A	N/A
Normal Greedy	31016	20577	22890
Group Greedy	25936	20251	21474
AGA	27025	20609	20658
Ours	30885	22292	25727

Table 2, page 4335: “Runtime in seconds for the top-10 routes.” Smaller is better.
Methods	Airline1	Airline2	Airline3
Brute Force	Timeout	Timeout	Timeout
Normal Greedy	47	34	42
Group Greedy	20	19	19
AGA	14	15	15
Ours	18	18	18

Table 3, page 4335: “Optimization results for the top-1,000 routes.” Optimised passengers, larger is better.
Methods	Airline1	Airline2	Airline3
Ground Truth	501919	566868	448126
Brute Force	N/A	N/A	N/A
Normal Greedy	N/A	N/A	N/A
Group Greedy	929345	978315	746235
AGA	896992	961166	636136
Ours	1089126	1074594	873283

Table 4, page 4335: “Runtime in seconds for the top-1,000 routes.” Smaller is better.
Methods	Airline1	Airline2	Airline3
Brute Force	Timeout	Timeout	Timeout
Normal Greedy	Timeout	Timeout	Timeout
Group Greedy	282	237	194
AGA	27	26	26
Ours	37	36	37

Cells are as printed, without thousands separators. Tables 1 to 4 print no bold. The paper marks direction with an arrow on each column: up for passengers, down for runtime. “N/A” and “Timeout” are the paper’s words; of brute force it says “the running time is prohibitively long”. The tinted row and its tag are this page’s, not the paper’s.

05 The predictor, taken apart

Take away the attention or the network prior and every printed error gets worse.

The loop is only as good as the model it climbs. The paper’s predictor turns the airport map inside out: routes become nodes, linked when one route ends where the next begins. Attention layers then let every route gather from every other route, weighted by a learned similarity plus a prior that fades with hop distance in that network. Table 5 compares it with five other predictors and with two cut-down versions of itself.

Figure 7Measured, Table 5

Pick a metric and compare the eight printed rows

Problem size

10 routes 1,000 routes

Metric

CC R² MAE RMSE

Zoom to the printed range

computed from the cells RMSE, 10 routes, smaller is better: Model4 (Ours) prints the lowest value, 0.0345. The lowest of the five other predictors is Model3 (Li et al. 2021) at 0.0430.

The paper underlines Model3 as second best. Its two cut-down variants, No Att and No Prior, print better values than Model3 in all eight columns (computed from the table), so the underline is second best among the six full models. Every row is worse at 1,000 routes than at 10, which the paper attributes to “more complicated scenarios in 1,000 routes”.

Table 5, page 4336: “Market share prediction performance comparison. Bold: Best; underline: Second best.” CC and R² larger is better, MAE and RMSE smaller is better. No unit is printed; market share is a ratio (Eq. 16).
Methods	10 routes				1,000 routes
Methods	CC	R²	MAE	RMSE	CC	R²	MAE	RMSE
XGBoost	0.9583	0.8644	0.0534	0.0758	0.9204	0.7769	0.0677	0.1358
RandomForest	0.9578	0.9124	0.0466	0.0643	0.9224	0.8743	0.0537	0.1332
Model1 (Suzuki 2000a)	0.9625	0.9231	0.0410	0.0579	0.9231	0.8757	0.0523	0.1309
Model2 (Wei and Hansen 2005)	0.9507	0.9086	0.0478	0.0665	0.9246	0.8763	0.0510	0.1294
Model3 (Li et al. 2021)	0.9809	0.9608	0.0268	0.0430	0.9443	0.8864	0.0463	0.1220
Model4 (Ours)	0.9881	0.9748	0.0220	0.0345	0.9613	0.9107	0.0360	0.1133
Model4 (No Att)	0.9814	0.9637	0.0255	0.0393	0.9463	0.8896	0.0446	0.1201
Model4 (No Prior)	0.9831	0.9667	0.0247	0.0386	0.9503	0.9023	0.0374	0.1148

Four decimals, bold and underline exactly as printed: the paper sets all eight cells of Model4 (Ours) in bold and all eight cells of Model3 underlined, and rules off the three Model4 rows. CC is the correlation coefficient, R² the coefficient of determination, MAE the mean absolute error, RMSE the root mean square error.

Figure 8IllustrationMeasured, Table 5

Switch off a part of the predictor and see what it can no longer use

can be flown next: “the end airport of route r is the beginning airport of route i”
learned similarity, to every route

Printed cells for

10 routes 1,000 routes

CC, larger is better

R², larger is better

MAE, smaller is better

RMSE, smaller is better

“No Att” removes the attention coefficient, so the variant “only considers the direct connection (Equation (14))”. “No Prior” removes the prior from Equation (13), and the paper reports that this “will lead to performance degradation”.

computed from the cells Against the full model, No Att is worse in all eight columns and No Prior is worse in all eight. No Att also prints worse values than No Prior in all eight columns. The paper does not compare the two variants with each other and prints no seeds or error bars, so this page draws no conclusion about which part matters more.

The ablation covers the predictor only; the paper reports none of the optimiser.

IllustrationWhich information each variant can use, drawn on the toy’s six routes. Link strengths are not computed here: in the paper they are learned (Eq. 13), and its prior depends on the real route network (Eq. 14), which the paper does not print. Hop counts here follow the direction of travel, as the paper prints its adjacency. The paper does not say whether its shortest paths follow that direction, so “no path” is this page’s reading. The four tiles are printed cells of Table 5.

What goes in

Each route’s frequency is joined with five other features, “the ticket price, delay ratio, cancel ratio, divert ratio, and seat availability”, and embedded by one fully connected layer (Eq. 11).

What the prior is

The prior is strongest for routes one hop away and fades with hop distance through a Gaussian kernel whose width is the standard deviation of all pairwise shortest path lengths in that network (Eq. 14). The paper does not print its value.

What comes out

The model predicts each airline’s passengers on a route and takes the airline’s part of the total as its share (Eq. 16). It is trained with an L1 loss on ten years of data except the last month, which is the test month: 4 attention layers, hidden size 64.

The takeaway

Instead of enumerating plans, the paper lets a penalty signal hold the budget.

Frequencies climb the predicted passengers quickly, a penalty coefficient follows slowly, and the paper proves that the pair converges almost surely to a fixed point, under its step-size assumption plus stability and bounded-noise assumptions it cites; its Lemma 1 argues that this point fits the budget.

What the paper contributes

The budget enters as a penalty signal whose coefficient is updated by its own gradient, on a slower timescale than the frequencies, with a convergence proof. The predictor it climbs uses the route network as a prior for attention.

What the tables show

The most optimised passengers for all three airlines at 1,000 routes and for two of three at 10 routes. A gradient baseline is faster in every runtime cell. The predictor prints the best cell in all eight columns of Table 5.

Not claimed

No guarantee of the best plan, only of a fixed point. No plan was flown, competitors never react, and there are no seeds, no error bars and no ablation of the optimiser.

06 Office hours

The night shift answers.

Written by Tian's agent while Tian slept and Pepper supervised. Pepper accepts no liability either.

Each answer says where in the paper it comes from, so you can check the agent's work.

Pepper, the tabby cat, supervising: fast asleep on his blanket on the sofa, beside the laptop.

Are the “optimized passengers” real passengers?

No. The objective is passenger demand times market share summed over routes, and the share “is estimated by a pre-trained prediction model”. The numbers in Tables 1 and 3 are what that model expects for a plan; the paper reports no plan that was flown. Its predictor is tested only on the observed last month (Table 5), while the optimised plans differ from the original frequencies: the paper’s Figure 2 shows frequencies “distributed more evenly” after optimisation, and at 1,000 routes the optimised count is about twice the row the paper labels Ground Truth (2.17, 1.90 and 1.95 times, computed from Table 3), a row the paper does not define. The paper does not test how accurate the predictor is for plans that far from the data it was tested on, and does not model competitors reacting.

Source: Problem Definition and Metrics, pages 4331 and 4334; Tables 3 and 5; the paper’s Figure 2

Does it find the best plan?

The paper does not claim that. Theorem 1 gives almost sure convergence to a fixed point under a step-size assumption plus stability and bounded-noise assumptions that it cites and does not check; the proof calls the limit “a local saddle point”, and Lemma 1 argues that it satisfies the budget. The paper criticises the earlier gradient method because it “may be trapped in a stationary point and the global optimal solution is not guaranteed”, and offers no such guarantee of its own. Brute Force is “N/A” at both sizes, so the distance to the best plan is never measured. On the top 10 routes Normal Greedy prints more passengers for Airline1: 31016 against 30885. In this page’s toy the rounded-down plan can be checked against every plan; that check is the toy’s and says nothing about the paper’s scale.

Source: Theorem 1 and Lemma 1, pages 4332 and 4333; Introduction, page 4330; Tables 1 and 3

Is it faster?

Faster than greedy search, slower than the other gradient method. Top 10 routes: 18 s for each airline against 34 to 47 s for Normal Greedy, 19 to 20 s for Group Greedy and 14 to 15 s for AGA. Top 1,000 routes: 36 to 37 s against 194 to 282 s for Group Greedy and 26 to 27 s for AGA; Normal Greedy and Brute Force time out. The paper’s text compares runtime only with Normal Greedy. It gives no hardware, no timeout threshold, no repeated runs and no complexity for its own method.

Source: Tables 2 and 4, page 4335; Baselines and Configuration, page 4334

What exactly is new compared with the earlier gradient method, and is that part tested on its own?

In the paper’s words, the earlier method (Li et al. 2021, the AGA baseline) “solves the problem in only one space” and adds a regularisation term to derive the multiplier, whereas this paper treats the budget as a penalty signal whose coefficient is updated on a slower timescale than the frequencies, with a convergence proof. The evidence is end to end: more optimised passengers than AGA in all six cells. There is no ablation of the optimiser: no run with λ fixed, with one timescale, or without the logarithm in the gradient, and the paper does not say whether every optimiser was scored with the same predictor. The Introduction also describes an actor and a TD-learning critic; the method section and Algorithm 1 contain neither.

Source: Introduction, pages 4330 and 4331; Baselines, page 4334; Tables 1 and 3; Algorithm 1

What was not tested?

One country’s domestic data, three unnamed airlines, one test month. Only two constraints, the budget and a per-route maximum; nothing on fleet, crews or slots. Competitors are inputs that never react. The effect of rounding the frequencies down is not reported. Step sizes, the convergence test and the iteration count are not printed. There are no seeds, error bars or significance tests, and the paper has no limitations section; these limits are read from what the experiments cover.

Source: Dataset and Configuration, page 4334; Problem Definition, page 4331; Algorithm 1

Constrained Market Share Maximization by Signal-Guided Optimization

Every extra route multiplies the choices, and no route moves alone.

Let the budget push back: a penalty that grows while the plan costs too much.

The signal is one subtraction

The overspend moves the coefficient

Frequencies move on the faster clock

Follow one pass: predict, score, push the frequencies, then nudge the signal.

Start from the airline’s given frequencies, with no penalty

Ask the frozen predictor what share this plan would win

Score the plan twice: passengers won, and budget broken

Let the budget push back: subtract the penalty signal

Fast move: every frequency steps uphill on the penalised objective

Slow move: the overspend itself raises the signal

Repeat until nothing moves, then round down

Predictor Θ

Frequencies f

Features X

Competitors

Embed

Structure-aware attention

Share ratio

Share m

Passengers o

Two timescales

Gradient step

Keep in range

Settled?

Round down

Penalised objective L

Budget gap c

Signal coefficient λ

Keep at or above zero

At 1,000 routes the paper prints the most optimised passengers for all three airlines. At 10 routes greedy takes one, and a gradient baseline is faster throughout.

The four tables as printed

Take away the attention or the network prior and every printed error gets worse.

What goes in

What the prior is

What comes out

Instead of enumerating plans, the paper lets a penalty signal hold the budget.

What the paper contributes

What the tables show

Not claimed

The night shift answers.