New Algorithm Recovers Unknown Item Values Using Only Comparison Queries

A new paper from researchers Ritabrata Barat, Siddharth Barman, Nirjhar Das, and Sukruta Midigeshi tackles a classic optimization problem—packing linear programs (LPs)—but with a twist: the algorithm only gets comparison feedback about optimal solutions under varying constraints. Traditional inverse optimization assumes you observe the actual optimal solution; here, the oracle merely tells you which of two price vectors yields a larger optimal packing value. This matches real-world scenarios like monopoly pricing, where a seller infers a buyer's unknown valuations for divisible items by asking them to choose between differently priced bundles (discrete-choice surveys).

The team focuses on the fractional knapsack problem (a packing LP with a single budget constraint) and develops a polynomial-time algorithm that recovers item values up to scale. The query complexity is O(n log(1/δ) + B^2), where n is the number of items, B is the knapsack capacity, and δ is the value grid resolution. They also prove a matching Ω(n log(1/δ)) lower bound, showing the algorithm is essentially optimal. A key insight: in the comparison-oracle model, fractional knapsack is as general as any packing LP—by treating each constraint matrix row as a price vector and zeroing others, the algorithm solves general packing problems. The work also extends to profit-maximization settings, providing a comparison-oracle analogue of a classic revealed-preference result by Amin et al. (AAAI 2015). Practical implications range from pricing strategy design to preference learning from ordinal data.