• Skip to main content
  • Skip to primary sidebar

Biz Builder Mike

You can't sail Today's boat on Yesterdays wind - Michael Noel

  • Tokenomics is not Economics – Digital CX -The Digital Transformation
  • Resume / CV – Michael Noel
  • Contact Us
  • Featured
You are here: Home / AI / Researcher solves nearly 60-year-old game theory dilemma

Mar 14 2023

Researcher solves nearly 60-year-old game theory dilemma

To understand how driverless vehicles can navigate the complexities of the road, researchers often use game theory — mathematical models representing the way rational agents behave strategically to meet their goals.

Dejan Milutinovic, professor of electrical and computer engineering at UC Santa Cruz, has long worked with colleagues on the complex subset of game theory called differential games, which have to do with game players in motion. One of these games is called the wall pursuit game, a relatively simple model for a situation in which a faster pursuer has the goal to catch a slower evader who is confined to moving along a wall.

Since this game was first described nearly 60 years ago, there has been a dilemma within the game — a set of positions where it was thought that no game optimal solution existed. But now, Milutinovic and his colleagues have proved in a new paper published in the journal IEEE Transactions on Automatic Control that this long-standing dilemma does not actually exist, and introduced a new method of analysis that proves there is always a deterministic solution to the wall pursuit game. This discovery opens the door to resolving other similar challenges that exist within the field of differential games, and enables better reasoning about autonomous systems such as driverless vehicles.

Game theory is used to reason about behavior across a wide range of fields, such as economics, political science, computer science and engineering. Within game theory, the Nash equilibrium is one of the most commonly recognized concepts. The concept was introduced by mathematician John Nash and it defines game optimal strategies for all players in the game to finish the game with the least regret. Any player who chooses not to play their game optimal strategy will end up with more regret, therefore, rational players are all motivated to play their equilibrium strategy.

This concept applies to the wall pursuit game — a classical Nash equilibrium strategy pair for the two players, the pursuer and evader, that describes their best strategy in almost all of their positions. However, there are a set of positions between the pursuer and evader for which the classical analysis fails to yield the game optimal strategies and concludes with the existence of the dilemma. This set of positions are known as a singular surface — and for years, the research community has accepted the dilemma as fact.

But Milutinovic and his co-authors were unwilling to accept this.

“This bothered us because we thought, if the evader knows there is a singular surface, there is a threat that the evader can go to the singular surface and misuse it,” Milutinovic said. “The evader can force you to go to the singular surface where you don’t know how to act optimally — and then we just don’t know what the implication of that would be in much more complicated games.”

So Milutinovic and his coauthors came up with a new way to approach the problem, using a mathematical concept that was not in existence when the wall pursuit game was originally conceived. By using the viscosity solution of the Hamilton-Jacobi-Isaacs equation and introducing a rate of loss analysis for solving the singular surface they were able to find that a game optimal solution can be determined in all circumstances of the game and resolve the dilemma.

The viscosity solution of partial differential equations is a mathematical concept that was non-existent until the 1980s and offers a unique line of reasoning about the solution of the Hamilton-Jacobi-Isaacs equation. It is now well known that the concept is relevant for reasoning about optimal control and game theory problems.

Using viscosity solutions, which are functions, to solve game theory problems involves using calculus to find the derivatives of these functions. It is relatively easy to find game optimal solutions when the viscosity solution associated with a game has well-defined derivatives. This is not the case for the wall-pursuit game, and this lack of well-defined derivatives creates the dilemma.

Typically when a dilemma exists, a practical approach is that players randomly choose one of possible actions and accept losses resulting from these decisions. But here lies the catch: if there is a loss, each rational player will want to minimize it.

So to find how players might minimize their losses, the authors analyzed the viscosity solution of the Hamilton-Jacobi-Isaacs equation around the singular surface where the derivatives are not well-defined. Then, they introduced a rate of loss analysis across these singular surface states of the equation. They found that when each actor minimizes its rate of losses, there are well-defined game strategies for their actions on the singular surface.

The authors found that not only does this rate of loss minimization define the game optimal actions for the singular surface, but it is also in agreement with the game optimal actions in every possible state where the classical analysis is also able to find these actions.

“When we take the rate of loss analysis and apply it elsewhere, the game optimal actions from the classical analysis are not impacted ,” Milutinovic said. “We take the classical theory and we augment it with the rate of loss analysis, so a solution exists everywhere. This is an important result showing that the augmentation is not just a fix to find a solution on the singular surface, but a fundamental contribution to game theory.

Milutinovic and his coauthors are interested in exploring other game theory problems with singular surfaces where their new method could be applied. The paper is also an open call to the research community to similarly examine other dilemmas.

“Now the question is, what kind of other dilemmas can we solve?” Milutinovic said.

[mailpoet_form id="1"]

Researcher solves nearly 60-year-old game theory dilemma Republished from Source https://www.sciencedaily.com/releases/2023/03/230314205331.htm via https://www.sciencedaily.com/rss/computers_math/artificial_intelligence.xml

crowdsourcing week

Written by bizbuildermike · Categorized: AI · Tagged: AI

Primary Sidebar

https://youtu.be/Qvad1CQ9WOM

Blockchain Weekly Rebooted –

During the Blockchain Spring 2016 to 2020 I hosted Blockchain Weekly. Each week I interviewed someone who was doing interesting things in the blockchain space. At one time we had 29k subscribers and we were consistently getting over 15k views a week on the channel. All of that went away during the lockdown, including the Gmail address that controlled that channel. Recently, I found some of the original videos on some old hard drives. So I’m reposting a few of the relevant ones while I am starting to shoot new Blockchain Weekly Episodes to be aired 1st quarter 2023. Please subscribe to bless the You Tube Algorithm, and allow me to let you know about any updates! Our Sponsor – https://BlockchainConsultants.io

The Utah State Legislature has approved a new law, the Utah Decentralized Autonomous Organizations Act, providing legal recognition and limited liability to decentralized autonomous organizations (DAOs). This legislation, also known as the “Utah LLDs,” was passed after the combined efforts of the Digital Innovation Taskforce and the Utah Blockchain Legislature. The Utah DAO Act defines […]

Search Here

Market Insights

  • FTX Founder Allegedly Sought Federal Regulation Before Collapse
  • DeFi Hack Linked to North Korea
  • US Banking Crisis Fuels Regulation Debate
  • HSBC approves multi-million-pound bonuses for Silicon Valley Bank UK staff
  • Swiss regulators consider UBS takeover of Credit Suisse to prevent collapse
  • Mid-Size Banks Ask for Deposit Insurance Extension
  • Former Coinbase CTO Bets $1 Million on Bitcoin Reaching $1 Million in 90 Days
  • Binance Responds to U.S. Senators Letter, Excludes Financial Data
  • Crypto Entrepreneur Bail Package Revised
  • DeFi Hacker Returns $5.4M to Euler Finance

Tags

Advanced materials (1) AI (259) andrewchen (4) Biz Builder Mike (28) Blockchain (834) Crowd Funding (69) crowdfundinsider (2) entrepreneur (969) eonetwork (43) Front Page Featured (33) MIT AI (89) startupmindset (146) Technology (676) virtual reality (1) youngupstarts (100)
  • Twitter
  • Facebook
  • About Us
  • LinkedIn
  • ANTI-SPAM POLICY
  • Google+
  • API Terms and Conditions
  • RSS
  • Archive Page
  • Biz Builder Mike is all about New World Marketing
  • Cryptocurrency Exchange
  • Digital Millennium Copyright Act (DMCA) Notice
  • DMCA Safe Harbor Explained: Why Your Website Needs a DMCA/Copyright Policy
  • Marketing? Well, how hard can that be?
  • Michael Noel
  • Michael Noel CBP
  • Noels Law of decentralization

Copyright © 2023 · Altitude Pro on Genesis Framework · WordPress · Log in