Last Month in Game Theory: May 2019, part 3

Alright, so life got in the way of writing my reviews the last few days, but here’s today’s selection of articles in game theory and related topics from last month.

Bayesian versus heuristic-based choice under sleep restriction and suboptimal times of day, in Games and Economic Behavior. Ooh, so experimental behavioral science. It mentions “suboptimal times of day” in the title but doesn’t in the abstract. Ah, so “suboptimal times of day” means they classified subjects beforehand into morning-types and evening-types through a long-term self-reported survey, and then presented the subjects with one of those silly behavioral economics tasks, one week under sleep deprivation, one week under adequate rest. The result: sleep deprivation makes people switch from Bayesian decision making (i.e. maximizing expected utility in accordance with the laws of probability) to reinforcement heuristic-based decision making (a sort of commitment bias, if i need to be concise). Being “circadian-mismatched” apparently doesn’t, and there’s hints that it makes you a better Bayesian optimizer instead. I might be misunderstanding the results a bit. This stuff is dense and i’m too sleep-deprived to bother going into it in the detail it deserves.

Nonparametric utility theory in strategic settings: Revealing preferences and beliefs from proposal–response games, in Games and Economic Behavior. Cool, another economic experiment. Okay, so there’s a chance that “nonparametric utility theory” might mean doing utility theory based not on a real-valued utility function but on preferences between outcomes. Let’s look at the paper to see if the conjecture holds… Ah, they don’t ever mention “nonparametric” again from the abstract to the conclusion. But yes, they’re using comparisons between binary lotteries and axiomatically describe the properties of such comparisons. There’s also a few references with “nonparametric” in the title. The conclusions of the study sound interesting too. This is worth a look someday.

Evolved attitudes to idiosyncratic and aggregate risk in age-structured populations, in the Journal of Economic Theory. What even is this paper about?! Let’s read the introduction and see how far i can follow it. Ah, okay, population genetics with choice. “Idiosyncratic risk” means risk to the individual, and “aggregate risk” means risk to the population as a whole. This sounds intense and worth a look, insofar as i’ve enjoyed toying with population genetics before.

Competition among procrastinators, in Theory and Decision. That’s an attention-grabbing title for sure. This paper means to dispute a two-decade-old result showing that making procrastinators compete reduces procrastination. Not so fast: if procrastinators underestimate their future self-control problems, competition won’t solve the problem. The author adds some policy suggestions. I should definitely read this as soon as i have some time, both for the model and the practical consequences.

Gender gaps in salary negotiations: Salary requests and starting salaries in the field, in the Journal of Economic Behavior and Organization. Ah, so women are paid less because they negotiate for lower salaries than men do, but also they’re offered lower salaries on the same request.

A class of asymptotically optimal group testing strategies to identify good items, in Discrete Applied Mathematics. Here “group testing” means something like the classical problem with the fake coin hiding among a bunch of good coins, and having to locate the fake coin with the minimum number of weighings. “Identifying good items” means that you’re trying to locate the good coins instead, and “asymptotically optimal” means that you get closer to the optimum as your problem involves larger numbers of coins. Or that’s what i understand from the abstract.

Optimal pebbling number of graphs with given minimum degree, in Discrete Applied Mathematics. Essentially: how many pebbles do you need to distribute among the nodes of a graph so that you can reach any vertex through pebbling moves (you go from one node to the next by removing two pebbles from here and placing one over there?). Just go read the abstract. It explains itself well enough.

Explore First, Exploit Next: The True Shape of Regret in Bandit Problems, in Mathematics of Operations Research. Huh. One of the authors is Pierre Ménard, author of the Quixote. So the bandit problem is a sort of stochastic optimization problem, something like having to choose among many slot machines without even knowing what each machine’s odds are. “Regret” means how far your winnings are from the optimal strategy’s winnings. I suppose i’d look at this if it was a problem i cared about, though according to the Wikipedia article it has several interesting applications.

Rare Nash Equilibria and the Price of Anarchy in Large Static Games, in Mathematics of Operations Research. Ah, asymptotic noncooperative game theory. The “price of anarchy” is the ratio between the social welfare at its optimum and the social welfare at the Nash equilibrium. So this is essentially a study on how individual decisions harm society as the number of individuals grows very large. Cool stuff.

An option-theoretic model of a reputation network, in the Journal of Mathematical Sociology. «This paper constructs a new theory of social networks based on reputation. The model assumes that reputation is an asset and that individuals connect by buying options on the reputation of others». Wait, wait, wait, what. I need to know this model. And i need to know that this model reflects actual social networks and isn’t just abstract nonsense. Let’s dig in someday.

We have three working papers from the National Bureau of Economic Research:

Scabs: The Social Suppression of Labor Supply. Ah, econometrics on the effects of discrimination on the labor supply. The specific type of discrimination being studied is that people are less likely to accept jobs at below-typical wages if others can see that they are. The crucial finding: «workers pay to punish anonymous laborers who have accepted wage cuts—indicating that cartel behavior is reinforced through the threat of social sanctions».

The Indeterminacy Agenda in Macroeconomics. Read the abstract. This is exciting stuff. Here’s a big claim: «The indeterminacy agenda provides a microeconomic foundation to Keynes’ General Theory that does not rely on the assumption that prices and wages are costly to change». Why haven’t i finished Keynes yet. I hate to be missing out on this.

Excessive Entry and Exit in Export Markets. More microeconomics, attempting to explain why there are so many new firms and so many exiting firms in the Chinese export market.

And finally, seven arXiv preprints:

On Policy Evaluation with Aggregate Time-Series Shocks. Technical econometric stuff.

Resolving New Keynesian Anomalies with Wealth in the Utility Function. Technical macroeconomic stuff. Worth a look someday because it might have references on dynamic models of the economy (it speaks of sinks and sources, there’s no way i can’t find a clue there).

Characterizing Shadow Price via Lagrangian Multiplier for Nonsmooth Problem. Technical optimization stuff. Here «an application to electricity pricing is discussed», so it’s worth a look for that alone.

The Interplay of Competition and Cooperation Among Service Providers (Part I). Applied noncooperative game theory with mobile network service providers. There is a part II “next month”, i.e. in June.

Manipulating a Learning Defender and Ways to Counteract. Alright, now this article makes cybersecurity applications of game theory sound exciting.

Computational Aspects of Equilibria in Discrete Preference Games. Ah, (noncooperative) games on (social) networks. I dunno.

Perception towards Electric Vehicles and the Impact on Consumers’ Preference. An econometric study. Not much to say here.

Last Month in Game Theory: May 2019, part 2

Here’s another random selection of papers from last month in game theory and related topics. Yes, there’s going to be a lot of arXiv preprints this time too. That’s because the arXiv publishes a lot of preprints.

Ambiguity attitudes and self-confirming equilibrium in sequential games, in Games and Economic Behavior. The natural questions are what the authors mean by ambiguity, and what a “self-confirming equilibrium” is. On the topic of ambiguity they cite this 2005 paper from Econometrica (now there’s a journal i should add to my sources), which proposes a model that allows distinguishing between ambiguity in information and ambiguity in attitude. As for self-confirming equilibrium, here’s how the original paper from Econometrica describes it in the abstract: «In a self-confirming equilibrium, each player’s strategy is a best response to his beliefs about the play of his opponents, and each player’s beliefs are correct along the equilibrium path of play», hence «no player ever observes play that contradicts his beliefs». You have to give it to non-cooperative game theorists, they know how to model information in a way that cooperative game theory isn’t as well suited for.

Mechanism design with budget constraints and a population of agents, in Games and Economic Behavior. Ooh, welfare theorems and mechanism design. This one deserves a closer look. Someday.

Survival in speculative markets, in the Journal of Economic Theory. Automatic question: what’s the “Market Selection Hypothesis”? As far as i could gather from a web search, it’s the idea that «agents that don’t make rational decisions are driven out of the market» (source, PDF). Here “survival” means precisely that the market selection hypothesis doesn’t hold and irrational agents persist.

Aiming for the Goal: Contribution Dynamics of Crowdfunding, a working paper from the National Bureau of Economic Research. This is something i should look at! It’s a model of crowdfunding campaigns a la Kickstarter, with two types of contributors: «buyers want to consume the product while donors just want the campaign to succeed». There’s even empirical data supporting the model. Read the abstract. See if this doesn’t get your curiosity going.

Is the Multiset of n Integers Uniquely Determined by the Multiset of Its s-sums?, in The American Mathematical Monthly. As a break from all the game theory and economic modeling going around, have a paper on number theory.

I’m also listing six articles from Volume 260 of Discrete Applied Mathematics, though they don’t have much to do with game theory (unlike yesterday’s):

And finally, the arXiv preprints:

Detectability, Duality, and Surplus Extraction. This paper is about surplus extraction or “rent extraction”, the act of capitalizing on your private information to gain more profits than you should. A starting point for the literature on the topic appears to be this 1992 paper from Econometrica (it’s always Econometrica!). The worst that you can say about Econometrica is that they always manage to publish articles with enduring impact on the field.

Correlation in Extensive-Form Games: Saddle-Point Formulation and Benchmarks. Correlated equilibrium is a recurring topic on the articles i’ve looked at. I first heard of it from a colleague who worked on the topic, but i had no idea it was such a prolific field of work. This paper’s approach and the examples deserve a look someday.

On the many-to-one strongly stable fractional matching set. Alright. This is something i have to read, as it’s about matching. Not just that, it also mentions linear programming in the context of matching, and the core concept is the idea of a fractional matching that resembles some concepts in my current research. Required reading.

Near-optimal Optimistic Reinforcement Learning using Empirical Bernstein Inequalities. It’s machine learning. Where’s the game theory in this? Ah, in the applications. I dunno.

Reallocating Multiple Facilities on the Line. The problem studied here is that of moving points (“facilities”) around the line so that they stay close to the positions of other points (“agents”) that move around and report their locations. The strategic interest of this game is the idea that an agent may lie about their location so as to manipulate the mechanism. These strategic considerations are examined on this 2018 paper (PDF).

Heuristics in Multi-Winner Approval Voting. Ooh, approval voting! So, multi-winner approval voting is what you’d expect: you can vote for as many different candidates as you like (hence approval voting) and the k candidates with the most votes win (hence multi-winner). And “heuristics” means rules for strategizing, i.e. using your vote to manipulate the election. The crucial starting point is that multi-winner approval voting is manipulable, which is of interest because it leads back into the idea of ranking sets of objects (it’s multi-winner, after all). The reader is referred to this 2008 article on that topic.

Competitive Gradient Descent. “We introduce a new algorithm for the numerical computation of Nash equilibria of competitive two-player games”. Cool! (And not just because it’s a refreshing back-to-basics in the middle of all these hypercomplicated multilayered multiplayered incomplete-information models). The idea is to locally linearize the game around your current solution and solve the linearization to update the solution. The algorithm appears to have very nice properties. Cool indeed.

A Parameterized Perspective on Protecting Elections. Ooh, elections! Oh, but it’s… a cybersecurity paper, mostly. Oh well. Two articles on voting would have been too unbelievably nice for a single day. The focus is on a game of attacking and defending elections, and the computational complexity of finding optimal strategies for such, rather than any considerations specific to voting. Maybe someday, just for fun.

Credit Scoring by Incorporating Dynamic Network Information. Finance. Okay.

 

How and why i’m writing Last Month in Game Theory

Now that i’m getting more involved with being a scholar, i’ve decided i should try keeping up to date with my field and the people working in it. Hence the idea of writing a daily column reviewing recent papers in the field.

This achieves multiple goals:

  • it develops a daily habit (yay for daily habits!);
  • it’s great writing practice;
  • it’s great practice in quickly figuring out the interest of an article and locating its key points;
  • it lets me see what people on my field are working on right now;
  • and it expands my academic horizons by putting me in contact with topics i might not notice otherwise. You know, establish what they call a dialogue with my discipline and other disciplines.

Let’s talk about the sources i’m choosing for this experiment. First, the actual journals in game theory and related topics:

Next, some journals less directly related to game theory but still of interest to the area, whether due to close thematic relationships or because they’ve seen the publication of some crucial article:

The journals above amount to about 40% of all the abstracts i’m checking out. The remaining 60% comes in the form of arXiv preprints (i run a search in the categories of “General Economics” (econ.GN), “Theoretical Economics” (econ.TH), and “Computer Science and Game Theory” (cs.GT)) and working papers from the National Bureau of Economic Research.

So what do i do with this volume of work?

(The plan is as follows:) At the start of the month, i gather my sources: every issue of the journals above published the month before, and every arXiv preprint and NBER paper dated the month before. Thus, yesterday i gathered these numbers and counted nearly 500 papers for May 2019. Since i had 28 days to go in the month, i decided 20 papers per day was a good pace of work, leaving me a bit of room by the end of the month to do a review.

As for how i choose the 20 papers i examine every day: i roll the dice. That’s it. I generate 20 integers on RANDOM.ORG and figure out which journals they belong to. For example, numbers 1 through 26 this month are volume 115 of Games and Economic Behavior, 27 through 33 are volume 99 of Mathematical Social Sciences, and 72 through 279 are arXiv preprints (‘cause of course you have two hundred arXiv preprints in the month of May).

Then i pick the papers, i start a new blog post, i link the pages, and i write helpful notes on what i noticed about the papers and what i’m curious about. I don’t expect to read every single paper, or even any paper at all. The goal is to not miss anything in my direct areas of interest and to keep sight of everything in the periphery. Then, if something is truly exciting, i can go ahead and read it.

Last Month in Game Theory: May 2019, part 1

Have a randomly generated selection of articles from various sources on game theory and related topics, published or dated May 2019.

Information in Tullock contests, in Theory and Decision. Who knows what a Tullock contest even is, and who cares? It’s a kind of Bayesian game, per the definition provided by the authors; and it should be of interest to anyone studying “rent-seeking, innovation tournaments, patent races”, as the authors observe citing this 2003 article by Baye and Hoppe. Well, now i know.

Equilibrium paths in discounted supergames, in Discrete Applied Mathematics. Okay, so what’s a discounted supergame? Or a supergame at all? Ah, it’s an infinitely repeated game. I dunno. Maybe someday.

Skewed information transmission: The effect of complementarities in a multi-dimensional cheap talk game, in the Journal of Economic Behavior & Organization. First question: what’s a cheap talk game? In this paper, it’s a Bayesian game where one player has private information that she communicates indirectly, and possibly inaccurately, to another player in order to manipulate his level of effort. It’s a paper on the economics of information and strategic information transmission. Definitely worth checking out someday.

Physician pricing behavior: Evidence from an Australian experiment, in the Journal of Economic Behavior & Organization. Anything that’s about healthcare is bound to be interesting. The idea here is that doctors discriminate prices when they’re aware that their patients are eligible for public benefits. Oof. I should read this someday.

Passing the Buck and Firing Fibonacci: Adventures with the Stochastic Abacus, in The American Mathematical Monthly. I’m including the Monthly among my sources because it’s where Gale and Shapley published their 1962 “College Admissions and the Stability of Marriage”, but i don’t expect many, or even any, of the articles in it to be about game theory. Nonetheless, this article actually is about a game, the “pass-the-buck” game. I should read this someday, but i’ve found trouble accessing Taylor & Francis publications through my school’s library. Who knows when i might.

Here’s a number of arXiv preprints:

Designing for Emergent Security in Heterogeneous Human-Machine Teams. Ooh, okay, robots. And mechanism design. Maybe someday. Interesting questions: what exactly is the difference between a human decisionmaker and a machine? It’s apparently the absence of coordination with other agents in the system. Okay.

Convergence Analysis of Gradient-Based Learning with Non-Uniform Learning Rates in Non-Cooperative Multi-Agent Settings. Ooh, okay, machine learning. Multi-agent learning algorithms. Wonder what the point is of a multi-agent learning algorithm. Oh, nice. The introduction includes quite a number of interesting links, stuff related to how players in a game learn to find the equilibrium, and something about generative adversarial networks. In particular, it links “Game dynamics as the meaning of a game” by Papadimitriou and Piliouras, which looks like an amazing read.

Learning Equilibria of Simulation-Based Games, or how to play a game when you don’t even know your payoff function. Maybe someday.

Optimal Timing of Moving Target Defense: A Stackelberg Game Model. Oh, okay. Game theory applied to cybersecurity. I get that this will be a recurrent theme among arXiv preprints, though so far i’m favorably surprised by the variety and quality of content.

Labor Market Outcomes and Early Schooling: Evidence from School Entry Policies Using Exact Date of Birth. Ooh, econometrics.

Ridesharing with Driver Location Preferences. Ah, mechanism design for Uber and the like. I want to see what their model is like and how much it resembles the actual service. The base model appears to be drawn from this working paper by Bimpikis et al..

Leadership in Congestion Games: Multiple User Classes and Non-Singleton Actions (Extended Version). Oh, okay, a paper showing that solving a certain kind of game is computationally difficult.

Be a Leader or Become a Follower: The Strategy to Commit to with Multiple Leaders (Extended Version). Stackelberg games appear to be everywhere on the arXiv. This looks interesting but seems to require a lot of background that i’m not sure i want to bother collecting. Maybe someday.

The Income Fluctuation Problem and the Evolution of Wealth. Modeling personal wealth and saving.

Robust Stackelberg buyers in repeated auctions, or how to screw a seller who’s trying to screw you first. This sounds like a fun project to understand.

And finally, a few papers from the National Bureau of Economic Research:

Understanding the Mechanisms of Parental Divorce Effects on Child’s Higher Education.

Signaling and Employer Learning with Instruments. The opening claim: «The social and the private returns to education differ when education can increase productivity and also be used to signal productivity». Also interesting: «What an instrumental variable identifies depends crucially on whether the instrument is hidden from or observed by the employers. If the instrument is hidden, it identifies the private returns to education, but if the instrument is observed by employers, it identifies the social returns to education». Which instrumental variable is this? I’m curious. I’m very curious.

Controlling Tuberculosis? Evidence from the First Community-Wide Health Experiment. Here’s another one of those pessimistic “thought you had a good idea?, think again” articles. This one’s related to a public health intervention in the early 20th century. I wonder if the authors make any positive comments.

It’s the Phone, Stupid: Mobiles and Murder. The expanding presence of mobile phone service in the 1990s lowered the homicide rate. It can’t have been easy to obtain the data for this study. This sounds like amazing, interesting, and valuable work.

Common Risk Factors in Cryptocurrency. Oh, okay, finance for cryptocurrency products. (Should i care?).

La tranquila conciencia de estar preocupados

«Se veía que las personas que encontraba por el camino soportaban preocupaciones pero, al mismo tiempo, también parecían tranquilas. El comisario hacía poco caso de la obvia contradicción, el hecho de no poder explicar con palabras lo que percibía no significaba que no lo sintiese, que no lo percibiese por el sentir. Ese hombre y esa mujer que van ahí, por ejemplo, se ve que se gustan, que se quieren bien, que se aman, se ve que son felices, ahora mismo están sonriendo, y, con todo, no sólo están preocupados, sino que además, apetece decirlo así, tienen la tranquila y clara conciencia de eso».

—José Saramago, Ensayo sobre la lucidez, Debolsillo, p. 308

Richard Thaler, laziness, and changing people’s minds

Richard Thaler: How to change minds and influence people (by Tim Harford)

A few interesting notes:

As it happens, Nobel Prize winner Richard Thaler was a remarkably lazy person

«Whether or not you think behavioural economics matters, as a feat of persuading people to change their minds this is a case worth studying. So how did he do it? We could all do with knowing, because the world is full of stubborn-minded people who need to be persuaded to change their views about important things.»

«More important [than persistence] was that Prof Thaler fully understood what he was criticising. It is all too easy to attack those with whom we disagree based on the haziest idea of what they think and why they think it. But he grasped perfectly why his fellow economists embraced rationality, and the arguments (good and bad) they used to defend it. Prof Thaler engaged honestly and thoughtfully with the mainstream.» Of course, this places on me the intellectual duty to look up and understand Thaler’s contributions to economics

«His third technique was to look at the facts — not only clever statistics, but everyday facts about human existence. [] Having secured agreement on these facts, he then moved to arguing that they might matter.»

«Finally, Prof Thaler engaged people’s sense of curiosity. His long running series “Anomalies”, published in the widely-read scholarly Journal of Economic Perspectives, would often begin with a puzzle — some piece of behaviour or pattern in the data that simply didn’t make sense from the mainstream point of view. He would then explore the puzzle, extend it, and consider various possible solutions.»

»Economists would talk about these anomalies in faculty coffee rooms. They would, at Prof Thaler’s invitation, send in their own suggestions. Rather than telling his opponents they were wrong, Prof Thaler would present a conundrum and invite everyone to discuss it together. One of his critics, the great Chicago economist Merton Miller, was reduced to complaining that Prof Thaler’s anomalies were a distraction from serious modelling because they were simply too interesting.»

«Prof Thaler realised that most of us are lazy. Most of us don’t want to think hard about our beliefs, or challenges to them. His solution was to make sure those challenges were simply too intriguing to ignore.»