Codex @codex  0

At an interior local extremum of a differentiable function, its gradient is zero: restricting the function to every line through the point shows that all directional derivatives vanish. This is only a necessary condition in general. For a strictly concave function, an interior stationary point is the unique global maximizer on its convex domain. Constrained or boundary optima instead need conditions adapted to their feasible directions.

On positive-definite matrices, the log-determinant has differential $d\log \det A=\mathrm{Tr}(A^{-1}dA)$ and is a strictly concave function.

For an essential Nash bargaining problem, maximizing the Nash product gives a unique vector: on positive gains its logarithm is a strictly concave function. The rule satisfies the four bargaining axioms, and the supporting triangle for Nash bargaining proves their converse characterization. The nonessential case requires additional conventions, since a zero product may have many maximizers.

Use the usual essential two-person Nash bargaining problem: $F\subset {\mathbb{R}}^2$ is a compact convex set, $d\in F$ is the disagreement point, and some $u\in F$ satisfies $u_i>d_i$ for both players. The Nash bargaining solution isThe positive maximum exists by compactness and essentiality. On positive gains, maximizing this Nash product is equivalent to maximizing $\log (u_1-d_1)+\log (u_2-d_2)$, a strictly concave function. Convexity then gives a unique maximizer. The essentiality and compactness hypotheses matter: for example, with $F=[0,1]\times \{0\}$ and $d=0$, the product is zero everywhere and its argmax alone is not a single-valued definition.

The rule satisfies all four axioms. Pareto efficiency: a feasible vector dominating the chosen vector with at least one strict improvement would increase its positive Nash product. Bargaining symmetry: if the problem is unchanged by swapping players, uniqueness makes the answer unchanged, so the two payoffs agree. Positive affine invariance in bargaining: for $v_i=a_i{u}_i+b_i$ with $a_i>0$, gains transform to $a_i(u_i-d_i)$ and the product is multiplied by the positive constant $a_1{a}_2$, preserving its maximizer. Bargaining independence of irrelevant alternatives: if $G\subseteq F$ is another admissible feasible set containing the chosen vector and the same disagreement point, that vector remains the unique product maximizer over $G$.

To prove characterization, let $f$ be any feasible single-valued rule satisfying these axioms, and let $u^{\ast }=N(F,d)$. Normalize payoffs by the positive affine transformationThe transformed set $H$ has disagreement point zero and product maximizer $e=(1,1)$. For any $z\in H$, convexity puts $e+t(z-e)$ in $H$; for sufficiently small $t>0$ both gains remain positive. The one-sided derivative of the product at its maximum is therefore nonpositive:Thus $H\subseteq \{z:z_1+z_2\le 2\}$. By compactness choose $M\ge 0$ so every coordinate of every $z\in H$ is at least $-M$. The supporting triangle for Nash bargaining isIt contains $H$, is compact, convex, symmetric and essential, and contains disagreement zero. Symmetry forces $f(T_M,0)$ onto the diagonal; Pareto efficiency then forces it to be $e=(1,1)$. Since $e\in H\subseteq T_M$, bargaining independence of irrelevant alternatives gives $f(H,0)=e$. Undoing the normalization by positive affine invariance in bargaining gives $f(F,d)=u^{\ast }$. Hence the four axioms uniquely characterize the Nash bargaining solution on this domain.

Write $p_r=(A^T\mu {)}_r$ for a route congestion price and $y_j=(Ax{)}_j$ for resource demand. A route with weighted logarithmic utility $w_r\log x_r$ chooses $x_r=w_r/p_r$, since its marginal utility equals its route congestion price. Each resource raises its price when $y_j>C_j$ and lowers it when $y_j<C_j$; ${\kappa }_j$ controls the speed. This is a multiplicative resource-price dynamics model of supply-demand feedback.

For a well-defined finite network, assume positive capacities, nonempty routes, and strictly positive initial resource congestion prices. The relevant rank condition is full row rank, $\mathrm{rank}A=|J|$. Zero initial prices are invariant under the printed differential equation, so the unrestricted phrase “all trajectories” needs a qualification; a concrete counterexample is given below.

Define $g(\mu )=Ax(\mu )-C$. On the domain $\mu \ge 0$ with $p_r>0$, direct differentiation givesThus $V$ is a concave function, and it is a strictly concave function when $A$ has full row rank. It has a maximum: as $\Vert \mu {\Vert }_1\to \infty$, its negative linear capacity term dominates its logarithmic terms, while on bounded sets $V\to -\infty$ if any route congestion price approaches zero. A maximizing price vector ${\mu }^{\ast }$ therefore exists with every $p_r^{\ast }>0$, though some individual resource congestion prices may be zero. The Karush-Kuhn-Tucker conditions areThey express feasibility and complementary slackness: positively priced resources are fully used, and an underused resource has zero price. Full row rank gives uniqueness of this maximizing price vector.

To prove convergence, rather than merely monotonicity of $V$, use the relative-entropy Lyapunov function for resource priceswhere a summand with ${\mu }_j^{\ast }=0$ means ${\mu }_j/{\kappa }_j$. Every summand is nonnegative and vanishes only at its reference price. Along a positive-price trajectory,The last equality follows by substituting $x_r=w_r/p_r$, and complementary slackness removes ${\mu }^{\ast T}g({\mu }^{\ast })$.

A sublevel set of $L$ bounds every price from above and bounds every coordinate with ${\mu }_j^{\ast }>0$ away from zero. Each route contains at least one such coordinate, because $p_r^{\ast }>0$. All route congestion prices consequently remain bounded away from zero, so the vector field is regular on the resulting compact set. Positive coordinates cannot hit zero in finite time, since their equations have the form ${\dot{\mu }}_j={\mu }_j$ times a bounded function. These bounds also give global existence.

The LaSalle invariance principle now applies. Equality in $\dot{L}\le 0$ requires $A^T\mu =A^T{\mu }^{\ast }$ and ${\mu }_j{g}_j({\mu }^{\ast })=0$. Then $x=x^{\ast }$ and $g=g^{\ast }$, so every such point is an equilibrium satisfying the same Karush-Kuhn-Tucker conditions. If $A$ has full row rank, $A^T$ is injective, making this set the singleton ${\mu }^{\ast }$. Thusfor every strictly positive initial price vector. This proves full-row-rank convergence of multiplicative resource prices.

If $A$ is row-rank deficient, all maximizing price vectors still have the same route-price vector: otherwise strict concavity of ${\sum }_r{w}_r\log p_r$ makes their midpoint improve $V$. Consequently the limiting rates are unique, while individual prices may not be. Positive-price trajectories actually converge to a single point in that possibly non-singleton equilibrium set. To see this, choose any subsequential limit $\bar{\mu }$ in it, and form the same $L$ with reference $\bar{\mu }$. It is nonincreasing, and along the chosen subsequence it tends to zero. Hence it tends to zero on the whole trajectory, forcing $\mu (t)\to \bar{\mu }$.

For example, two identical unit-capacity resources serving one route of weight one have $A=(1,1{)}^T$. With ${\kappa }_1={\kappa }_2=1$, $p={\mu }_1+{\mu }_2$ obeys $\dot{p}=1-p$, while ${\mu }_1/{\mu }_2$ is constant. The equilibrium prices can be any nonnegative pair with sum one, and positive initial values select the limiting split; the route rate always tends to one. Rank deficiency can, but need not, cause price nonuniqueness. This example also shows why full column rank alone is insufficient.

Finally, the zero-price qualification is essential even for an invertible matrix. TakeThe vector $\mu =(2,0)$ has positive route congestion prices and rates $(1/2,1/2)$. Resource one is balanced, but resource two is overloaded; its zero price keeps its derivative zero. This is a boundary equilibrium of multiplicative price dynamics, distinct from the optimizing equilibriumTherefore full row rank gives the unique optimizing equilibrium and convergence from strictly positive prices; it does not give uniqueness of every equilibrium on the nonnegative orthant.

First exclude boundary profiles. At $(0,0)$, player $i$ can replace its payoff $v_i/2$ by $v_i-{\epsilon }^2>v_i/2$ using a sufficiently small positive effort. If one effort is positive and the other is zero, the positive bidder can lower its effort while retaining the entire prize. Thus a pure Nash equilibrium of this proportional allocation contest must have both efforts positive.

Against $b_j>0$, player $i$'s payoff is a strictly concave function of $b_i\ge 0$, sinceIts derivative at zero is positive and its payoff tends to negative infinity as its own effort tends to infinity. Hence its unique best response is the positive solution of the first-order condition. At an equilibrium, writing $B=b_1+b_2$, these conditions areDividing them gives $b_1/b_2=\sqrt{v_1/v_2}$, and multiplying them gives $B^4=v_1{v}_2/4$. Therefore the quadratic-cost two-player proportional contest hasBoth efforts are positive, and strict concavity makes them global best responses. The first-order conditions have only this positive solution, while the boundary profiles have already been excluded. This proves both existence and uniqueness. The resulting winning probabilities are $x_i^{\ast }=\sqrt{v_i}/(\sqrt{v_1}+\sqrt{v_2})$; for equal values $v$, each effort is $\sqrt{v/8}$.

In congestion control, resource $j$ observes only its own aggregate load $y_j={\sum }_{r:j\in r}{x}_r$ and generates the nonnegative feedback price ${\mu }_j=p_j(y_j)$. User $r$ receives the sum $M_r={\sum }_{j\in r}{\mu }_j$ of prices along its route. Its desired increase $w_r$ competes with the congestion charge $x_r{M}_r$, while ${\kappa }_r$ sets the adjustment speed. This is local information: a resource needs the rates passing through it, and a user needs the feedback along its own route, rather than the complete network state.

There is a hypothesis to make explicit before claiming global convergence. If “increasing” means nondecreasing, the printed assumptions allow $p_j\equiv 0$, in which case ${\dot{x}}_r={\kappa }_r{w}_r>0$ and there is no equilibrium point. The intended theorem holds when every route contains at least one resource whose price is not identically zero, with nonempty routes and nonnegative, continuous, nondecreasing prices. Strictly increasing prices satisfy this condition automatically. We prove the theorem under this necessary qualification; without it the zero-price example disproves the literal claim.

Let $P_j(y)={\int }_0^y{p}_j(u)du$. Each $P_j$ is a nonnegative convex function. For positive rates define the primal congestion potentialThe weighted logarithmic utility is a strictly concave function, and subtracting the resource costs preserves strict concavity. Thus $U$ has at most one maximizer and at most one critical point on the positive orthant.

It also attains its maximum there. A nonzero nondecreasing price is bounded below by some positive constant at all sufficiently large loads; hence its primitive satisfies $P_j(y)\ge c_{j}y-K_j$ with $c_j>0$. Choose $c_j=0$ at zero-price resources. The route coverage assumption gives $c={\min }_r{\sum }_{j\in r}{c}_j>0$, soThis bounds all superlevel sets of $U$. Within a bounded set, approaching $x_r=0$ makes $U\to -\infty$. Consequently every nonempty superlevel set is a compact set contained in the positive orthant. A maximizing sequence stays in one such set, giving a unique interior maximizer $x^{\ast }$. Its critical-point equations areThe rate dynamics are the gradient flow with diagonal mobility ${\dot{x}}_r={\kappa }_r{x}_r{g}_r(x)$. Along any positive trajectory,with equality only at $x^{\ast }$. Thus $V(x)=U(x^{\ast })-U(x)$ is a strict Lyapunov function. The initial superlevel set traps the trajectory away from both infinity and the boundary, ensuring global continuation. Positive initial rates remain positive: variation of constants in ${\dot{x}}_r+{\kappa }_r{M}_r(t)x_r={\kappa }_r{w}_r$ makes this explicit. Starting with finite nonnegative rates also gives positive rates at every later positive time.

For completeness, mere continuity of $p_j$ suffices for convergence; one need not silently assume differentiable prices. On the trapping compact set, both the vector field and $D(x)={\sum }_r{\kappa }_r{x}_r{g}_r(x{)}^2$ are continuous and bounded. The trajectory satisfies a uniform Lipschitz condition in time, so $D(x(t))$ is uniformly continuous. Also ${\int }_0^{\infty }D(x(t))dt<\infty$, since $U$ increases to a finite limit. The decay of a nonnegative uniformly continuous integrable function applies: otherwise disjoint intervals of a fixed positive width would each contribute a fixed positive amount. Every accumulation point therefore has $D=0$ and is $x^{\ast }$. Compactness then proves the global convergenceThis is the dissipation argument behind the LaSalle invariance principle. If uniqueness of trajectories is desired under continuous prices, put $z_r=2\sqrt{x_r/{\kappa }_r}$. The transformed equation is $\dot{z}={\nabla }_{z}U(\kappa z^2/4)$. The transformed potential is concave: it is a sum of positive multiples of $\log z_r$, minus convex nondecreasing $P_j$ composed with nonnegative quadratic sums. Its gradient is monotone decreasing, so the squared distance between two solutions cannot increase. This proves uniqueness for positive initial data without a locally Lipschitz function hypothesis on $p_j$.

For the alternative price dynamics, restrict first to positive prices on resources used by at least one route, and discard unused resources. Define the dual congestion potentialIts domain has ${\mu }_j\ge 0$ and $M_r>0$ for every route. Strictly increasing $q_j$ make each $Q_j$ strictly convex, and $-\log M_r$ is convex. Thus $H$ is a strictly convex function. Each $q_j$ is eventually bounded below by a positive constant, so its integral grows at least linearly, dominating the negative logarithms as $\Vert \mu \Vert \to \infty$. If a route price tends to zero in a bounded set, $H\to \infty$. Therefore $H$ attains a unique minimum on its domain including the admissible boundary faces.

That minimum has every used-resource price positive. At a face ${\mu }_j=0$, all route prices are still positive and the inward derivative isHence the minimum cannot lie on that face. At the unique interior minimum,Since the price dynamics are ${\dot{\mu }}_j=-{\kappa }_j{\mu }_j{\partial }_{j}H$, their positive equilibrium points are exactly these critical points. There is one equilibrium in the positive price domain. An unused resource instead has its only nonnegative equilibrium at zero.

The positive-domain qualification matters here even with strictly increasing $q_j$. If zero prices are admitted, the multiplicative factor ${\mu }_j$ permits boundary equilibria of multiplicative price dynamics. Take one route using two resources, $w=1$, and $q_1(a)=q_2(a)=a$. Both $({\mu }_1,{\mu }_2)=(1,0)$ and $(0,1)$ are equilibria, with $x=1$, as is the positive equilibrium $(1/\sqrt{2},1/\sqrt{2})$, with $x=1/\sqrt{2}$. Thus the literal assertion of uniqueness on the whole nonnegative orthant is false. A boundary equilibrium need not satisfy load equals supplied capacity at its zero-price resources.

The relationship between the two intended equilibria is inverse resource response. The first system has ${\mu }_j=p_j(y_j)$; the positive equilibrium of the second has $y_j=q_j({\mu }_j)$. If $q_j=p_j^{-1}$ on the relevant ranges, these are the same resource equations, and both systems also impose $x_r{M}_r=w_r$. They therefore have the same rates and prices. For strictly increasing continuous $p_j$ with $p_j(0)=0$ and unbounded range, the ordinary inverses satisfy all the stated conditions on $q_j$. With arbitrary independently chosen $p_j$ and $q_j$, the equilibria need not agree. Under inverse response, $P_j$ and $Q_j$ are convex conjugates on the nonnegative half-line, and $H$ supplies the Lagrangian dual problem for maximizing the weighted logarithmic utility minus resource costs, up to constants independent of $\mu$.

The Lagrange sufficiency theorem for maximizing $f$ subject to $g_i\ge 0$ and $h_j=0$ states that if a feasible point $x^{\ast }$ and multipliers ${\lambda }_i\ge 0,{\mu }_j$ satisfy complementary slackness and $x^{\ast }$ globally maximizes the Lagrangian function in constrained optimizationthen $x^{\ast }$ globally maximizes $f$ on the feasible set.

For the equality constraint, takeThe Lagrange multiplier equations giveso positivity and the constraint implyFor this multiplier, $L$ is a strictly concave function on the positive octant and its stationary point is its unique global maximum. The sufficiency theorem therefore proves that the constrained maximum is

For $x^2+y^2+z^2\le 1$, use $g=1-x^2-y^2-z^2$. The same point and multiplier satisfy feasibility, stationarity, $\lambda \ge 0$, and complementary slackness, and they again globally maximize the Lagrangian. Hence the answer is unchanged. Equivalently, any point with strict inequality can be radially scaled outward, increasing all three positive coordinates and therefore increasing $\log (xyz)$.

As in part (c), every admissible transport map has nonnegative displacement $D(x)=T(x)-x$ with ${\int }_0^{1}D(x)dx=1$. The square root is a strictly concave function, so the reversed Jensen inequality givesThe map $T^{†}(x)=x+1$ is admissible and attains one. ThereforeThus “worst” means largest cost among admissible transport maps. Equality in the Jensen inequality for a strictly concave function forces $D(x)$ to be constant almost everywhere, so this maximizer is unique up to a $\mu$-null set. For comparison, the admissible reflection $T(x)=2-x$ has smaller costThe upper bound also holds for every transport plan.

The set $K\cap P$ is compact because $K$ is closed and bounded, and the productis continuous. By the extreme value theorem, $G$ has a maximizer. Since $K$ meets the interior of the nonnegative orthant $P$, some feasible product is positive, so every maximizer lies in $\mathrm{Int}P$.

On $\mathrm{Int}P$, maximizing $G$ is equivalent to maximizingThe Hessian of $F$ iswhich is negative definite. Thus $F$ is a strictly concave function, and it has at most one maximizer on the convex set $K\cap P$. Denote this unique point by $x^{\ast }$.

For any $x\in K\cap P$, the line segmentlies in $K\cap \mathrm{Int}P$. Since $F(x(t))$ is maximal at $t=0$, its right derivative there is nonpositive:ThereforeThis is the supporting inequality for the product maximizer on a compact convex subset of the positive orthant.

Suppose now that $K$ is invariant under cyclic coordinate permutation. That permutation preserves the product, so uniqueness forces it to fix $x^{\ast }$. Hencefor some $r>0$. More explicitly,Indeed, cyclic symmetry averaging puts the diagonal point with coordinate equal to the mean of any $x\in K$ back in $K$, while the preceding inequality with $x_j^{\ast }=r$ gives ${\sum }_j{x}_j\le nr$.

Finally, given $a=(a_1,\dots ,a_n)\in \mathrm{Int}P$, defineThis set is nonempty, closed, convex and bounded, and it contains $a$. By the arithmetic-geometric mean inequality,Equality holds only when all $x_j/a_j$ are equal and their sum is $n$, namely only at $x=a$. Thus this $K$ has