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

Korean

우리는 수용량 제한된 흐름 네트워크에서 엔드 노드 간의 경로 설정 할당 문제를 연구합니다. 우리는 출처 - 목적지 (OD) 입찰 언어를 소개합니다. 참가자가 가스 소스에 상관없는 제한된 콘닉 조합을 제공하고 메커니즘은 네트워크 흐름 최적화 승자 결정 문제를 통해 라우팅을 수행합니다. 우리는 OD 메커니즘에 대한 지불 규칙을 연구합니다. 개방적이고 동일하게 가격을 지불 한 출처와 입찰자에 대한 제한 된 모델에서 Vickrey - Clarke - Groves (VCG) 지불 메커니즘은 핵심 안정적입니다. 주요 구조적 사실은이 모드에서 일부 최적 집계 흐름이 양방향 물리적 파이프를 사용하지 않는다는

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