The ordered field property and a finite algorithm for the Nash bargaining solution (Q1185756)

When in 1950 Nash introduced his bargaining solution (the one for which the product of utilities \((u-u_ 0)\) \((v-v_ 0)\) is the biggest), his existence proof essentially used the fact that utilities are real numbers. If we have finitely many pure alternatives \(A_ 1,\dots,A_ N\), then we choose between their convex combinations whose utilities \((u,v)\) form a convex polygon: namely, a convex hull of the points \((u_ i,v_ i)\) that correspond to pure alternatives \(A_ i\). For this case, an algorithm has been proposed that finds the Nash solution. This algorithm also uses the fact that we are dealing with real numbers. In the paper under review, the author proves that if \(u_ i\) and \(v_ i\) belong to some ordered field \(F\) (e.g., to the field of all rational numbers), then there exists a point \((u,v)\) in this polygon with \(u\in F\) and \(v\in F\), for which \((u-u_ 0)(v-v_ 0)\to\max\). The author also presents an algorithm for computing these \(u\) and \(v\) that take \(\leq Cm^ 2\) computational steps, where \(m\) denotes the number of extreme points. The basic idea of the proof and the algorithm is as follows: Nash's solution must lie on the border of the polygon; therefore, it must belong to one of the arcs that connect extreme points. All the points of the arc between \((u_ i,v_ i)\) and \((u_ j,v_ j)\) are of the type \((\alpha u_ i+(1-\alpha)u_ j,\alpha v_ i+(1-\alpha)v_ j)\). For these points, \((u-u_ 0)\) \((v-v_ 0)\) is quadratic in \(\alpha\). The standard transformation of a quadratic expression \(\alpha^ 2+a\alpha+b\) to \((\alpha+a/2)^ 2+c\) works for an arbitrary field, so the maximum is either attained at the endpoint, or in the point that can be easily computed from \((u_ i,v_ i)\) and \((u_ j,v_ j)\). So, for each pair we need \(\leq\) const computational steps, and totally \(\leq Cm^ 2\).