Game Theory and Applications in Lisbon, October 25-27, 2018

The Lisbon Meetings in Game Theory and Applications #10. The Anniversary Edition​. October 25-27, 2018

The program is here.

I'll be speaking at noon on Friday, with a working title of
Game theory in a large world:  Market design, and the example of kidney exchange

The announcement says:
"The UECE Lisbon Meetings in Game Theory and Applications are an annual event that brings together leading scholars doing theoretical or applied research in the field of game theory.

The first edition of the conference took place in 2009 and throughout the years it has become a reference event in the field, attracting renowned academics from all over the world.

In the tenth edition of the Lisbon Meetings, we are pleased to announce four keynote lectures  by

Prof. Itzhak Gilboa (HEC, Paris-Saclay, and Tel-Aviv University)
Prof. Itay Goldstein (University of Pennsylvania)
Prof. Alvin E. Roth (Stanford University)
Prof. Larry Samuelson (Yale University)

Prof. Gilboa will present the annual lecture in honor of the preeminent game theorist Jean-François Mertens

The organizing Committee
​
Filomena Garcia (Indiana University, ISEG/UECE)
Luca David Opromolla (Banco de Portugal, UECE)
Joana Pais (ISEG, UECE)
Joana Resende (CE-FUP, University of Porto)"


I also plan to give a short talk at a ceremony this evening,  about markets and market design along the lines of my book Who Gets What and Why (which was translated into Portugese as Como Funcionam Os Mercados }.


Here's a news story:
Teoria dos Jogos revoluciona ciência, economia e vida em sociedade
Prémio Nobel Alvin E. Roth cruza Teoria dos Jogos e transplante de rins

Envy free (not quite stable) matchings

It's hard for decentralized markets to achieve stable matchings (i.e. matchings with no blocking pairs) in the way that centralized clearinghouses can (and this is why we see some markets organized by clearinghouses).  So it's worthwhile looking at larger sets of outcomes, and in this paper we look at matchings such that any blocking pairs must involve an unfilled position--i.e. they are envy free in the sense that there are no blocking pairs in which some worker can take the job presently held by another worker.

Wu, Qingyun and Alvin E. Roth, “The Lattice of Envy-free Matchings,” Games and Economic Behavior, May 2018, 109, 201-211

The lattice of envy-free matchings

Author links open overlay panelQingyunWu1  Alvin E.Rothb

https://doi.org/10.1016/j.geb.2017.12.016Get rights and content

Highlights

•

Envy-free matchings are matchings that can only be unstable with respect to a blocking pair of a worker with a firm that has some unfilled positions.

•

These envy-free but unstable matchings may arise in the course of filling “vacancy chains” following a worker's retirement.

•

The set of envy free matchings is a lattice under the partial ordering of the common preferences of the workers.

Abstract

In a many-to-one matching model, we show that the set of envy-free matchings is a lattice. A Tarski operator on this lattice, which can be interpreted as modeling vacancy chains, has the set of stable matchings as its fixed points.

*************
Here's an ungated version of the paper.

Martin Shubik, 1926-2018

Ed Kaplan emails me with the sad news that Martin Shubik died yesterday.

Here's the first brief announcement from Yale School of Management:
Prof. Martin Shubik, Influential Game Theory Scholar, Dies

He was a pioneering game theorist, and a frequent collaborator with his graduate school roommate Lloyd Shapley. My understanding is that the two of them shared a double room, in a suite with John Nash. 

He suffered from a rare disease, Inclusion Body Myositis, and established a charity to organize research about it, Inclusion Body Myositis Registry at Yale.

He was a man of many parts. (See here, for example.)

Here are two photos I took of him at a Stonybrook conference in honor of Shapley. (In the second he must have been proving an especially difficult theorem...)

Martin Shubik in 2003

Two papers by Shapley and Shubik played important roles in areas in which I've worked:

The second (by publication date) was their landmark 1971 paper on matching as an assignment game (with all payments freely transferable), published in volume 1 number 1 of the International Journal of Game Theory: The assignment game I: The core

(Years after it was published, I asked Shapley what ever happened to part II, and his reply was "Never call a paper part I unless you have already written part II."  As I recall, he further said that the plan for the never-written part II had been to study the von Neumann-Morgenstern solutions of the assignment game.)

The first was their famous 1954 paper in the American Political Science Review, perhaps Shubik's most cited, on how to evaluate the strength of each position in "simple" coalitional games, in which every coalition is either 'winning' or 'losing'
A Method for Evaluating the Distribution of Power in a Committee System

I have many times used his model of escalation, The Dollar Auction Game, as an in-class demonstration of the importance of auction rules for auction outcomes and strategies.

Historians of game theory are sure to learn a lot from the archives of his papers and correspondence at Duke:
The Martin Shubik Papers: From Early Game Theory to the Strategic Analysis of War
************
Update: Yale SOM has now published a long, fond remembrance:
Remembering Prof. Martin Shubik, 1926–2018

Bob Wilson, Paul Milgrom and Dave Kreps on the future (and past) of Economics

An interview at Stanford GSB with three of the greatest game theorists. You can read it at this link:
The Future of Economics
Three award-winning economists talk about where the field has been and where it’s heading.

Related

David M. Kreps

Professor, Economics

Paul R. Milgrom

Professor (by courtesy), Economics

Robert Wilson

Professor Emeritus, Economics

John Roberts

Professor Emeritus, Economics

Israel celebrates Sergiu Hart

The Israel Prize goes to Sergiu Hart! Here's a picture of him I once took in Jerusalem:

Sergiu Hart

Here's the story from the Jerusalem Post:
PROF. SERGIU HART TO RECEIVE ISRAEL PRIZE IN ECONOMIC RESEARCH, STATISTICS

"Prof. Sergiu Hart of the Hebrew University will be awarded the Israel Prize for economic research and statistics, the Education Ministry announced on Thursday.
...
"In its decision, the prize committee called Prof. Hart – a former president of the World Association of Game Theory and member of the Academy of Sciences of Israel, Europe and the United States – one of the world’s leading economists.

“Prof. Hart specializes in the field of game theory and its comprehensive implications in various economic fields. Among other things, it has an important contribution to the understanding of the convergence to market equilibrium, the value of a player in the game, how cartels are created in the markets and the development of objective risk indices,” the committee wrote.

"In recent years, it added, Hart’s research has focused on “designing mechanisms such as tenders, which are important in online trade.”

"Hart was born in Bucharest, Romania, and immigrated to Israel at the age of 14 along with his family. After serving in the IDF, he received undergraduate and graduate degrees from Tel Aviv University in mathematics with honors before completing his post-Doctoral studies at Stanford University in California.

"In 1991, Hart founded the Center for the Study of Rationality at the Hebrew University, whose academic committee he now chairs.
“Under his leadership the center became a unique leader in the world in the study of game theory with its implications in a wide range of fields such as economics, statistics, psychology, law, biology, philosophy and more,” the prize committee wrote in its decision.

"The Israel Prize is largely regarded as the state’s highest honor. It is presented annually on Independence Day in a state ceremony in Jerusalem attended by the president, the prime minister, the Knesset speaker and the Supreme Court president."

Biological markets--from primates to cleaner wrasses to plants

Evolution as the designer of market exchange between and among members of different species: here's a Bloomberg article about the work of the primatologist Ronald Noe, the mathematical biologist Peter Hammerstein and a variety of other biologists.

The Secret Economic Lives of Animals
Wasps do it, baboons do it. Economics isn’t just a human activity.

"In 1994, Noë and Hammerstein laid out their new theory of biological markets in the journal Behavioral Ecology & Socialbiology. The paper fused the biologists’ different styles: Hammerstein developed the mathematical models, while Noë dug through the scientific literature for evidence from the field. Examples turned up across the animal kingdom. Male scorpion flies offer females a “nuptial gift” of prey before mating. In some species of bird, such as the purple martin, a male will allow another male to occupy part of his territory in exchange for help raising his young. Lycaenid butterfly caterpillars produce a sweet “nectar” whose only purpose is to attract ants, which eat the nectar and protect the caterpillars from predators.
...
"Noë and Hammerstein admit that one of the hardest parts of their theory is to fix quantities and exchange rates; most of the time they can only say how a change in supply and demand will influence an exchange. And they are also careful to draw distinctions between human and biological markets. Animals obviously can’t use currency or sign contracts. And the animal kingdom has no third-party institutions to punish cheaters. Evolution may have produced fish dentists, but it has yet to produce fish lawyers."


Here are my earlier posts about work by Ronald Noe

Tom Schelling (1921-2016)

Tom Schelling has passed away. Here's an obit in the Washington Post:
Thomas Schelling has died. His ideas shaped the Cold War and the world.

His 1960 book The Strategy of Conflict is one of the first books I read about game theory. It was both an introduction to game theory, and a critique of some of its conventional formulations. I still sometimes teach some of the experiments he wrote about there.

He shared the 2005 Nobel Prize in Economics with Bob Aumann

What is Happening in Game Theory? in the JEP

The Fall 2016 Journal of Economic Perspectives contains a

Symposium: What is Happening in Game Theory?

Game Theory in Economics and Beyond (#6) Larry Samuelson

Full-Text Access (Complimentary) | Supplementary Materials

New Directions for Modelling Strategic Behavior: Game-Theoretic Models of Communication, Coordination, and Cooperation in Economic Relationships (#7) Vincent P. Crawford

Full-Text Access (Complimentary) | Supplementary Materials

Whither Game Theory? Towards a Theory of Learning in Games (#8) Drew Fudenberg and David K. Levine

Full-Text Access (Complimentary) | Supplementary Materials

A von Neumann medal in the shape of a saddle point

It's a little hard to see, but the medal forms a saddle point: the intersection of the two lines is a maximum in the horizontal direction and a minimum in the vertical direction...  It had been a long time since I thought of equilibrium that way, but it is from von Neumann's first game theory paper, on two person zero sum games and the minimax theorem.

It is from my trip to Hungary in early September. You can read about it in Hungarian...

Nobel-díjas közgazdász, Alvin E. Roth kapta idén a Neumann János-díjat

Piaci megoldással osztaná el a migránsokat a Nobel-díjas közgazdász


Nobel-díjas közgazdász oldhatja meg a menekültproblémát

Hungarian radio: (interview in Hungarian voice-over)
A pénz sem old meg mindent - így látja a Nobel-díjas, InfoRádió / Czwick Dávid

Isten teremtette a búzát. És az árutőzsdét? (a newspaper interview in Hungarian)

Google translate: God created the wheat. And the commodities market?

Celebration of David Kreps

I was away and missed the academic festival to mark Dave Kreps' 65th birthday. But here's a nice account of it (after a non-sequitur first paragraph) by David Warsh at Economic Principals:
It Takes (an Invisible) College 

"A celebration last week of the sixty-fifth birthday of David Kreps, of Stanford University’s Graduate School of Business, marked the scholarly contributions of one of the leading figures in the integration of game theory into economics.  "

Reinhard Selten (1930-2016)

Reinhard Selten, a pioneer in both game theory and experimental economics, passed away last week. Rosemarie Nagel and Eyal Winter wrote this morning with the news. Here is an obituary from the Frankfurter Allgemeine
Trauer um berühmten Ökonom
Wirtschaftsnobelpreisträger Reinhard Selten gestorben
Der Mathematiker und Ökonom Reinhard Selten ist tot, wie die F.A.Z. aus seinem Umfeld erfuhr. Er war der bisher einzige Deutsche, der jemals den Ökonomie-Nobelpreis erhalten hat. 
Google translates the headline this way:
"Mourning famous economist
died Nobel laureate Reinhard Selten
The mathematician and economist Reinhard Selten is dead, as the FAZ learned from his environment. He was so far the only German who has ever received the Nobel Prize in economics."

That obit comes with this undated  photo:

Here's a picture of the two of us that Axel Ockenfels took in Cologne in 2006

Reinhard Selten and Al Roth

***************
Update: further obituaries
Reinhard Selten, German Nobel economist, dies aged 85

Reinhard Selten, Game Theorist Who Won Nobel Prize, Dies at 85
"Reinhard Selten was born on Oct. 5, 1930, in Breslau, a German city before World War II and now called Wroclaw in present-day Poland. His father ran a magazine-lending business, which the Nazi regime forced him to sell because he was Jewish.
"Selten and his mother were Protestant, yet his father’s Jewish roots forced Selten to leave school at 14 and he was refused entry to a trade. They left Breslau and became refugees in the German states of Saxony and Hesse as well as in Austria, where he worked as a farm hand after the war. His life in a village in Hesse required walking 3 ½ hours to and from school, during which he solved mathematical problems, he said in his biography for the Nobel Foundation.

“My situation as a member of an officially despised minority forced me to pay close attention to political matters very early in my life,” he said. “I had to learn to trust my own judgment rather than official propaganda or public opinion. This was a strong influence on my intellectual development.”
...
"Selten and his wife, the former Elisabeth Langreiner, were proficient in Esperanto, an invented language devised in the 19th century to assist international communication."


Reinhard Selten, Deutschlands einziger Ökonomie-Nobelpreisträger ist tot
Google t: Reinhard Selten, Germany's only Nobel laureate in economics is dead
"Reinhard Selten was like many older men with disheveled white hair and a little too big, held by suspenders suit. He chose his words carefully. But his eyes lit up when he talked about current projects, for example, a new experiment on decision theory. Even many years after his retirement, he devoted himself every day for two to three hours of research. Therefore he remained scientific coordinator and founder of the Laboratory of Experimental Economics at the University of Bonn.
...
" Finally ... he came to economic laboratory experiments. "I was familiar through my psychology studies with experiments that approach made sense to me." His credo: "Who wants to know what is in the real world going on, must make empirical and experimental work, the reality can be devised at the desk no."
"Not for nothing, the economist is therefore regarded as a pioneer of experimental economics. After receiving his doctorate in Frankfurt and lectureships in Berlin and Bielefeld was rare in 1984 to Bonn, where he founded the first European laboratory for economic experiments."


And, in the NY Times:
Reinhard Selten, Whose Strides in Game Theory Led to a Nobel, Dies at 85
By Sam Roberts

"Alvin E. Roth, another Nobel laureate in economics who teaches at Stanford University, wrote in 1999 that game theory and experimental economics were two of the most important developments in the field in the second half of the 20th century.
“Reinhard Selten is one of the pioneers in both of these endeavors, and he has been a leader in each of them throughout his career,” Professor Roth wrote. “This makes him unique: No one else in the world has made such important or such sustained contributions to both fields.”

More recently, from Andreas Ortmann in Australia:
In Memoriam Reinhard Selten (1930 – 2016), September 2, 2016 by Andreas Ortmann

Aumann Lecture (video): Economists as Engineers: Game Theory and Market Design

Here's a video of my Aumann Lecture last week in Israel--I took as my starting point Bob's 1985 paper "What is Game Theory Trying to Accomplish?"

Theory and application, and age...

An op-ed yesterday by Manil Suri in the NY Times, celebrating the 90th birthday of the mathematician Ivo Babuska, was in part a meditation on "pure" versus applied math, that should ring a bell for economists and game theorists too: The Mathematician’s 90th-Birthday Party.

Suri contrasts Babuska's career with the famous views of G.H. Hardy (he of "A Mathematician's Apology")

"Hardy believed that the only important questions in the field arose internally from this game, that the sole purpose of a mathematician was to create beautiful and “almost wholly useless” theorems.

"But ever since its inception, mathematics has also been driven by another powerful force: applications. From the early commerce and measurement needs that motivated the Sumerians to the subject’s symbiotic co-development with physics, mathematical inquiry has been spurred by questions from external fields. Although Hardy disparaged any math that could be applied to real life as “ugly,” “dull” and “trivial,” surely usefulness should be an additional measure for a mathematician’s worth?
...
"Hardy dismissed exposition as “work for second-rate minds,” but such activity is critical for a field notoriously inept at communicating its results to outsiders.

"It’s of course unfair to criticize Hardy, given how much the world has changed since his day. The division he created between “beautiful but useless” and “useful but ugly” mathematics has long been breached; even his own “useless” research area of number theory has become essential in cryptography and cybersecurity. Conversely, many elegant and aesthetically pleasing mathematical theories have emerged from the most utilitarian applications — even from the analysis of machine parts, as I can personally attest.

"Let’s cherish Hardy’s theorems, not his opinions, and recognize mathematics as a field with diverse goals and needs, where people can expect to make useful contributions regardless of gender or age."

Lloyd Shapley: an intellectual obituary

Here's the link to  my necessarily brief intellectual obituary of Lloyd Shapley, published in Vox EU yesterday:

Lloyd Shapley: A founding giant of game theory

Here are the first paragraphs...:

"Lloyd Shapley was one of the founding giants of game theory. He shared the 2012 Nobel Prize in Economicsfor his seminal work with the late David Gale on stable matching – situations in which there are no two agents who would prefer one another over their current counterparts. But he could have won a Nobel for any of a number of his papers that initiated whole literatures.

In addition to being one of the very first to formulate and study the core of a game, which was intimately related to his work on matching, he invented the Shapley value for evaluating games with side payments, which he and Martin Shubik showed could also be used in studying voting and political processes. He and John Milnor initiated the study of games with a continuum of players (‘oceanic games’), a subject that he later explored in depth with Robert Aumann; his paper on ‘stochastic games’ initiated the study of Markov decision processes as well as Markov games; and he contributed deep insights about learning in games and the structure of markets.

At a time when game theory was viewed as addressing two fairly distinct kinds of situations – cooperative games (in which models focus on what coalitions could accomplish if they agree) and non-cooperative games (which focus on individual players’ strategic choices) – Shapley made fundamental contributions to both."

...

and the last paragraph:

"No brief account can summarise Lloyd Shapley’s intellectual life and career, which was among the most fertile of the 20th century. He opened up vast areas to be explored by those who followed. To pick just an area in which I have worked, a few of his foundational ideas – the core, two-sided matching, and exchange in cycles of trade – have led to the study of matching markets, and to a thriving branch of practical market design, which is the engineering part of game theory."

*************

Update: That obituary has been reprinted on the Lindau site, here, with this photo by Peter Badge from his ‘Nobel Portraits’ series.:

Whither Game Theory? by Fudenberg and Levine (we need to learn more about learning)

Whither Game Theory? Drew Fudenberg David K. Levine, January 31, 2016

Abstract: We examine the state of game theory. Many important questions have been answered, and
game theoretic methods are now central to much economic investigation. We suggest areas where
further advances are important, and argue that models of learning and of social preferences
provide promising routes for improving and widening game theory’s predictive power, while
preserving the sucesses of existing theory where it works well. We emphasize in particular the
need for better understanding of the speed with which learning takes place, and of the evolution
of social norms.

Videos of the Simons Institute lectures on Algorithmic Game Theory and Practice

The archived videos from Algorithmic Game Theory and Practice Workshop at the Simons Institute for the Theory of Computing can be found by clicking on the titles of individual talks on the schedule (below) or on the Simons Institute YouTube channel.

9:30 am – 10:10 am		Kidney Exchange: Algorithms and Incentives Alvin Roth, Stanford University
10:10 am – 10:40 am		Break
10:40 am – 11:20 am		Designing Online Advertising Markets Susan Athey, Stanford University
11:20 am – 12:00 pm		Outsourcing Tasks Online: Matching Supply and Demand on Peer-to-Peer Internet Chiara Farronato, Harvard University
12:00 pm – 1:30 pm		Lunch
1:30 pm – 2:10 pm		Business Model Analysis Kamal Jain, Faira.com
2:10 pm – 2:50 pm		The Limits of Reputation in Platform Markets Steve Tadelis, UC Berkeley
2:50 pm – 3:20 pm		Break
3:20 pm – 4:00 pm		Dynamic Labor Supply in the Sharing Economy Chris Nosko, University of Chicago
4:00 pm – 5:00 pm		Reception

Tuesday, November 17th, 2015

9:00 am – 9:30 am		Coffee & Check-In
9:30 am – 10:10 am		Adverse Selection and Auction Design for Internet Display Advertising Paul Milgrom, Stanford University
10:10 am – 10:40 am		Break
10:40 am – 11:20 am		Machine Learning in an Exchange Environment R. Preston McAfee, Microsoft
11:20 am – 12:00 pm		From Theory to Practice in Auction Modeling Hal Varian, Google, Inc.
12:00 pm – 1:30 pm		Lunch
1:30 pm – 2:10 pm		Online Advertisements and Online Algorithms Nikhil Devanur, Microsoft Research
2:10 pm – 2:40 pm		Break
2:40 pm – 4:00 pm		On How Machine Learning and Auction Theory Power Facebook Advertising Eric Sodomka, Facebook

Wednesday, November 18th, 2015

9:00 am – 9:30 am		Coffee & Check-In
9:30 am – 10:10 am		On-Line Systems with Long-Range Goals Jon Kleinberg, Cornell University
10:10 am – 10:40 am		Break
10:40 am – 11:20 am		Decision Making at Scale: Platforms and Problems Ashish Goel, Stanford University
11:20 am – 12:00 pm		Strong Truthfulness in Multi-signal Peer Prediction with Overlapping Tasks David Parkes, Harvard University
12:00 pm – 1:30 pm		Lunch
1:30 pm – 2:10 pm		The State of Techniques for Solving Large Imperfect-Information Games Tuomas Sandholm, Carnegie Mellon University
2:10 pm – 2:50 pm		Security Games: Key Algorithmic Principles, Deployed Applications and Research Challenges(*) Milind Tambe, University of Southern California
2:50 pm – 3:20 pm		Break
3:20 pm – 4:00 pm		Robust Inference for Games via Theoretical Guarantees Denis Nekipelov, University of Virginia

Thursday, November 19th, 2015

9:00 am – 9:30 am		Coffee & Check-In
9:30 am – 10:10 am		An Evolutionary Model of Economic Behavior, Bounded Rationality, and Intelligence Andrew Lo, MIT
10:10 am – 10:40 am		Break
10:40 am – 11:20 am		The Design of Financial Exchanges: Some Open Questions at the Intersection of Econ and CS Eric Budish, University of Chicago
11:20 am – 12:00 pm		Algorithmic Trading and Machine Learning Michael Kearns, University of Pennsylvania
12:00 pm – 1:30 pm		Lunch
1:30 pm – 2:10 pm		Incentive Auctions and Spectrum Repacking Kevin Leyton-Brown, University of British Columbia
2:10 pm – 2:50 pm		Informational Substitutes and Complements for Prediction Yiling Chen, Harvard University
2:50 pm – 3:20 pm		Break
3:20 pm – 4:20 pm		Open Directions Session

Friday, November 20th, 2015

9:00 am – 9:30 am		Coffee & Check-In
9:30 am – 10:10 am		AGT and Machine Learning Christos Papadimitriou, UC Berkeley
10:10 am – 10:40 am		Break
10:40 am – 11:20 am		Bitcoin's Incentive Structure Aviv Zohar, Hebrew University of Jerusalem
11:20 am – 12:00 pm		Dynamic Pricing in Ride-Sharing Platforms Ramesh Johari, Stanford University