Showing posts with label game theory. Show all posts
Showing posts with label game theory. Show all posts

Tuesday, October 22, 2024

Stability vs. No Justified Envy, by Romm, Roth and Shorrer

 Here's a recent paper that clarifies some of the prior literature on comparing stability in two-sided matching with a related kind of envy-freeness in allocations of goods to individuals using priorities.


Romm, Assaf, Alvin E. Roth, and Ran I. Shorrer, "Stability vs. No Justified Envy," Games and Economic Behavior, Volume 148, November 2024, Pages 357-366  https://doi.org/10.1016/j.geb.2024.10.002
 
Abstract: Stability and “no justified envy” are used almost synonymously in the matching theory literature. However, they are conceptually different and have logically separate properties. We generalize the definition of justified envy to environments with arbitrary school preferences, feasibility constraints, and contracts, and show that stable allocations may admit justified envy. When choice functions are substitutable, the outcome of the deferred acceptance algorithm is both stable and admits no justified envy.

Monday, August 5, 2024

Theory brunch at Stanford

 A Sunday brunch to welcome Fuhito Kojima back for a summer visit brought together an eclectic group of Stanford theorists, past, present, and future. (Mike Ostrovsky, Mohammad Akbarpour and Bob Wilson had already run off before things settled down for this picture  of Fuhito Kojima, Ilya Segal, Itai Ashlagi, Jason Hartline, Ravi Jagadeesan, Oguzhan Celebi, Roberto Corrao, and Frank Yang.)



Saturday, April 27, 2024

No Prices No Games! Four Economic Models by Michael Richter and Ariel Rubinstein

 Here's a new book on economic theory by Richter and Rubinstein.

No Prices No Games!  Four Economic Models  by Michael Richter and Ariel Rubinstein  

At the link you can download a pdf or read it online for free, or purchase a printed edition.

"While current economic theory focuses on prices and games, this book models economic settings where harmony is established through one of the following societal conventions:

• A power relation according to which stronger agents are able to force weaker ones to do things against their will.

• A norm that categorizes actions as permissible or forbidden.

• A status relation over alternatives which limits each agent's choices.

• Systematic biases in agents' preferences.

"These four conventions are analysed using simple and mathematically straightforward models, without any pretensions regarding direct applied usefulness. While we do not advocate for the adoption of any of these conventions specifically – we do advocate that when modelling an economic situation, alternative equilibrium notions should be considered, rather than automatically reaching for the familiar approaches of prices or games."



By email, Ariel tells me that he designed the cover.

Contents

0. Introduction

(pp. 1–12)
  • Michael Richter
  • Ariel Rubinstein
  • Michael Richter
  • Ariel Rubinstein
  • Michael Richter
  • Ariel Rubinstein
  • Michael Richter
  • Ariel Rubinstein
  • Michael Richter
  • Ariel Rubinstein
  • Michael Richter
  • Ariel Rubinstein




"In the final chapter, we compare this book's modeling approaches with each other and to those of standard Game Theory on two ``battlegrounds''.
The first is the matching economy. An even-sized population of agents must match into exclusive pairs (pairings). Each agent possesses a preference relation over potential mates.
The standard cooperative game theory solution concept for matching economies is ``pairwise stability''. Following Richter and Rubinstein (2024), we compare this concept with the jungle equilibrium, the Y-equilibrium and the status and initial status equilibrium concepts.
The second battleground is a ``political economy'' situation. A group of agents hold views on a political issue. Each agent chooses a position and has preferences only regarding the position he himself chooses (and not the choices of others). However, there is a need that a majority of agents choose the same position.
Traditionally, such a situation is modeled as a non-cooperative game and its Nash equilibria are calculated. Extending Richter and Rubinstein (2021), we compare this approach with the convex Y-equilibrium and the biased preferences equilibria.
On both battlegrounds, the new approaches lead to very different outcomes than the traditional ones."

Friday, December 8, 2023

Computers in Econ (and in market design)

 The current issue of the journal Œconomia. is devoted to The Computerization of Economics. Computers, Programming, and the Internet in the History of Economics

It includes this surprisingly grumpy-sounding take on market design, particularly on its intersection with game theory:

 Nik-Khah, Edward. "The Closed Market: Platform Design and the Computerization of Economics." Œconomia. History, Methodology, Philosophy 13-3 (2023): 877-905.

Here's a paragraph that caught my eye:

"In his book Who Gets What—And Why, the market designer Alvin Roth pronounced firms such as Google, Amazon, and Uber to be “markets,” proclaiming, “Successful designs depend greatly on the details of the market, including the culture and psychology of the participants” (Roth, 2015). One need not actually find an example of an economist counseling advisees to skip that additional course in game theory and take up cultural anthropology to arrive at the sense that matters had taken a surprising turn: only a decade before one regularly encountered brash claims that all social science worth its salt must be reducible to game theory, with market design cited as evidence for why this must be so (e.g., Binmore, 2004)."

#####

Here's the table of contents of the issue:

Monday, October 30, 2023

Simple Proofs of Important Results in Market Design-- (video of my talk at Berkeley's Simons Institute)

Here's a video of the talk I gave on Friday at the Simons Institute, on simple proofs of important theorems about matching, that have had impact on practical market design.

Wednesday, July 5, 2023

Eric van Damme is moving on

 It appears that the great Dutch game theorist Eric van Damme is retiring from Tilburg.

Here's the announcement from Tilburg:

Outgoing professor Van Damme: Economics serves people, 20th June 2023

"Game theory supports design markets

"Game theory is a mathematical theory that allows us to better understand how people resolve conflicts and can benefit from cooperation. Game theory is used in designing markets so that they function well, and auctions (such as this summer's auction of FM radio frequencies) to ensure that predetermined goals are met. The theory is also important in competition policy, such as in detecting cartels and preventing the abuse of dominant positions.

"In his speech, Van Damme discusses three examples from his own work: the theory of "Global Games," which predicts how coordination problems are solved and provides insights for regulating financial markets. Also, work on platform markets that played a role in a US Supreme Court ruling on the credit-card market. And finally recent research for the Ministry of Economic Affairs on the effectiveness of legislation on abuse of dominance.   

"Eric van Damme worked at Tilburg University since 1989. He started as a research professor at the then newly founded CentER and later served as director of TILEC, the Tilburg Law and Economics Center. He is a Fellow of the Econometric Society (1993) and has been a member of the Royal Netherlands Academy of Arts and Sciences, KNAW, since 2003. In 2009 he was appointed Knight of the Order of the Dutch Lion for his scholarly achievements."

*********

And below is a link to and some excerpts from his valedictory speech, in which (among other things) he explains game theory and economics to non-economists, and gives very eloquent thanks to those who have influenced him.  Among those are Stef Tijs, his undergraduate mentor, who he calls "the Godfather of Game Theory in the Netherlands," and later Reinhard Selten. (Selten wrote in his 1994 Nobel autobiography that  "Eric van Damme needed very little advice and is now a well known game theorist.").

Eric's lecture has a bilingual title:

The beauty and the beast; Het spel en de knikkers, Prof. dr. Eric van Damme

"I should still explain the first part of the title. The “beauty” refers to the world of science, and the “beast” is reality (including the economy).

...

"In this lecture, I will talk about how I tried to navigate between the beauty and the beast.

...

"An example: school choice

"Let me give an example of a “market” on which I did not work on myself, but which is important and which the non-economists among you might not view as a market. The question that we want to address: how, in a given city (or region), to allocate children to (high) schools? Schools differ in quality and parents prefer their children go to good schools. Furthermore, everything else equal, a school that is closer by is more attractive. It can easily happen that some schools are oversubscribed, i.e., there are more applications than there is capacity. Hence, there is scarcity of positions. In such a case, which kids should be allowed to enter their preferred school and which one not? There will be some criteria, which will be reflected in allocation rules. But what should these rules be? Lotteries are simple but may not lead to a good allocation. We also do not want to give the places to the kids of which the parents are willing to pay the most. What should we do? Note that if we really want a good solution, we should look at all the schools in the region or city together. How can we solve this problem? And what criteria should we use for judging allocations?

"There is an active line of research on these questions, with important contributions from economists from Amsterdam, who influenced the way the allocation is done there. (De Haan et al, 2023). The current literature is based on a pure mathematics paper, Gale and Shapley (1962) that was inspired by the process by which teenagers taking their first dancing lesson were matched: the girls standing on the side and the boys asking them to dance, with each boy moving on to another girl after a rejection until he found a partner or was rejected by all. Two very different situations, but with the same solution. Based on the ideas developed in this literature, we can now also match donor organs to patients in a more efficient way, and can save more lives; see Roth (2015) for a popular account. "


...

"I thank my parents. They always stimulated me to get the best out of myself and stressed the importance of education to get a better life than had been possible for them. For somebody in my generation and coming from Koewacht (Zeeuws Vlaanderen) it certainly was not common to go to university. I am grateful that my mother can be here today, healthy and strong, and still caring, not only for me, but also for the rest of our (extended) family. If I recall well, my parents’ dream was that I would become an engineer. Being all thumbs (met twee linkerhanden), this was impossible for me, but with a PhD
from Eindhoven University of Technology and with Nobel Prize Winner Al Roth speaking about “The economist as engineer” (Roth, 2002), I think I have come reasonably close.

"My headmaster of elementary school, Meester Lammens, told my parents that my Cito-toets was not representative of my capabilities and urged them to not take it too seriously. I was fortunate that, when I went to high-school, the Mammoetwet had just entered into force so that I could go from Mavo, through Havo and Atheneum, to the university without delay.

"Studying mathematics in Nijmegen showed me its beauty and taught me the importance of learning by doing. After the lectures, we had tutorials to practice the material, but, at first, it frequently seemed that the questions had nothing to do with what had been taught. But then discovering the link and the corresponding solution by oneself (with only a little bit of help) was always exciting. I am immensely grateful to Stef Tijs, the Godfather of Game Theory
in the Netherlands. Everybody who has interacted with Stef knows what an inspirational figure he was. After having followed his courses, it was clear that Game Theory would be my area and I wrote my thesis under his supervision. Stef also helped me on many other occasions and more than could be expected, and he also ensured that I got my first job in Eindhoven to do my PhD there.

"In Eindhoven, I had the privilege to work in the Operations Research Group of Jaap Wessels. This was a fantastic environment offering excellent conditions for research and stimulating supervision. The research culture forced me to go out at an early stage and present my work at conferences. When it became clear that I preferred to work on Game Theory problems rather than things like inventory management, Jaap allowed me to follow my interests, although it was only a side interest of the group. Jaap, however and rightly, insisted that I should find a “true expert” who was willing to testify that my work was indeed pushing the research frontier forward. When I met Reinhard Selten at a conference in Oberwolfach (Germany), he was willing to act as a second supervisor, even if at first I had tried to convince him that his concept of subgame perfect equilibrium did not make sense
and had thus demonstrated how much I still had to learn. Reinhard and I had many discussions, for which he also invited me to his home in Rheda-Wiedenbrück. I think these were the most intensive discussions I ever had. I am very, very grateful to Reinhard. Throughout my career I have kept Reinhard, Jaap and Stef in mind and I tried to treat my students as they (my teachers) had treated me."

Friday, June 30, 2023

Lloyd Shapley (1923-2016) Centennial

 Lloyd Harlow Shapley was born in 1923: he would be (and I guess is) 100 years old this year.  His family is assembling a website honoring his centennial. (It's part of a family of web pages devoted to the life and work of Lloyd's dad, the astronomer Harlow Shapley.)

Here's the page for the Lloyd Shapley Centennial

It appears to be a work in progress, with many links. It begins this way:

"Lloyd Shapley (1923-2016) was a Nobel prizewinning mathematician. Shapley’s "intellectual life and career ... was among the most fertile of the 20th century." For the Centennial of Lloyd’s birth the Harlow Shapley Project offers this easy-access guide to Lloyd's WORK, his favorite GAME Kriegspiel, personal STORIES not published before and his four PRIZES.

"Lloyd Shapley was one of the founding giants of game theory. He shared the 2012 Nobel Prize in Economics for 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,” wrote Alvin E. Roth, Lloyd’s Nobel co-winner (right).

"Mathematical giant John von Neumann (right) invited Lloyd to leave RAND for Princeton on the basis of a two-page paper Lloyd sent him. After getting his Princeton PhD Lloyd returned to RAND full-time. He was a very productive member of the fabled Mathematics Division. Lloyd was almost unbeatable in the Division’s lunchtime Kriegspiel matches. 

"The Work page has summaries of Lloyd’s main contributions prepared by Dr. Bruce E. Krell, a game theorist who was a colleague of Lloyd’s at RAND. The Work page also offers a bibliography of selected descriptions of his work. The Work includes the 1962 “marriage problem” paper with David Gale (right), which won the Nobel."

Friday, June 16, 2023

Ehud Kalai, interviewed on the past and future of game theory

Here's a half-hour video interview of Ehud Kalai, by Sandeep Baliga, that touches on the history of game theory at Northwestern and elsewhere, his work on axiomatic models of bargaining, Econ-CS (and the Kalai Prize), and more.

 

Saturday, December 10, 2022

Amnon Rapoport (1936-2022)

 Amnon Rapoport, a pioneer of experimental game theory, has died. 

Here's a brief obituary:

Amnon Rapoport, Distinguished Professor Emeritus of Management and Organizations at the University of Arizona, passed away on December 6th

I don't find his date of birth on the web, but in August of 1996 I participated in a conference in honor of his 60th birthday, at the University of North Carolina at Chapel Hill, where he had both studied and taught in the Department of Psychology.  Amnon had already had several heart attacks by then, and his students, who loved him, thought it prudent to have a celebration of his work at that relatively young age, but that caution proved unnecessary. 

Here's the volume of papers presented at that conference, edited by three of his students:

Budescu, David V., Ido Erev, and Rami Zwick, eds. Games and human behavior: Essays in honor of Amnon Rapoport. Erlbaum, 1999.

I first learned of his work when, as a grad student, I took a course in game theory taught by Michael Maschler, who told us about Amnon's experiments on the bargaining set.

He was a man ahead of his time, and maybe situated in the wrong discipline.  It seemed to him natural that psychologists should take a leading role in the experimental study of game theory, and he noted with some regret that instead that literature had been ceded to economists. Here's a paragraph from the introduction to 

Rapoport, Amnon. Experimental studies of interactive decisions. Vol. 5. Springer Science & Business Media, 2012.

"The history of experimentation in psychology is rich and old. It would have been quite natural and highly desirable for psychologists to extend their scope of research and assume a major role in the study of economic decision behavior. Psychology professes to be the general study of human behavior. Most psychologists are trained to regard their discipline as an observational science; they do not have to overcome the conditioning of many economists who think of economics as an a priori science. Psychologists' knowledge of experimental techniques is comprehensive. and their experience in conducting experiments. analyzing data. and discovering empirical regularities exceeds that of most economists. However. with the exception of research on individual choice behavior - where psychologists like Tversky, Kahneman, and Slovic have played a major role - psychologists have not contributed in any significant way to the growing research in experimental economics. Social psychologists for whom interactive behavior is the core of their discipline, have virtually abandoned the study of economic decisions in small groups to their colleagues in economics and related disciplines. "

Here's his cv as of 2017, and his google scholar page.

**********

Update: here's an email that Rami Zwick sent to the Economic Science Association (ESA):

"Dear ESA community,

It is with great sadness that we announce the passing of our teacher, mentor, colleague, co-author and friend, Professor Amnon Rapoport, in Tucson Arizona on December 6, 2022. 

Professor Rapoport served on the faculty of the University of California, Riverside School of Business; University of Arizona; UNC Chapel Hill; University of Haifa, Israel; and the Hebrew University of Jerusalem, Israel. He earned his Bachelor of Arts degree in psychology and philosophy from the Hebrew University of Jerusalem, then went on to earn his M.A. and Ph.D. in quantitative psychology at UNC Chapel Hill. 

Professor Rapoport was one of the pioneers and leaders in the experimental study and quantitative modeling of human decisions in social and interactive contexts. During his distinguished career, he published four books (and edited others) and more than 300 research papers and chapters in leading psychological, management, operation, marketing, decision theory, economics, and political science journals, and is recognized as a leading authority in many of these areas. His most important and influential work was on experimental studies of interactive decision-making behavior. This includes theoretical and empirical research on: 

Coalition formation 

Bargaining 

Social dilemmas 

Behavioral operations management 

Behavioral game theory 

Dynamic pricing 

Directed networks 

 Professor Rapoport’s work was theory-driven, and, in most cases, the theory was represented formally by mathematical (primarily, but not exclusively, game theoretical) models. At the same time, he was a meticulous and rigorous, yet imaginative and creative experimentalist. In fact, he was one of the pioneers of computerized experimentation in the domain of individual and group decision making. 

With a career spanning over 60 years, Professor Rapoport nurtured and supported the careers of generations of scholars and researchers. He will be greatly missed by his family, friends, colleagues, co-authors, and students."