Improving Access to Electric Vehicle Charging Stations

Unusual approach using game theory

 Improving Access to Electric Vehicle Charging Stations

NC State University News

Matt Shipman, October 17, 2022

North Carolina State University (NC State) researchers aim to make electric vehicles more appealing to drivers by improving access to charging stations via a game theory-based computational tool. The tool uses a game theory framework to balance factors such as the length of time required to reach a charging station, the cost of using it, wait times for access, and the potential for fines for exceeding charging time limits. The method helps users find the nearest charging station, and incorporates a dynamic system that charging station operators can use to ascertain how long vehicles can spend charging before they must make way for the next vehicle. ... ' 

Poker and Game Theory

Re Game-theory Optimal Poker

How Game Theory Changed Poker

The Wall Street Journal, Oliver Roeder, January 13, 2022

Researchers at the University of Alberta's Computer Poker Research Group in Canada pioneered game theory mathematics that has transformed how professional poker players approach the game. Poker's mathematical complexity rivals or surpasses that of chess while adding randomness and hidden data, bringing it closer to the "real world" that artificial intelligence scientists want to control. Many poker-playing algorithms incorporate the minimization of regret, a mathematical concept for decision-making in uncertain environments. Game-theory optimal poker players hire programmers to analyze their game data, finding "leaks" or errors in strategy, and to conduct game-theoretical analyses, calculating optimal plays in any of the innumerable situations that can confront a player.  ... ' 

Game Theory for Large Scale Data Analysis

Intriguing thought, technical.

Game theory as an engine for large-scale data analysis  By Brian McWilliams, Ian Gemp, Claire Vernade

EigenGame maps out a new approach to solve fundamental ML problems.

Modern AI systems approach tasks like recognising objects in images and predicting the 3D structure of proteins as a diligent student would prepare for an exam. By training on many example problems, they minimise their mistakes over time until they achieve success. But this is a solitary endeavour and only one of the known forms of learning. Learning also takes place by interacting and playing with others. It’s rare that a single individual can solve extremely complex problems alone. By allowing problem solving to take on these game-like qualities, previous DeepMind efforts have trained AI agents to play Capture the Flag and achieve Grandmaster level at Starcraft. This made us wonder if such a perspective modeled on game theory could help solve other fundamental machine learning problems.

Today at ICLR 2021 (the International Conference on Learning Representations), we presented “EigenGame: PCA as a Nash Equilibrium,” which received an Outstanding Paper Award. Our research explored a new approach to an old problem: we reformulated principal component analysis (PCA), a type of eigenvalue problem, as a competitive multi-agent game we call EigenGame. PCA is typically formulated as an optimisation problem (or single-agent problem); however, we found that the multi-agent perspective allowed us to develop new insights and algorithms which make use of the latest computational resources. This enabled us to scale to massive data sets that previously would have been too computationally demanding, and offers an alternative approach for future exploration. ... " 

Game Theory Modeling Vaccine Rollout

Excerpt,   Found Game Theory to be useful, as the article suggests, when you are modeling problems that include potentially competing and cooperative players.   Most difficult were establishing varying payoffs.    Full article at link.  

How Game Theory Could Solve the COVID-19 Vaccine Rollout Puzzle

Rand, Fortune

"  ..... Game theory is a field of mathematics that models competitive and cooperative human interactions, where a “game” is composed of players, their actions, and the resulting payoffs. Often applied to competitive economic and political contexts, game theory can be valuable for predicting behavior and incentivizing decisions that improve a broader system. In the context of health care, it models individuals' decisionmaking criteria when accessing health services.

In the COVID-19 vaccine rollout, the “players” would be individuals seeking care; the actions would be the individuals' selection of a facility; and the payoffs would be measured in terms of how individuals perceive the risk of vaccination, distance traveled, and level of service available at a chosen facility. The level of service might be captured in terms of the congestion of facilities or a supply-demand ratio.

In past research, game theory predicted whether or not individuals would vaccinate, if herd immunity could be achieved, potential vaccine accessibility, and how individuals select vaccination centers. Among other things, these analyses can help calculate how many vaccines need to be sent to each vaccination center. This approach has been proven valuable in after-the-fact analyses of the H1N1 vaccination campaign in 2009 and the response to Haiti's cholera epidemic in 2010. In those scenarios it enabled the identification of “equilibrium solutions,” which represent how individuals may select vaccination centers when given the freedom to choose. .... " 

Competition in Retail Pricing Algorithms

Algorithms don't just come from the suggestion of AI methods,  we worked with many, over many years.   Here an attempt to infer retail pricing strategies from data, and implications.  Note increased data from online.  Also note the implication of action and reaction,  what actions are being caused by competitive actions.   Can be taken all the way to game theory, which we examined as well.

Competition in Pricing Algorithms
by Zach Y. Brown and Alexander MacKay

The adoption of pricing technology can lead to higher prices, by increasing the frequency of price changes and/or encoding pricing strategies in algorithms. This raises new antitrust questions for policymakers, as firms do not need to coordinate or collude to raise prices.
Author Abstract

Increasingly, retailers have access to better pricing technology, especially in online markets. Through pricing algorithms, firms can automate their response to rivals’ prices. What are the implications for price competition? We develop a model in which firms choose algorithms, rather than prices. Even with simple (i.e., linear) algorithms, competitive equilibria can have higher prices than in the standard simultaneous Bertrand pricing game. Using hourly prices of over-the-counter drugs from five major online retailers, we document evidence that these retailers possess different pricing technologies. In addition, we find pricing patterns consistent with competition in pricing algorithms. A simple calibration of the model suggests that pricing algorithms lead to meaningful increases in markups, especially for firms with superior pricing technology.

Paper Information
Full Working Paper Text (pdf)
Working Paper Publication Date: November 2019
HBS Working Paper Number: HBS Working Paper #20-067
Faculty Unit(s): Strategy

Game Theory and Autonomous Cars

How do we construct models about elements of autonomy and how they interact our own behavior?

Game Theory and AI Systems: Use Case For Autonomous Cars  By Dr. Lance Eliot, CEO, Techbrium Inc.   AI Trends Insider

When you get onto the freeway, you are essentially entering into the matrix. For those of you familiar with the movie of the same name, you’ll realize that I am suggesting that you are entering into a kind of simulated world as your car proceeds up the freeway onramp and into the flow of traffic. Whether you know it or not, you are indeed opting into playing a game, though one much more serious than an amusement park bumper cars arena.

On the freeway, you are playing a game of life-and-death.

It might seem like you are merely driving to work or trying to get to the ballgame, but the reality is that for every moment you are on the freeway you are at risk of your life. Your car can go awry, say it suddenly loses a tire, and you swerve across the lanes, possibly ramming into other cars or going off a freeway embankment. Or, you might be driving perfectly well, and all of a sudden, a truck ahead of you unexpectedly slams on its breaks and you crash into the truck.

 I hope this doesn’t seem morbid. Nor do I want to appear to be an alarmist. But, you have to admit, these scenarios are all possible and you are in fact at the risk of your life while on the freeway. For a novice driver, such as a teenager starting to drive, you can usually see on their face an expression that sums up the freeway driving circumstance – abject fear. They know that one wrong move can be fatal. They are usually somewhat surprised that anyone would trust a teenager to be in such a situation of great responsibility. Most teenagers are held in contempt by adults for a lack of taking responsibility seriously, and yet we let them get behind the wheel of a multi-ton car and drive amongst the rest of us. .... 

 For related article about how greed motivates drivers and its impacts on self-driving cars, see: 

 Leveraging Game Theory

Anyway, if you are willing to concede that we can think of freeway driving as a game, you then might be also willing to accept the idea that we can potentially use game theory to help understand and model driving behavior.

With game theory, we can consider the freeway driving and the traffic to be something that can be mathematically modeled. This mathematical model can take into account conflict. A car cuts off another car. One car is desperately trying to get ahead of another car. And so on. The mathematical model can also take into account cooperation. As you enter onto the freeway, perhaps other cars let you in by purposely slowing down and making an open space for you. Or, you are in the fast lane and want to get over to the slow lane, so you turn on your blinker and other cars let you make your way from one lane to the next. There is at times cooperative behavior on the freeway, and likewise at times there is behavior involving conflict. ..... "

Game Theory and Human/Robot Goals

Good way to systematically think about the problem, but we never found it to be a way to solve the problem.  I like the approach outlined here:

How Game Theory Can Bring Humans, Robots Closer Together 
University of Sussex (U.K.)
By Neil Vowles

Researchers at the University of Sussex and Imperial College London in the U.K., and Nanyang Technological University in Singapore, have used game theory to enable robots to assist humans in a safe and versatile manner. The researchers used adaptive control and Nash equilibrium game theory to program a robot that can understand its human user's behavior in order to better anticipate their movements and respond to them. The researchers overcame the robot’s inability to understand a human's intentions by enabling the robot to identify its human user while safely and efficiently interacting with their motion. The resulting system allows a robot to continuously learn the human user's control and adapt its own control correspondingly. Imperial College London’s Etienne Burdet said that to apply game theory to human-robot interaction, “it was necessary to understand how the robot can identify the human user’s control goals simultaneously to smoothly interacting with them."  ... " 

Game Theory and Society

A favorite topic is how game theory can be made practical   We tried that and got little out of it beyond descriptive rather than prescriptive models.   Is this new approach useful beyond that?  Note especially regarding networks and social dynamics.

What game theory tells us about politics and society
Economist Alexander Wolitzky uses game theory to model institutions, networks, and social dynamics.   By Peter Dizikes | MIT News Office

How Businesses Can Get Inside the Minds of Their Competitors

If we could, perhaps we could make a better use of game dynamics.     Or just simulate their behavior under multiple contexts.

How Businesses Can Get Inside the Minds of Their Competitors

Wharton's Anoop Menon and Jaeho Choi discuss their research on using natural language processing to analyze competitive strategy.

Every business would love to know the minds of its competitors, and what they are likely to do next. Strategy analysts have thus far used simple tools that employ mostly financial and other structured data to try and predict competitors’ moves. But new research at Wharton has shown how natural language processing techniques could be used to parse tomes of unstructured data such as text buried in conference calls or annual reports to more accurately anticipate competitor strategies.

The research opens new pathways to measure and test assumptions firms make in their competitive strategies, and to “visualize how firms are positioned with respect to each other, and then map that on to performance consequences,” says Wharton management professor Anoop Menon. His research paper, “What You Say Your Strategy Is and Why It Matters: Natural Language Processing of Unstructured Texts,” is co-authored with Jaeho Choi, a Wharton doctoral student, and Haris Tabakovic, an associate at The Brattle Group, a Boston-based international arbitration services firm.

For their study, the researchers used natural language processing (NLP) techniques to measure “strategic change, positioning, and focus,” across their sample of 50,506 business descriptions of publicly held companies contained in their 10-K annual reports, from 1997 to 2016.

Menon and Choi shared the main takeaways for business strategy analysis from their research with Knowledge@Wharton.

An edited transcript of the conversation follows.

Knowledge@Wharton: Anoop, could you tell us what led you to explore this topic in your research? What was your objective?

Anoop Menon: The notion that there is a lot of information that is buried in unstructured text has been around for a while. We know that strategy is very complicated, but we tend to measure it using very, “simple metrics” like a few financials here and there. But we all agree and understand there is a huge amount of information that is buried in text like conference calls and annual reports that gets at the meat of the strategy, how the strategists are thinking about competition and product market choices.

Sadly, we currently don’t have a really good technique or set of techniques to get at that information. So that was the starting point. About six or seven years ago, my co-author Haris [Tabakovic] and I came across this burgeoning line of research in computer science about using natural language processing techniques to extract text, but in very different fields – not ours. [There were] some applications to political science but not at all to strategy. We said we should be able to take some of those techniques and get at the information that is buried in the text..... "

Introduction to Game Theory

We used Game theory linked methods to try to understand competitive activity.   We used these methods not necessarily to solve for a best strategy, but to think about how to gather data about the underlying competitive process.  Follow all the parts:

KDnuggets provides a simple, non technical view of game theory.  Part 1:

Check out this game theory basics post for an introduction to Two-player Sequential games — 

Dominant Strategies, Nash Equilibrium, and Cooperation vs. Defection.

Game theory generally refers to the study of mathematical models that describe the behavior of logical decision-makers. It is widely used in many fields such as economics, political science, politics, and computer science, and can be used to model many real-world scenarios. Generally, a game refers to a situation involving a set of players who each have a set of possible choices, in which the outcome for any individual player depends partially on the choices made by other players.  ... "

When to Hold Em, When to Compete

Nash Equilibrium's use in Competitive Situations is re-examined, with hope for its use in competitive behavior situations.  We looked at it for that and found no golden egg, but it doesn't mean others couldn't find it.   A reexamination.   Complexity technical.  Just because optimum solutions are known to be probably impossibly hard, very good solutions are probably better than what we are doing today.

When to Hold 'Em    By CACM Staff 
Communications of the ACM, Vol. 61 No. 6, Pages 6-7
10.1145/3210585

Neil Savage deserves praise for his informative overview of recent computational results related to Nash equilibrium in his news story "Always Out of Balance" (Apr. 2018). I fully agree that the notion of Nash equilibrium does not always reflect how competitors behave in competitive situations, and that the fact that Nash equilibrium is provably computationally intractable makes it less useful than John Nash himself might have envisioned when he developed it. However, Savage also overstated (somewhat) the effect of intractability by claiming the intractability of computing Nash equilibrium necessitates researchers abandon this notion in favor of other competition-related ideas.

While looking for Nash equilibrium yields additional computational complexity, the decision-making problem is, in general, already computationally intractable (NP-hard) for non-competitive situations (such as when a company makes internal planning decisions). In doing so, a company would be looking for an optimal solution (such as one that would aim to help produce maximum profit), but computational optimization is, in general, NP-hard. Such computational intractability does not mean researchers have to abandon the idea of optimization and look for other ideas. Many real-life problems are NP-hard (such as robotic movement) and what makes working on them such an intellectual and computational challenge.

Indeed, there is no general feasible algorithm (unless P = NP), so computer scientists need to be creative when designing algorithms for specific practical problems.  .... " 

Vladik Kreinovich, EL Paso, TX, USA

Cancer Algorithm and Game Theory

New heath care approaches.

Cancer algorithm uses game theory to Double Survival time

Using algorithms to monitor cancer evolution and apply game theory to their treatment has doubled the survival time of men with advanced prostate cancer    By Andy Coghlan in NewScientist

Approaching cancer treatment as a game has doubled the survival time of men with advanced prostate cancer. This achievement could mark the start of using game theory to target a range of cancers more cleverly.

“This approach is elegant and exciting, and shows real promise to delay treatment failure,” says Charles Swanton at the Francis Crick Institute in London.

People with cancer aren’t usually killed by their initial tumour, but by the rapidly evolving secondary tumours that occur once the disease …  "

Update: Adversarial Risk Analysis Talk

 Talk given this week by Dr David Banks of Duke University and sponsored by Yichen Qin,  Assistant Professor, Department of Operations, Business Analytics, and Information Systems,  Lindner College of Business, University of Cincinnati,  on April 6, 2018

Adversarial Risk Analysis Talk, full announcement.

Speaker: Dr. David Banks, Duke University

Title: Adversarial Risk Analysis

Abstract: Adversarial Risk Analysis (ARA) is a Bayesian alternative to classical game theory. Rooted in decision theory, one builds a model for the decision-making of one's opponent, placing subjective distributions over all unknown quantities. Then one chooses the action that maximizes expected utility. This approach aligns with some perspectives in modern behavioral economics, and enables principled analysis of novel problems, such as a multiparty auction in which there is no common knowledge and different bidders have different opinion about each other.   .... " 

Here are the slides from the talk  (Technical)

Good talk. In particular because it dealt with  how people work in interactions.   Either versus nature, or versus other humans, here in some sort of competition.  The most common game example used was the Auction.  In the cases described these were adversarial.  Under the structure of this  'game' to win the auction.   Humans in any interaction build a model of who they are interacting with.   The methods proposed construct numerical methods to define the value of alternative strategies.

 But it immediately came to  mind that these methods don't need to be adversarial.   When people converse, or ask for help from an adviser  (Human or machine).  they are looking to maximize the value of the interaction.   In a chatbot, for example a person wants to solve a problem, the chatbot has defined knowledge.  How should the interaction proceed?   How should these advisory approaches be strategically designed?  Under constraints and costs?   How do we rate Assistants in an approach to provide value?  Whats the structure of that game?    Examining.

Always Out of Balance: Looking for Equilibria

Nicepiece, which includes a short, easy to understand video  that explains the basics of the Nash Equilibrium.  We sought to use these methods to understand competitive behavior.   Not very successfully I admit, but the approach did make us think of better models for the processes and integrated behaviors involved.  Even the supposed rationality of decisions were an issue.  It is what we called competitive modeled economics. What were the right counter behavior for competition?

Always Out of Balance  By Neil Savage  in  
Communications of the ACM, Vol. 61 No. 4, Pages 12-14

"Computational Theorists show that there is no easy way to to find Nash Equilibria, so game theory will have to look in new directions"....

When John Nash won the Nobel Prize in economics in 1994 for his contribution to game theory, it was for an elegant theorem. Nash had shown that in any situation where two or more people were competing, there would always be an equilibrium state in which no player could do better than he was already doing. That theorem has since been used to model all sorts of competitive systems, from markets to nuclear strategy to living creatures competing for finite resources.

"In some sense, it started not just game theory, but also modern economics," says Christos Papadimitriou, a professor of computer science at Columbia University. Nash's idea gave economists the ability to create hypotheses about market design, for instance. They could now ask what happened when a market reached equilibrium.

Nash's theorem is also an essential component of game theory, which had first been developed by computing pioneer John von Neumann. "Games are a mathematical thought experiment and we study them just because we want to understand how strategic rational players would behave in situations of conflict," Papadimitriou says. "And that's important because all of society is full of such situations."

Though Nash proved that at least one such Nash equilibrium existed for all games, what he did not do was predict how an equilibrium might be reached in a given situation. Was there, scientists wanted to know, an algorithm that would show players how to efficiently reach an equilibrium? After more than 65 years of researchers' studying that question, the answer turns out to be no, there is not. That means economists had better start rethinking some of their models. .... "

Talk: Adversarial Risk Analysis

Of interest in particular, due to the adversarial element.   Risk analysis does not often enough consider the intelligent nature of agents that create risk.   Competitors for example, and now even intelligent agents in the form of assistants or other machine driven systems.

The OBAIS department at the Lindner College of Business, University of Cincinnati, invites you to attend the Lindner Research Excellence Seminar and Professional Development Discussion:

Research Seminar:
Date and time: Friday, April 6, 2018, 10:30AM-12:00PM 
Location: Lindner Hall 218
Speaker: Dr. David Banks, Duke University
Title: Adversarial Risk Analysis

Abstract: Adversarial Risk Analysis (ARA) is a Bayesian alternative to classical game theory. Rooted in decision theory, one builds a model for the decision-making of one's opponent, placing subjective distributions over all unknown quantities. Then one chooses the action that maximizes expected utility. This approach aligns with some perspectives in modern behavioral economics, and enables principled analysis of novel problems, such as a multiparty auction in which there is no common knowledge and different bidders have different opinion about each other.

This presentation is based on:
Rios Insua, D., Rios, J., Banks, D. L., “Adversarial Risk Analysis,” Journal of the American Statistical Association, 2009.
https://www.tandfonline.com/doi/abs/10.1198/jasa.2009.0155
Banks, D. L., Rios, J., Rios Insua, D., “Adversarial Risk Analysis,” Chapman and Hall/CRC, 2015, ISBN 9781498712392.

https://www.crcpress.com/Adversarial-Risk-Analysis/Banks-Aliaga-Insua/p/book/9781498712392

Best wishes,
Yichen Qin,  Assistant Professor
Department of Operations, Business Analytics, and Information Systems
Lindner College of Business, University of Cincinnati
Website: http://business.uc.edu/academics/departments/obais/faculty/qinyn.html
Email: qinyn@ucmail.uc.edu

CIA Releases Operational Board Games

Intriguing.   How useful these might be is unclear.  I recall seeing a board-style game with supposed espionage related origins that utilized game theory.   We edited some of the player parameters to get something that might be useful for real-life business.    It was suggested that the game could be used to set operational and strategic approaches for competitive activity. 

CIA’s in-house board games can now be yours thanks to FOIA request
After SXSW 2017 reveal, CIA releases buckets of marked-up board game design notes.  By Sam Machkovech  in ArsTechnica

Last year, the CIA used a South By Southwest festival event to reveal one of its weirdest training exercises: a series of globe-trotting, espionage-filled board games. If you're wondering why we're circling back to this news almost exactly one year later, we have four letters for you: FOIA.

A series of Freedom of Information Act requests, filed last June by Southern California tech entrepreneur Doug Palmer, finally bore fruit last week. The CIA has now released rules, art, and design documents for the two board games we played at last year's SXSW.  .... " 

Game Theory and Cybersecurity

A Purdue connection informed me of this. A rare practical pointer to Nash equilibrium in game theory.   And 'Prospect theory' which I had not heard of.  Dealing with aspects of risk.  But  I see it is what Kahneman's work is called.  Taking a closer look.

Game Theory Harnessed for Cybersecurity of Large-Scale Nets
Purdue University News   By Emil Venere

Researchers at Purdue University are leading the development of a platform for improving the cybersecurity of large-scale networks by tapping game theory and new intelligent algorithms. Purdue professor Shreyas Sundaram says the team has harnessed Nash equilibrium as well as prospect theory, defining how people make decisions amid uncertainty and risk. Sundaram thinks the work "will lead to a more complete understanding of the vulnerabilities that arise in large-scale interconnected systems and guide us to the design of more secure systems." The team has demonstrated the formulation of an "optimization problem" to efficiently calculate how much a given stakeholder will decide to invest, and they plan to use the "moving-target defense," in which the system can reconfigure itself to lower a repeated cyberattack's success rate. "The project will provide new insights into the types of decisions that humans make when faced with security threats, via a comprehensive approach spanning theory and experiments," says Purdue professor Timothy Cason. ... "

Links vs Privacy vs Asset Value?

The researchers want to implement this as a browser extension.  Could a variation on this be used to estimate asset value of data over time?   ....

Algorithm shows the data you give away when clicking suggested links
Researchers found the best way to surf recommendation engines without giving up privacy.

If you're roaming the internet, you might run across recommendation engines. Some offer products or services you'd actually want to use, but does interacting with them harm your privacy even more? Researchers developed an algorithm to reveal how much info you're handing over when you click around, essentially picking out which parts of a recommendation engine are and aren't safe for privacy-minded users.

The team fed their algorithm datasets from recommendation engines Movielens and Jester. Essentially, their math weighs the value users get by clicking against the personal info they're disclosing, and points out when users would be handing over too much information for too little effect. While not everyone uses those particular services, they've definitely used a recommendation before if they've spun up a Pandora station or let Netflix suggest films.

Of course, since these are academics, their paper (PDF) goes a step further, applying game theory to the algorithm's results in order to develop clicking strategies for the average internet browser to adopt. At best, following a shrewd strategy means a little over 5 percent of clicking certain things sides heavily in the user's favor. On the other side of the equation, it identifies 16 percent of clicks that would hand over much more personal info with very little gained.  .... " 

Game Theory and Competitive Strategy

A favorite topic for corporate strategy considerations, but as we discovered, somewhat hard to apply in realistic circumstances.   Especially for competitive interactions. Fairly non-technical view.

In Game Theory, No Clear Path to Equilibrium   In Quanta Magazine.
In 1950, John Nash — the mathematician later featured in the book and film “A Beautiful Mind” — wrote a two-page paper that transformed the theory of economics. His crucial, yet utterly simple, idea was that any competitive game has a notion of equilibrium: a collection of strategies, one for each player, such that no player can win more by unilaterally switching to a different strategy.

Nash’s equilibrium concept, which earned him a Nobel Prize in economics in 1994, offers a unified framework for understanding strategic behavior not only in economics but also in psychology, evolutionary biology and a host of other fields. Its influence on economic theory “is comparable to that of the discovery of the DNA double helix in the biological sciences,” wrote Roger Myerson of the University of Chicago, another economics Nobelist.

When players are at equilibrium, no one has a reason to stray. But how do players get to equilibrium in the first place? In contrast with, say, a ball rolling downhill and coming to rest in a valley, there is no obvious force guiding game players toward a Nash equilibrium.  .... " 

Game Theory in Practice

A apace we worked in, especially to understand and react to models of competitive activity.  In practice usually means getting good understanding of how these models work with available data.

In the Economist  (May require subscription)
Game theory in practice
Computing: Software that models human behaviour can make forecasts, outfox rivals and transform negotiations  .... "