Summer School on Game Theory and Social Choice June 21 - June 24 and July 9 - July 13, 2021

Talk Information

Approximation algorithms for bilevel integer programming with application in defending election control

Lin Chen

Texas Tech University

Talk details: Slides Recording

Abstract:

We study a bilevel optimization problem which is a zero-sum Stackelberg game. In this problem, there are two players, a leader and a follower, who pick items from a common set. Both the leader and the follower have their own (multi-dimensional) budgets, respectively. Each item is associated with a profit, which is the same to the leader and the follower, and will consume the leader's (follower's) budget if it is selected by the leader (follower). The leader and the follower will select items in a sequential way: First, the leader selects items within the leader's budget. Then the follower selects items from the remaining items within the follower's budget. The goal of the leader is to minimize the maximum profit that the follower can obtain. Let $s_A$ and $s_B$ be the dimension of the leader's and follower's budget, respectively. A special case of our problem is the bilevel knapsack problem studied by Caprara et al. [SIAM Journal on Optimization, 2014], where $s_A=s_B=1$. We consider the general problem and obtain an $(s_B+\epsilon)$-approximation algorithm when $s_A$ and $s_B$ are both constant. In particular, if $s_B=1$, our algorithm implies a PTAS for the bilevel knapsack problem, which is the first $\OO(1)$-approximation algorithm. We also complement our result by showing that there does not exist any $(4/3-\epsilon)$-approximation algorithm even if $s_A=1$ and $s_B=2$. Moreover, we show that our problem cannot be approximated in polynomial time to within a constant factor when $s_A$ or $s_B$ is part of the input.

As an application of our general algorithm, we study the election control problem in computational social choice. In this problem, the leader is the defender who tries to protect an election, and the follower is an attacker that tries to manipulate the electoral result. More specifically, the attacker can delete voters at some cost, while the defender can select and protect a subset of voters at some cost so that these voters can always cast their votes (i.e., these voters become immune to the voter-deletion attack of the attacker). We formulate this problem as a bi-level optimization problem via a bi-level integer program. In this bilevel integer program, the follower’s constraint, $s_B$, can be an arbitrary constant. However, by exploiting its special structure, we are able to present a polynomial-time approximation scheme by relaxing the defender’s budget a bit.

Bio:

Lin Chen is an assistant professor at Texas Tech University. He received Ph.D from Zhejiang University, and then worked as a postdoc at Technical University of Berlin and Technical University of Munich. His research interest lies in approximation algorithms and fixed paramter-tractable algorithms for operational research problems, with a particular focus on scheduling, computational social choice, and integer programming of a special block structure. He publishes at top-tier conferences including SODA, ICALP, AAAI. IJCAI, etc, and journals including SICOMP, Math. Programming, TALG, etc.

Bayesian Auctions with Efficient Queries

Jing Chen

Algorand Inc

Talk details: Slides Recording

Abstract:

Generating good revenue is one of the most important problems in Bayesian auction design, and many (approximately) optimal dominant-strategy incentive compatible (DSIC) Bayesian mechanisms have been constructed for various auction settings. However, most existing studies do not consider the complexity for the seller to carry out the mechanism. It is assumed that the seller knows ``each single bit'' of the distributions and can optimize perfectly based on the entire distributions. Unfortunately, this assumption may not hold in reality: for example, when the value distributions have exponentially large supports or do not have succinct representations.

In this work we consider, for the first time, the query complexity of Bayesian mechanisms. We only allow the seller to have limited oracle accesses to the players' value distributions, via quantile queries and value queries. For a large class of auction settings, we prove logarithmic lower-bounds for the query complexity for any DSIC Bayesian mechanism to be of any constant approximation to the optimal revenue. For single-item auctions and multi-item auctions with unit-demand or additive valuation functions, we prove tight upper-bounds via efficient query schemes, without requiring the distributions to be regular or have monotone hazard rate. Thus, in those auction settings the seller needs to access much less than the full distributions in order to achieve approximately optimal revenue.

Bio:

Jing Chen is Chief Scientist and Head of Theory Research at Algorand. She is also an affiliated faculty member in the Computer Science Department at Stony Brook University. Her main research interests are distributed ledgers, smart contracts, game theory, mechanism design, and algorithms. Previously, she was a faculty in the Computer Science Department at Stony Brook University and affiliated faculty in the Economics Department. Jing received her bachelor's and master’s degrees in computer science from Tsinghua University, and her PhD in computer science from MIT. She received the NSF CAREER Award in 2016.

Mechanisms and Algorithms for Improving Peer Selection

Nicholas Mattei

Tulane University

Talk details: Slides Recording

Abstract:

In peer selection a group of agents must choose a subset of themselves, as winners for, e.g., peer-reviewed grants or prizes. We take a Condorcet view of this aggregation problem, assuming that there is an objective ground-truth ordering over the agents. We study agents that have a noisy perception of this ground truth and give assessments that, even when truthful, can be inaccurate. Our goal is to select the best set of agents according to the underlying ground truth by looking at the potentially unreliable assessments of the peers.

Besides being potentially unreliable, we also allow agents to be self-interested, attempting to influence the outcome of the decision in their favour. Hence, we are focused on tackling the problem of impartial (or strategyproof) peer selection – how do we prevent agents from manipulating their reviews while still selecting the most deserving individuals, all in the presence of noisy evaluations? In this talk I will survey recent work in this area including our impartial peer selection algorithms PeerNomination and ExactDollarPartition, that aim to fulfil the above desiderata. We provide a comprehensive theoretical analysis of these algorithms and prove various properties, including impartiality and monotonicity. We also provide empirical results based on computer simulations to show its effectiveness compared to other peer selection algorithms.

Bio:

Nicholas Mattei is an Assistant Professor of Computer Science at Tulane University in New Orleans, LA, USA. His research lies at the intersection of artificial intelligence and machine learning with applications in data science, economics, decision making, and psychology. His projects leverage theory, data, and experiments to create novel algorithms, mechanisms, and systems that enable and support individual and group decision making. He has published over 75 academic articles in top conferences and journals and is a co-author of the new book Computing and Technology Ethics: Engaging Through Science Fiction from MIT Press. Before joining Tulane he was a Research Staff Member at IBM Research, TJ Watson Research Laboratory in New York, USA; a Senior Researcher at Data61/CSIRO/NICTA and Conjoint Senior Lecturer at UNSW Sydney in Australia; and before that was an aerospace technology engineer at NASA Ames Research Center in Mountain View, CA, USA. He completed his PhD in 2012 at the University of Kentucky, USA.

How to manipulate restaurant reviews

Paolo Turrini

University of Warwick

Talk details: Slides Recording

Abstract:

I will consider a scenario where a set of individuals (e.g., the customers of a restaurant) evaluate a given service (e.g., the restaurant), based on the opinion of their trusted peers (e.g., their friends in some underlying social network), determining its final revenue. On top of that I will allow a malicious service provider (e.g., the restaurant owner) to bribe some of the individuals, i.e., to invest a part of the expected income to modify their opinion (and therefore their peers’ opinion), thus affecting the final revenue. I will analyse the effect of bribing strategies under various constraints and show under which conditions the system is bribery-proof, i.e., no bribing strategy yields a strictly positive expected gain to the service provider.

This is joint work with Umberto Grandi (Toulouse).

Bio:

Paolo Turrini is an Associate Professor in the Department of Computer Science at the University of Warwick and a Fellow of the Alan Turing Institute, the UK centre for AI and Data Science. In 2011 he received his PhD in Computer Science from the University of Utrecht with a thesis on logic and games. He was then a Marie Curie COFUND fellow at the University of Luxembourg (2011-2013), a Marie Curie Intra European Fellow (2013-2015) and an Imperial College Re- search Fellow (2015-2017) at Imperial College London. He joined Warwick as an Assistant Professor in 2017, where he became Associate Professor in 2020. He is particularly interested in computational models of social influence and its role in collective decisions.

Analyzing Results of Elections and Participatory Budgeting

Piotr Faliszewski

AGH University of Science and Technology

Talk details: Slides Recording

Abstract:

After conducting an election and finding the winners, there is still a lot to do. For one, even if a candidate did not win, he or she still would like to know how well he or she performed. Similarly, a candidate who was very close to winning might ask for an election audit, and before such an audit is performed, it may be useful to learn if small changes in the votes truly could have affected the result. If not, then the audit is not really needed.

However, it turns out that evaluating how well a candidate performed, or how robust is the election result, may be quite nontrivial. At first, one might think that scores assigned by election rules would suffice for such tasks, but score-based approaches have two drawbacks. First, some voting rules (such as the Phragmen rule or Method of Equal Shares or STV) do not even provide scores. Second, it turns out that for rules that do provide scores, their values are less informative than one might initially suspect.

In this talk, I will describe a framework based on the family of bribery problems that allows one to establish candidate performance and analyze robustness of election results (while "bribery" certainly sounds a bit suspicious, in computational social choice this is an umbrella name for problems where we evaluate how easy it is to ensure a given candidate's victory by changing the votes one way or another). We will discuss both computational complexity of related bribery problems and show experimental results for various elections and participatory budgeting scenarios.

Bio:

Piotr Faliszewski is a professor at the AGH University in Krakow, Poland. He received his PhD from the University of Rochester, USA. His research interest span computational social choice, parameterized and approximation algorithms, and numerical experiments. He is an associate editor of the Artificial Intelligence, Journal of Artificial Intelligence Research, and Autonomous Agents and Multiagent Systems journals. He publishes at such venues as AAAI, IJCAI, AAMAS, and journals such as AIJ, JAIR, and others. He is currently running an ERC Consolidator project PRAGMA.

Fairly Allocating Indivisible Goods to Strategic Agents

Georgios Birmpas

The University of Liverpool

Talk details: Slides Recording

Abstract:

We consider the problem of fairly allocating a set of indivisible goods to a set of strategic agents with additive valuation functions. We assume no monetary transfers and, therefore, a mechanism in our setting is an algorithm that takes as input the reported---rather than the true---values of the agents. Our main goal is to explore whether there exist mechanisms that have pure Nash equilibria for every instance and, at the same time, provide fairness guarantees for the allocations that correspond to these equilibria.

We focus on a relaxation of envy-freeness, namely envy-freeness up to one good (EF1), and we positively answer the above question. In particular, we study an algorithm that is known to produce such allocations in the non-strategic setting: Round-Robin. We show that all of its pure Nash equilibria induce allocations that are EF1 with respect to the underlying true values, while we also prove that surprisingly, a version of this result holds even for agents with cancelable or submodular valuation functions.

Bio:

Georgios Birmpas got his PhD degree from Athens University of Economics and Business, Greece, and he then worked as a Postdoc researcher at University of Oxford, UK, and Sapienza University of Rome, Italy. From September 2023, he will be a Lecturer (Assistant Professor), at University of Liverpool, UK. His research focuses on the intersection of Theoretical Computer Science and Microeconomic Theory.

The Congested Assignment Problem

Hervé Moulin

University of Glasgow

Talk details: Slides Recording

Abstract:

We propose a fair, efficient and essentially unique solution for assigning n agents to m posts subject to negative congestion, when agents care about both their post and its congestion.

If congestion is unweighted (only the number of agents in a given post matters) ex ante fairness guarantees to each agent one of their top n allocations from the n × m pairs of a post and its congestion; a similar result holds if congestion is weighted: everyone secures an allocation in 1 the top m quantile of her feasible set.

An assignment is competitive if, taking the congestion at a given post as its ”price”, each agent is assigned to one of their best posts. If it exists it delivers unique congestion and welfare profiles, is also efficient and ex ante fair.

In the randomised extension of our model there is always a unique competitive congestion profile, implemented by a mixture of deterministic assignments: the latter are ex ante fair up to one unit of congestion and approximately efficient and welfare equivalent.

Bio:

Hervé Moulin graduated in 1971 from the Ecole Normale Superieure and received his Ph.D. in mathematics in 1975 at the university of Paris. After teaching at the University Paris- Dauphine, and the Virginia Polytechnic Institute, Duke and Rice universities in the US, he is currently the D.J. Robertson Chair in Economics at the University of Glasgow. A Fellow of the Econometric Society since 1983, of the Royal Society of Edinburgh since 2015, and of the British Academy since 2018, he is a past President of the Game Theory Society and of the Social Choice and Welfare Society. He is currently the Editor in Chief of Games and Economic Behaviour.

Randomized mechanisms for resource allocation

Sujoy Sikdar

Binghamton University, State University of New York

Talk details: Slides Recording

Abstract:

In the assignment problem, a set of items must be allocated to a group of agents who have preferences over being allocated combinations of the items. This serves as a general model with a plethora of useful applications, where both fairness and efficiency of the final allocation are equally desired, and often required. A canonical fairness property, envy-freeness, requires that no agent prefers the allocation of another agent to its own. When the items are indivisible, an envy-free assignment, that is discrete, i.e., allocates every item to a single agent, may not exist. In light of this, envy-freeness can only be guaranteed ex-ante by a randomized assignment, that loosely speaking, induces a lottery over discrete assignments; and only an approximation of envy-freeness can be guaranteed ex-post.

In this talk, we will introduce the challenges in designing mechanisms that provide both ex-ante and ex-post fairness and efficiency guarantees, review recent positive results on the design of such mechanisms, impossibility results that induce tradeoffs between fairness and efficiency, some recent successes in circumventing these impossibilities under certain domain restrictions, and discuss some exciting and significant open problems.

Bio:

Sujoy Sikdar is an assistant professor in the Computer Science department at Binghamton University. He received his Ph.D. and MS in Computer Science at the Rensselaer Polytechnic Institute (RPI). He has broad interests across artificial intelligence, mechanism design, problems at the intersection of computer science and microeconomics, machine learning, and computational social science. His research focuses on algorithmic decision making in the allocation of resources, and voting, with an eye at learning and faithfully representing preferences.

Distributing Mixed Items Fairly: A Lexicographic Excursion

Hadi Hosseini

Penn State University

Talk details: Slides Recording

Abstract:

Fair division of indivisible items encompasses a wide range of real-world applications. The discrete nature of this problem has given rise to several intriguing approximate notions such as envy-freeness up to any item (EFX), envy-freeness up to one item (EF1), and maximin share guarantee (MMS). In this talk, I will focus on fair allocation of mixture of goods and chores under lexicographic preferences. I will argue that this class of preferences is natural, common in computational social choice and AI, and more importantly, elevates our understanding of computational and structural challenges in achieving fairness.

In particular, I will i) demonstrate the non-existence and intractability of achieving EFX, ii) identify natural subclasses of preferences for which positive results can be obtained (along with Pareto optimality), and iii) discuss some of the remaining challenges in achieving other fairness notions and pushing beyond this domain. The negative results immediately carry over to additive valuations while the positive results highlight the challenges of achieving fair and efficient allocations of mixed items.

Bio:

Hadi Hosseini is an Assistant Professor in the College of Information Sciences and Technology at the Pennsylvania State University, USA. He received his Ph.D. in Computer Science from the University of Waterloo (Canada), where he also worked as an instructional developer at the Centre for Teaching Excellence, and was subsequently a postdoctoral research fellow at Carnegie Mellon University, USA. His research interest lies at the interface of artificial intelligence and economics, focusing primarily on algorithmic mechanism design, fair division, matching theory, and computational social choice. He is a recipient of the prestigious NSF CAREER award and is currently the PI on an NSF RI medium grant, sole PI on an NSF CRII grant, and a co-PI in an NSF EHR grant. Hadi is a recipient of Penn State’s Junior Faculty Excellence in Research award, the government of Canada’s NSERC fellowship and UW's Exceptional Teaching Award. He is the founder of MatchU.ai, a not-for-profit publicly available platform that blends education and research by offering an interactive framework for socially desirable decision-making. He is currently an Associate Director of the Center for Artificial Intelligence Foundations and Engineered Systems (CAFÉ) and the director of the FAIR Lab at Penn State.

Sequential information and mechanism design

Jiarui Gan

University of Oxford

Talk details: Slides Recording

Abstract:

Many problems in game theory involve reasoning between multiple parties with asymmetric access to information. This broad class of problems leads to many research questions about information and mechanism design, with broad-ranging applications from governance and public administration to e-commerce and financial services. In particular, there has been a recent surge of interest in exploring the more generalized sequential versions of these problems, where players interact over multiple time steps in a changing environment.

In this talk, I will present a framework of sequential principal-agent problems that is capable of modeling a wide range of information and mechanism design problems. I will discuss our recent algorithmic results on the computation and learning of optimal decision-making in this framework.

Bio:

Jiarui Gan is a Departmental Lecturer at the Computer Science Department, University of Oxford, working in the Artificial Intelligence & Machine Learning research theme. Before this he was a postdoctoral researcher at Max Planck Institute for Software Systems, and he obtained his PhD from Oxford. Jiarui is broadly interested in algorithmic problems in game theory. His current focus is on sequential information and mechanism design problems. His recent work has been selected for an Outstanding Paper Honorable Mention at the AAAI'22 conference.

Altruism, Collectivism and Egalitarianism: On a Variety of Prosocial Behaviors in Binary Networked Public Goods Games

Yukun Cheng

Suzhou University of Science and Technology

Talk details: Slides Recording

Abstract:

Binary Networked public goods (BNPG) game consists of a network G= (V, E) with n players residing as nodes in a network and making a YES/NO decision to invest a public project. Examples of such public projects include face mask wearing during a pandemic, crime reporting and vaccination, etc. Most of the conventional modes of BNPG games solely posit egoism as the motivation of players: they only care about their own benefits. However, a series of real-world examples show that people have a wide range of prosocial behaviors in making decisions. To address this property, we introduce a novel extension of BNPG games to account for three kinds of prosocial motivations: altruism, collectivism, and egalitarianism. We revise utility functions to reflect different prosocial motivations with respect to the welfare of others, mediated by a prosocial graph.

We develop computational complexity results to decide the exisence of pure strategy Nash equilibrium in these models, for cases where the prosocial graph is a tree, a clique or a general network. We further discuss the Prosocial Network Modification (PNM) problem, in which a principal can change the network structure within a budget constraint, to induce a given strategy profile with respect to an equilibrium. For all three types of PNM problems, we completely characterize their corresponding computational complexity results.

Bio:

Dr. Cheng Yukun, full professor at Suzhou University of Science and Technology. Editorial board member of "IEEE Open Journal of Computer Society," "Journal of Operations Research," and "Blockchain". Her main research areas include Computational Economics, Algorithmic Game Theory, Combinatorial Optimization, Blockchain Technology and Applications, etc. From 2010 to 2013, she worked as a postdoctoral researcher at Zhejiang University. In 2012-2013, she was sponsored by the China Scholarship Council to visit the University of Melbourne, Australia. She received the National Science and Technology Academic Publication Fund in 2020. She has hosted three projects funded by the National Natural Science Foundation and two provincial-level projects. She has published in top international journals in the field of Operations Research, such as "Mathematics of Operations Research," and important international journals in theoretical computer science, including "IEEE Transactions on Cloud Computing", "IEEE Transactions on Computer", and "Theoretical Computer Science". She has also published high-level academic papers at top conferences in the field of computational economics, such as EC2022, top international conferences in the field of blockchain, such as FC 2022 and top conferences in the field of artificial intelligence, such as IJCAI2016, with over 60 high-level academic papers. She was respectively awarded the "Young Academic Leader" and "Excellent Young Backbone Teacher" in the “Qinglan” Project of Jiangsu Province's higher education institutions.

A Network Game Model of Community Formation and Risk Sharing

Zhigang Cao

Beijing Jiaotong University

Talk details: Slides Recording

Abstract:

We investigate informal risk sharing using a dynamic network game model. In each round, a randomly selected agent experiences a negative shock, and the agent's friends decide whether to provide assistance. Assuming that agents have concave utility functions, we prove a version of the Folk Theorem. Our analysis shows that a pair of agents are able to help each other in all relevant rounds of a subgame perfect Nash equilibrium if and only if this connection is a part of a subgraph, in which each agent has a number of friends that is neither too low nor too high. We refer to this type of a subgraph as an inner-core. Connected inner-cores can be understood as communities. Although optimization problems related to inner-cores are generally NP-hard, we are able to perform several natural comparative statics.(joint work with Guopeng Li and Yiqing Xing)

Bio:

Cao Zhigang is a professor at the School of Economics and Management, Beijing Jiaotong University. He graduated from the Academy of Mathematics and Systems Science, Chinese Academy of Sciences in 2010， and stayed on as an assistant researcher. In September 2017, he joined the School of Economics and Management at Beijing Jiaotong University as a professor under the "Outstanding Hundred Talents Program." His main research interests include cooperative games, transportation games, network games, and algorithmic games. He has published papers in journals such as Operations Research, Mathematics of Operations Research, and Games and Economic Behavior. His work has received honors including the Chinese Information Economics Theory Contribution Award, and the Youth Science and Technology Award in Systems Science and Systems Engineering. He was supported by the National Science Foundation of China for Excellent Young Scholars.

Fair Division of Mixed Goods

Shengxin Liu

Harbin Institute of Technology (Shenzhen)

Talk details: Slides Recording

Abstract:

The fair division problem studies how to fairly allocate a set of resources to a set of agents who have heterogeneous preferences over the resources. The problem has been receiving significant attention in the past decades.

In this talk, I will focus on the fair division problem when the goods to be allocated contain both divisible and indivisible goods. I will discuss recent advances and highlight open questions in this area.

Bio:

Shengxin Liu is currently an Assistant Professor with the School of Computer Science and Technology, Harbin Institute of Technology, Shenzhen, China. He was a Post-Doctoral Research Fellow with the School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore. He received the Ph.D. degree from the Department of Computer Science, the City University of Hong Kong, China. His research interests include theoretical computer science and computational economics. He was a recipient of the Outstanding Student Paper Award at AAAI 2020 and the Best Paper Award at FAW 2020.

Prophet Inequalities

Zhihao Tang

Shanghai University of Finance and Economics

Talk details: Slides Recording

Abstract:

In the classical prophet inequality, a gambler faces a sequence of items, whose values are drawn independently from known distributions. Upon the arrival of each item, its value is realized and the gambler either accepts it and the game ends, or irrevocably rejects it and continues to the next item. The goal is to maximize the value of the selected item and compete against the expected maximum value of all items.

In this tutorial, we describe several variants of the classical prophet inequality, including the i.i.d. model, the random arrival order model, and the order selection model. We highlight the applications of prophet inequalities in mechanism design and online algorithms, and mention several open questions.

Bio:

Zhihao Tang is an associate professor at ITCS, Shanghai University of Finance and Economics. He has obtained his PhD degree at the University of Hong Kong under the supervision of Dr. Hubert Chan. Before that, he received his BSc in Mathematics and BA in Economics from Peking University. He is broadly interested in theoretical computer science, particularly in algorithms under uncertainty. More specifically, he works on online algorithms and algorithmic game theory.

Mechanism Design without Money: Matching, Facility Location, and Beyond

Chenhao Wang

Beijing Normal University

Talk details: Slides Recording

Abstract:

Algorithmic mechanism design is the study of designing efficient mechanisms that elicit private information from self-interest and rational agents in order to achieve desirable outcomes while satisfying desirable properties. While the area of mechanism design is originated from the economic literature, computer scientists and AI researchers have made significant contributions to this area from the algorithmic and computational perspectives in the last decades.

In a typical setting, the designed mechanism takes agents’ private information and incentives into consideration (as input), and computes/outputs, in polynomial time, an (approximately) optimal outcome that provides necessary incentives for the agents to reveal their private information truthfully. In essence, a mechanism is a function that selects an outcome given the reports of the agents, and it is strategy-proof if it guarantees the truthful reports of agents.

Bio:

Dr. Chenhao Wang is an assistant professor in Beijing Normal University-Zhuhai，and jointly in BNU-HKNU United International College (UIC). Dr. Wang received his bachelor degree from Beihang University in 2015, a PhD degree in Operations Research from AMSS, Chinese Academy of Sciences, and jointly a PhD degree in Computer Science from City University of Hong Kong, in 2020. After that, he worked successively in University of Nebraska-Lincoln and Kyushu University as a postdoctoral researcher. He is broadly interested in algorithms, AI and computational economics, including algorithms and mechanisms for combinatorial optimization and game-theoretical problems, in the intersection of computer science and economics.

On the Complexity of Equilibrium Computation

Zhengyang Liu

Beijing Institute of Technology

Talk details: Slides Recording

Abstract:

In this talk, we will provide an overview of the computational complexity associated with equilibrium computation, highlighting the hardness of well-known algorithms (Lemke-Howson algorithm, Lipton-Markakis-Mehta algorithm etc.) and PPAD-complete problems (discrete fixed-points and Nash equilibria for kinds of games). Furthermore, we will also list some open problems in this area.

Bio:

Zhengyang Liu is an assistant professor in School of Computer Science and Technology in Beijing Institute of Technology. He obtained his PhD degree in 2018 supervised by Prof. Xiaotie Deng. He is currently interested in the algorithmic game theory.

The Existence of EFX and PMMS Allocations under Additive Value Functions

Yong Zhang

University of Chinese Academy of Sciences

Talk details: Slides Recording

Abstract:

Fair division is an important problem in operation research, especially in the field of resource allocation. In this talk, we consider the assignment of indivisible goods between agents with additive value functions and analyze the fairness property while the Nash Social Welfare (NSW) is maximized. To measure fairness, three well-adopted concepts, EFX (Envy-freeness up to any item) and PMMS (Pairwise Maximin Share), are considered. We show that an MNW allocation also satisfies PMMS and EFX respectively if the value functions among agents are identical. This result directly leads to the existence of PMMS under identical value functions.

In this setting, we give an algorithm to achieve a PMMS allocation. Moreover, we consider the budget-feasible allocation where the budget of each agent is bounded by some positive values. For the budget-feasible variant, we show that EFX can be approximated with the ratio of 1/(k∙(k-1)) if the value functions are in the range [1, k], or with the ratio of 1/4 if agents have binary value functions. Additionally, we propose an algorithm to compute an EFX allocation for binary variants under budget constraints in polynomial time.

Bio:

Yong Zhang is currently a Professor in Shenzhen Institute of Advanced Technology, Chinese Academy of Sciences. He received his PhD. In Department of Computer Science and Engineering at Fudan University in 2007. Before joining SIAT, he worked as Post-Doctoral Fellow and Senior Researcher in TU-Berlin and HKU, respectively. His research interests include design and analysis of algorithms, combinatorial optimization and wireless networks. He has published more than 100 papers in refereed journals and conferences.

Best Cost-Sharing Rule Design for Selfish Bin Packing

Changjun Wang

Chinese Academy of Sciences

Talk details: Slides Recording

Abstract:

In selfish bin packing, each item is regarded as a selfish player, who aims to minimize the cost-share by choosing a bin it can fit in. To have a least number of bins used, cost-sharing rules play an important role. The currently best known cost sharing rule has PoA (Price of Anarchy) larger than 1.45, while a general lower bound 4/3 on PoA applies to any cost-sharing rule under which no items have incentive unilaterally moving to an empty bin. In this work, we propose a novel and simple rule with a PoA matching the lower bound 4/3, thus completely resolving this game. The new rule always admits a Nash equilibrium and its PoS (Price of Stability) is one.

Furthermore, the well-known bin packing algorithm BFD (Best-Fit Decreasing) is shown to achieve a strong equilibrium, implying that a stable packing with an asymptotic approximation ratio of 11/9 can be produced in polynomial time. As an extension of the designing framework, we further study a variant of the selfish scheduling game, and design a best coordination mechanism achieving PoS=1 and PoA=4/3 as well. (Joint work with Guochuan Zhang)

Bio:

Changjun Wang is an associate professor at the Academy of Mathematics and Systems Science (AMSS), Chinese Academy of Sciences (CAS). He received his Ph.D. in Operations Research at AMSS, CAS and he then worked as an assistant professor at Beijing University of Technology from 2015 to 2021. His research interests mainly lie in algorithmic game theory and combinatorial optimization.

Best-of-Both-Worlds Fairness in Committee Voting

Mashbat Suzuki

UNSW Sydney

Talk details: Slides Recording

Abstract:

The best-of-both-worlds paradigm advocates an approach that achieves desirable properties both ex-ante and ex-post. We launch a best-of-both-worlds fairness perspective for the important social choice setting of approval-based committee voting. To this end, we initiate work on ex-ante proportional representation properties in this domain and formalize a hierarchy of properties including Individual Fair Share (IFS), Unanimous Fair Share (UFS), Group Fair Share (GFS), and their stronger variants. We establish their compatibility with well-studied ex-post concepts such as extended justified representation (EJR) and fully justified representation (FJR). Our first main result is a polynomial-time algorithm that simultaneously satisfies ex-post EJR, ex-ante GFS and ex-ante Strong UFS. Subsequently, we strengthen our ex-post guarantee to FJR and present an algorithm that outputs a lottery which is ex-post FJR and ex-ante Strong UFS, but does not run in polynomial time.

Bio:

Mashbat Suzuki is a Postdoctoral Fellow in the School of Computer Science and Engineering at UNSW Sydney. Prior to joining UNSW, he finished his PhD in computer science at McGill University, Canada. His research interests lie at the interface between AI, theoretical computer science, and economics. In particular, his recent research has been focused on fair division and social choice.

The cognitive understanding in game theoretical algorithm implementation

Xiaotie Deng

Peking University

Talk details: Slides Recording

Abstract:

The cognitive understanding of game algorithm implementation encompasses the understanding of game theory, the ability to select appropriate algorithms and models, and the capability to perform decision analysis and optimization. These cognitions are crucial for designing and developing computer programs for game algorithms.

Bio:

Xiaotie Deng, Chair Professor of the Center on Frontiers of Computing Studies (CFCS) at Peking University, Director of Blockchain Committee at China Society for Industrial and Applied Mathematics (CSIAM), and Director of the Center for Multi-agent Research at Institute for Artificial Intelligence, Peking University.

Xiaotie's main research interests are algorithmic game theory, blockchain, internet economy, online algorithms and parallel computing. His recent research focuses on equilibrium calculation, multi-agent game, internet economy, and game theory in blockchain.

Xiaotie was honored with the FOCS Best Paper Award in 2006. He is a fellow of the Association of Computing Machinery (ACM) for his contributions to the interface of algorithms and game theory (2008), and the Institute of Electrical and Electronics Engineers (IEEE) for his contributions to computing in partial information and interactive environments (2019). He was elected as foreign member of Academia Europaea in 2020, CSIAM fellow in 2021. In 2022, he won ACM SIGecom Test of Time Award.

Strong Revenue (Non-)Monotonicity of Single-Parameter Auctions

Zhiyi Huang

University of Hong Kong

Talk details: Slides Recording

Abstract:

Consider Myerson's optimal auction with respect to an inaccurate prior, e.g., estimated from data, which is an underestimation of the true value distribution. Can the auctioneer expect getting at least the optimal revenue w.r.t. the inaccurate prior since the true value distribution is larger? This so-called strong revenue monotonicity is known to be true for single-parameter auctions when the feasible allocations form a matroid. We find that strong revenue monotonicity fails to generalize beyond the matroid setting, and further show that auctions in the matroid setting are the only downward-closed auctions that satisfy strong revenue monotonicity.

On the flip side, we recover an approximate version of strong revenue monotonicity that holds for all single-parameter auctions, even without downward-closedness. As applications, we get sample complexity upper bounds for single-parameter auctions under matroid constraints, downward-closed constraints, and general constraints. They improve the state-of-the-art upper bounds and are tight up to logarithmic factors.

Bio:

I am an associate professor of Computer Science at the University of Hong Kong. I work broadly on theoretical computer science. Before joining HKU, I was a postdoc at Stanford University from 2013 to 2014, working with Tim Roughgarden. I obtained my Ph.D. from the University of Pennsylvania under Sampath Kannan and Aaron Roth in 2013. During grad school, I interned at Microsoft Research Redmond under Nikhil R. Devanur in the summers of 2011 and 2012. Before that I got a bachelor degree from the first "Yao Class" under Andrew Yao at Tsinghua University in 2008. I was the recipient of the Best Paper Awards of FOCS 2020 and SPAA 2015, an Excellent Young Scientists Fund (HK & Macau) by NSFC, an Early Career Award by RGC Hong Kong, a Morris and Dorothy Rubinoff Dissertation Award, and a Simons Graduate Fellowship in Theoretical Computer Science.

Improved Approximation Ratios of Fixed-Price Mechanisms in Bilateral Trades

Zihe Wang

Renmin University of China

Talk details: Slides Recording

Abstract:

We continue the study of the performance for fixed-price mechanisms in the bilateral trade problem, and improve approximation ratios of welfare-optimal mechanisms in several settings. Specifically, in the case where only the buyer distribution is known, we prove that there exists a distribution over different fixed-price mechanisms, such that the approximation ratio lies within the interval of [0.71, 0.7381]. Furthermore, we show that the same approximation ratio holds for the optimal fixed-price mechanism, when both buyer and seller distributions are known. As a result, the previously best-known (1 - 1/e+0.0001)-approximation can be improved to 0.71.

Additionally, we examine randomized fixed-price mechanisms when we receive just one single sample from the seller distribution, for both symmetric and asymmetric settings. Our findings reveal that posting the single sample as the price remains optimal among all randomized fixed-price mechanisms.

Bio:

Zihe Wang received his bachelor's degree from Tsinghua Institute of Interdisciplinary Information in 2011. In 2016, he received his Ph.D. from the Institute of Interdisciplinary Information, Tsinghua University. The field of research is auction design, advised by Pingzhong Tang and Andrew Chi-Chih Yao. After graduation, he worked in Shanghai University of Finance and Economics for four years, and then transferred to Renmin University of China. He is currently an assistant professor at the Gaoling School of Artificial Intelligence. His research interests lie at the intersection of computer science and economic theory.

Network Characterizations for Excluding Informational Braess's Paradox

Xujin Chen

University of Chinese Academy of Sciences

Talk details: Slides Recording

Abstract:

In this talk, we investigate the class of congestion games in which users have different information sets about the available edges in the network and can only use routes consisting of edges in their information sets. Informational Braess’s paradox, which extends the classic Braess’s Paradox in traffic equilibria, exposes a counterintuitive phenomenon that users receiving additional information become worse off. We discuss recent progress on characterizing network topologies in which informational Braess’s paradox never occurs. (Joint work with Xinqi Jing)

Bio:

Xujin Chen received her Ph.D degree in Operations Research from Hong Kong University in 2004. She is currently a Professor at Academy of Mathematics and System Science, Chinese Academy of Sciences. Dr. Chen's research interests include Combinatorial Optimization (with an emphasis on polyhedral combinatoric and approximation algorithms), and Algorithmic Game Theory (with an emphasis on network games). Dr. Chen received Excellent Young Scientists Fund of NNSFC (2013-2015), the first place Youth Award of Science & Technology of the Operations Research Society of China in 2010, and China Youth Science and Technology Award in 2020. She has been selected as a leading talent in science and technology innovation under the National "Ten Thousand Talents Program".

Mechanism Design Powered by Social Interactions

Dengji Zhao

ShanghaiTech University

Talk details: Slides Recording

Abstract:

Mechanism design has traditionally assumed that the participants are fixed and independent. However, in reality, the participants are well-connected (e.g., via their social networks) and we can utilize their connections to power the design. One interesting trend is to incentivize the existing participants to use their connections to invite new participants. This helps to form larger games in auctions, coalitional games, matching etc., which is not achievable with the traditional solutions. The challenge is that the participants are competitors and they would not invite each other by default. Solving this is well-coupled with the existing challenges.

For example, in auctions, solving it may require revenue monotonicity and false-name-proofness, which were proved impossible to achieve under certain sensible conditions. In matching, this cannot get along with standard optimality and stability. Hence, we believe there is an important theoretical value to discover and the study will stimulate many interesting applications, especially under decentralized systems with blockchain.

Bio:

Dr Dengji Zhao is a Tenured Associate Professor at ShanghaiTech University, China. He received a double PhD in CS from Western Sydney University (Australia) and the University of Toulouse (France) in 2012. He worked as a postdoc with Makoto Yokoo and Nick Jennings. Most of Zhao’s research is on algorithmic game theory and multi-agent systems, especially mechanism design and its applications on social networks. He pioneered and promoted a new trend of mechanism design on social networks, namely how to incentivize the existing participants of a game to invite new participants via their social connections. He has a blue sky paper at AAMAS 2021 to set up the related research agenda and was invited to give an Early Career Spotlight talk at IJCAI 2022. Zhao was elected as a member of the IFAAMAS Board of Directors in 2022, the first representative from a Chinese institution since IFAAMAS was founded in 2002. He was program/track co-chair of DAI 2021, Workshop Track of PRICAI 2021, Competitions Track of IJCAI 2022, Sponsorship of PRICAI 2022, and Demo Track of AAMAS 2023.

Scalable and Efficient Algorithms for Facility Accessibility Improvement Problems

Hau Chan

University of Nebraska-Lincoln

Talk details: Slides Recording

Abstract:

Facility location problems on networks often deal with locating facilities (e.g., parks, schools, or health facilities) to serve a set of clients (e.g., local citizens). Many existing facility location studies assume that it is always possible to (re-)locate predetermined facilities. However, this assumption is not realistic for facilities that have already been built, where relocating them would be too expensive or impossible.

Recognizing this challenge, existing literature proposed the facility accessibility improvement problems (FAIPs) on networks that aim to add a given number of new edges (e.g., constructing new roadways or bridges) to improve the accessibility of the clients to the facilities under various accessibility cost objectives. Yet, all existing approaches for FAIPs fail to scale to even moderate-sized problem instances and provide no solution quality guarantees.

In the first part of the talk, we will discuss our approaches to address these shortcomings by developing novel scalable (approximation) algorithms and heuristics for FAIPs. In the second part of the talk, we will discuss the strategic aspects of FAIPs in which clients’ locations are not visible publicly and their information is required for optimization. We will discuss approaches for designing new scalable truthful algorithms and heuristics to address FAIPs while incentivizing clients to report their locations truthfully. We will also discuss our experiments on synthetic and real-world networks to demonstrate the (empirical) effectiveness and efficiency of all proposed methods against various baselines.

Bio:

Hau Chan is currently an assistant professor in the School of Computing at the University of Nebraska-Lincoln. He received his Ph.D. in Computer Science from Stony Brook University in 2015 and completed three years of Postdoctoral Fellowships, including at the Laboratory for Innovation Science at Harvard University in 2018.

His research aims to establish mathematical and algorithmic foundations to address societal problems from AI and optimization perspectives. He leverages computational game theory and algorithmic mechanism design when the problems involve analyzing/predicting and inducing agent strategic behavior, respectively, and ML and algorithms when the problems deal with predictions and optimizations with non-strategic agents. His research has been supported by NSF, NIH, and USCYBERCOM.

He has received several Best Paper Awards at SDM and AAMAS and distinguished/outstanding SPC/PC member recognitions at IJCAI and WSDM. He has given tutorials and talks on computational game theory and mechanism design at venues such as AAMAS and IJCAI since 2018, including an Early Career Spotlight at IJCAI 2022. He has served as a co-chair for Doctoral Consortium, Scholarships, and Diversity & Inclusion Activities at AAMAS and IJCAI.

Market Design for Constrained Matching

Makoto Yokoo

Kyushu University

Talk details: Slides Recording

Abstract:

The theory of two-sided matching (e.g., assigning residents to hospitals, or students to schools) has been extensively developed, and it has been applied to design clearinghouse mechanisms in various markets in practice, including resident matching programs and school choice programs. As the theory has been applied to increasingly diverse types of environments, however, researchers and practitioners have encountered various forms of distributional constraints.

As these features have been precluded from consideration until recently, they pose new challenges for market designers. One example of such distributional constraints is a minimum quota, e.g., school districts may need at least a certain number of students in each school in order for the school to operate. In this talk, I present an overview of research on designing mechanisms that work under distributional constraints.

Bio:

Makoto Yokoo is currently a Distinguished Professor of Information Science and Electrical Engineering, Kyushu University. His research interests include multi-agent systems and market/mechanism design. He received the ACM SIGAI Autonomous Agents Research Award in 2004.

He is a fellow of the Association for the Advancement of Artificial Intelligence (AAAI), and a past president of the International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).

The Wisdom of Strategic Voting

Biaoshuai Tao

Shanghai Jiao Tong University

Talk details: Slides Recording

Abstract:

We study the voting game with information uncertainty where agents can coordinate in groups. We show that strategic voting behaviors have a positive impact on leading to the “correct” decision, outperforming the common non-strategic behavior of informative voting and sincere voting. Our results give merit to strategic voting and extend the Condorcet Jury Theorem to settings with coalitional strategic agents. We reveal the surprising equivalence between a strategy profile being a strong equilibrium and leading to the decision favored by the majority. In our model, voters' preferences between two alternatives depend on a discrete state variable that is not directly observable. Each voter receives a private signal that is correlated with the state variable.

This is a joint work with Qishen Han, Grant Schoenebeck, and Lirong Xia

Bio:

Biaoshuai Tao is an assistant professor at John Hopcroft Center for Computer Science at Shanghai Jiao Tong University since 2020. In 2020, he received his Ph.D. degree in computer science at the University of Michigan, Ann Arbor. His research interests mainly include the interdisciplinary area between theoretical computer science and economics, including social network analyses, resource allocation problems, and algorithmic game theory. Before joining the University of Michigan, Biaoshuai was employed as a project officer at Nanyang Technological University in Singapore from 2012 to 2015, and he received the B.S. degree in mathematical science with a minor in computing from Nanyang Technological University in 2012.