Trip Report -- The 15th International Symposium on Algorithmic Game Theory (SAGT 2022)

Back in September of 2022 I attended the 15th International Symposium on Algorithmic Game Theory, otherwise known as SAGT 2022, hosted by the University of Essex. Its aim is to bring together researchers from computer science and economics to present and discuss recent advances in the field of algorithmic game theory, where the two topics meet. I am fond of this conference in particular since the year prior – at SAGT 2021 – had been my first time attending a conference in person, having started my Ph.D. at King’s while the COVID pandemic was in full swing. Having now attended SAGT twice I also like its friendly atmosphere and the close-knit community of researchers that attends it.

Since studying it during my undergraduate years I have been interested in computational complexity theory and even though my research is focused in algorithmic game theory now I am always interested in seeing the latest results from this area of theoretical computer science. Here I will write about a nice topic I was introduced to during one of the tutorial days at the conference that I found particularly interesting, namely total search problems and their application to problems in game theory and economics. I will also give a brief rundown of some of the other talks I listened to and some of the papers I found interesting, including one from my colleague Stavros at King’s and another from a friend across the road at LSE!

My attendance at the conference was supported by the King’s Student Opportunity Fund which covered registration, accommodation, and travel costs, so I am grateful to them as otherwise I would not have been able to attend!

Total Search Problems in Game Theory and Economics

There is an active area of research in algorithmic game theory that deals with the complexity of finding solutions to special types of computational problems. Often in computer science we want to find the complexity of determining whether some object exists. For many topics of interest in algorithmic game theory there is some theorem that guarantees the existence solutions, hence we focus on slightly different classes of problem. This tutorial, given by Aris Filos-Ratsikas and Alexandros Hollender, gave an overview of recent results in computational complexity for total function problems, complexity classes relevant to algorithmic game theory.

Primer on computational complexity

Computational complexity theory is concerned with quantifying the difficulty of solving certain computational problems. For example, given some natural number \(n\) we may wish to decide if \(n\) is prime or composite, or in other words output 1 if the only divisors of \(n\) are 1 and itself and otherwise output 0. This is an example of a decision problem, which asks us to decide whether some object (in this case, natural number \(n\)) has some property or not (in this case, whether \(n\) is prime). The name of this computational problem is \(\texttt{PRIMES}\). Another example of a decision problem is the \(\texttt{CLIQUE}\) problem: given a graph \(G = (V,E)\) and an integer \(k\), does there exist a subset \(V' \subseteq V\) such that \(\| V' \| \ge k\) and every pair of vertices in \(V'\) is connected by an edge? If such a subset \(V'\) exists then we output 1, otherwise we output 0.

Two popular complexity classes used to classify these types of problems are the classes \(\texttt{P}\) and \(\texttt{NP}\). Informally \(\texttt{P}\) contains all decision problems whose solutions we can find in polynomial time, while NP contains all decision problems whose solutions we can verify in polynomial time. Resolving whether these two complexity classes are equal is a somewhat important open problem. Central to the field of complexity theory is the notion of a reduction, which allows us to transform one problem into another and prove things about how hard it is to solve. One important reduction is the Karp reduction which formalises one concept of using an oracle for one problem as a subroutine for solving another. A problem \(A \subseteq \{ 0,1 \}^*\) is polynomial-time Turing reducible to another problem \(B \in \{ 0,1 \}^*\) if there exists a polynomial-time computable function \(f : \{ 0,1 \}^* \to \{ 0,1 \}^*\) such that \(x \in A \iff f(x) \in B\). This is denoted \(A \le_p B\). A problem \(A\) is \(\texttt{L}\)-hard if \(X \le_p A\) for every problem \(X\) in \(\texttt{L}\). We say that \(A\) is \(\texttt{L}\)-complete if both \(A \in \texttt{L}\) and \(A\) is \(\texttt{L}\)-hard.

So far we have introduced decision problems. It is well-known, for example, that \(\texttt{CLIQUE}\) is \(\texttt{NP}\)-complete, meaning it represents all the hardest problems in \(\texttt{NP}\). In other words, if we can solve \(\texttt{CLIQUE}\) efficiently then we would be able to solve all problems in \(\texttt{NP}\). Related to decision problems are search problems which ask us to both determine whether a solution exists and return a solution if it exists (and 0 otherwise).¹ Finally we arrive at the notion of interest for this first day’s tutorial: total function problems and problems belonging to the complexity class \(\texttt{TFNP}\). A functional problem is any problem with the following form: given input \(x\) and polynomial-time predicate \(F(x,y)\), if there exists a \(y^*\) satisfying \(F(x,y)\) then output any such \(y^*\), otherwise output 0. For example, if \(F\) is the predicate “assignment \(y\) is a satisfying assignment for Boolean formula \(x\)” then the function problem would be to output, whenever \(x\) is satisfiable, a satisfying assignment \(y\) of \(x\).

It may be that there exist some instances \(x\) for which there exist no \(y\) such that \(F(x,y)\) is satisfied – it is easy, for example, to construct an unsatisfiable Boolean formula, e.g. \(\phi = x \land \neg x\). To simplify matters we may restrict our attention to function problems that are guaranteed to have a solution. When considering function problems whose decision variants are in \(\texttt{NP}\), i.e. function problems whose certificates we may verify in polynomial time, this gives rise to the complexity class \(\texttt{FNP}\). When the corresponding function problem is guaranteed to have a solution (i.e., the function is total) then we have the class \(\texttt{TFNP}\).

The class \(\texttt{TFNP}\)

For each problem in \(\texttt{TFNP}\) we are guaranteed to have a solution. In other words given some predicate \(F\) then for each \(x\) there must exist at least one \(y\) such that \(F(x,y)\) is true. We can further classify the problems in \(\texttt{TFNP}\) depending on how such a guarantee is provided. The following are a few subclasses of \(\texttt{TFNP}\):

• \(\texttt{PPA}\) (for Polynomial Parity Argument): existence is guaranteed by the fact that any graph whose nodes have degree at most two must have an even number of leaves.
• \(\texttt{PPAD}\) (for PPA on Directed graphs): existence is guaranteed by the fact that a directed graph with an unbalanced (in-degree unequal to out-degree) node must have another unbalanced node
• \(\texttt{PPP}\) (for Polynomial Pigeonhole Principle): existence is guaranteed by the Pigeonhole Principle which states that if \(n\) items are to be put into \(m < n\) containers then there must be at least one container with more than one item.
• \(\texttt{PLS}\) (for Polynomial Local Search): existence is guaranteed by the fact that any directed acyclic graph must have a sink.

A celebrated result in the algorithmic game theory literature is that \(\texttt{εNASH}\), the problem of computing an approximate Nash Equilibrium of a finite game, is \(\texttt{PPAD}\)-complete. Since then there has been much interest in the algorithmic game theory community in classifying a host of other total function problems. The takeaway from this tutorial was that the theorem by which some mathematical object is guaranteed to exist can provide hints as to which subclass of \(\texttt{TFNP}\) the associated computational problem belongs.

\(\texttt{TFNP}\) problems in algorithmic game theory

Here we will introduce some problems that might be of interest to us in algorithmic game theory, starting with the problem of computing an approximate Nash Equilbrium of a finite game.

ε-Nash Equilbrium, or \(\texttt{εNASH}\): Consider some finite \(n\)-person game given in normal form where each player \(i \in [n]\) has a finite set \(S_i\) of pure strategies. By \(S = \times_{i \in [n]}\) we denote the set of all strategy profiles. A mixed strategy for player \(i\) is a probability distribution \(\Delta(S_i)\) over her pure strategies, and a mixed profile \(\sigma \in \Delta(S)\) is a probability distribution over pure strategy profiles. For each mixed profile \(\sigma \in \Delta(S)\) player \(i\) has an associated expected utility \(u_i(\sigma) \in \mathbb{R}\). A mixed strategy \(\sigma_i\) is a best response to the partial mixed profile \(\sigma_{-i}\) if \(u_i(\sigma_i,\sigma_{-i}) \ge u_i(\sigma_i',\sigma_{-i})\) for every \(\sigma_i' \in \Delta(S_i)\). Finally a Nash Equilbrium is a mixed profile \(\sigma^\ast\) such that each player \(i\) is playing a best response \(\sigma_i^\ast\) to \(\sigma_{-i}^\ast\). Our aim is to find a Nash Equilibrium of a given game. Now a game for three or more people may admit only irrational solutions, so we instead look for ε Nash Equilibria, where in a given solution each player can only benefit by switching from mixed strategy \(\sigma_i\) to \(\sigma_i'\) by at most \(\varepsilon > 0\).

ε-Bayes-Nash Equilibrium of First-Price Auctions: In a first-price auction there are \(n\) bidders and a single item for sale. Each player has a private valuation \(v_i\) and submits a bid \(b_i \in B \subseteq [0,1]\). The item is awarded to the highest bidder, who is made to pay their bid. If there are ties then the winner is selected from the set of highest bidders uniformly at random. The bidders also have beliefs of the true values of each of the other bidders: for each bidder \(i\) her belief of the valuation of bidder \(j\) is given by the continuous distribution \(F_{i,j}\) over \([0,1]\). In other words, bidder \(i\) believes that the valuation \(v_j\) of bidder \(j\) is drawn from \(F_{i,j}\). In this context a strategy of bidder \(i\) is a function \(\sigma_i : [0,1] \to B\) mapping her own value to a bid (taking into account her subjective beliefs). Again we are looking to compute an \(\varepsilon > 0\) (Bayes) Nash Equilibrium of the induced game, or a mixed strategy profile \(\sigma\) such that for each bidder \(i\) we have \(u_i(\sigma_i(v_i),\sigma_{-i}) \ge u_i(b_i,\sigma_{-i}) - \varepsilon\) for all \(b_i \in B\).

Necklace Splitting with Two Thieves: We have a necklace with two types of jewels and two thieves who want a cut of equal value of the necklace. Our goal is to cut the necklace using \(n\) cuts such that each thief receives the same number of each type of jewel.

ε-Consensus Halving: In a continuous analogue of necklace splitting, for consensus halving we want a set of agents to divide a cake into pieces labelled “+” and “-“ and reach consensus that the two labelled sets are of equal value. Specifically there is a set of \(n\) agents where each agent \(i\) has a valuation function \(v_i\) over the interval \([0,1]\). The goal is to find a partition of \([0,1]\) into two sets \(I^+\) and \(I^-\) using at most \(n\) cuts such that for each agent we have \(| v_i(I^+) - v_i(I^-)| \le \varepsilon\).

For each of these problems we are guaranteed to have a solution. Contrast this with the \(\texttt{CLIQUE}\) problem from earlier, where it is easier to construct an example graph \(G\) and integer \(k\) such that there is no clique of size at least \(k\) in \(G\). Importantly the existence of this solution is not merely a promise, but stems from some structural property of the underlying problem. But what does this mean? To answer this question we introduce one more problem, known as \(\texttt{EndOfALine}\).

EndOfALine: Given a graph described implicitly by two circuits \(P\) and \(S\) outputting the predecessor and successor of a given node, respectively, where each node has in-degree and out-degree at most one, and a source node (node with in-degree zero), output either a sink node (node with out-degree zero) or another source node.

What makes \(\texttt{EndOfALine}\) difficult? If the graph were given to us explicitly, for example by listing each edge of the graph, then the task would be simple: we can simply run a graph traversal algorithm until we reach the desired node, and this would take time polynomial in the size of the input. However, since the graph is given to us implicitly then the graph could be exponential in the size of the input.² It turns out that this problem is \(\texttt{PPAD}\)-complete. In a celebrated result due to Daskalakis, Goldberg, and Papadimitriou³ they showed that computing an approximate Nash Equilibrium is \(\texttt{PPAD}\)-complete via reduction from \(\texttt{EndOfALine}\).

The Message

Loosely, Nash showed that for any finite game we are guaranteed to have a Nash Equilbrium due to Brouwer’s fixed-point theorem,⁴ that states that for any function \(f : S \to S\) from some compact convex set \(S\) to itself there must be a fixed point \(x\) that \(f\) maps to itself. More loosely, Sperner’s lemma can be viewed as a discretised version of Brouwer’s theorem and says that in any triangulation of a simplex and any colouring of the vertices of this triangulation with a certain structure, there is a triangle where each vertex has a unqiue colour. The associated search problems for these two problems are \(\texttt{BROUWER}\) and \(\texttt{SPERNER}\). For \(\texttt{BROUWER}\) we are given an arithmetic circuit of \(f\) and we are asked to find a fixed point of \(f\). For \(\texttt{SPERNER}\) we are given a polynomial-sized colouring circuit⁵ and a triangulation of a simplex \(\Delta^d\) and we are asked to find a panchromatic subsimplex, that is, a triangle such that each node has a unique colour. A useful result is that \(\texttt{EndOfALine} \le_p \texttt{SPERNER}\) since \(\texttt{SPERNER}\) is a bit easier to work with. It turns out that for a number of problems which are \(\texttt{PPAD}\)-complete the proof of existence of the underlying mathematical object for which we are searching (a Nash Equilibrium in the case of \(\texttt{εNASH}\)) is due to a reduction from Brouwer’s theorem. Thus for problems whose solution is guaranteed by Brouwer’s theorem and we are having a hard time finding a polynomial time algorithm for finding the solution then it may be useful to try reducing from \(\texttt{SPERNER}\), the combinatorial analogue of Brouwer’s theorem, to show the problem to be \(\texttt{PPAD}\)-complete.

The same can be said for the other complexity classes listed above. For the class \(\texttt{PPA}\) there are another two problems useful for proving completeness of other computational problems where the solution is guaranteed by the handshaking lemma. These problems are \(\texttt{BU}\) (for “Borsuk-Ulam”) and \(\texttt{TUCKER}\). The Borsuk-Ulam theorem is similar to Brouwer’s theorem and says that every continuous function \(f : S^n \to \mathbb{R}^n\) to Euclidean \(n\)-space maps some pair of antipodal points \(x\) and \(-x\) to the same point, i.e. there is an \(x \in S^n\) such that \(f(-x) = f(x)\). In \(\texttt{BU}\) we are given a circuit computing \(f\) and we are tasked with finding a zero of \(f\). In the same way Sperner’s lemma is a combinatorial analogue of Brouwer’s theorem, Tucker’s lemma is a combinatorial analogue of the Borsuk-Ulam theorem and says that given some valid labelling of a triangulation of the \(n\)-dimensional ball \(B_n\), there is always an edge of the triangulation whose endpoints have the same label but opposite signs. Thus for \(\texttt{TUCKER}\) we are given such a labelling (implictly) and asked to find such an edge. The canonical \(\texttt{PPA}\)-complete problem is \(\texttt{LEAF}\) which asks us to find a leaf of the graph, which is given to us implicitly. Just like we had \(\texttt{EndOfALine} \le_p \texttt{SPERNER}\), meaning we could reduce problems we want to prove \(\texttt{PPAD}\)-complete from \(\texttt{SPERNER}\) (as it is easier to work with), we may similarly want to reduce from \(\texttt{TUCKER}\) to prove our problem \(\texttt{PPA}\)-complete.

The final example given in the tutorial was for \(\texttt{PLS}\), and the message was that, if the solution can be guaranteed to exist using a potential function argument then it might be worth trying to prove the problem \(\texttt{PLS}\)-complete. Related to this is the class \(\texttt{CLS}\), for Continuous Local Search, which was recently shown to be equal to \(\texttt{PLS} \cap \texttt{PPAD}\) ⁶ and describes the complexity of gradient descent.

This was only the first half of the tutorial. The second half was dedicated to introducing a new problem known as \(\texttt{PureCircuit}\), which has recently been shown to be \(\texttt{PPAD}\)-complete.⁷ Informally we are given a Boolean circuit which may have cycles and nodes take values in \(\{0,1,\bot\}\) and we have a “purify” gate, which takes one input and guarantees that at least one of its two outputs is not \(\bot\). The goal is then to assign values to each of the nodes satisfying the rules of each gate.

Fair Division of the Indivisibles

This tutorial was given by Rohit Vaish and took a tour around the world of fair allocation of indivisible goods. Consider for example items such as houses, cars, and other objects for which it would not make much reasonable sense to split between two or more agents. It introduced key concepts such as the “envy graph” from which we devise the envy-cycle elimination and top trading cycles algorithms for computing envy-free allocations.

What’s Fair?

The setup behind the fair division literature is very simple. Generally we have a set of \(n\) agents and a set \(G = \{ g_1, g_2, \ldots, g_m \}\) distinct goods. Each agent \(i \in [n]\) has a valuation function \(v_i : 2^G \to \mathbb{R}\) that maps bundles of goods to a numeric value for that bundle. Given these valuation functions we are interested in computing an allocation that is considered “fair”. An allocation \(A = (A_1, A_2, \ldots, A_n)\) describes the bundle allocated to the agents, where \(A_i \subseteq G\) is the bundle allocated to agent \(i\). Importantly goods are indivisible, meaning each good appears at most once in any bundle, and the agent receives the entire good. As it turns out, there are many different notions of what it means for an allocation to be fair. Allocation \(A\) is proportional if \(v_i(A_i) \ge v_i(G) / n\) for all \(i\), meaning each agents her allocation at least as much as a \(1/n\) fraction of how she values the entire set of goods. It is envy-free (EF) if \(v_i(A_i) \ge v_i(A_j)\) for every agent \(i\) and every other agent \(j \neq i\), i.e., no agent prefers another agent’s allocation to her own. A weaker notion of EF is envy-freeness up to one good, which says that an agent \(i\) must prefer her own allocation to any other agent \(j\)’s after removing \(i\)’s most valued item from \(j\)’s allocation. In symbols allocation \(A\) is envy-free up to one good (EF1) if for each \(i\), for each \(j \neq i\), there exists a good \(g \in A_j\) such that \(v_i(A_i) \ge v_i(A_j \setminus \{g\})\). Somewhere between EF and EF1 is envy-freeness up to any good, which says that agents prefer their own bundle as long as we can remove any item (or equivalently, the agent’s most valued item) from any other agent’s bundle. Allocation \(A\) is envy-free up to any good (EFX) if for each \(i\), for each \(j \neq i\), for all goods \(g \in A_j\) we have \(v_i(A_i) \ge v_i(A_j \setminus \{g\})\).

So What?

One immediate observation is that for a given instance (i.e., agents \([n]\) and goods \(G\)) an EF allocation may not be possible. Consider the simple example with \(n = 2\) and \(G = \{ g_1 \}\). Since the goods are indivisible then either allocation we pick (i.e., \(A = (\emptyset, \{ g_1 \})\) or \(A = (\{ g_1 \}, \emptyset)\)) has one agent envy the other.⁸ EF is difficult to work with for a number of other reasons: it is \(\texttt{NP}\)-complete to decide whether an instance admits a complete envy-free allocation, even for two agents with identical additive utilities, and can require exponential communication. EF1 on the other hand is possible in a variety of settings: when agents have weakly additive utilities the round robin algorithm finds a complete EF1 allocation,⁹ and in the more general case when agents have monotone utilities – where the total valuation for bundle \(S\) is at least as much as the total valuation for bundle \(T\) whenever \(S\) is a superset of \(T\) – then envy-cycle elimination finds a complete EF1 allocation. This works by assigning an unallocated good to an agent that no one envies, and otherwise swapping all pairs of envied items amongst agents until such an agent appears. This process is repeated until all goods are allocated, and can be modified to also work with chores – where agents experience a negative utility from being allocated the item – using the top-trading envy-cycle elimination algorithm.

The overall takeaway of the first part was that when we have additive valuations round-robin can compute an EF1 allocation efficiently for both goods and chores, while efficient algorithms exist for computing such allocations with the slightly more general monotone valuations with the envy-cycle elimination and top-trading envy-cycle elimination algorithms. These also work with some modifications for instances with both goods and chores.

Computing envy-free allocations efficiently

Why might envy-freeness up to one good be undesirable? Consider allocating two doughnuts and a Ferrari to two agents who both (unsurprisingly) value the car more than the doughnut, and suppose we give one agent a doughnut and the other a doughnut and the Ferrari. This allocation is EF1, since we can remove the car from the allocation and the envy is removed, but it doesn’t actually seem very fair.

As mentioned EF1 can be strengthened to EFX. It is stronger than EF1 since for an EF1 allocation we can remove the most valuable item (in the eyes of agent \(i\)) from agent \(j\) to resolve agent \(i\)’s envy, while EFX requires envy-freeness to hold after we remove any item from agent \(j\). Now, for identical agents with additive valuations an EFX allocation always exists an can be efficiently computed – just allocate the goods in non-increasing order of (identical) values, giving each new good to the least-happy agent. The most recently allocated good is the least valued among all agents, and the allocation is EF up to the most recent good, and hence EFX. Relaxing the additive valuations to monotone, an EFX allocation still always exists for identical agents, but might not be efficiently computable. The results get slightly more complicated as agents become non-identical agents. Another variation of EFX is introduce charity, where an allocation may now leave behind a pool of unallocated items so long as no agent envies the pool. For monotone valuations, such an allocation always exists.

Again we can extend EFX to work with chores, which introduces a few obstacles. Firstly, resolving arbitrary envy cycles can break EFX but choosing the right cycles to eliminate is not straightforward. If we consider a mixed setting of goods and chores then EFX allocations can fail to exist. One nice open question is the complexity of deciding an EFX allocation exists in such a setting.

Again my notes seem to dwindle towards the end of the tutorial, but it mainly revolved around two more notions of fairness and efficiency in Pareto Optimality and Nash Social Welfare. An allocation is Pareto Optimal (PO) if we can only make an agent better off if another agent suffers because of it, while an allocation is Nash optimal if it maximises the Nash Social Welfare defined as \(\text{NSW}(A) = ( \prod_i v_i(A_i) )^{1/n}\), i.e. the geometric mean of the agents’ valuations. Any Nash optimal allocation is PO and EF1, but maximising Nash Social Welfare is \(\texttt{APX}\)-hard. This is not necessarily bad news, since an EF1 and PO allocation can at least be computed in pseudopolynomial time, where the runtime is polynomial in the numeric value of the input (the valuations) but not necessarily the number of bits required to represent it.

Invited Talks and Paper Presentations

Over the next couple of days there were two invited talks followed by presentations on the accepted papers. The first invited talk, Algorithmic Game Theory Meets Behavioural Economics, was given by Sigal Oren and looked at issues from behavioural economics from the perspective of algorithmic game theory. For example, what if agents value quicker results more? Evidence has shown that agents only collect about a quarter of the gains available from lying in manipulable mechanisms, so models have been introduced to study moral agents. In an \(\alpha\)-moral mechanism agents will only lie when the benefit from doing so is at least an \(\alpha\) factor of the sum of resulting losses of the other players, for \(\alpha \in [0,1]\). Setting \(\alpha = 0\) we recover strategyproofness (as here agents will lie when the gain is at least zero) while \(\alpha = 1\) means players only lie if they gain at least the damage they cause to the other players. Intuitively, moral mechanisms extend the class of implementable allocation functions, and also allows auctioneers to leverage the morality of the bidders to extract more revenue.

The second invited talk, New Fairness Concepts for Allocating Indivisible Items, was given by Ioannis Caragiannis and took a look at some of the more obscure fairness concepts in the literature, such as envy-freeness up to any good (EFX), maximin share (MMS), epistemic envy-freeness (EEF), and minimum EFX value (MXS).

The three presentations on accepted papers that stood out in my mind were:

• Financial Networks with Singleton Liability Priorities, Stavros Ioannidis, Bart de Keijzer, and Carmine Ventre
• PPAD-Complete Pure Approximate Nash Equilibria in Lipschitz Games, Paul W. Goldberg and Matthew Katzman
• Automated Equilibrium Analysis of 2x2x2 Games, Sahar Jahani and Bernhard von Stengel

Feel free to go and check them out! The first one won the best student paper award and was written by Stavros Ioannidis from King’s.

Pictures

Here are some pictures that I took while out in lovely Colchester.

That concludes my write-up for my trip to Colchester and the University of Essex for SAGT 2022. It was a fun conference and was good excuse to see people from the algorithmic game theory research community again. The trip was made possible thanks to the financial assistance from the King’s Student Opportunity Fund so thank you to them once again. I hope you learned something about \(\texttt{TFNP}\) and fair division and note that all mistakes are my own!

Footnotes