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

French

Nous étudions le problème d'allocation d'itinéraire entre les nœuds finaux dans les réseaux de flux limités de capacité avec les coûts de transfert. Nous introduisons un langage d'offre d'origine-destination (OD) dans lequel un participant offre des combinaisons coniques limitées de licences d'entrée-sortie-quantité et le mécanisme effectue le routage à travers un problème de flux réseau optimisant le gagnant-détermination. Nous étudions ensuite les règles de paiement pour le mécanisme OD. Sous un modèle restreint avec des sources de prix ouverts et uniformes et des soumissionnaires qui sont indifférents à la source du gaz, le Vickrey-Clarke-Groves (VCG) effectue le pai

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