Algorithmic game theory

Algorithmic game theory (AGT) is an area in the intersection of game theory and computer science, with the objective of understanding and design of algorithms in strategic environments. Typically, in Algorithmic Game Theory problems, the input to a given algorithm is distributed among many players who have a personal interest in the output. In those situations, the agents might not report the input truthfully because of their own personal interests. We can see Algorithmic Game Theory from two perspectives: Analysis: given the currently implemented algorithms, analyze them using Game Theory tools (e.g., calculate and prove properties on their Nash equilibria, price of anarchy, and best-response dynamics) Design: design games that have both good game-theoretical and algorithmic properties. This area is called algorithmic mechanism design. On top of the usual requirements in classical algorithm design (e.g., polynomial-time running time, good approximation ratio), the designer must also care about incentive constraints. In 1999, the seminal paper of Nisan and Ronen drew the attention of the Theoretical Computer Science community to designing algorithms for selfish (strategic) users. As they claim in the abstract: We consider algorithmic problems in a distributed setting where the participants cannot be assumed to follow the algorithm but rather their own self-interest. As such participants, termed agents, are capable of manipulating the algorithm, the algorithm designer should ensure in advance that the agents’ interests are best served by behaving correctly. Following notions from the field of mechanism design, we suggest a framework for studying such algorithms. In this model the algorithmic solution is adorned with payments to the participants and is termed a mechanism. The payments should be carefully chosen as to motivate all participants to act as the algorithm designer wishes. We apply the standard tools of mechanism design to algorithmic problems and in particular to the shortest path problem.

About this result

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 categories (5)

Related concepts (3)

Related courses (3)

Related lectures (3)

Related people (1)

Related publications (12)

MGT-300: Game theory and strategic decisions

Game theory studies the strategic interactions between rational agents. It has a myriad of applications in politics, business, sports. A special branch of Game Theory, Auction Theory, has recently g

FIN-620: Game Theory

Game theory deals with multiperson strategic decision making. Major fields of Economics, such as Microeconomics, Corporate Finance, Market Microstructure, Monetary Economics, Industrial Organization,

MGT-431: Information: strategy & economics

Introduction to the economics of information and its strategic ramifications. The main objectives are to use economic theory to understand strategic interactions in the presence of uncertainty, estima

Algorithmic mechanism design

Algorithmic mechanism design (AMD) lies at the intersection of economic game theory, optimization, and computer science. The prototypical problem in mechanism design is to design a system for multiple self-interested participants, such that the participants' self-interested actions at equilibrium lead to good system performance. Typical objectives studied include revenue maximization and social welfare maximization. Algorithmic mechanism design differs from classical economic mechanism design in several respects.

Auction theory

Auction theory is an applied branch of economics which deals with how bidders act in auction markets and researches how the features of auction markets incentivise predictable outcomes. Auction theory is a tool used to inform the design of real-world auctions. Sellers use auction theory to raise higher revenues while allowing buyers to procure at a lower cost. The conference of the price between the buyer and seller is an economic equilibrium. Auction theorists design rules for auctions to address issues which can lead to market failure.

Mechanism design

Mechanism design is a field in economics and game theory that takes an objectives-first approach to designing economic mechanisms or incentives, toward desired objectives, in strategic settings, where players act rationally. Because it starts at the end of the game, then goes backwards, it is also called reverse game theory. It has broad applications, from economics and politics in such fields as market design, auction theory and social choice theory to networked-systems (internet interdomain routing, sponsored search auctions).

Game-theoretic Mechanisms for Eliciting Accurate Information

Boi Faltings

Artificial Intelligence often relies on information obtained from others through crowdsourcing, federated learning, or data markets. It is crucial to ensure that this data is accurate. Over the past 20 years, a variety of incentive mechanisms have been dev ...

2022

Distributional Robustness in Mechanism Design

Cagil Kocyigit

Mechanism design theory examines the design of allocation mechanisms or incentive systems involving multiple rational but self-interested agents and plays a central role in many societally important problems in economics. In mechanism design problems, agen ...

EPFL2020

An important class of game-theoretic incentive mechanisms for eliciting effort from a crowd are the peer based mechanisms, in which workers are paid by matching their answers with one another. The other classic mechanism is to have the workers solve some g ...

ASSOC ADVANCEMENT ARTIFICIAL INTELLIGENCE2019

Markets

In economics, a market is a composition of systems, institutions, procedures, social relations or infrastructures whereby parties engage in exchange. While parties may exchange goods and services by barter, most markets rely on sellers offering their goods or services (including labour power) to buyers in exchange for money. It can be said that a market is the process by which the prices of goods and services are established. Markets facilitate trade and enable the distribution and allocation of resources in a society.

Macroeconomics

Macroeconomics is a branch of economics that deals with the performance, structure, behavior, and decision-making of an economy as a whole—for example, using interest rates, taxes, and government spending to regulate an economy's growth and stability. This includes regional, national, and global economies. Macroeconomists study topics such as GDP (Gross Domestic Product), unemployment (including unemployment rates), national income, price indices, output, consumption, inflation, saving, investment, energy, international trade, and international finance.

Economics

Economics (ˌɛkəˈnɒmᵻks,_ˌiːkə-) is a social science that studies the production, distribution, and consumption of goods and services. Economics focuses on the behaviour and interactions of economic agents and how economies work. Microeconomics analyzes what's viewed as basic elements in the economy, including individual agents and markets, their interactions, and the outcomes of interactions. Individual agents may include, for example, households, firms, buyers, and sellers.

Auctions and Mechanism Design CS-430: Intelligent agents

Explores auctions, mechanisms, and social choice functions, including bidding strategies and truthful mechanisms.

Introduction to Game Theory CS-430: Intelligent agents

Covers game theory fundamentals, Nash equilibrium, and strategic interactions in multi-agent systems.

Basics of Demand: Determinants and Bidding Strategies

Covers the determinants of willingness to pay and bidding strategies in economics.