Meritocratic systems, from admissions to hiring, aim to impartially reward skill and effort. Yet persistent disparities across race, gender, and class challenge this ideal. Some attribute these gaps to structural inequality; others to individual choice. We develop a game-theoretic model in which candidates from different socioeconomic groups differ in their perceived post-selection value—shaped by social context and, increasingly, by AI-powered tools offering personalized career or salary guidance. Each candidate strategically chooses effort, balancing its cost against expected reward; effort translates into observable merit, and selection is based solely on merit. We characterize the unique Nash equilibrium in the large-agent limit and derive explicit formulas showing how valuation disparities and institutional selectivity jointly determine effort, representation, social welfare, and utility. We further propose a cost-sensitive optimization framework that quantifies how modifying selectivity or perceived value can reduce disparities without compromising institutional goals. Our analysis reveals a perception-driven bias: when perceptions of post-selection value differ across groups, these differences translate into rational differences in effort, propagating disparities backward through otherwise "fair" selection processes. While the model is static, it captures one stage of a broader feedback cycle linking perceptions, incentives, and outcomes—bridging rational-choice and structural explanations of inequality by showing how techno-social environments shape individual incentives in meritocratic systems.

Abstract This paper extends a recently proposed robust computational framework for constructing the boundary representation (brep) of the volume swept by a given smooth solid moving along a one parameter family h of rigid motions. Our extension allows the input solid to have sharp features, and thus it is a significant and useful generalization of that work. This naturally requires a precise description of the geometry of the surface generated by the sweep of a sharp edge supported by two intersecting smooth faces. We uncover the geometry along with the related issues like parametrization and singularities via a novel mathematical analysis. Correct trimming of such a surface is achieved by an analysis of the interplay between the cone of normals at a sharp point and its trajectory under h. The overall topology is explained by a key lifting theorem which allows us to compute the adjacency relations amongst entities in the swept volume by relating them to corresponding adjacencies in the input solid. Moreover, global issues related to body‐check such as orientation, singularities and self‐intersections are efficiently resolved. Examples from a pilot implementation illustrate the efficiency and effectiveness of our framework.

Using Lemke's scheme, we give a complementary pivot algorithm for computing an equilibrium for Arrow--Debreu markets under separable, piecewise-linear concave (SPLC) utilities. Despite the polynomial parity argument on directed graphs (PPAD) completeness of this case, experiments indicate that our algorithm is practical---on randomly generated instances, the number of iterations it needs is linear in the total number of segments (i.e., pieces) in all the utility functions specified in the input. Our paper settles a number of open problems: (1) Eaves (1976) gave an LCP formulation and a Lemke-type algorithm for the linear Arrow--Debreu model. We generalize both to the SPLC case, hence settling the relevant part of his open problem. (2) Our path following algorithm for SPLC markets, together with a result of Todd (1976), gives a direct proof of membership of such markets in PPAD and settles a question of Vazirani and Yannakakis (2011). (3) We settle a question of Devanur and Kannan (2008) of obtaining a “systematic way of finding equilibrium instead of the brute-force way” for the separable case and we obtain a strongly polynomial algorithm if the number of goods or agents is constant. (4) We give a combinatorial way of interpreting Eaves' algorithm for the linear case, hence answering Eaves' question (1976), “That the algorithm can be interpreted as a `global market adjustment mechanism' might be interesting to explore.”

In this paper we consider the problem of computing market equilibria in the Fisher setting for utility models such as spending constraint and perfect, price-discrimination. These models were inspired from modern e-commerce settings and attempt to bridge the gap between the computationally hard but realistic separable, piecewise-linear and concave utility model and, the tractable but less relevant linear utility case. While there are polynomial time algorithms known for these problems, the question of whether there exist polynomial time Simplex-like algorithms has remained elusive, even for linear markets. Such algorithms are desirable due to their conceptual simplicity, ease of implementation and practicality. This paper takes a significant step towards this goal by presenting the first Simplex-like algorithms for these markets assuming a positive resolution of an algebraic problem of Cucker, Koiran and Smale. Unconditionally, our algorithms are FPTASs; they compute prices and allocations such that each buyer derives at least a -fraction of the utility at a true market equilibrium, and their running times are polynomial in the input length and 1/ε. We start with convex programs which capture market equilibria in each setting and, in a systematic way, convert them into linear complementarity problem (LCP) formulations. Then, departing from previous approaches which try to pivot on a single polyhedron associated to the LCP obtained, we carefully construct a polynomial-length sequence of polyhedra, one containing the other, such that starting from an optimal solution to one allows us to obtain an optimal solution to the next in the sequence in a polynomial number of complementary pivot steps. Our framework to convert a convex program into an LCP and then come up with a Simplex-like algorithm that moves on a sequence of connected polyhedra may be of independent interest.

Using the powerful machinery of the linear complementarity problem and Lemke's algorithm, we give a practical algorithm for computing an equilibrium for Arrow-Debreu markets under separable, piecewise-linear concave (SPLC) utilities, despite the PPAD-completeness of this case. As a corollary, we obtain the first elementary proof of existence of equilibrium for this case, i.e., without using fixed point theorems. In 1975, Eaves [10] had given such an algorithm for the case of linear utilities and had asked for an extension to the piecewise-linear, concave utilities. Our result settles the relevant subcase of his problem as well as the problem of Vazirani and Yannakakis of obtaining a path following algorithm for SPLC markets, thereby giving a direct proof of membership of this case in PPAD.

Given a rank-1 bimatrix game (A,B), i.e., where rank(A+B)=1, we construct a suitable linear subspace of the rank-1 game space and show that this subspace is homeomorphic to its Nash equilibrium correspondence. Using this homeomorphism, we give the first polynomial time algorithm for computing an exact Nash equilibrium of a rank-1 bimatrix game. This settles an open question posed by Kannan and Theobald (SODA'07). In addition, we give a novel algorithm to enumerate all the Nash equilibria of a rank-1 game and show that a similar technique may also be applied for finding a Nash equilibrium of any bimatrix game. Our approach also provides new proofs of important classical results such as the existence and oddness of Nash equilibria, and the index theorem for bimatrix games. Further, we extend the rank-1 homeomorphism result to a fixed rank game space, and give a fixed point formulation on [0,1]k for solving a rank-k game. The homeomorphism and the fixed point formulation are piece-wise linear and considerably simpler than the classical constructions.

In [K. D. Mulmuley and M. Sohoni, SIAM J. Comput., 31 (2001), pp. 496–526], henceforth referred to as Part I, we suggested an approach to the P vs. $NP$ and related lower bound problems in complexity theory through geometric invariant theory. In particular, it reduces the arithmetic (characteristic zero) version of the $NP \not \subseteq P$ conjecture to the problem of showing that a variety associated with the complexity class $NP$ cannot be embedded in a variety associated with the complexity class P. We shall call these class varieties associated with the complexity classes P and $NP$. This paper develops this approach further, reducing these lower bound problems—which are all nonexistence problems—to some existence problems: specifically to proving the existence of obstructions to such embeddings among class varieties. It gives two results towards explicit construction of such obstructions. The first result is a generalization of the Borel–Weil theorem to a class of orbit closures, which include class varieties. The second result is a weaker form of a conjectured analogue of the second fundamental theorem of invariant theory for the class variety associated with the complexity class $NC$. These results indicate that the fundamental lower bound problems in complexity theory are, in turn, intimately linked with explicit construction problems in algebraic geometry and representation theory. The results here were announced in [K. D. Mulmuley and M. Sohoni, in Advances in Algebra and Geometry (Hyderabad, $2001$), Hindustan Book Agency, New Delhi, India, 2003, pp. 239–261].

MOTIVATION: Characterization of the restricted nature of the protein local conformational space has remained a challenge, thereby necessitating a computationally expensive conformational search in protein modeling. Moreover, owing to the lack of unilateral structural descriptors, conventional data mining techniques, such as clustering and classification, have not been applied in protein structure analysis. RESULTS: We first map the local conformations in a fixed dimensional space by using a carefully selected suite of geometric invariants (GIs) and then reduce the number of dimensions via principal component analysis (PCA). Distribution of the conformations in the space spanned by the first four PCs is visualized as a set of conditional bivariate probability distribution plots, where the peaks correspond to the preferred conformations. The locations of the different canonical structures in the PC-space have been interpreted in the context of the weights of the GIs to the first four PCs. Clustering of the available conformations reveals that the number of preferred local conformations is several orders of magnitude smaller than that suggested previously. SUPPLEMENTARY INFORMATION: www.it.iitb.ac.in/~ashish/bioinfo2005/.

Many image transformations in computer vision and graphics involve a pipeline when an initial integer image is processed with floating point computations for purposes of symbolic information. Traditionally, in the interests of time, the floating point computation is approximated by integer computations where the integerization process requires a guess of an integer. Examples of this phenomenon include the discretization interval of rho and theta in the accumulator array in classical Hough transform, and in geometric manipulation of images (e.g., rotation, where a new grid is overlaid on the image). The result of incorrect discretization is a poor quality visual image, or worse, hampers measurements of critical parameters such as density or length in high fidelity machine vision. Correction techniques include, at best, anti-aliasing methods, or more commonly, a "kludge" to cleanup. In this paper, we present a method that uses the theory of basis reduction in Diophantine approximations; the method outperforms prior integer based computation without sacrificing accuracy (subject to machine epsilon).

We suggest an approach based on geometric invariant theory to the fundamental lower bound problems in complexity theory concerning formula and circuit size. Specifically, we introduce the notion of a partially stable point in a reductive-group representation, which generalizes the notion of stability in geometric invariant theory due to Mumford [Geometric Invariant Theory, Springer-Verlag, Berlin, 1965]. Then we reduce fundamental lower bound problems in complexity theory to problems concerning infinitesimal neighborhoods of the orbits of partially stable points. We also suggest an approach to tackle the latter class of problems via construction of explicit obstructions.