| paper | d4-conf-aaai-2007-0229 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: The approximation guarantee is attainable in polynomial time: $W\geq\mathrm{OPT}/(6\log_2 R)$. · discrete side: other · adjudication: proved
full proof & adversarial review →
Proposition 2
statement extracted from the paper’s text layer
Given finitely many bidder classes \(q\), each with a fixed OR-linear bundle template, a rational mass distribution over private values \(\theta\), rational per-capita spatial supply, and a finite rational description of candidate rectangles, compute a polynomial-time direct menu mechanism. Each bidder must receive an integral feasible bundle and a transfer; aggregate assignments must respect supply, and truthful menu choice must be dominant-strategy optimal. Does such a mechanism guarantee welfare at least \(\mathrm{OPT}/(c\log R)\) for a universal constant \(c\), where \(R\) bounds the ratio of rectangle edge lengths?
A society is a distribution \(\mu\) over complete types \((q,\theta)\), where \(q\) specifies the OR-linear valuation template. The mechanism offers report-contingent bundles and transfers; a single bidder has zero mass and does not change the aggregate decision, while mass assignments must satisfy per-capita spatial supply. The objective is to maximize truthful welfare subject to dominant-strategy menu choice, with an \(O(\log R)\) approximation target.
Dominant-strategy truthfulness changes from a finite bidder's report affecting the allocation rule to an infinitesimal bidder choosing from a menu that leaves the aggregate decision fixed; Proposition 2 therefore does not transfer directly.
fatal: False
Covers Proposition 2's welfare approximation and incentive-compatible mechanism for OR-linear rectangular-bundle auctions. It leaves the general MAX characterization results and the bitonicity application unmirrored.
The best case is for a continuous mirror of Proposition 2, proved in this paper. It says that for rectangular-bundle auctions with single-parameter OR-linear valuations, there is a polynomial-time, incentive-compatible mechanism that achieves an \(O(\log R)\) approximation to optimal welfare, where \(R\) bounds the ratio between rectangle edge lengths. The mechanism’s running time is polynomial in the input representation, including the bidders’ bundle lists. The proposition is proved here using a shifting mechanism whose underlying approach was developed in cited earlier work.
A plausible high-multiplicity setting is a large market for rectangular office or industrial space. Bidders fall into a small number of public classes \(q\): each class has the same desired bundles \(S_{q1},\ldots,S_{qk_q}\) and coefficients \(\alpha_{q1},\ldots,\alpha_{qk_q}\). A bidder’s private scalar \(\theta\in[0,1]\) scales the value of those bundles. For a feasible bundle \(B\), write
\[ w_q(B)=\max_{I}\sum_{j\in I}\alpha_{qj}, \]
where the maximum is over sets \(I\) for which the \(S_{qj}\), \(j\in I\), are pairwise disjoint and contained in \(B\). The bidder’s value is then \(v_{q,\theta}(B)=\theta w_q(B)\). There may be many bidders but only \(\tau\) distinct complete types \((q,\theta)\), with rational masses \(\mu_{q,\theta}\). Standardized firms or procurement cohorts make that repetition plausible. For a growing market, available space scales with population, so the normalized supply of each part of the plane is fixed per unit of population.
Here is the continuous problem I would hand to a prover:
Continuous OR-Linear Rectangular Auction. The input gives a finite rational description of the candidate rectangles and their geometry, the class templates \(q\), rational masses \(\mu_{q,\theta}\) on finitely many private-value levels, and a rational per-capita supply field \(s(z)\) over locations \(z\) in the plane. Find a polynomial-time direct mechanism that, for each aggregate report distribution, assigns each infinitesimal bidder an integral feasible bundle of rectangles and a transfer. Aggregate assignments must respect supply: the mass receiving bundles that cover \(z\) is at most \(s(z)\) at every location. Each realization gives each agent an integral bundle, though a type’s average assignment may be fractional.
The mechanism must be dominant-strategy truthful: fixing all other reports, a bidder of class \(q\) and true value \(\theta\) must prefer reporting \(\theta\) to any \(r\in[0,1]\). Its expected welfare at truthful reports must be at least \(\mathrm{OPT}(\mu)/(c\log R)\) for a universal constant \(c\), where \(\mathrm{OPT}(\mu)\) is the maximum welfare over feasible assignments of the population mass. A solution is the mechanism, not merely a welfare-maximizing allocation at the truthful profile; truthfulness requires its allocation and payment rules to work under deviations.
I expect this bounded-support version to be Class A, though Proposition 2 does not establish that it carries over. The continuous mass variables and per-capita feasibility constraints give a natural optimization formulation, and the question preserves the paper’s central combination of rectangular allocation, OR-linear preferences, welfare approximation, and dominant-strategy incentives. The result to try to carry across is its \(O(\log R)\) guarantee. Further questions include whether the shifting argument extends to mass allocations with efficient pricing, how the running time depends on \(\tau\) and the bit length \(L\), and whether the discrete problem admits additive approximation from the continuous one.
My weakest point is the truthfulness limit. Proposition 2 concerns individually strategic bidders in a finite auction with fixed land supply. The proposed mirror scales supply with population and treats a bidder as infinitesimal: their report can affect their own menu but not the aggregate report measure. That is a genuine change in the mechanism model, and the paper proves no result for it. A referee might accept it as the large-market version of the same auction problem, but might regard the supply scaling and pointwise incentives as too large a change. This is why I would present it as a serious, narrow mirror of Proposition 2—not as a mirror of the paper’s general MAX-characterization theorems or of its full setting.
Proposition 2 is a genuine computational result: it gives a polynomial-time, incentive-compatible \(O(\log R)\)-approximation for rectangular auctions with OR-linear valuations. The proposed market of repeated firms is plausible, so I would not reject the mirror on demographic grounds.
The strongest objection is that the population limit changes what dominant-strategy truthfulness means. If the mechanism takes only the report distribution \(\mu\) as input, one bidder’s deviation changes \(\mu\) by zero. An aggregate allocation, defined only up to sets of measure zero, also does not specify that bidder’s outcome. The paper’s individual incentive comparison therefore cannot be read directly from the continuous input and output.
There are ways to repair this, but each changes the strategic object. Treating a cohort as one player makes its report change a positive mass and gives it market power; that is not the paper’s per-bidder guarantee. Keeping individual agents in the model requires the mechanism to give each a report-contingent allocation and payment, such as a menu, alongside the aggregate feasibility constraints. That is a coherent atomless market-design problem, and likely the best mirror. Its incentive constraints concern an individual choosing from a menu while their report has no effect on aggregate supply or on the mechanism’s aggregate decision. Preserving each bidder’s effect instead requires positive atom sizes such as \(1/n\), which retains a discrete high-multiplicity model.
This is a real mismatch with the proposition’s mechanism-design question, but it does not establish that the menu version is uninteresting or that the authors would not recognize it. A negative case strong enough to rule out every worthwhile mirror is weak here: the best formulation changes the strategic interpretation, while still leaving a plausible computational problem.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.