The Info List - Donald B. Gillies

--- Advertisement ---

Donald Bruce Gillies (October 15, 1928 – July 17, 1975) was a Canadian mathematician and computer scientist, known for his work in game theory, computer design, and minicomputer programming environments.


1 Education 2 Early career 3 Later career 4 In memoriam 5 Students 6 See also 7 References 8 External links

Education[edit] Donald B. Gillies
Donald B. Gillies
was born in Toronto, Ontario, Canada
and attended the University of Toronto
University of Toronto
Schools, a laboratory school originally affiliated with the University. Students at this Ontario school skipped a year ahead and so he finished his 13th-grade studies at the age of 18. Gillies attended the University of Toronto
University of Toronto
(1946–1950), intending to major in Languages and started his first semester taking seven different language courses. In his second semester he quickly switched back to majoring in Mathematics
which was his love while in high school. During his time as an undergraduate, he spent a great deal of time at the U-Toronto Computation Center. In the Putnam exam competition of 1950, Gillies was stunned at not being selected by the faculty to compete with the U-Toronto team. To avenge himself, Gillies placed in the top 10 in North America, following his University of Toronto classmates John P. Mayberry and Richard J. Semple who were top 5 Putnam Fellows. Toronto would likely have won the competition in 1950 had Gillies been on the faculty-designated team.[1] For graduate school, Gillies applied to the University of Illinois University of Illinois
University of Illinois
at Urbana-Champaign, which was "a very busy place building lots of computers". While he was there, he began working on the ORDVAC/ Illiac I
Illiac I
project. After one year of graduate school (1951), Gillies transferred to Princeton University
Princeton University
to work with John von Neumann, at the urging of and also to be with John P. Mayberry, who was also studying under John von Neumann. Gillies and Mayberry were both arch-rivals and best friends,[2] and after Mayberry beat Gillies in the Putnam exam, each competed to finish their PhD degree first. At Princeton Gillies met his future wife, Alice E. Dunkle, and began dating her, but after several months, their relationship fizzled. Miss Dunkle, knowing of the rivalry between Mayberry and Gillies, intentionally flirted with Mayberry, who subsequently approached Gillies to ask if he was still dating her. This tactic, used only once, led to their eventual marriage. During his graduate studies, and after working with von Neumann, Gillies became a fan of the book "One-upmanship" by Stephen Potter. John von Neumann
John von Neumann
was also a fan of this work, and was extremely successful at impressing others with his intelligence. An apocryphal math problem asks about a bumble bee flying back and forth between two approaching trains, and how far did it fly before colliding? When von Neumann gave the correct answer, the questioner asked if he used a standard time/rate-of-travel trick, and he replied, 'no, I summed the infinite series in my head' to impress the questioner. This method of impressing and astonishing others appealed to both Gillies and von Neumann. During his time at Princeton his interest area was computer design first and mathematics second. He continued to work with U-Illinois researchers and participated the check-out of the ORDVAC
Computer (from U-Illinois) at Aberdeen Proving Ground
Aberdeen Proving Ground
in Maryland, in the summer of 1951. At one point during his graduate studies, Von Neumann found out that Gillies had been spending time working on an Assembler (something that had not yet been invented). Von Neumann became enraged and told Gillies to stop work immediately because computers would never be used to perform such menial tasks.[3] After only two years of study at Princeton, Gillies completed his PhD before Mayberry, at age 25, in 1953, which was published in Contributions to the theory of games, vol.2 — in which he characterized the core which is the set of stable solutions in a non-zero sum game.[4] Early career[edit] Gillies then went to England for two years to work for the NRDC (National Research Development Corporation) and worked with an early Ferranti Pegasus
Ferranti Pegasus
computer there. This was done at a time when the U.S. government was drafting young people of all kinds—including Canadians—into service in the Korean War. In later years, after he returned to the U.S., the government would again try to draft Gillies, who at one point was forced to make a presidential appeal not to serve in the military. When Gillies returned to the USA in 1956 he received a 1-A draft status which persisted until he was age 36. Upon returning to the USA, Gillies married Alice E. Dunkle and began a job as a professor at the University of Illinois
University of Illinois
at Urbana-Champaign.[5] In early October 1957 the Soviet Military launched Sputnik I, and caused a widespread panic across the United States. Just hours later the UIUC
Astronomy Department[6] rigged an ad-hoc interferometer to measure signals from the satellite. The astronomers approached Dr. Gillies and Dr Jim Snyder to program the ILLIAC I
computer to calculate the satellite orbit from this data. The programming and calculation was completed in under two days. The very rapid publication of the ephemeris (orbit) in the journal Nature[7]—just a month after satellite launch—helped to dispel some of the fear created by the Sputnik launch by the Soviet Union. It also lent credence to the (likely false) idea that the Sputnik launch was part of an organized effort to dominate space.[8] Gillies wrote 3 patents in the late 1950s. One of them laid out all the details of how to implement a base register for program relocation in computers—before it had been done. He considered these patents as kind of a joke, and assigned the rights of the patents to IBM, without taking fees for this service. This kept the ideas from being patented by others which would have hindered progress in the computer industry. Starting in 1958, Gillies designed the 3-stage pipeline control of the ILLIAC II supercomputer at the University of Illinois. The control circuitry consisted of advanced control, delayed control, and interplay. This work was in the public domain, and competed with the Stretch computer system design from IBM that is often credited with inventing pipelining. This work was presented in a 1962 Michigan conference on computer design, "On the design of a very high speed computer" [9]

The Math Department at UIUC
celebrated the new primes with a postal meter cancellation stamp — until Appel and Haken proved the 4-color theorem in 1976.

As the main designer of the pipelined control circuitry for ILLIAC II, Gillies developed the algorithms for the month-long checkout and acceptance testing of the new computer. To draw attention to this new computer design in the field of mathematics, he wrote a mersenne prime-number algorithm and found 3 new Mersenne primes, and published them in a paper, "Three new Mersenne primes
Mersenne primes
and a statistical theory." [10] The new Mersenne primes
Mersenne primes
were reported in the Guinness Book of World Records, and the largest one was immortalized on all mail sent from the Post Office (Annex) at the Math department of the University of Illinois. In the same paper, Gillies made a conjecture about the distribution of prime divisors of Mersenne numbers. Later career[edit] In the late 1960s, Gillies became concerned that students were not getting direct access to computers any more. He lobbied UIUC
to adopt the 1968 WATFOR one-pass FORTRAN compiler / runtime system from the University of Waterloo
University of Waterloo
in Ontario. This was a fast-turnaround IDE for batch-based mainframe computers. At the time it was common practice to submit a job (card deck) and pick up the results the next day. The WATFOR compiler could compile, link, and run a short program in the compiler's memory space in a few seconds. This compiler allowed the university to offer underclass programming courses not only to computer scientists but also to business majors and to other non-specialists. Gillies and his family traveled to Waterloo to pick up a magtape with this compiler, on one of his visits to see his family, in the early 1970s. In 1969, Gillies received a preprint of Wirth's "Pascal User Manual and Report" and launched a project to build the first Pascal compiler written in North America. Ian Stocks was one of the graduate students who worked on this fast-turnaround in-memory 2-pass compiler, and the compiler (for the Digital Equipment PDP-11
minicomputer) was completed in the early 1970s. This work was part of the " PDP-11
Playpen" project which focused on getting graduate students direct access to low-cost computer hardware, such as the PDP-11/23, where the Pascal compiler ran. Two years later at the urging of his new graduate student, Greg Chesson, Gillies became in 1974 the first licensee for the UNIX operating system from Bell Labs.[11] [12] Chesson went on to be the third person to edit the Unix
kernel and was the eighth hire at Silicon Graphics Inc.. In memoriam[edit] Gillies died unexpectedly at age 46 on July 17, 1975, of a rare viral myocarditis. Digital Equipment Corporation and many of his friends, colleagues, and family contributed money for the Donald B. Gillies Memorial Lectureship In Computer Science, at the University of Illinois at Urbana Champaign. This annual lectureship continues until this day. In 1994, the Nobel Memorial Prize in Economic Sciences
Nobel Memorial Prize in Economic Sciences
was awarded to John Forbes Nash. In the Nash Seminar,[13] Gillies (who was at Princeton at the same time, and was friends with Nash) was mentioned as a pioneer in the field of game theory. Nash proved the existence of stable solutions for non-zero sum games; Gillies and Shapley extended this work by characterizing the core which is the set of stable solutions that cannot be improved by a coalition. In 2006 the Donald B. Gillies
Donald B. Gillies
Chair Professorship was established in the department of Computer Science
Computer Science
at the University of Illinois. A generous donation from Lawrence (Larry) White, a former student, established this chair. The first professor to hold this chair is Lui Sha, a well-known authority on real-time and embedded systems. In 2011, the UIUC
Department of Computer Science
Computer Science
awarded a Memorial Achievement Award[14] to Gillies, and family members accepted the award on his behalf at the Urbana-Champaign campus. Students[edit]

Greg Chesson Ian Stocks Al Davis Many others, some in the UIUC

See also[edit]

History of computing Largest known prime number


^ L.E. Bush, William Lowell Putnam Mathematical Competition, American Math Monthly Vol 57 No 7 (Aug-Sep 1950) pp 467-470 ^ Kuhn, H. W.; Tucker, A. W.., eds. (1953). "Two variants of Poker, D. B. Gillies, J. P. Mayberry, and J. von Neumann". Contributions to the Theory of Games. 2. pp. 13–51.  ^ Douglas Jones (U-Iowa Faculty), alt.folklore.computers, 14 July 2000 ^ Kuhn, H. W.; Tucker, A. W.., eds. (1953). "Discriminatory and Bargaining Solutions to a class of Symmetric n-Person Games, D. B. Gillies". Contributions to the Theory of Games. 2. pp. 325–342.  ^ Engagement Announcement (New York Times), Alice E. Dunkle is Betrothed to Donald Gillies, a Mathematician, December 10, 1955. ^ A HISTORY OF ASTRONOMY AT ILLINOIS ^ I. R. King, G. C. McVittie, G. W. Swenson, Jr., and S. P. Wyatt, Jr., "Further observations of the first satellite," Nature, No. 4593, November 9, 1957, p. 943. ^ Vladimir Isachenov (AP), Secrets of Sputnik Launch Revealed, October 1, 2007. ^ Gillies, Donald B.; Meagher, Ralph E.; Muller, David E.; McKay, R.W.; Nash, Jack P.; Robertson, James E.; Taub, Abe H. (October 1957). "On the design of a very high-speed computer". UIUC
Dept. of CS Technical Report no. 80. doi:10.2172/4311370.  ^ Gillies, Donald B. (Jan 1964). "Three new Mersenne primes
Mersenne primes
and a statistical theory". Mathematics
of Computation. 18 (5): 93. doi:10.2307/2003409. JSTOR 2003409.  ^ Greg Chesson, Personal communication to Donald W. Gillies, Spring 1995, 115 Waverley Street, Palo Alto, CA ^ Thompson, Ken (16 Sep 2014). "personal communication, Ken Thompson to Donald W. Gillies". UBC ECE Website.  ^ Nash Seminar ^ Memorial Achievement Award Archived 2015-03-18 at Archive.is

External links[edit]

Donald B. Gillies
Donald B. Gillies
at the Mathematics
Genealogy Project Donald B. Gillies
Donald B. Gillies
Memorial Lecture ( UIUC
CS Dept.), Donald B. Gillies Memorial Lecture ( UIUC
Math Dept.) University of Illinois
University of Illinois
Computing Timeline At the dawn of the space age ( UIUC
Astronomy Dept.) Sputnik's Secret History Finally Revealed (AP via FOX News, October 1, 2007) Mersenne Primes History, Theorems and Lists Donald B. Gillies
Donald B. Gillies
chair professorship at the University of Illinois
University of Illinois
at Urbana-Champaign Five Mathematics
PhDs granted by Donald B. Gillies, 1965-1973 Donald B. Gillies, Three New Mersenne Primes and a Statistical Theory, Mathematics
of Comput., Vol. 18:85 (Jan. 1964), pp. 93-97. Ian Stocks and Jayant Krishnaswamy, On a transportable high level language for minicomputers, ACM SIGMINI/SIGPLAN Conference, March 1976[permanent dead link] On a transportable high level language for minicomputers

v t e

Topics in game theory


Cooperative game Determinacy Escalation of commitment Extensive-form game First-player and second-player win Game complexity Graphical game Hierarchy of beliefs Information set Normal-form game Preference Sequential game Simultaneous game Simultaneous action selection Solved game Succinct game

Equilibrium concepts

Nash equilibrium Subgame perfection Mertens-stable equilibrium Bayesian Nash equilibrium Perfect Bayesian equilibrium Trembling hand Proper equilibrium Epsilon-equilibrium Correlated equilibrium Sequential equilibrium Quasi-perfect equilibrium Evolutionarily stable strategy Risk dominance Core Shapley value Pareto efficiency Gibbs equilibrium Quantal response equilibrium Self-confirming equilibrium Strong Nash equilibrium Markov perfect equilibrium


Dominant strategies Pure strategy Mixed strategy Strategy-stealing argument Tit for tat Grim trigger Collusion Backward induction Forward induction Markov strategy

Classes of games

Symmetric game Perfect information Repeated game Signaling game Screening game Cheap talk Zero-sum game Mechanism design Bargaining problem Stochastic game n-player game Large Poisson game Nontransitive game Global game Strictly determined game Potential game


Chess Infinite chess Checkers Tic-tac-toe Prisoner's dilemma Optional prisoner's dilemma Traveler's dilemma Coordination game Chicken Centipede game Volunteer's dilemma Dollar auction Battle of the sexes Stag hunt Matching pennies Ultimatum game Rock–paper–scissors Pirate game Dictator game Public goods game Blotto game War of attrition El Farol Bar problem Fair division Fair cake-cutting Cournot game Deadlock Diner's dilemma Guess 2/3 of the average Kuhn poker Nash bargaining game Prisoners and hats puzzle Trust game Princess and Monster game Rendezvous problem


theorem Nash's theorem Purification theorem Zermelo's theorem Folk theorem Revelation principle Arrow's impossibility theorem

Key figures

Albert W. Tucker Amos Tversky Ariel Rubinstein Claude Shannon Daniel Kahneman David K. Levine David M. Kreps Donald B. Gillies Drew Fudenberg Eric Maskin Harold W. Kuhn Herbert Simon Hervé Moulin Jean Tirole Jean-François Mertens John Harsanyi John Maynard Smith Antoine Augustin Cournot John Nash John von Neumann Kenneth Arrow Kenneth Binmore Leonid Hurwicz Lloyd Shapley Melvin Dresher Merrill M. Flood Oskar Morgenstern Paul Milgrom Peyton Young Reinhard Selten Robert Axelrod Robert Aumann Robert B. Wilson Roger Myerson Samuel Bowles Thomas Schelling William Vickrey

See also

All-pay auction Alpha–beta pruning Bertrand paradox Bounded rationality Combinatorial game theory Confrontation analysis Coopetition First-move advantage in chess Game mechanics Glossary of game theory List of game theorists List of games in game theory No-win situation Solving chess Topological game Tragedy of the commons Tyranny of small decisions

Authority contro