Papers for

market platform engineers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Complexity boundaries found for network Cournot competition approximations

Sharp Complexity Thresholds for Network Cournot Competition

Abstract: We determine the approximation complexity of network Cournot equilibrium as a function of demand degree and the number of firms sharing a market. For common, nonincreasing concave polynomial inverse demands, convex quadratic costs of firms' allocation vectors, and rational total capacities, high-precision approximation is polynomial-time solvable for cubic demands, regardless of market size. Quartic demands remain tractable when each market has at most three firms, and quintic demands remain tractable with at most two. These thresholds are exact: approximation at a fixed positive profit-regret tolerance is PPAD-hard for quartic demands with four firms per market, quintic demands with three, and sextic demands with two. Each hardness result uses one fixed demand curve in every market, a constant number of markets per firm, and globally nondecreasing strongly convex quadratic costs. We also give a polynomial-time algorithm for arbitrary-degree nonincreasing concave polynomial demands when each firm's convex polynomial cost depends only on its total production. The algorithm applies to arbitrary access graphs and permits firm-specific inverse demands. Its running time is polynomial in the input size and the logarithm of the inverse accuracy. The algorithm assigns one marginal charge to each firm and adjusts the charges until each firm's total sales approximate the quantity it would produce at that charge.

Wed 18 NovComputer Science and Game TheoryComputational Complexity
The gist
Network Cournot competition studies how companies set quantities to sell when they share multiple markets. This paper finds exactly when approximating these market equilibria is computationally easy or hard, based on how demand curves behave and how many firms compete in each market. The authors identify precise thresholds—such as cubic demand curves being easy and quartic or higher becoming hard under certain conditions. They also provide an algorithm that can efficiently approximate equilibrium for some cases where costs depend only on total production. This helps clarify the limits of computing equilibria in complex market networks.
Open → 2611.24931v1