International Conference on Operations Research and Decision Science
(ICORDS 2025)

Difficult Combinatorial Optimization problems like the symmetric travelling salesman problem, have been identified as challenges by computational complexity theorists and applied operations researchers. However, such problems have been solved routinely in practice to ensure that the computational burden is not too much and the optimality is not compromised severely. Are these problems theoretically solvable by polynomial time algorithms?, is a million dollar question. A recent book by the speaker published by Springer* contains a proof of the polynomial solvability, and it has not yet been published as a journal article. However, the proof crystallized during the last stages of publication of the book requires additional validation by experts. This conference presentation traces that proof. It is a fitting tribute to Professor TES Raghavan on his eightieth birthday, as he has been my well wisher since I joined the Indian Statistical Institute as a student sixty years ago.

In 1972, Hoffman initiated the study of limit points of eigenvalues of nonnegative symmetric integer matrices and posed the question of finding all limit points of the set of spectral radii of all nonnegative symmetric integer matrices. In the same article, the author showed that it is enough to consider the adjacency matrices of simple graphs to study the limit points of spectral radii. Since then, many researchers have worked on similar problems, considering various specific eigenvalues such as the least eigenvalue, the k-th largest eigenvalue, and the k-th smallest eigenvalue, among others. Motivated by this, we ask the question, “which real numbers are the limit points of the set of the smallest positive eigenvalues (respectively, the largest negative eigenvalues) of graphs?” In this talk, we provide a complete answer to this question by proving that any non-negative (respectively, nonpositive) real number is a limit point of the set of all smallest positive eigenvalues (respectively, largest negative eigenvalues) of graphs. We also show that the union of the sets of limit points of the smallest positive eigenvalues and the largest negative eigenvalues of graphs is dense in $\mathbb{R}$.

Consider a seller who wishes to sell $n$ items to $m$ buyers, whose valuations for the items are additive. The distribution of the valuations of the buyer are assumed to be common knowledge, but the exact valuation for each item is the buyer’s private information. The seller naturally wishes to maximize his expected revenue. This leads to the problem of optimal auction design in multi-item multi-buyer setting.

The problem in the one-item setting was solved by Roger Myerson in 1981. He showed that the optimal mechanism under any distribution turns out to be a second price auction mechanism but with the bids being the virtual valuations and not the actual valuations of the buyers. In the single buyer setting, Myerson showed that the optimal mechanism is a take-it-or-leave-it offer for a reserve price $p$ that depends on the distribution of the valuation of the buyer.

The problem in the two-item setting though, is not that straightforward, and thus remains unsolved till date even in the single buyer case. The solutions are known for certain distributions such as uniform, exponential, and beta distribution. In this talk, I will begin by explaining the Myerson’s optimal mechanism for the one-item setting, point out the difficulties in extending the same solution to the two-item setting, and then explain the method to construct the solution for certain distributions.

We examine almost (strictly) semimonotone matrices which are also either Z-matrices or matrices having Property (++) and show that both parts of Wendler’s conjecture [Spec. Matrices 7 (2019) 291–303] hold for these matrices. We discuss some interesting properties related to the structure of almost (strictly) semimonotone matrices. We also present results pertaining to the existence and multiplicity of solutions to the linear complementarity problem which provides a unified framework to study various mathematical programming problems like the linear and quadratic programming problems as well as the bimatrix game.

This lecture will begin with reminiscences of the guidance I had received from my PhD advisor, T.E.S. Raghavan, in the late 1970s and in subsequent interactions spanning several decades. I welcome this opportunity to express my gratitude for the wisdom, kindness and friendship of such a great scholar and teacher on his 85th birthday.

One mathematical object I encountered during my PhD on Stochastic Games was the so-called Puiseux series (a fractional power series). Over the next four decades this object kept recurring in several seemingly unrelated studies. Most recently, in my investigations of risk sensitivity.

One simple notion of risk is simply the probability of some random variable falling below (or above) some designated threshold. This is what motivates the “threshold risk problem”.

On some level the problem is at least as old as the history of agriculture with farmers being concerned about rainfall falling below some acceptable level, or onset of frost; a prototypical tipping point for successful cultivation of certain crops. More recently, concerns about climate change induced global warming focused on the level of such warming exceeding thresholds such as 1.5 or 2.0 degrees C, by the year 2030 or 2050.

Because of the ubiquity of applications, it would be reasonable to assume that mathematical properties of threshold risk have been fully understood long ago. Yet, we encountered two separate applications – one in hospital admissions and another in fishery modelling – where threshold risk exhibited a characteristic extreme parametric sensitivity phenomenon which we could not easily explain.

This led to a deeper, and a more mathematically abstract, investigation of this phenomenon. Specifically, we considered the problem of parametric sensitivity of risk, with respect to a threshold parameter δ. Such threshold risk was modelled as the probability of a δ−perturbed function of a random variable falling below 0. We demonstrated that for polynomial and rational functions of that random variable there exist at most finitely many risk critical points. The latter are those special values of the threshold parameter for which rate of change of risk is unbounded as δ approaches them. Under weak conditions, we characterised candidates for risk critical points as zeroes of either the discriminant of a relevant δ−perturbed polynomial, or of its leading coefficient, or both. We named these important equations as “hidden equations of risk critical thresholds”, because some knowledge of algebra and analysis, including Puiseux series, is required to discover them. We also supplied extensions to multi-parameter threshold risk.

This is a joint work with Vladimir Ejov and Zhihao Qiao.

Multi-objective problems arise naturally in most decision models. Efficient sets (Pareto frontier) are the sets of non-dominated solutions. A solution point from the efficient set is usually identified by linear (or nonlinear) scalarization methods by casting these multi-objective problems as classical single objective problems. Many a time, these objective functions are of different nature and for such cases, scalarizations are not suitable. For such scenarios, we define a solution based on minmax criteria; a solution from the efficient set that minimizes the maximum loss of efficiency. We also propose a method that considers the relative loss of efficiencies. We next consider Markov decision models with average and discounted criteria. For moderate and low discount rates, these two criteria are distinctly different as average criteria captures the asymptomatic reward behaviour while the discounted criteria focuses on the transient rewards. For MDPs under some regularity conditions, we show that an efficient policy that minimizes the maximum relative loss of efficiency can be identified by a Linear Program. We also discuss many open problems in this direction.

In theoretical cooperative game theory we assume important primitives to be given by some ‘oracle’ in order to concentrate on the distribution of the benefits of cooperation among all players. Even under such ideal circumstances, the computation of an actual solution may be time-
consuming as for instance the nucleolus, the Shapley value or the core become increasingly hard to determine as the number of agents increases.

In cooperative transportation games (CTGs) computing the worth of a coalition may involve solving a traveling salesman or vehicle routing problem which are NP-hard, and there are exponentially many worths to determine. We therefore deal with the situation that a solution for a CTG is required before the ‘oracle’ has determined all primitives. An inductive nucleolus is determined on a series of auxiliary games.

First, the worth of the grand coalition is determined which (by assumption) is always possible, and this worth is taken equal for all auxiliary games. While the time constraint is not met, the worths for all coalitions with cardinality 1 are computed, then for those with cardinality 2, and
so on. Each time computations of all worths for a certain cardinality are complete, an auxilliary game and its nucleolus are determined. If the computation time reaches the constraint while computing worths for coalitions with cardinality $U+1$, the nucleolus of the auxilliary game based on the completed calculations up to $U$ is reported as the inductive nucleolus of the game. If the time constraint is not binding, the inductive nucleolus coincides with the nucleolus, which is reported as the solution.

We show that the inductive nucleolus satisfies attractive axioms, especially those that incorporate aspects of fairness for computations being based on this type of restricted information.

Shapley (1953), in his seminal paper on stochastic games, mentioned that stochastic games (in general) do not have the orderfield property. Parthasarathy and Raghavan (1981) were the first to identify a class of stochastic games with the orderfield property. This spawned a flurry of research on identifying classes of stochastic games with the orderfield property and in designing algorithms to solve them. In this talk, we shall review some of these works, especially of Prof. T.E.S. Raghavan and his co-authors, and we shall discuss some relatively new and ongoing research in this direction. For example, some mixtures of classes of stochastic games have the orderfield property. Acyclic stochastic games have the orderfield property. But not all cycles disrupt the orderfield property. Stochastic games with “simple” cycles have the orderfield property. We shall also discuss ongoing research to design efficient algorithms for solving some classes of stochastic games.

References:
(1) Shapley, L. S. (1953). Stochastic Games. Proceedings of the National Academy of Sciences, 39, 1095–1100.
(2) Parthasarathy, T., and Raghavan, T.E.S. (1981). An orderfield property for stochastic games when one player controls transition probabilities. Journal of Optimization Theory and Applications, 33, 375–392.

A general duality theorem in a generalized conjugacy framework, which generalizes a classical result on the minimization of a convex function over a closed convex cone, is established. The main theorem yields two quasiconvex duality schemes; one of them is of the surrogate duality type and is applicable to problems having an evenly quasiconvex objective function, whereas the other one is applicable to problems with Lipschitz quasiconvex objective functions and yields duals whose objective functions do not involve any surrogate constraint. Using the Örst duality scheme, one obtains a surrogate duality theorem for weakly e¢ cient solutions of multiobjective optimization problems with evenly quasiconvex objectives.

In this talk we discuss on max-plus walk which is a walk model over the max-plus algebra through optimization and game theory models. Max-Plus algebraic modeling is useful in several fields like matrix algebra, cryptography, combinatorial optimization, multi-objective optimization, genetic algorithms, queueing theory. These models are used to study discrete event systems like subway traffic networks, parallel processing systems, telecommunication networks for many years. In fact, Max-plus algebra provides mathematical methods for solving nonlinear problems by using linear equations that arise in areas such as allocation of resources, and information processing technology. Several systems which are not linear in the conventional algebra turn out to be linear in max algebra and hence become amenable to mathematical treatment, similar to that we use for linear systems. In this talk, we revisit various optimization problems using methods based on max-plus algebra, which has maximization and addition as its basic arithmetic operations. We also present some new game theoretic applications of Max-Plus algebra.

Authors introduced the max-plus walk which is a walk model.

Public goods—such as parks, community centers, and digital infrastructure—are frequently under-provisioned due to the free-rider problem and poor coordination among budget-constrained agents. Welfare maximization can be examined in two settings: (i) when agents are truthful about their valuations, and (ii) when agents are strategic and may misreport them. In the truthful case, the problem generalizes participatory budgeting with quasi-linear utilities, where welfare maximization is tractable via an FPTAS. However, introducing even mild participation constraints makes the problem hard to approximate. In the strategic setting, there are refund-based mechanisms that aim to fund the welfare-optimal subset at equilibrium, and show that this is impossible under any monotone refund scheme. Finally, there are practical agent heuristics and simulations to evaluate the trade-off between social welfare and individual utility.

As the global economy continues to grow, the need for transportation also grows. Transportation researchers are developing new methods for integrating new technologies into existing transportation systems and for addressing the associated challenges. This paper addressed bi-objective fixed charge solid transportation problem that consider two objectives minimizing the total transportation cost, including fixed and variable costs, and minimizing the total transportation time. It is a challenging optimization problem, as it is difficult to find a solution that simultaneously minimizes both objectives. Additionally, the problem with bi-objective fixed-charge solid transportation problem (BOFCSTP) under uncertainty with neutrosophic concept is presented here. This problem constructed with all the parameters such as cost, fixed-charge, source availability and requirements as neutrosophic values. Neutrosophic sets are efficiently handling the indeterminacy and imprecise data in many fields and single-valued neutrosophic sets are extension and simpler form of NS. Further, to convert the neutrosophic values to crisp values a ranking function is used. To solve the considered BOFCSTP different approaches are employed namely, neutrosophic linear programming, neutrosophic goal programming, fuzzy goal programming to get the compromised solution to the problem. Additionally, a real-life problem is given with numerical example and the results compared with the different approaches.

The classification of growth curves is discussed. Using the classical Growth Curve model of Potthoff and Roy (1964) a likelihood approach is taken when classifying a new observation as belonging to one of several populations. In particular a new approach is proposed so that a new observation can be classified to not belong to any of the populations from where samples have been obtained.

Mathematical modeling plays a crucial role in optimizing complex decision-making processes. Petri Net Modeling and Simulation, a powerful tool in decision science, uses mathematical structures to represent dynamic systems and processes. By simulating various decision scenarios, Petri nets help identify optimal paths, predict outcomes, and manage uncertainties of the modelled system. This talk explores the integration of Petri net modeling with mathematical decision-making frameworks, demonstrating its application in fields like computer science, biological data analytics, data science, healthcare, manufacturing, and finance. Through case studies, we will highlight how mathematical modeling via Petri nets enhances decision optimization, risk management, and system efficiency.

Given a partially specified real symmetric matrix, there are infinitely many completions which are positive definite. Among these, the inverse of the unique matrix, with the maximum determinant value, has an interesting structural property. In this talk, I will present an exposition of this result and discuss some recent generalizations, that we have obtained.

Let $T$ be a tree with vertex set $V(T) = \{1, 2, \dots, n\}$. The \emph{Steiner distance} of a subset $S \subseteq V(T)$ of vertices of $T$ is defined to be the number of edges in a smallest connected subtree of $T$ that contains all the vertices of $S$. The \emph{2-Steiner distance matrix} $D_2(T)$ of $T$ is the $\binom{n}{2} \times \binom{n}{2}$ matrix whose rows and columns are indexed by subsets of vertices of size 2. The entry in the row indexed by $P$ and column indexed by $Q$ is equal to the Steiner distance of $P \cup Q$. We show that $\text{rank}(D_2(T)) = 2n – p – 1$, where $p$ is the number of pendant vertices (or leaves) in $T$. We construct a basis $B$ for the row space of $D_2(T)$ and obtain a formula for the inverse of the nonsingular square submatrix $D = D_2(T)[B, B]$. We also compute the determinant of $D$ and show that its absolute value is independent of the structure of $T$.

Two other matrices associated to Buneman’s Four Point Condition (4PC) about distances in a tree $T$ are the matrices $\text{MinT}$ and $\text{MaxT}$. These are also $\binom{n}{2} \times \binom{n}{2}$ matrices. The entry in the row indexed by $\{x, y\}$ and column $\{p, q\}$ equals the minimum or the maximum of the set $D_{p,q,x,y} = \{d_{x,y} + d_{p,q},\ d_{x,p} + d_{y,q},\ d_{x,q} + d_{y,p}\}$.

We show for all trees $T$, that $$D_2(T) = \frac{1}{2}(\text{MinT} + \text{MaxT})$$ and give our results on these three matrices.

Based on joint work with Ali Azimi, Rakesh Jana and Mukesh Nagar.

Consider a graph with edges colored red and blue. It was proved by Bhattacharya, Peled, and the speaker that a balanced sum of cycles is a (positive rational) sum of balanced subgraphs. We asked whether a balanced sum of cycles is a sum of balanced subgraphs. This was shown by Petrovic using the theory of toric ideals. It is an interesting problem to find a purely graph theoretic proof of this result.

This paper investigates how platform businesses can promote sustainable agricultural practices by managing farmer heterogeneity. It focuses on two distinct types of farmers – those who prioritize sustainability and those who do not – and examines how platforms can design operational strategies that encourage collaboration among them to scale sustainable practices.

The platform considered generates positive cross-side externalities: as more farmers collaborate and form groups, buyers’ willingness to pay increases, thereby benefiting the entire ecosystem. The paper makes two key contributions. First, it proposes a cooperative game-theoretic approach to designing a fair pricing mechanism on the platform. This approach involves reframing the pricing problem as a payoff allocation problem and determining fair pricing through the Shapley value that ensures equitable compensation for participating farmers. Second, the paper highlights that farmers prioritizing sustainability form coalitions and take joint actions, unlike the other types of sellers who are purely driven by individual self-interest and remain singleton. The central question addressed is: how can a stable coalition of sustainability-oriented farmers be formed and maintained on the platform? To answer this, the paper uses a cooperative game theory model of coalition formation.

Consider a common marine fishery, possibly divided into exclusive economic
zones of countries. Each of the countries fishes to maximize their profit, not taking
into account that its fishing effort generates ”the tragedy of the commons”. The Nash
equilibrium results in overexploitation, leading to depletion of the fishery, while it
is optimal to preserve it. We present a differential game modelling this process and
various ways to solve ”the tragedy”. Our main question is whether it is possible and
how to counteract ”the tragedy” if facing various limitations of real world economies.

To answer it, we derive regulatory tax-subsidy systems and self-enforcing environmental agreements in a problem of extraction of common renewable resources. The first considered limitation is that the feasible class of tax-subsidy systems may have a complicated form. Alternative limitation is that there is no institution that can impose taxes or subsidize, so sustainability can be achieved only by self-enforcing international agreements. Next limitation is in those agreements: we assume that it takes time to detect a defection. We study these enforcement tools in a continuous-time version of a Fish War type game with n countries, with fish indispensable for their economies. We calculate the social optimum, a Nash equilibrium and partial cooperation equilibria. The Nash equilibrium leads to depletion of fish, while the social optimum typically results in sustainability. For partial cooperation, only 2-country coalitions are stable. We calculate tax-subsidy systems that enforce maximization of joint payoff, also if there are additional constraints, and we propose an algorithm that looks for such a system in an arbitrary class of regulatory tax-subsidy systems. For the international agreement with imperfect monitoring, we are interested in the maximal detection delay for which the agreement remains self-enforcing.

Counter-intuitively, the more players, the more stable the agreement
The talk is mainly based on results of [1].
[1] A. Wiszniewska-Matyszkiel, R. Singh, 2024, How to avoid the tragedy of the
commons in an imperfect world, Journal of Public Economic Theory 2024;26:e12713,
https://doi.org/10.1111/jpet.12713