Search papers, labs, and topics across Lattice.
This paper investigates the credibility of marketplace operators in mechanism-mediated service markets with polymatroidal feasibility, where efficient and DSIC allocation is typically assumed. It establishes a "credibility trilemma," showing that no static sealed-bid mechanism can simultaneously be revenue-optimal, DSIC for agents, and credible for the operator in non-modular polymatroids. The authors then quantify the Cost of Non-Credibility (CoNC) across various network topologies and propose three structurally distinct resolutions to the trilemma, highlighting the importance of marketplace neutrality.
Forget incentive compatibility, can you even trust the marketplace operator?
Mechanism-mediated service markets with polymatroidal feasibility admit efficient, dominant-strategy incentive-compatible (DSIC) allocation, but these guarantees implicitly assume truthful execution by the marketplace operator. Modelling the operator as a strategic player, we establish a credibility trilemma: for single-parameter agents on a non-modular polymatroid, no static sealed-bid mechanism is simultaneously revenue-optimal, DSIC for agents, and credible for the operator. We introduce the Cost of Non-Credibility (CoNC) as a price-of-anarchy-style welfare-loss measure and obtain tight $\Theta$-bounds across five topology classes (single-edge, series, parallel, tree, series-parallel), plus a matching upper bound $O(|\mathcal{S}|)$ on general DAGs realised by an $\Omega(|\mathcal{S}|)$ witness on the SP-augmented sub-family, turning the trilemma into a structural quantity. Three structurally distinct resolutions follow: public broadcast or deferred-revelation commitment, administrative domain separation under settlement separation and four side conditions, and integrator competition orthogonal to mechanism execution under disjoint actors. An instance-level grounding over the edge-pricing market of Amin et al. confirms the trilemma's robustness on a refereed external setting. The result establishes marketplace neutrality as a first-order design constraint on polymatroidal service markets rather than an implementation detail: where the operator is a strategic player, credibility trades off against revenue optimality and agent incentive compatibility along structurally characterised lines.
