Newest papers

Auction-based allocation of routes in capacity-constrained networks

Gergely Csáji, Dávid Csercsik · 2026 · arXiv (Cornell University)

DOI: 10.48550/arxiv.2610.20125 · cited by 0 works (OpenAlex) · open-access PDF

Chinese

我们研究在容量限制流量网络中以传输成本为代价的输入节点之间的路由分配问题。我们引入了一个源头 - 目的地 (OD) 招标语言,其中参与者向输入 - 输出 - 数量许可证的局限性阴性组合进行招标,并且机制通过网络流量优化赢家 - 决定问题进行路由;关键的结构事实是,在这个模式中,一些最佳的总流量从来没有使用物理管道在两种方向,所以赢家 - 定价问题会减少到一个单一的商品流量网络,其成本值在积极的报价节点中是子模块化的。

Machine translation (Meta M2M100); the English original follows.

Abstract

We study the route-set allocation problem between end nodes in capacity-constrained flow networks with transfer costs. We introduce an origin--destination (OD) bidding language, in which a participant bids for bounded conic combinations of inlet--outlet--quantity licences and the mechanism performs the routing through a network-flow optimising winner-determination problem. We then study payment rules for the OD mechanism. Under a restricted model with openly and uniformly priced sources and bidders who are indifferent to the source of the gas, the Vickrey--Clarke--Groves (VCG) payment is core-stable; the key structural fact is that in this regime some optimal aggregate flows never use a physical pipe in both directions, so the winner-determination problem reduces to a single-commodity network flow whose value is submodular in the set of active bidders. If source access is allowed to depend on the individual consumer -- a realistic feature, e.g. when gas deals are embedded in bilateral political bargaining -- the reduction fails and VCG payments may lie strictly outside the core. For this general model we propose a dual (nodal) pricing rule derived from the shadow prices of the flow-conservation constraints, and prove it is always core-stable, at the cost of dominant-strategy incentive compatibility. Illustrative examples accompany each result.

Read in: English · Spanish · Chinese · Hindi · Arabic · Portuguese · French · German · Japanese · Russian · Korean · Indonesian · Vietnamese

Topics: Bidding, Submodular set function, Payment, Computer science, Mathematical optimization, Incentive compatibility

Sources: OpenAlex (CC0), arXiv, Crossref. Agent Exchange