Algorithmic Game Theory 2021

A special issue of Algorithms (ISSN 1999-4893).

Deadline for manuscript submissions: closed (15 September 2021) | Viewed by 4682

Special Issue Editors

Facebook Core Data Science, London, UK
Interests: rtificial intelligence; game theory; optimization
Dipartimento di Elettronica, Informazione e Bioingegneria, Politecnico di Milano, 20133 Milan, Italy
Interests: artificial intelligence; multi-agent systems; algorithmic game theory; economics and computation
Dipartimento di Elettronica, Informazione e Bioingegneria, Politecnico di Milano, 20133 Milan, Italy
Interests: artificial intelligence; algorithmic game theory; machine learning; optimization

Special Issue Information

Dear Colleagues,

Algorithmic game theory (AGT) is a research field at the intersection of computer science and economics. The main goal of AGT is to devise computational tools that facilitate the adoption of economic models in practice, with a particular focus on strategic games. This is motivated by the fact that, nowadays, most economic transactions are carried out on the Internet and are oftentimes managed by complex algorithms. This makes the computational study of economic problems of paramount importance. In recent years, AGT has led to various milestone results in several fields of computer science, ranging across artificial intelligence, theoretical computer science, operations research, and machine learning. Thus, the advancement of AGT research would likely result in other high-impact results in the near future.

We invite you to submit high-quality papers to this Special Issue on “Algorithmic Game Theory”. Areas of interest include, but are not limited to, the following:

  • Equilibrium computation;
  • Dynamics in games;
  • Algorithmic mechanism design;
  • Market design and matching markets;
  • Computational social choice;
  • Bayesian persuasion and information structure design;
  • Algorithmic fairness;
  • Social networks, information cascades, and network diffusion;
  • Game theoretical models for privacy and security;
  • Learning in games and multi-agent learning.

Dr. Andrea Celli
Dr. Nicola Gatti
Dr. Alberto Marchesi
Guest Editors

Manuscript Submission Information

Manuscripts should be submitted online at www.mdpi.com by registering and logging in to this website. Once you are registered, click here to go to the submission form. Manuscripts can be submitted until the deadline. All submissions that pass pre-check are peer-reviewed. Accepted papers will be published continuously in the journal (as soon as accepted) and will be listed together on the special issue website. Research articles, review articles as well as short communications are invited. For planned papers, a title and short abstract (about 100 words) can be sent to the Editorial Office for announcement on this website.

Submitted manuscripts should not have been published previously, nor be under consideration for publication elsewhere (except conference proceedings papers). All manuscripts are thoroughly refereed through a single-blind peer-review process. A guide for authors and other relevant information for submission of manuscripts is available on the Instructions for Authors page. Algorithms is an international peer-reviewed open access monthly journal published by MDPI.

Please visit the Instructions for Authors page before submitting a manuscript. The Article Processing Charge (APC) for publication in this open access journal is 1600 CHF (Swiss Francs). Submitted papers should be well formatted and use good English. Authors may use MDPI's English editing service prior to publication or during author revisions.

Published Papers (2 papers)

Order results
Result details
Select all
Export citation of selected articles as:

Research

15 pages, 608 KiB  
Article
A Branch-and-Bound Algorithm for Polymatrix Games ϵ-Proper Nash Equilibria Computation
by Slim Belhaiza
Algorithms 2021, 14(12), 365; https://0-doi-org.brum.beds.ac.uk/10.3390/a14120365 - 16 Dec 2021
Viewed by 1913
Abstract
When several Nash equilibria exist in the game, decision-makers need to refine their choices based on some refinement concepts. To this aim, the notion of a ϵ-proper equilibria set for polymatrix games is used to develop 0–1 mixed linear programs and compute [...] Read more.
When several Nash equilibria exist in the game, decision-makers need to refine their choices based on some refinement concepts. To this aim, the notion of a ϵ-proper equilibria set for polymatrix games is used to develop 0–1 mixed linear programs and compute ϵ-proper Nash equilibria. A Branch-and-Bound exact arithmetics algorithm is proposed. Experimental results are provided on polymatrix games randomly generated with different sizes and densities. Full article
(This article belongs to the Special Issue Algorithmic Game Theory 2021)
Show Figures

Figure 1

7 pages, 276 KiB  
Communication
Short Communication: Optimally Solving the Unit-Demand Envy-Free Pricing Problem with Metric Substitutability in Cubic Time
by Marcos M. Salvatierra, Mario Salvatierra, Jr. and Juan G. Colonna
Algorithms 2021, 14(10), 279; https://0-doi-org.brum.beds.ac.uk/10.3390/a14100279 - 26 Sep 2021
Viewed by 1430
Abstract
In general, the unit-demand envy-free pricing problem has proven to be APX-hard, but some special cases can be optimally solved in polynomial time. When substitution costs that form a metric space are included, the problem can be solved in [...] Read more.
In general, the unit-demand envy-free pricing problem has proven to be APX-hard, but some special cases can be optimally solved in polynomial time. When substitution costs that form a metric space are included, the problem can be solved in O(n4) time, and when the number of consumers is equal to the number of items—all with a single copy so that each consumer buys an item—a O(n3) time method is presented to solve it. This work shows that the first case has similarities with the second, and, by exploiting the structural properties of the costs set, it presents a O(n2) time algorithm for solving it when a competitive equilibrium is considered or a O(n3) time algorithm for more general scenarios. The methods are based on a dynamic programming strategy, which simplifies the calculations of the shortest paths in a network; this simplification is usually adopted in the second case. The theoretical results obtained provide efficiency in the search for optimal solutions to specific revenue management problems. Full article
(This article belongs to the Special Issue Algorithmic Game Theory 2021)
Show Figures

Figure 1

Back to TopTop