PaperlayerView exact revision on arXiv

Source-linked AI summary

Differentiable Combinatorial Auction Design: Optimizing Revenue-Welfare-Fairness Frontiers With Graph Attention Networks

Mai Pham, Vikrant Vaze, Peter Chin

arXiv:2610.31977v1cs.GT

TL;DR

Public-resource auctions must accommodate bundle interdependence and balance revenue, welfare, and fairness, challenges that traditional mechanisms and standard architectures do not jointly address. The paper learns constraint-aware combinatorial mechanisms and approximates fractional allocations with feasible discrete lotteries; reported revenue exceeds VCG in synthetic and airport-slot settings, though exact implementation and incentive guarantees have limits.

  • Problem

    Traditional mechanisms and standard neural architectures do not jointly handle multi-objective combinatorial auctions with complex feasibility constraints.

    Source: §1 · pp. 1–2, §1.1.3 · p. 2

  • Method

    The paper combines constraint-aware neural auction architectures with a Matching Pursuit-inspired decomposition to approximate implementable lotteries over feasible schedules.

    Source: §1 · p. 2, §4.5 · p. 9

  • Results

    Expected revenue gains reach 73.5% in synthetic settings and 180% in the airport-slot case study compared with VCG, with low empirical regret.

    Source: §7 · p. 18

  • Takeaways & Limitations

    The framework lets regulators compare revenue–welfare–fairness trade-offs in airport-slot allocation rather than prescribing a single policy rule.

    Source: §7 · p. 18

    Fractional feasibility does not guarantee exact lottery implementability, and incentive properties do not automatically transfer through decomposition and conditional pricing.

    Source: §4.5 · pp. 9–10

Abstract

from arXiv · show

Designing optimal auctions for allocating public infrastructure-such as airport slots and energy resources-is challenging due to interdependent resources and complex side-constraints. While the Vickrey-Clarke-Groves (VCG) auction guarantees maximum welfare, it cannot maximize revenue or accommodate the multi-objective trade-offs inherent in public infrastructure systems. We propose a differentiable, constraint-aware framework for combinatorial auction design that enables end-to-end learning of fractionally feasible, approximately strategy-proof mechanisms. Our primary contribution is a combinatorial constraint enforcement technique that ensures fractional feasibility by construction, bypassing the need for penalty-based approximations. We introduce CAGraph, a novel graph-based architecture designed to capture dependencies between items and bidders, alongside CANet and CAFormer as deep learning baselines, for combinatorial settings. We also provide a Matching Pursuit-inspired decomposition that maps fractional allocations to feasible discrete allocations and empirically evaluates the resulting discretization gap. In synthetic benchmarks and an airport slot-divestiture case study, respectively, the learned mechanisms achieve up to 73.5% and 180% higher expected revenue than VCG, under small empirical regret. Finally, we visualize the Pareto frontiers for revenue, welfare, and fairness, providing regulators with a decision-support tool to design infrastructure auctions that balance profitability, efficiency and equity.

1 Introduction

Combinatorial public-resource auctions must handle bundle values and balance revenue, welfare, and fairness, yet traditional mechanisms and standard neural networks do not address these demands together. The paper proposes data-driven, constraint-aware auction design and evaluates its trade-offs in synthetic settings and an airport-slot case study.

1.1.1 The Allocative Challenge

  • Traditional mechanisms target individual objectives, while multi-objective combinatorial design with side constraints is analytically and computationally difficult.Bundle complementarities make allocation challenging, and winner determination is NP-hard.Source: §1.1.1 · p. 2

1.1.2 Application to Airport Slot Allocation

  • Airport slot allocation combines incumbent advantages under grandfather rights with regulatory goals for competition, efficiency, revenue, and fairness.The paper uses airport slot divestiture as an application domain for comparing policy trade-offs.Source: §1.1.2 · p. 2, §1.1.3 · pp. 2–3

1.1.3 Methodological Gap

  • Standard neural architectures do not encode combinatorial structure, motivating problem-specific models that respect feasibility constraints.The paper frames fairness and other side constraints as part of the methodological gap.Source: §1.1.3 · p. 2

1.2 Contributions

  • The framework learns constraint-aware combinatorial mechanisms and traces revenue, welfare, and fairness trade-offs using deep neural networks.Contributions include CANet, CAFormer, CAGraph, and a Matching Pursuit-inspired approximation for implementing fractional allocations.Source: §1.2 · p. 3
  • In the Washington National Airport divestiture setting, conditional full-assignment implementation reaches mean realized revenue of $536.3k, a 284.2% increase relative to VCG.This is the specific case-study result reported among the paper’s contributions.Source: §1.2 · p. 3

2 Related Literature

Prior work provides tools for single-objective auctions, differentiable mechanism learning, and combinatorial allocation, but combining these in constrained, multi-objective settings remains difficult. This paper positions its framework as a data-driven way to trace revenue–welfare–fairness frontiers and compare airport-allocation policies.

2.1 Multi-Objective Auction Theory

  • Classical auction theory offers mechanisms for welfare, revenue, or fairness, but multi-objective approaches generally do not extend to combinatorial constraints.The paper emphasizes empirical frontier tracing rather than an analytical characterization of one optimal mechanism.Source: §2.1 · pp. 3–4

2.2 Airport Resource Allocation

  • Airport slot policies must balance allocative efficiency, public revenue, and competitive equity, while existing divestiture and auction approaches face implementation complexity and equity concerns.The framework compares policies rather than prescribing one regulatory rule.Source: §2.2 · p. 4

2.3 Deep Neural Networks for Mechanism Design

  • Differentiable mechanism learning and graph networks offer relevant tools, but bundle valuations and overlapping constraints require architectures that enforce feasibility.Standard feed-forward and transformer models may produce impractical fractional assignments; overlapping combinatorial constraints may not admit exact lottery decomposition.Source: §2.3 · pp. 4–5

3 Problem Statement and Model

The paper models a combinatorial auction with private bundle valuations, fractional allocation probabilities, and payments, then optimizes design objectives subject to feasibility and mechanism requirements. It includes welfare, revenue, and utility fairness, while distinguishing fractional feasibility from exact discrete implementation.

Auction setting and utilities

  • An auction consists of allocation and payment rules; fractional allocation entries represent probabilities that bidders receive bundles, with deterministic allocations as the binary case.Bidders report values for bundles, and their expected utility is allocated value minus payment.Source: §3 · p. 5

Valuations

  • Each bidder has a private valuation for every nonempty bundle, drawn from a bidder-specific distribution that may be symmetric or asymmetric.The bundle valuation space contains 2^m − 1 nonempty bundles for m items.Source: §3 · p. 5

Incentives and scope

  • The learned fractional mechanism is audited for incentive properties, but those properties do not automatically carry through discrete resolution and conditional pricing.The paper says post-resolution regret must be audited separately rather than claiming it is established.Source: §3 · p. 5

Feasibility

  • Combinatorial feasibility limits each item to at most one allocation and each bidder to at most one bundle; binary constraints are relaxed for differentiable learning.The fractional feasible region does not necessarily guarantee exact lottery implementability.Source: §3 · p. 6

Multi-objective formulation

  • The mechanism evaluates design objectives on truthful reports, with welfare based on fractional allocations and revenue or combined objectives available to the auctioneer.Training and evaluation set reports equal to valuations, b = v.Source: §3 · p. 6

Fairness

  • Fairness is treated as a soft training target using the Jain index of bidder utilities, where J = 1 denotes equal utility.The equality-style penalty targets a selected Jain-index value.Source: §3 · p. 6

4 Solution approach

The solution approach converts neural allocation scores into fractionally feasible assignments, trains multiple architectures for auction objectives, and uses a discrete-resolution procedure when fractional allocations are not exactly implementable. It reports explicit limits on what the fractional feasibility and incentive guarantees establish.

4.1 Constraint Enforcement via Factorization

  • The factorized constraint layer maps unnormalized scores into fractional allocations satisfying item-wise and bidder-wise feasibility.It constructs bundle availability from item-level probabilities and combines it with an agent-bundle assignment factor.Source: §4.1 · p. 7

4.2.1 CANet Architecture

  • CANet uses a feed-forward MLP with separate allocation and payment heads, routing allocation logits through the constraint factorization layer.The payment head outputs fractional payments through a sigmoid activation.Source: §4.2.1 · p. 8

4.2.2 CAFormer Architecture

  • CAFormer processes exchangeable item and agent embedding streams with self- and cross-attention before producing agent-bundle logits.The final output is processed by an invariant attention head so results are independent of bidder ordering.Source: §4.2.2 · p. 8

4.3 Proposed New Architecture: CAGraph

  • CAGraph represents each bidder-bundle pair as a node and connects pairs that share a bidder or overlapping bundles, enabling learned reasoning about conflicts.Graph attention encodes conflicts, while the separate constraint factorization—not attention alone—enforces feasibility.Source: §4.3 · p. 8

4.4 Training Procedure

  • All three architectures use a common training procedure with an economic objective and adaptive penalties for requirements such as approximate DSIC and selected fairness targets.The revenue–welfare parameter traces an empirical frontier, whose allocation changes are characterized empirically rather than by a closed-form solution.Source: §4.4 · pp. 8–9

4.5 Implementability and Discrete Decomposition

  • Because fractional allocations may not be lotteries over feasible schedules, the paper uses a Matching Pursuit-inspired decomposition to construct an implementable lottery.When allocations lie outside the convex hull of feasible deterministic schedules, this is an approximation; the implementation residual bounds worst-case welfare change by vmax∥ET∥1.Source: §4.5 · pp. 9–10
  • The greedy decomposition is a tractable sparse approximation, not a guaranteed sparsest representation, and its residual measures approximation error.Universal exact lottery implementability is not claimed for non-bihierarchical environments; incentives of the fractional mechanism also do not automatically transfer through decomposition and conditional pricing.Source: §4.5 · p. 10

5 Computational Results: Synthetic Benchmarks

Synthetic benchmarks test the learned architectures in additive and combinatorial auction settings. CAGraph delivers higher revenue in the reported combinatorial results, including a 73.5% gain over VCG in the 2 × 5 asymmetric case.

Experimental Setup

  • Models trained for 100,000 iterations on additive and combinatorial valuations, including symmetric and asymmetric settings with complementarity terms.The additive setting uses item values drawn from U[0, 1]; combinatorial values include a complementarity term drawn from U[−1, 1].Source: §5 · p. 10

Revenue and Welfare Analysis

  • In additive settings, CANet and CAFormer match standard auction baselines, while CAGraph reaches 1.111 revenue in the 2 × 2 setting.The expected efficient-welfare benchmark is approximately 1.33, and measured regret is approximately 0.008.Source: §5 · p. 10, Table 1 · p. 11

Combinatorial Advantages

  • 12.123 revenue in the 2 × 5 asymmetric case is 73.5% above VCG (6.987) and 6.4% above CAFormer.The table reports that CAGraph consistently outperforms the other methods in revenue.Source: Table 2 · p. 11, §5 · p. 11

6 Practical Applications: Airport Slot Allocation

The airport-slot case study evaluates a tunable combinatorial auction against VCG and RSD across revenue, welfare, and fairness objectives. Its results show trade-offs among those objectives, with discrete implementation and sensitivity analyses qualifying the ex-ante findings.

6 Practical Applications: Airport Slot Allocation; 6.1.1 Experimental Setup; 6.1.2 Statistical Properties of Valuations

  • The DCA slot-divestiture case models four carriers and candidate slot times, deriving bundle valuations from airline data and finding right-skew, subadditivity, and incumbent–entrant asymmetry.The valuation summary also compares four-slot bundles with disjoint two-slot bundles and examines marginal-value consistency across time blocks.Source: §6 · pp. 11–12, §6.1.1 · p. 12, §6.1.2 · p. 12

6.2 Benchmark Mechanisms

  • CAGraph is presented as a tunable alternative to VCG and RSD, using revenue weight λ and a separate soft Jain-index target to navigate economic and fairness objectives.VCG maximizes welfare but may concentrate allocations, while RSD provides procedural symmetry but ignores monetary valuations.Source: §6.2 · p. 13

6.3 Empirical Results I: Economic Efficiency and Revenue

  • At λ = 0.5, revenue reaches $376k—approximately 171% above VCG—while retaining 77% of VCG welfare; Figure 3 presents the revenue–welfare frontier.At λ = 1, revenue reaches $391k, approximately 181% above VCG, while welfare falls by 49%; fairness also declines as λ approaches 1.Source: §6.3 · pp. 13–14, Figure 3 · p. 14, Table 3 · p. 14

6.4 Empirical Results II: Equity and Efficiency; 6.5 Empirical Results III: Revenue–Fairness Trade-offs

  • Under welfare maximization, target J = 0.5 reduces Gini from 0.75 to 0.54 with only a 4% welfare loss, illustrating a tunable welfare–fairness trade-off.Higher targets further improve dispersion but bring more pronounced welfare losses near J = 0.875.Source: §6.4 · p. 14, Table 4 · p. 15

6.5 Empirical Results III: Revenue–Fairness Trade-offs

  • Under revenue maximization, raising target J from 0.25 to 0.875 lowers revenue by 4.3% ($396k to $379k) while reducing Gini from 0.75 to 0.17.The authors characterize the revenue-screening pattern as empirical, not exact Myerson ironing in this combinatorial approximately incentive-compatible setting.Source: §6.5 · pp. 14–15, Figure 4 · p. 15, Table 5 · p. 16

6.6 Incentive Compatibility Audit

  • The configured adversarial misreport search finds small empirical regret relative to revenue gains, but this audit does not establish low regret after discrete resolution and conditional pricing.Regret is an empirical local-best-response estimate from the validation search.Source: §6.6 · p. 15, Table 6 · p. 17

6.7 Empirical Results IV: Ex-Post Outcomes and Practical Implementation

  • Full assignment yields mean ex-post revenue of $536,328, a 284.2% increase over VCG, and a $411,399 25th percentile above VCG’s $158,656 75th percentile.The standard lottery approximately preserves the learned mechanism’s ex-ante expected revenue on average, but its 25th percentile is zero; full assignment conditions on a nonempty feasible assignment and is a separate implementation variant.Source: Figure 6 · p. 16, §6.7 · pp. 16–17, Table 7 · p. 17

6.8 Structural Robustness and Scalability; 6.9 Policy Implications and Practical Feasibility

  • Sensitivity tests find time-of-day preferences more consequential than operating costs, while a forward pass takes under 15ms; policy tuning uses λ or Jain target J and structural changes require validation or retraining.The reported sensitivity checkpoint uses J = 0.25 and differs from the J = 0.875 mechanism in Figure 5(d); a hierarchical decomposition for larger systems is proposed but unevaluated.Source: §6.8 · p. 17, Figure 7 · p. 18, §6.9 · p. 18

7 Conclusion

The conclusion presents a framework for navigating revenue–welfare–fairness trade-offs in combinatorial auctions and reports revenue gains over VCG with low empirical regret. The accompanying training procedure uses VCG imitation, adversarial misreport search, and a fractional-outcome payment rule.

7 Conclusion

  • Up to 73.5% higher expected revenue in synthetic settings and 180% in the airport-slot case study than VCG, with low empirical regret.CAGraph models bundle conflicts across the revenue–welfare–fairness frontier; a Matching Pursuit-inspired decomposition approximates feasible discrete schedules and quantifies the remaining implementation gap.Source: §7 · p. 18

A Notation Summary

  • The notation summary distinguishes fractional allocations, deterministic schedules, lottery weights, and the implementation residual.The residual is the difference between the fractional allocation and the expected allocation of the implemented lottery.Source: A Notation Summary · p. 22

C Training Procedure and Loss Function

  • The mechanism jointly uses an allocation network and payment network, mapping reported valuations and context to allocations and payments.Training balances efficiency, low regret, and fairness of realized utilities.Source: C Training Procedure and Loss Function · p. 22

C.1 Warm-Start via VCG Imitation

  • Training is initialized by imitating the VCG outcome.The supplied passage introduces the warm-start but does not provide its computation details.Source: §C.1 · p. 23

C.2 Adversarial Misreport Search

  • Adversarial misreports are optimized by gradient ascent, and regret is estimated from the largest utility improvement found across candidate reports.This is an empirical local-best-response estimate; additional starts or optimization steps can reveal a larger profitable deviation.Source: §C.2 · p. 23, §C.3 · p. 23

C.4 Payment Parameterization and Truthful IR

  • At a truthful report, the fractional mechanism satisfies pointwise truthful-profile individual rationality before the lottery is realized.Incentive and IR claims for the separate post-resolution conditional payment rule must be assessed after resolution.Source: §C.4 · p. 24

C.5 Fairness Metrics

The training procedure combines an economic objective with soft penalties and adaptive weights for regret and fairness. The text cautions that high revenue and target levels do not establish general truthfulness or hard feasibility guarantees.

C.5 Fairness Metrics

  • Fairness training uses a soft target penalty for a selected Jain index; the other monitored fairness indices are evaluation diagnostics.The regularizer is equality-style, not a hard lower-bound constraint.Source: §C.5 · p. 24

C.6 Economic Objective

  • The economic objective mixes revenue and welfare using λ, while the log-transformed loss rescales the objective and gradients without removing non-convexity.The revenue-range term, when enabled, is a regularizer rather than a hard constraint, and no fixed revenue-to-welfare percentages are assumed.Source: §C.6 · p. 24, §C.7 · p. 25

C.7 Optional Revenue-Range Regularization

  • The revenue-range bounds are configuration parameters expressed in normalized or monetary units, and their penalty is soft rather than a feasibility constraint.The section does not assume fixed revenue-to-welfare percentages.Source: §C.7 · p. 25

C.8 Adaptive Weights for Regret and Fairness

  • Adaptive multipliers weight regret and fairness penalties in the training loss, with updates described using an Adam-style rule.The complete loss adds the economic, regret, fairness, and optional revenue-bound terms.Source: §C.8 · p. 25, §C.9 · p. 25

C.10 Interpretation of High-Revenue Solutions

  • Revenue close to allocated welfare is an empirical outcome, not a consequence of a general VCG payment-minimality theorem.Revenue, regret, and individual rationality should be interpreted together on held-out data; the finite-sample penalties and approximate inner search do not establish DSIC from revenue alone.Source: §C.10 · p. 25
  • Reported target levels are optimization targets checked empirically, not feasibility guarantees, because training uses soft penalties rather than a hard constrained program.The optional revenue-range term is also soft.Source: §C.10 · p. 26

D Proof of Theorem 1 and Implementation Details

The constraint-aware layer constructs fractional allocations subject to item and bidder feasibility constraints. A separate revenue–welfare mixture parameter controls the empirical trade-off between revenue extraction and allocative efficiency.

D Proof of Theorem 1 and Implementation Details

  • The layer's bundle-availability and bundle-to-agent assignment matrices are constructed to satisfy both fractional feasibility constraints.Masked per-item normalization bounds total probability across bundles containing each item, while the assignment matrix is doubly sub-stochastic.Source: D Proof of Theorem 1 and… · p. 26

E Revenue–Welfare Weighting

  • The mixture parameter λ controls the empirical trade-off between revenue extraction and allocative efficiency.The single-item virtual-value result is used only as an analogy; the trained combinatorial mechanism is not claimed to have a closed-form virtual-value representation or exact Myerson ironing.Source: E Revenue–Welfare Weighting · p. 27

F.1 Implementability Limitation

Fractional feasibility does not generally guarantee that an allocation can be implemented as a lottery over feasible deterministic schedules. The paper describes a greedy extraction and normalization procedure whose residuals quantify approximation and implementation error.

F.1 Implementability Limitation

  • When the constraint structure is not a bihierarchy, feasible fractional allocations may not be expressible as lotteries over deterministic feasible schedules.Airport-slot bundle overlaps can create conflict cycles, so satisfying fractional constraints alone does not imply lottery implementability.Source: §F.1 · p. 27

F.2 Proof of Proposition 5

  • The extraction residual does not increase at an iteration and decreases strictly when the extraction weight is positive and the selected schedule has nonempty support.Source: §F.2 · p. 28

F.3 Economic Discretization Gap

  • The normalized lottery's implementation residual measures error between the fractional allocation and its expected implemented allocation; the bound scales with this residual and the valuation upper bound.The raw extraction residual measures remaining nonnegative mass and coincides with the implementation residual only when the normalizer cT equals 1.Source: §F.3 · p. 28

G.1 Airport Valuation Construction with Gurobi

The airport case study grounds the auction framework in a small, realistic slot-divestiture setting and compares learned mechanisms with existing allocation approaches. Fractional allocations are converted into a lottery over feasible schedules using a greedy approximation, whose airport audit finds errors at numerical precision.

G.1 Airport Valuation Construction with Gurobi

  • The DCA valuation artifact contains 100,000 profiles for four carriers and seven bundles, with 80,000 training profiles and 20,000 held-out profiles.Valuations are generated by solving a binary flight-to-slot assignment model for each carrier and bundle.Source: §G.1 · p. 29

G.1.1 Slot Allocation at U.S. Coordinated Airports: Practice and Precedent

  • U.S. slot reallocations include lotteries and rare divestiture auctions, providing precedents for evaluating small-scale combinatorial allocation.The 2011 Delta–US Airways divestiture auction sold predefined slot bundles to eligible carriers.Source: §G.1.1 · p. 30, §G.1.3 · p. 31

G.1.2 Comparison to Lottery and Serial Dictatorship Mechanisms

  • The learned auction represents bundle preferences and optimizes revenue, welfare, and a soft fairness target, unlike equal-share lotteries or item-by-item serial dictatorship.Lottery shares ignore valuations and yield no revenue; individual picks in serial dictatorship need not represent preferences over complete bundles.Source: §G.1.2 · p. 31

G.1.3 The 2011 Slot Auction

  • The 2011 Delta–US Airways exchange required divestiture of 16 LGA slot pairs and 8 DCA slot pairs, which were sold through a sealed-bid, one-round auction.Eligibility was restricted to carriers holding less than 5% of slots at the respective airport.Source: §G.1.3 · p. 31

H Greedy Discrete Approximation and Proportional Pricing

  • Fractional feasibility does not guarantee an exact lottery over deterministic schedules when overlapping bundles create non-bihierarchical constraints.The procedure is therefore a greedy discrete approximation, not a guaranteed exact convex decomposition.Source: H Greedy Discrete Approximation and… · p. 32

H.1 Greedy Discrete Approximation

  • The Matching Pursuit-inspired procedure repeatedly selects the feasible schedule most aligned with the residual and extracts the largest weight that keeps the residual nonnegative.Residual mass remains unless extraction exhausts it; the resulting weights need not themselves form a probability distribution.Source: §H.1 · pp. 32–33

H.2 Empirical Decomposition Audit

  • On 20,000 held-out airport profiles, normalization changed neither extracted weights nor expected allocation, and maximum absolute welfare difference was 1.34 × 10^-8 dollars.The audit establishes numerical implementability for the evaluated allocations, not universal implementability or post-resolution incentive properties.Source: §H.2 · p. 33, Table 11 · p. 33

H.3 Proportional Ex-Post Pricing

The implementation converts expected payment targets into conditional charges so that bidders pay only when allocated a bundle. An optional full-assignment variant removes null schedules but changes expected outcomes and must be evaluated separately.

H.3 Proportional Ex-Post Pricing

  • Conditional proportional pricing charges a bidder only upon receiving a bundle, preserving ex-post individual rationality relative to reported values.When the target payment does not exceed expected reported value, expected realized payment matches the target; losers pay zero.Source: §H.3 · p. 34

H.4 Optional Full-Assignment Variant

  • Conditioning the lottery on a non-null schedule preserves feasibility and reported-value ex-post individual rationality but changes expected allocation, revenue, welfare, and regret.The full-assignment variant must be reported and audited as a separate implementation.Source: §H.4 · p. 35

I Computational Complexity

The framework’s computational cost is shaped by exponential growth in the bundle set and by the deterministic winner-determination oracle used for discrete implementation. Its feasibility layer adds polynomial overhead, making the approach best suited to problems with a moderate number of valid bundles.

I Computational Complexity

  • Fully enumerating nonempty bundles gives k = 2^m − 1, making bundle growth the dominant scalability bottleneck.The bid tensor contains O(nk) entries.Source: I Computational Complexity · p. 35
  • CAGraph’s conflict graph has O(nk) bidder-bundle nodes, while its worst-case edge count is O(n^2k^2); filtered airport bundles make the practical graph sparser.The graph connects mutually incompatible allocations, including overlapping bundles and allocations involving the same bidder.Source: I Computational Complexity · p. 35
  • The discrete decomposition’s repeated winner-determination oracle dominates residual updates and remains exponential in the worst case, although it is tractable for the small airport instance.The neural feasibility layer adds only polynomial overhead, and the framework is most appropriate for targeted problems with moderate numbers of valid bundles.Source: I Computational Complexity · pp. 35–36

J Empirical Regret Audit

The supplied audit describes how empirical regret and fairness targets should be interpreted, while the scaling discussion proposes extensions for broader airport-allocation settings. These extensions require evaluation rather than assuming runtime or incentive guarantees.

J Empirical Regret Audit

  • The regret audit reports the best deviation found by gradient-based search on held-out profiles, a lower bound on true ex-post regret rather than proof of DSIC.Fairness labels are target Jain indices, not certified lower bounds.Source: J Empirical Regret Audit · p. 36

K Scaling to Real-World Problems

K.1 Non-Homogeneous Resource Capacity

  • For non-homogeneous resource capacities, the proposed resource-weighted conflict graph represents bundle use of capacity blocks, with normalization capped at each block’s capacity.The capacity constraint is expressed as zi,s · ωs,k ≤ Ck.Source: §K.1 · p. 37

K.2 Hierarchical Decomposition for N Bidders

  • For larger bidder and block sets, the proposed hierarchy combines graph partitioning, parallel sub-block clearing, and high-level coordination of coupling constraints.Runtime and approximation quality would require empirical evaluation; no linear-time or millisecond guarantee is claimed.Source: §K.2 · p. 37

K.3 Scalable Candidate Generation

  • Candidate generation could reduce full bundle enumeration, but report-dependent generation requires re-auditing incentive compatibility for the combined system.The proposal does not assume that allocation monotonicity or incentive compatibility is preserved.Source: §K.3 · p. 37

Related papers

Loading 2610.31977v1…