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

Arabic

ونحن ندرس مشكلة توزيع الطرق بين الأقمار الصناعية في شبكات النقل المحدودة مع تكلفة التحويل. ونحن نقدم لغة التوزيع الأساسية، حيث يقدم المشارك مزيجًا محدودًا من مزيجات التوزيع المحدودة من الأقمار الصناعية، ويقوم ميكانيكية Vickrey-Clarke-Groves (VCG) بإجراء التوزيع من خلال مشكلة التكلفة المحدودة التي تعزز الفائز-المحدد. ونحن ندرس أيضًا قواعد الدفع لميكانيكا 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