Algorithmic Game Theory

Incorporating budget constraints into the analysis of auctions has become increasingly important, as they model practical settings more accurately. The social welfare function, which is the standard measure of efficiency in auctions, is inadequate for settings with budgets, since there may be a large disconnect between the value a bidder derives from obtaining an item and what can be liquidated from her. The Liquid Welfare objective function has been suggested as a natural alternative for settings with budgets. Simple auctions, like simultaneous item auctions, are evaluated by their performance at equilibrium using the Price of Anarchy (PoA) measure – the ratio of the objective function value of the optimal outcome to the worst equilibrium. Accordingly, we evaluate the performance of simultaneous item auctions in budgeted settings by the Liquid Price of Anarchy (LPoA) measure – the ratio of the optimal Liquid Welfare to the Liquid Welfare obtained in the worst equilibrium.

For pure Nash equilibria of simultaneous first price auctions, we obtain a bound of 2 on the LPoA for additive buyers. Our results easily extend to the larger class of fractionally-subadditive valuations. Next we show that the LPoA of mixed Nash equilibria for first price auctions with additive bidders is bounded by a constant. Our proofs are robust, and can be extended to achieve similar bounds for Bayesian Nash equilibria. To derive our results, we develop a new technique in which some bidders deviate (surprisingly) toward a non-optimal solution. In particular, this technique goes beyond the smoothness-based approach.

We revisit the inefficiency of the uniform price auction, one of the standard multi-unit auction formats, for allocating multiple units of a single good. In the uniform price auction, each bidder submits a sequence of non-increasing marginal bids, one for each additional unit. The per unit price is then set to be the highest losing bid. We focus on the pure Nash equilibria of such auctions, for bidders with submodular valuation functions. Our result is a tight upper and lower bound on the inefficiency of equilibria, showing that the Price of Anarchy is bounded by 2.188. This resolves one of the open questions posed in previous works on multi-unit auctions.

We study online multi-unit auctions in which each agent’s private type consists of the agent’s arrival and departure times, valuation function and budget. Similarly to secretary settings, the different attributes of the agents’ types are determined by an adversary, but the arrival process is random. We establish a general framework for devising truthful random sampling mechanisms for online multi-unit settings with budgeted agents. We demonstrate the applicability of our framework by applying it to different objective functions (revenue and liquid welfare), and a range of assumptions about the agents’ valuations (additive or general) and the items’ nature (divisible or indivisible). Our main result is the design of mechanisms for additive bidders with budget constraints that extract a constant fraction of the optimal revenue, for divisible and indivisible items (under a standard large market assumption). We also show a mechanism that extracts a constant fraction of the optimal liquid welfare for general valuations over divisible items.

Liquid welfare is an alternative efficiency measure for auctions with budget constrained agents. Previous studies focused on auctions of a single (type of) good. In this paper, we initiate the study of general multi-item auctions, obtaining a truthful budget feasible auction with constant approximation ratio of liquid welfare under the assumption of large market.

Our main technique is random sampling. Previously, random sampling was usually used in the setting of single-parameter auctions. When it comes to multi-dimensional settings, this technique meets a number of obstacles and difficulties. In this work, we develop a series of analysis tools and frameworks to overcome these. These tools and frameworks are quite general and they may find applications in other scenarios.

We study a type of cooperative games introduced in [8] called shortest path games. They arise on a network that has two special nodes s and t. A coalition corresponds to a set of arcs and it receives a reward if it can connect s and t. A coalition also incurs a cost for each arc that it uses to connect s and t, thus the coalition must choose a path of minimum cost among all the arcs that it controls. These games are relevant to logistics, communication, or supply-chain networks. We give a polynomial combinatorial algorithm to compute the nucleolus. This vector reflects the relative importance of each arc to ensure the connectivity between s and t. Our development is done on a directed graph, but it can be extended to undirected graphs and to similar games defined on the nodes of a graph.

Earning limits are an interesting novel aspect in the classic Fisher market model. Here sellers have bounds on their income and can decide to lower the supply they bring to the market if income exceeds the limit. Beyond several applications, in which earning limits are natural, equilibria of such markets are a central concept in the allocation of indivisible items to maximize Nash social welfare.

In this paper, we analyze earning limits in Fisher markets with linear and spending-constraint utilities. We show a variety of structural and computational results about market equilibria. The equilibrium price vectors form a lattice, and the spending of buyers is unique in non-degenerate markets. We provide a scaling-based algorithm that computes an equilibrium in time \(O(n^3\ell \log (\ell + nU))\), where n is the number of agents, \(\ell \ge n\) a bound on the segments in the utility functions, and U the largest integer in the market representation. Moreover, we show how to refine any equilibrium in polynomial time to one with minimal prices, or one with maximal prices (if it exists). Finally, we discuss how our algorithm can be used to obtain in polynomial time a 2-approximation for Nash social welfare in multi-unit markets with indivisible items that come in multiple copies.

We investigate how robust are results of committee elections to small changes in the input preference orders, depending on the voting rules used. We find that for typical rules the effect of making a single swap of adjacent candidates in a single preference order is either that (1) at most one committee member can be replaced, or (2) it is possible that the whole committee can be replaced. We also show that the problem of computing the smallest number of swaps that lead to changing the election outcome is typically \({\mathrm {NP}}\)-hard, but there are natural \({\mathrm {FPT}}\) algorithms. Finally, for a number of rules we assess experimentally the average number of random swaps necessary to change the election result.

This paper studies constrained approximate Nash equilibria in polymatrix games. We show that is \(\mathtt {NP}\)-hard to decide if a polymatrix game has a constrained approximate equilibrium for 9 natural constraints and any non-trivial \(\epsilon \). We then provide a QPTAS for polymatrix games with bounded treewidth and logarithmically many actions per player that finds constrained approximate equilibria for a wide family of constraints.

In varied real-life situations, ranging from carpooling to workload delegation, several activities are to be performed, to which end each activity should be assigned to a group of agents. These situations are captured by the Group Activity Selection Problem (GASP). Notably, relevant relations among agents, such as acquaintanceship or physical distance, can often be modeled naturally using graphs. To exploit this modeling ability, Igarashi, Peters and Elkind [AAAI 17] introduced gGASP. Specifically, it is required that each group would correspond to a connected set of the underlying graph. In addition, to enforce the execution of the activities in practice, no individual should desire to desert its group in favor of joining another group. In other words, the assignment should be Nash stable. In this paper, we study gGASP with Nash stability (gNSGA), whose objective is to compute such an assignment. This problem is computationally hard even on such restricted topologies as paths and stars, which naturally led Igarashi, Bredereck, Peters and Elkind [AAAI 17, AAMAS 17] to the study gNSGA in the framework of parameterized complexity. We take this line of investigation forward, significantly advancing the state-of-the-art. First, we show that gNSGA is NP-hard even when merely one activity is present. In fact, this special case remains NP-hard when we further restrict the graph to have maximum degree \(\varDelta =5\). Consequently, gNSGA is not fixed-parameter tractable (FPT), or even XP, when parameterized by \(p+\varDelta \), where p is the number of activities. However, we are able to design a parameterized algorithm for gNSGA on general graphs with respect to \(p+\varDelta +t\), where t is the maximum size of a group. Finally, we develop an algorithm that solves gNSGA on graphs of bounded treewidth \(\mathbf {tw}\) in time \(4^p\cdot (n\,+\,p)^{\mathcal {O}(\mathbf {tw})}\). Here, \(\varDelta +t\) can be arbitrarily large. Along the way, we resolve several open questions regarding gNSGA.

We show that for several solution concepts for finite n-player games, where \(n \ge 3\), the task of simply verifying its conditions is computationally equivalent to the decision problem of the existential theory of the reals. This holds for trembling hand perfect equilibrium, proper equilibrium, and CURB sets in strategic form games and for (the strategy part of) sequential equilibrium, trembling hand perfect equilibrium, and quasi-perfect equilibrium in extensive form games. For obtaining these results we first show that the decision problem for the minmax value in n-player games, where \(n\ge 3\), is also equivalent to the decision problem for the existential theory of the reals.

Our results thus improve previous results of \(\mathrm {NP}\)-hardness as well as \(\textsc {Sqrt-Sum}\)-hardness of the decision problems to completeness for \(\exists \mathbb {R}\), the complexity class corresponding to the decision problem of the existential theory of the reals. As a byproduct we also obtain a simpler proof of a result by Schaefer and Štefankovič giving \(\exists \mathbb {R}\)-completeness for the problem of deciding existence of a probability constrained Nash equilibrium.

Conditional Value-at-Risk, denoted as \({\mathsf {CVaR}}_{\alpha }\), is becoming the prevailing measure of risk over two paramount economic domains: the insurance domain and the financial domain; \(\alpha \in (0,1)\) is the confidence level. In this work, we study the strategic equilibria for an economic system modeled as a game, where risk-averse players seek to minimize the Conditional Value-at-Risk of their costs. Concretely, in a \({\mathsf {CVaR}}_{\alpha }\)-equilibrium, the mixed strategy of each player is a best-response. We establish two significant properties of \({\mathsf {CVaR}}_{\alpha }\) at equilibrium: (1) The Optimal-Value property: For any best-response of a player, each mixed strategy in the support gives the same cost to the player. This follows directly from the concavity of \({\mathsf {CVaR}}_{\alpha }\) in the involved probabilities, which we establish. (2) The Crawford property: For every \(\alpha \), there is a 2-player game with no \({\mathsf {CVaR}}_{\alpha }\)-equilibrium. The property is established using the Optimal-Value property and a new functional property of \({\mathsf {CVaR}}_{\alpha }\), called Weak-Equilibrium-for-\({\mathsf {VaR}}_{\alpha }\), we establish. On top of these properties, we show, as one of our two main results, that deciding the existence of a \({\mathsf {CVaR}}_{\alpha }\)-equilibrium is strongly \({\mathcal {NP}}\)-hard even for 2-player games. As our other main result, we show the strong \({\mathcal {NP}}\)-hardness of deciding the existence of a \({\mathsf {V}}\)-equilibrium, over 2-player games, for any valuation \({\mathsf {V}}\) with the Optimal-Value and the Crawford properties. This result has a rich potential since we prove that the very significant and broad class of strictly quasiconcave valuations has the Optimal-Value property.

Selfish routing is a central problem in algorithmic game theory, with one of the principal applications being that of routing in road networks. Inspired by the emergence of routing technologies and autonomous driving, we revisit selfish routing and consider three possible outcomes of it: (i) \(\theta \)-Positive Nash Equilibrium flow, where every path that has non-zero flow on all of its edges has cost no greater than \(\theta \) times the cost of any other path, (ii) \(\theta \)-Used Nash Equilibrium flow, where every used path that appears in the path flow decomposition has cost no greater than \(\theta \) times the cost of any other path, and (iii) \(\theta \)-Envy Free flow, where every path that appears in the path flow decomposition has cost no greater than \(\theta \) times the cost of any other path in the path flow decomposition. We first examine the relations of these outcomes among each other and then measure their possible impact on the network’s performance. Right after, we examine the computational complexity of finding such flows of minimum social cost and give a range for \(\theta \) for which this task is easy and a range of \(\theta \) for which this task is NP-hard for the concepts of \(\theta \)-Used Nash Equilibrium flow and \(\theta \)-Envy Free flow. Finally, we propose strategies which, in a worst-case approach, can be used by a central planner in order to provide good \(\theta \)-flows.

Network creation games investigate complex networks from a game-theoretic point of view. Based on the original model by Fabrikant et al. [PODC’03] many variants have been introduced. However, almost all versions have the drawback that edges are treated uniformly, i.e. every edge has the same cost and that this common parameter heavily influences the outcomes and the analysis of these games.

We propose and analyze simple and natural parameter-free network creation games with non-uniform edge cost. Our models are inspired by social networks where the cost of forming a link is proportional to the popularity of the targeted node. Besides results on the complexity of computing a best response and on various properties of the sequential versions, we show that the most general version of our model has constant Price of Anarchy. To the best of our knowledge, this is the first proof of a constant Price of Anarchy for any network creation game.

We study continuous opinion formation games with aggregation aspects. In many domains, expressed opinions of people are not only affected by local interaction and personal beliefs, but also by influences that stem from global properties of the opinions in the society. To capture the interplay of such global and local effects, we propose a model of opinion formation games with aggregation, where we concentrate on the average public opinion as a natural way to represent a global trend in the society. While the average alone does not have good strategic properties as an aggregation rule, we show that with a reasonable influence of the average public opinion, the good properties of opinion formation models are preserved. More formally, we prove that a unique equilibrium exists in average-oriented opinion formation games. Simultaneous best-response dynamics converge to within distance \(\varepsilon \) of equilibrium in \(O(n^2 \ln (n/\varepsilon ))\) rounds, even in a model with outdated information on the average public opinion. For the Price of Anarchy, we show a small bound of \(9/8 + o(1)\), almost matching the tight bound for games without aggregation. Moreover, some of the results apply to a general class of opinion formation games with negative influences, and we extend our results to the case where expressed opinions come from a restricted domain.

Best response (BR) dynamics is a natural method by which players proceed toward a pure Nash equilibrium via a local search method. The quality of the equilibrium reached may depend heavily on the order by which players are chosen to perform their best response moves. A deviator rule S is a method for selecting the next deviating player. We provide a measure for quantifying the performance of different deviator rules. The inefficiency of a deviator rule S with respect to an initial strategy profile p is the ratio between the social cost of the worst equilibrium reachable by S from p and the social cost of the best equilibrium reachable from p. The inefficiency of S is the maximum such ratio over all possible initial profiles. This inefficiency always lies between 1 and the price of anarchy.

We study the inefficiency of various deviator rules in network formation games and job scheduling games (both are congestion games, where BR dynamics always converges to a pure NE). For some classes of games, we compute optimal deviator rules. Furthermore, we define and study a new class of deviator rules, called local deviator rules. Such rules choose the next deviator as a function of a restricted set of parameters, and satisfy a natural independence condition called independence of irrelevant players. We present upper bounds on the inefficiency of some local deviator rules, and also show that for some classes of games, no local deviator rule can guarantee inefficiency lower than the price of anarchy.

Inspired by real world examples, e.g. the Internet, researchers have introduced an abundance of strategic games to study natural phenomena in networks. Unfortunately, almost all of these games have the conceptual drawback of being computationally intractable, i.e. computing a best response strategy or checking if an equilibrium is reached is NP-hard. Thus, a main challenge in the field is to find tractable realistic network formation models. We address this challenge by investigating a very recently introduced model by Goyal et al. [14] which focuses on robust networks in the presence of a strong adversary who attacks (and kills) nodes in the network and lets this attack spread virus-like through the network via neighboring nodes.

Our main result is to establish that this natural model is one of the few exceptions which are both realistic and computationally tractable. In particular, we answer an open question of Goyal et al. by providing an efficient algorithm for computing a best response strategy, which implies that deciding whether the game has reached a Nash equilibrium can be done efficiently as well. Our algorithm essentially solves the problem of computing a minimal connection to a network which maximizes the reachability while hedging against severe attacks on the network infrastructure and may thus be of independent interest.

We also obtain a tight bound on the inefficiency of deviated Nash flows for matroid congestion games and homogeneous populations if the path deviations can be decomposed into edge deviations. In particular, this provides a tight bound on the Price of Risk-Aversion for matroid congestion games.

In a resource exchange system, resources are shared among multiple interconnected peers. Peers act as both suppliers and customers of resources by making a certain amount of their resources directly available to other network participants. Their utilities are determined by the total amount of resources received from all neighbors. According to a preset mechanism, the allocation of the shared resources depends on the information that agents submit to the mechanism. The participating agents, however, may try to strategically manipulate its submitted information to influence the allocation with the expectation of its utility improvement. In this paper, we consider the tit-for-tat popular proportional response mechanism and discuss the incentives an agent may lie, by a vertex splitting strategy. We apply the concept of incentive ratio to characterize the multiplication factor by which utility of an agent can be increased with the help of the vertex splitting strategy. Because of the bounded rationality in the decentralized resource exchange system, a smaller incentive ratio makes the agents have the less incentive to play strategically. However the incentive ratio is proved to be unbounded in linear exchange market recently. In this paper we focus on the setting on trees, our linear exchange market proves to have the incentive ratio of exact two under the proportional response mechanism against the vertex splitting strategic behaviors of participating agents.

In this paper, we study contention resolution protocols from a game-theoretic perspective. In a recent work [8], we considered acknowledgment-based protocols, where a user gets feedback from the channel only when she attempts transmission. In this case she will learn whether her transmission was successful or not. One of the main results of [8] was that no acknowledgment-based protocol can be in equilibrium. In fact, it seems that many natural acknowledgment-based protocols fail to prevent users from unilaterally switching to persistent protocols that always transmit with probability 1. It is therefore natural to ask how powerful a protocol must be so that it can beat persistent deviators.

In this paper we consider age-based protocols, which can be described by a sequence of probabilities of transmitting in each time step. Those probabilities are given beforehand and do not change based on the transmission history. We present a 3-player age-based protocol that can prevent users from unilaterally deviating to a persistent protocol in order to decrease their expected transmission time. It is worth noting that the answer to this question does not follow from the results and proof ideas of [8]. Our protocol is non-trivial, in the sense that, when all players use it, finite expected transmission time is guaranteed. In fact, we show that this protocol is preferable to any deadline protocol in which, after some fixed time, attempt transmission with probability 1 in every subsequent step. An advantage of our protocol is that it is very simple to describe, and users only need a counter to keep track of time. Whether there exist n-player age-based protocols that do not use counters and can prevent persistence is left as an open problem for future research.

This paper examines the problem of multi-agent learning in \(N\)-person non-cooperative games. For concreteness, we focus on the so-called “hedge” variant of the (EW) algorithm, one of the most widely studied algorithmic schemes for regret minimization in online learning. In this multi-agent context, we show that (a) dominated strategies become extinct (a.s.); and (b) in generic games, pure Nash equilibria are attracting with high probability, even in the presence of uncertainty and noise of arbitrarily high variance. Moreover, if the algorithm’s step-size does not decay too fast, we show that these properties occur at a quasi-exponential rate – that is, much faster than the algorithm’s \({{\mathrm{\mathcal O}}}(1/\sqrt{T})\) worst-case regret guarantee would suggest.

We study ordinal approximation algorithms for maximum-weight bipartite matchings. Such algorithms only know the ordinal preferences of the agents/nodes in the graph for their preferred matches, but must compete with fully omniscient algorithms which know the true numerical edge weights (utilities). Ordinal approximation is all about being able to produce good results with only limited information. Because of this, one important question is how much better the algorithms can be as the amount of information increases. To address this question for forming high-utility matchings between agents in \(\mathcal {X}\) and \(\mathcal {Y}\), we consider three ordinal information types: when we know the preference order of only nodes in \(\mathcal {X}\) for nodes in \(\mathcal {Y}\), when we know the preferences of both \(\mathcal {X}\) and \(\mathcal {Y}\), and when we know the total order of the edge weights in the entire graph, although not the weights themselves. We also consider settings where only the top preferences of the agents are known to us, instead of their full preference orderings. We design new ordinal approximation algorithms for each of these settings, and quantify how well such algorithms perform as the amount of information given to them increases.

We study the variant of the stable marriage problem in which the preferences of the agents are allowed to include indifferences. We present a mechanism for producing Pareto-stable matchings in stable marriage markets with indifferences that is group strategyproof for one side of the market. Our key technique involves modeling the stable marriage market as a generalized assignment game. We also show that our mechanism can be implemented efficiently. These results can be extended to the college admissions problem with indifferences.

We study Nash equilibria of a symmetric Colonel Blotto and Colonel Lotto games. In these game two players, with \(N \ge 1\) units of resources each, distribute their resources simultaneously across \(K \ge 2\) battlefields. We introduce a characteristic of equilibria in this game called spectrum which stands for the fraction of battlefields receiving given numbers of units. We provide complete characterization of spectra of Nash equilibria in Colonel Lotto game as well as necessary conditions on spectra of Nash equilibria in Colonel Blotto game for the case of \({K}\! \mid \!{N}\).

Proportional allocation is an intuitive and widely applied mechanism to allocate divisible resources. We study proportional allocation for profit sharing in coalition formation games. Here each agent has an impact or reputation value, and each coalition represents a joint project that generates a total profit. This profit is divided among the agents involved in the project based on their reputation. We study existence, computational complexity, and social welfare of core-stable states with proportional sharing.

Core-stable states always exist and can be computed in time \(O(m \log m)\), where m is the total number of projects. Moreover, when profits have a natural monotonicity property, there exists a reputation scheme such that the price of anarchy is 1, i.e., every core-stable state is a social optimum. However, these schemes exhibit a strong inequality in reputation of agents and thus imply a lacking fairness condition. Our main results show a tradeoff between reputation imbalance and the price of anarchy. Moreover, we show lower bounds and computational hardness results on the reputation imbalance when prices of anarchy and stability are small.

We consider Stable Marriage with Covering Constraints (SMC): in this variant of Stable Marriage, we distinguish a subset of women as well as a subset of men, and we seek a matching with fewest number of blocking pairs that matches all of the distinguished people. We investigate how a set of natural parameters, namely the maximum length of preference lists for men and women, the number of distinguished men and women, and the number of blocking pairs allowed determine the computational tractability of this problem.

Our main result is a complete complexity trichotomy that, for each choice of the studied parameters, classifies SMC as polynomial-time solvable, \(\mathsf {NP}\)-hard and fixed-parameter tractable, or \(\mathsf {NP}\)-hard and \(\mathsf {W}[1]\)-hard. We also classify all cases of one-sided constraints where only women may be distinguished.