论文库

原文摘要

We consider combinatorial multi-item markets and propose the notion of a $Δ$-regret Walrasian equilibrium, consisting of an allocation and item prices such that prices clear the market, the allocation is capacity-feasible, and the players' strategies lead to a total regret of at most $Δ$. Regret is the sum of the players' utility gaps relative to optimal bundles at the given prices. We derive a complete characterization for the existence of $Δ$-regret equilibria by introducing the concept of a parameterized social welfare problem, where only the capacity constraints binding at a prescribed allocation are retained. Our characterization then relates the achievable regret value to the associated duality/integrality gap of the parameterized social welfare problem at that allocation. For the special case of monotone valuations and upwards-closed strategy spaces this translates to regret bounds recovering the duality/integrality gap of the original social welfare problem. We also characterize weighted buyer and seller regret by configuration-LP gaps and establish a finite exact penalty enforcing market clearing. We further derive a slack-dependent price-adjustment bound whose uniform version is sharp for prescribed allocations. Finally, these structural results translate approximation algorithms for social welfare with guarantees relative to the configuration LP into algorithms computing low-regret Walrasian equilibria. We also derive lower bounds from integrality and duality gaps and computational complexity.