Concept# Minimax

Summary

Minmax (sometimes Minimax, MM or saddle point) is a decision rule used in artificial intelligence, decision theory, game theory, statistics, and philosophy for minimizing the possible loss for a worst case (maximum loss) scenario. When dealing with gains, it is referred to as "maximin" – to maximize the minimum gain. Originally formulated for several-player zero-sum game theory, covering both the cases where players take alternate moves and those where they make simultaneous moves, it has also been extended to more complex games and to general decision-making in the presence of uncertainty.
Game theory
In general games
The maximin value is the highest value that the player can be sure to get without knowing the actions of the other players; equivalently, it is the lowest value the other players can force the player to receive when they know the player's action. Its formal definition is:
:\underline{v_i} = \max_{a_i} \min_{a_{-i}} {v_i(a_i,a_{-i})}

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading

Related publications (5)

Loading

Loading

Loading

Related units

Related people

No results

No results

Related courses (9)

EE-556: Mathematics of data: from theory to computation

This course provides an overview of key advances in continuous optimization and statistical analysis for machine learning. We review recent learning formulations and models as well as their guarantees, describe scalable solution techniques and algorithms, and illustrate the trade-offs involved.

CS-430: Intelligent agents

Software agents are widely used to control physical, economic and financial processes. The course presents practical methods for implementing software agents and multi-agent systems, supported by programming exercises, and the theoretical underpinnings including computational game theory.

EE-570: Power system restructuring and deregulation

This course presents different types and mechanisms of electricity markets. It addresses in particular their impacts on power/distribution systems operation and consequently the appropriate strategies capable to ensure a secure and reliable functioning.

Related concepts (23)

Game theory

Game theory is the study of mathematical models of strategic interactions among rational agents. It has applications in all fields of social science, as well as in logic, systems science and computer

Alpha–beta pruning

Alpha–beta pruning is a search algorithm that seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its search tree. It is an adversarial search algorithm used commonly

Nash equilibrium

In game theory, the Nash equilibrium, named after the mathematician John Nash, is the most common way to define the solution of a non-cooperative game involving two or more players. In a Nash equilib

Related lectures (22)

Model specification is an integral part of any statistical inference problem. Several model selection techniques have been developed in order to determine which model is the best one among a list of possible candidates. Another way to deal with this question is the so-called model averaging, and in particular the frequentist approach. An estimation of the parameters of interest is obtained by constructing a weighted average of the estimates of these quantities under each candidate model. We develop compromise frequentist strategies for the estimation of regression parameters, as well as for the probabilistic clustering problem. In the regression context, we construct compromise strategies based on the Pitman estimators associated with various underlying errors distributions. The weight given to each model is equal to its profile likelihood, which gives a measure of the goodness-of-fit. Asymptotic properties of both Pitman estimators and profile likelihood allow us to define a minimax strategy for choosing the distributions of the compromise, involving a notion of distance between distributions. Performances of such estimators are then compared to other usual and robust procedures. In the second part of the thesis, we develop compromise strategies in the probabilistic clustering context. Although this clustering method is based on mixtures of distributions, our compromise strategies are not applied directly to the estimates of the parameters, but on the posterior probabilities of membership. Two types of compromise are presented, and the performances of resulting classification rules are investigated.

An important prerequisite for developing trustworthy artificial intelligence is high quality data. Crowdsourcing has emerged as a popular method of data collection in the past few years. However, there is always a concern about the quality of the data thus collected. This thesis addresses two major challenges in collecting high quality data from a crowd: 1) how to incentivize crowd workers to report accurate data; 2) how to ensure that the data collection mechanism is transparent and fair.
We first propose two novel peer-consistency mechanisms for crowdsourcing: the Deep Bayesian Trust (DBT) mechanism and the Personalized Peer Truth Serum (PPTS). The DBT mechanism incentivizes workers to report accurate answers for objective questions with discrete ground truth answers. It is useful, for example, in collecting labels for supervised machine learning tasks. The mechanism ensures dominant uniform strategy incentive compatibility and fair rewards to the workers. The PPTS incentivizes workers to truthfully report their personal data (for example, body measurements). Since data is personal in nature, the tasks can not be shared between two workers. We show that when individuals report combinations of multiple personal data attributes, the correlation between them can be exploited to find peers and provide guarantees on the incentive compatibility of the mechanism.
We next address the transparency issue of data collection. Smart contracts often rely on a trusted third party (oracle) to get correct information about real-world events. We show how peer-consistency mechanisms can be used to build decentralized, trustless and transparent data oracles on blockchain. We derive conditions under which a peer-consistency incentive mechanism can be used to acquire truthful information from an untrusted and self-interested crowd, even when the crowd has outside incentives to provide wrong information. We also show how to implement the peer-consistency mechanisms in Ethereum. We discuss various non-trivial issues that arise in implementing peer-consistency mechanisms in Ethereum, suggest several optimizations to reduce gas cost and provide empirical analysis.
Finally, we address the problem of fair data collection from a crowd. Sharing economy platforms such as Airbnb and Uber face a major challenge in the form of peer-to-peer discrimination based on sensitive personal attributes such as race and gender. We show that how a peer-consistency incentive mechanism can be used to encourage users to go against common bias and provide a truthful rating about others, obtained through a more careful and deeper evaluation. In situations where an incentive mechanism canât be implemented, we show that a simple post-processing approach can also be used to correct bias in the reputation scores, while minimizing loss in the useful information provided by the scores. We also address the problem of fair and diverse data collection from a crowd under budget constraints. We propose a novel algorithm which maximizes the expected accuracy of the collected data, while ensuring that the errors satisfy desired notions of fairness w.r.t sensitive attributes.

,

1999