The 15th International Symposium on Algorithmic Game Theory (SAGT)

Scope

The program of SAGT 2022 will include invited lectures, and presentations of  peer-reviewed submissions. Foundational work is solicited on topics including but not limited to:

• Solution Concepts in Game Theory
• Efficiency of Equilibria and Price of Anarchy
• Complexity Classes in Game Theory
• Computational Aspects of Equilibria and Fixed-Point Theorems
• Repeated Games and Convergence of Dynamics
• Algorithmic Mechanism Design
• Reputation, Recommendation and Trust Systems
• Network Games and Graph-Theoretic Aspects of Social Networks
• Cost-Sharing Algorithms and Analysis
• Computing with Incentives
• Computational Social Choice
• Fair Resource Allocation
• Decision Theory, and Pricing
• Auction Design and Analysis
• Economic Aspects of Distributed Computing
• Incentives in Blockchain
• Internet Economics and Computational Advertising

Industrial application works and position papers presenting novel ideas, issues, challenges and directions are also welcome.

The symposium proceedings shall be published by Springer in its LNCS/ARCoSS series. Accepted papers will be allocated at most 18 pages in the proceedings (in particular, at most 16 pages for the technical part and at most 2 pages for references, in line with the submission guidelines). Alternatively, authors of accepted papers can choose to publish a one-page abstract in the proceedings, along with a URL pointing to the full paper.

There will be a SAGT 2022 Best Paper Award, accompanied by a prize of EUR 1,000 offered by Springer. Selected papers from SAGT 2022 will be invited to a special issue of Theoretical Computer Science.

Important Dates

• Submission deadline: 10th May 2022 16th May 2022, 23:59 AoE
• Notification: 1st July 2022
• Camera ready: 15th July 2022
• Tutorial Day: 12th September 2022
• Conference Dates: 13th-15th September 2022

Submission Instructions

Authors are invited to submit original research for possible presentation at the symposium. Each paper will be evaluated on significance, originality, technical quality, and exposition. It should clearly establish the research contribution, its relevance, and its relation to prior research.

Submissions must be prepared in LNCS style. Each submission must be at most 18 pages long; at most 16 pages for technical contribution (including title page), and at most 2 pages containing references only. Additional material can be added in a clearly marked appendix which will be reviewed at the discretion of the program committee.

Results previously published or presented at another archival conference prior to SAGT, or published (or accepted for publication) at a journal prior to the submission deadline, will not be considered for publication as regular papers. Simultaneous submission of regular papers to another conference with published proceedings is not allowed.

Simultaneous submission of results to a journal is allowed only if the author intends to publish the paper as a one page abstract in SAGT 2022.

Submission link: Submit your paper through EasyChair.

Submission deadline: 10th May 2022 16th May 2022, 23:59 AoE

It is expected that every accepted paper will be presented at the symposium by one of the authors.

Programme Committee

• Georgios Amanatidis, University of Essex
• Vittorio Bilo, University of Salento
• Georgios Birmpas, Sapienza University of Rome
• Bart de Keijzer, King's College London
• Argyrios Deligkas, Royal Holloway University of London
• Paul Duetting, Google Research
• Alon Eden, Harvard University
• Edith Elkind, University of Oxford
• Jiarui Gan, University of Oxford
• Jugal Garg, University of Illinois at Urbana-Champaign
• Yiannis Giannakopoulos, Friedrich-Alexander-Universität Erlangen-Nürnberg
• Laurent Gourves, Université Paris-Dauphine
• Tobias Harks, University of Augsburg
• Alexandros Hollender, University of Oxford
• Ayumi Igarashi, National Institute of Informatics 
• Panagiotis Kanellopoulos, University of Essex (co-chair)
• Pieter Kleer, Tilburg University
• Maria Kyropoulou, University of Essex (co-chair)
• Philip Lazos, Sapienza University of Rome and IOHK
• Stefanos Leonardos, Singapore University of Technology and Design
• Bo Li, The Hong Kong Polytechnic University
• Pasin Manurangsi, Google Research
• Reshef Meir, Technion
• Themistoklis Melissourgos, University of Essex
• Baharak Rastegari, University of Southampton
• Alkmini Sgouritsa, University of Liverpool
• Piotr Skowron, University of Warsaw
• Warut Suksompong, National University of Singapore
• Tami Tamir, Reichman University
• Rohit Vaish, Indian Institute of Technology Delhi
• Carmine Ventre, King's College London
• Adrian Vetta, McGill University
• Cosimo Vinci, University of Salerno
• Alexandros Voudouris, University of Essex (co-chair)
• Anaëlle Wilczynski, Université Paris-Saclay
• Jie Zhang, University of Southampton

Organising committee

• Panagiotis Kanellopoulos, University of Essex (co-chair)
• Maria Kyropoulou, University of Essex (co-chair)
• Alexandros Voudouris, University of Essex (co-chair)

Steering Committee

• Elias Koutsoupias, University of Oxford
• Marios Mavronicolas, University of Cyprus
• Dov Monderer, Technion
• Burkhard Monien, University of Paderborn
• Christos Papadimitriou, Columbia University
• Giuseppe Persiano, University of Salerno
• Paul Spirakis, University of Liverpool (chair)

• SAGT 2021, Aarhus
• SAGT 2020, virtual event
• SAGT 2019, Athens
• SAGT 2018, Beijing
• SAGT 2017, L'Aquila
• SAGT 2016, Liverpool
• SAGT 2015, Saarbrücken
• SAGT 2014, Patras
• SAGT 2013, Aachen
• SAGT 2012, Barcelona
• SAGT 2011, Salerno
• SAGT 2010, Athens
• SAGT 2009, Paphos
• SAGT 2008, Paderborn

In an effort to combat bullying, discrimination, and harassment, SAGT 2022 endorses the code of conduct outlined in appendix D of the Report from the Ad hoc committee to Combat Harassment and Discrimination in the Theory of Computing Community (.pdf).

The main venue of SAGT 2022 is in the STEM building at the University of Essex campus, room STEM 3.1. 

Please visit Find Your Way for a map of the campus to help you during your stay.

SAGT participants can choose to book (student) accommodation available at Colchester campus. This is priced at £55.00 per night including breakfast in an en-suite bedroom (you don’t need to be a student to book one if you are registered at SAGT).

You can make your booking by looking for “University Of Essex - Colchester Campus” at booking.com or speedybooker.com. (Please note that the university website was down and falsely reported no availability.) Alternatively, you can call +44 1206 872358 or email eventessex@essex.ac.uk to make your booking.

Usual booking websites, like booking.com, contain comprehensive lists of hotels in Colchester. You can check out how to get to Colchester Campus for more information on bus services to and from the conference venue (University of Essex campus).

Parking is free for SAGT participants. Please get in touch with sagt2022@essex.ac.uk if you plan to park on campus so that we can register your vehicle.

• Ioannis Caragiannis (Aarhus University)
• Aggelos Kiayias (University of Edinburgh and IOHK)
• Sigal Oren (Ben Gurion University)

• Jack Dippel and Adrian Vetta. An Improved Bound for the Tree Conjecture in Network Creation Games
• Fuga Kiyosue and Kenjiro Takazawa. A common generalization of budget games and congestion games
• Edith Elkind, Piotr Faliszewski, Ayumi Igarashi, Pasin Manurangsi, Ulrike Schmidt-Kraepelin and Warut Suksompong. Justifying Groups in Multiwinner Approval Voting
• Sumit Goel and Wade Hann-Caruthers. Optimality of the coordinate-wise median mechanism for strategyproof facility location in two dimensions
• Edith Elkind, Sonja Kraiczy and Nicholas Teh. Fairness in Temporal Slot Assignment
• Leora Schmerler, Noam Hazon and Sarit Kraus. Strategic Voting in the Context of Stable-Matching of Teams
• Martin Hoefer and Lisa Wilhelmi. Seniorities and Minimal Clearing in Financial Network Games
• Matan Gilboa and Noam Nisan. Complexity of Public Goods Games on Graphs
• Paul Goldberg and Matthew Katzman. PPAD-Complete Pure Approximate Nash Equilibria in Lipschitz Games
• Qian Wang. On Tree Equilibria in Max-Distance Network Creation Games
• Shaul Rosner and Tami Tamir. Cost-Sharing Games with Rank-Based Utilities
• Yichen Yang, Kai Jia and Martin Rinard. On the Impact of Player Capability on Congestion Games
• Kazuhisa Makino, Shuichi Miyazaki and Yu Yokoi. Incomplete List Setting of the Hospitals/Residents Problem with Maximally Satisfying Lower Quotas
• Fabien Gensbittel, Dana Pizarro and Jérôme Renault. Competition and Recall in Selection Problems
• Matthias Bentert, Niclas Boehmer, Klaus Heeger and Tomohiro Koana. Stable Matching with Multilayer Approval Preferences: Approvals can be Harder than Strict Preferences
• Yasushi Kawase and Hanna Sumita. Online Max-min Fair Allocation
• Jason Milionis, Christos Papadimitriou, Georgios Piliouras and Kelly Spendlove. Nash, Conley, and Computation: Impossibility and Incompleteness in Game Dynamics
• Yuki Amano, Ayumi Igarashi, Yasushi Kawase, Kazuhisa Makino and Hirotaka Ono. Fair ride allocation on a line
• Michal Feldman, Nick Gravin, Zhihao Gavin Tang and Almog Wald. Lookahead Auctions with Pooling
• Sahar Jahani and Bernhard von Stengel. Automated Equilibrium Analysis of 2x2x2 Games
• Reshef Meir and Riccardo Baldeschi. Explicitly Simple Near-tie Auctions
• Ronen Gradwohl and Moshe Tennenholtz. Coopetition Against an Amazon
• Ruben Brokkelkamp, Sjir Hoeijmakers and Guido Schaefer. Greater Flexibility in Mechanism Design Through Altruism
• Sushmita Gupta, Pallavi Jain, Daniel Lokshtanov, Sanjukta Roy and Saket Saurabh. Gehrlein Stable Committee with Multi-Modal Preferences
• Martin Durand and Fanny Pascual. Collective Schedules: Axioms and algorithms
• Alon Cohen, Argyrios Deligkas and Moran Koren. Learning Approximately Optimal Contracts
• Edith Elkind, Abheek Ghosh and Paul Goldberg. Simultaneous Contests with Equal Sharing Allocation of Prizes: Computational Complexity and Price of Anarchy
• Sophie Klumper and Guido Schäfer. Budget Feasible Mechanisms for Procurement Auctions with Divisible Agents
• Roy Shahmoon, Rann Smorodinsky and Moshe Tennenholtz. Data Curation from Privacy-Aware Agents
• Liad Blumrosen and Yehonatan Mizrahi. How Bad is the Merger Paradox?
• Stavros Ioannidis, Bart de Keijzer and Carmine Ventre. Financial Networks with Singleton Liability Priorities
• Evangelos Markakis, Georgios Papasotiropoulos and Artem Tsikiridis. On Improved Interval Cover Mechanisms for Crowdsourcing Markets
• Ryann Sim, Stratis Skoulakis, Georgios Piliouras and Lillian Ratliff. Fast Convergence of Optimistic Gradient Ascent in Network Zero-Sum Extensive Form Games
• Georgios Amanatidis, Georgios Birmpas, Philip Lazos and Francisco Marmolejo-Cossio. Decentralised Update Selection with Semi-Strategic Experts

• Rohit Vaish (Indian Institute of Technology Delhi), Fair Division of the Indivisibles.

This tutorial will focus on fair allocation of indivisible resources, which arise in a variety of real-world settings such as inheritance division, assignment of public housing units, and course allocation at universities. Fair allocation has gained increasing interest within theoretical computer science, artificial intelligence, and economics. The tutorial will highlight a collection of recent results in this area.

The technical narrative will involve formally defining various notions of fairness and identifying the conditions under which these notions provably exist and admit efficient algorithms. The emphasis will be on familiarizing the audience with important algorithmic ideas and proof techniques for the case of "desirable" resources (i.e., indivisible goods), as well as developing an understanding of when do techniques for goods extend or fail to extend to settings with "undesirable" resources (i.e., indivisible chores).

Prior background in fair division or game theory is not required. The tutorial will outline various open questions and avenues for future research, and should be of interest to beginners as well as experts.

• Aris Filos-Ratsikas (University of Liverpool) and Alexandros Hollender (University of Oxford), Total Search Problems in Game Theory and Economics.

Total search problems (i.e., problems for which a solution is guaranteed to exist) are ubiquitous in economics and computation, with several prominent examples coming from game theory, competitive markets and fair division.

In this tutorial we will highlight the major results of the related literature on these problems and will present the main techniques for analyzing their computational complexity. The aim of the tutorial is to introduce these concepts to the SAGT audience and to enable researchers to engage in research related to these problems.

The main venue of SAGT 2022 is in the STEM building at the University of Essex campus, room STEM 3.1.

Our preliminary programme can be downloaded as a Word document.

Monday 12 September

Tuesday 13 September

Wednesday 14 September

Thursday 15 September

The proceedings for SAGT 2022 are available with Springer.