Merrill Meeks Flood (1908 – 1991) was an American mathematician, notable for developing, with Melvin Dresher, the basis of the game theoretical Prisoner's dilemma model of cooperation and conflict while being at RAND in 1950 (Albert W. Tucker gave the game its prison-sentence interpretation, and thus the name by which it is known today).
Melvin Dresher (Dreszer) was a Polish-born American mathematician, notable for developing, with Merrill Flood, the game theoretical model of cooperation and conflict known as the Prisoner's dilemma while at RAND in 1950.
Game theory is the study of mathematical models of strategic interaction between rational decision-makers. It has applications in all fields of social science, as well as in logic and computer science. Originally, it addressed zero-sum games, in which one person's gains result in losses for the other participants. Today, game theory applies to a wide range of behavioral relations, and is now an umbrella term for the science of logical decision making in humans, animals, and computers.
The prisoner's dilemma is a standard example of a game analyzed in game theory that shows why two completely rational individuals might not cooperate, even if it appears that it is in their best interests to do so. It was originally framed by Merrill Flood and Melvin Dresher while working at RAND in 1950. Albert W. Tucker formalized the game with prison sentence rewards and named it "prisoner's dilemma", presenting it as follows:
Two members of a criminal gang are arrested and imprisoned. Each prisoner is in solitary confinement with no means of communicating with the other. The prosecutors lack sufficient evidence to convict the pair on the principal charge, but they have enough to convict both on a lesser charge. Simultaneously, the prosecutors offer each prisoner a bargain. Each prisoner is given the opportunity either to betray the other by testifying that the other committed the crime, or to cooperate with the other by remaining silent. The offer is:
Flood received an MA in mathematics at the University of Nebraska, and a PhD at Princeton University in 1935 under the supervision of Joseph Wedderburn, for the dissertation Division by Non-singular Matric Polynomials.
Princeton University is a private Ivy League research university in Princeton, New Jersey. Founded in 1746 in Elizabeth as the College of New Jersey, Princeton is the fourth-oldest institution of higher education in the United States and one of the nine colonial colleges chartered before the American Revolution. The institution moved to Newark in 1747, then to the current site nine years later, and renamed itself Princeton University in 1896.
Joseph Henry Maclagan Wedderburn FRSE FRS was a Scottish mathematician, who taught at Princeton University for most of his career. A significant algebraist, he proved that a finite division algebra is a field, and part of the Artin–Wedderburn theorem on simple algebras. He also worked on group theory and matrix algebra.
In the 1930s he started working at Princeton University, and after the War he worked at the Rand Corporation, Columbia University, the University of Michiganand the University of California.
Columbia University is a private Ivy League research university in Upper Manhattan, New York City. Established in 1754, Columbia is the oldest institution of higher education in New York and the fifth-oldest institution of higher learning in the United States. It is one of nine colonial colleges founded prior to the Declaration of Independence, seven of which belong to the Ivy League. It has been ranked by numerous major education publications as among the top ten universities in the world.
The University of Michigan, often simply referred to as Michigan, is a public research university in Ann Arbor, Michigan. The university is Michigan's oldest; it was founded in 1817 in Detroit, as the Catholepistemiad, or University of Michigania, 20 years before the territory became a state. The school was moved to Ann Arbor in 1837 onto 40 acres (16 ha) of what is now known as Central Campus. Since its establishment in Ann Arbor, the university campus has expanded to include more than 584 major buildings with a combined area of more than 34 million gross square feet spread out over a Central Campus and North Campus, two regional campuses in Flint and Dearborn, and a Center in Detroit. The university is a founding member of the Association of American Universities.
The University of California (UC) is a public university system in the U.S. state of California. Under the California Master Plan for Higher Education, the University of California is a part of the state's three-system public higher education plan, which also includes the California State University system and the California Community Colleges System.
In the 1950s Flood was one of the founding members of TIMS and its second President in 1955. End 1950s he was among the first members of the Society for General Systems Research. In 1961, he was elected President of the Operations Research Society of America (ORSA), and from 1962 to 1965 he served as Vice President of the Institute of Industrial Engineers. In 1983 he was awarded ORSA's George E. Kimball Medal.
Flood is considered a pioneer in the field of management science and operations research, who has been able to apply their techniques to problems on many levels of society. According to Xu (2001) "as early as 1936–1946, he applied innovative systems analysis to public problems and developed cost-benefit analysis in the civilian sector and cost effectiveness analysis in the military sector".
Management science (MS) is the broad interdisciplinary study of problem solving and decision making in human organizations, with strong links to management, economics, business, engineering, management consulting, and other sciences. It uses various scientific research-based principles, strategies, and analytical methods including mathematical modeling, statistics and numerical algorithms to improve an organization's ability to enact rational and accurate management decisions by arriving at optimal or near optimal solutions to complex decision problems. Management science helps businesses to achieve goals using various scientific methods.
Operations research, or operational research (OR) in British usage, is a discipline that deals with the application of advanced analytical methods to help make better decisions. Further, the term operational analysis is used in the British military as an intrinsic part of capability development, management and assurance. In particular, operational analysis forms part of the Combined Operational Effectiveness and Investment Appraisals, which support British defense capability acquisition decision-making.
The Merriam-Webster dictionary defines system analysis as "the process of studying a procedure or business in order to identify its goals and purposes and create systems and procedures that will achieve them in an efficient way". Another view sees system analysis as a problem-solving technique that breaks down a system into its component pieces for the purpose of the studying how well those component parts work and interact to accomplish their purpose.
In the 1940s Flood publicized the name Traveling salesman problem (TSP) within the mathematical community at mass. Flood publicized the traveling salesman problem in 1948 by presenting it at the RAND Corporation. According to Flood "when I was struggling with the problem in connecting with a school-bus routing study in New Jersey".
Even more important, as far as common usage goes, Dr. Flood himself claimed to have coined the term "software" in the late 1940s.
Equally at home in his original field of the mathematics of matrices and in the pragmatic trenches of the industrial engineer, his research addressed an impressive array of operations research problems. His 1953 paper on the Hitchcock transportation problem is often cited, but he also published work on the traveling salesman problem, and an algorithm for solving the von Neumann hide and seek problem.
George Bernard Dantzig was an American mathematical scientist who made contributions to industrial engineering, operations research, computer science, economics, and statistics.
The travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science.
Allen Newell was a researcher in computer science and cognitive psychology at the RAND Corporation and at Carnegie Mellon University’s School of Computer Science, Tepper School of Business, and Department of Psychology. He contributed to the Information Processing Language (1956) and two of the earliest AI programs, the Logic Theory Machine (1956) and the General Problem Solver (1957). He was awarded the ACM's A.M. Turing Award along with Herbert A. Simon in 1975 for their basic contributions to artificial intelligence and the psychology of human cognition.
Albert William Tucker was a Canadian mathematician who made important contributions in topology, game theory, and non-linear programming.
Lloyd Stowell Shapley was an American mathematician and Nobel Prize-winning economist. He contributed to the fields of mathematical economics and especially game theory. Shapley is generally considered one of the most important contributors to the development of game theory since the work of von Neumann and Morgenstern. With Alvin E. Roth, Shapley won the 2012 Nobel Memorial Prize in Economic Sciences "for the theory of stable allocations and the practice of market design."
Harold William Kuhn was an American mathematician who studied game theory. He won the 1980 John von Neumann Theory Prize along with David Gale and Albert W. Tucker. A former Professor Emeritus of Mathematics at Princeton University, he is known for the Karush–Kuhn–Tucker conditions, for Kuhn's theorem, for developing Kuhn poker as well as the description of the Hungarian method for the assignment problem. Recently, though, a paper by Carl Gustav Jacobi, published posthumously in 1890 in Latin, has been discovered that anticipates by many decades the Hungarian algorithm.
David Gale was an American mathematician and economist. He was a professor emeritus at the University of California, Berkeley, affiliated with the departments of mathematics, economics, and industrial engineering and operations research. He has contributed to the fields of mathematical economics, game theory, and convex analysis.
Philip McCord Morse, was an American physicist, administrator and pioneer of operations research (OR) in World War II. He is considered to be the father of operations research in the U.S.
Thomas L. Magnanti is an American engineer and Institute Professor and former Dean of the School of Engineering at the Massachusetts Institute of Technology. Magnanti served as President of the Singapore University of Technology and Design from 2009 to 2017.
George Elbert Kimball was an American professor of quantum chemistry, and a pioneer of operations research algorithms during World War II.
Harold Adrian Linstone was a German-American mathematician, consultant, futurist and University Professor Emeritus of Systems Science at Portland State University and a specialist in applied mathematics.
RAND Corporation is an American nonprofit global policy think tank created in 1948 by Douglas Aircraft Company to offer research and analysis to the United States Armed Forces. It is financed by the U.S. government and private endowment, corporations, universities and private individuals. The company has grown to assist other governments, international organizations, private companies and foundations, with a host of defense and non-defense issues, including healthcare. RAND aims for interdisciplinary and quantitative problem solving by translating theoretical concepts from formal economics and the physical sciences into novel applications in other areas, using applied science and operations research.
Selmer Martin Johnson was an American mathematician, a researcher at the RAND Corporation.
George Lann Nemhauser is an American operations researcher, the A. Russell Chandler III Chair and Institute Professor of Industrial and Systems Engineering at the Georgia Institute of Technology and the former president of the Operations Research Society of America.
Egon Balas was an applied mathematician and a professor of industrial administration and applied mathematics at Carnegie Mellon University. He was the Thomas Lord Professor of Operations Research at Carnegie Mellon's Tepper School of Business and did fundamental work in developing integer and disjunctive programming.
Andrew Vázsonyi (1916–2003), also known as Endre Weiszfeld and Zepartzatt Gozinto) was a Hungarian mathematician and operations researcher. He is known for Weiszfeld's algorithm for minimizing the sum of distances to a set of points, and for founding The Institute of Management Sciences.
William Wager Cooper was an American operations researcher, known as a father of management science and as "Mr. Linear Programming". He was the founding president of The Institute of Management Sciences, founding editor-in-chief of Auditing: A Journal of Practice and Theory, a founding faculty member of the Graduate School of Industrial Administration at the Carnegie Institute of Technology, founding dean of the School of Urban and Public Affairs at CMU, the former Arthur Lowes Dickinson Professor of Accounting at Harvard University, and the Foster Parker Professor Emeritus of Management, Finance and Accounting at the University of Texas at Austin.
The Steiner traveling salesman problem is an extension of the traveling salesman problem, one of the fundamental combinatorial optimization problems. Given a list of cities, some of which are required, and the lengths of the roads between them, the goal is to find the shortest possible walk that visits each required city and then returns to the origin city. As we are looking for a walk, vertices can be visited more than once, and edges may be traversed more than once.
David L. Applegate is a computer scientist known for his research on the traveling salesperson problem.