Text

A Unified Framework for Pricing in Nonconvex Resource Allocation Games

We consider a basic nonconvex resource allocation game, where the players’ strategy spaces are subsets of
and cost functions are parameterized by some common vector and, otherwise, only depend on their own strategy choice. A strategy of a player can be interpreted as a vector of resource consumption and a joint strategy profile naturally leads to an aggregate consumption vector. Resources can be priced, that is, the game is augmented by a price vector
and players have quasi-linear overall costs, meaning that in addition to the original costs, a player needs to pay the corresponding price per consumed unit. We investigate the following question: for which aggregated consumption vectors can we find prices that induce an equilibrium realizing the targeted consumption profile? For answering this question, we revisit a duality-based framework and derive a new characterization of the existence of such and using convexification techniques. Our characterization implies the following result: If strategy spaces of players are bounded linear mixed-integer sets and the cost functions are linear or even concave, the equilibrium existence problem reduces to solving a well-structured LP. We then consider aggregate formulations assuming that cost functions are additive over resources and homogeneous among players. We derive a characterization of enforceable consumption vectors , showing that is enforceable if and only if is a minimizer of a certain convex optimization problem with a linear functional. We demonstrate that this framework can unify parts of four largely independent streams in the literature: tolls in transportation systems, Walrasian equilibria, trading networks, and congestion control. Besides reproving existing results we establish new enforceability results for these domains as well.

Ketersediaan

Informasi Detail

Judul Seri

SIAM JOURNAL ON OPTIMIZATION; Vol.33 No.2 April-June 2023

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 1223-1249

Bahasa

English

ISBN/ISSN

-

Klasifikasi

NONE

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

PRICING
NASH EQUILIBRIUM
RESOURCE ALLOCATION
WARDROP EQUILIBRIUM
NONCONVEX GAMES
LAGRANGEAN DUALITY
WALRAS EQUILIBRIUM

Info Detail Spesifik

https://doi.org/10.1137/21M1400924

Pernyataan Tanggungjawab

Tobias Harks, Julian Schwarz

Versi lain/terkait

Lampiran Berkas

Komentar