Algorithmic Game Theory

Frontmatter

On Revenue Monotonicity in Combinatorial Auctions

Abstract

Along with substantial progress made recently in designing near-optimal mechanisms for multi-item auctions, interesting structural questions have also been raised and studied. In particular, is it true that the seller can always extract more revenue from a market where the buyers value the items higher than another market? In this paper we obtain such a revenue monotonicity result in a general setting. Precisely, consider the revenue-maximizing combinatorial auction for m items and n buyers in the Bayesian setting, specified by a valuation function v and a set F of nm independent item-type distributions. Let REV(v, F) denote the maximum revenue achievable under F by any incentive compatible mechanism. Intuitively, one would expect that \(REV(v, G)\ge REV(v, F)\) if distribution G stochastically dominates F. Surprisingly, Hart and Reny (2012) showed that this is not always true even for the simple case when v is additive. A natural question arises: Are these deviations contained within bounds? To what extent may the monotonicity intuition still be valid? We present an approximate monotonicity theorem for the class of fractionally subadditive (XOS) valuation functions v, showing that \(REV(v, G)\ge c\,REV(v, F)\) if G stochastically dominates F under v where \(c>0\) is a universal constant. Previously, approximate monotonicity was known only for the case \(n=1\): Babaioff et al. (2014) for the class of additive valuations, and Rubinstein and Weinberg (2015) for all subaddtive valuation functions.

Andrew Chi-chih Yao

Restricted Preference Domains in Social Choice: Two Perspectives

Abstract

Preference aggregation is a challenging task: Arrow’s famous impossibility theorem [1] tells us that there is no perfect voting rule. One of the best-known ways to circumvent this difficulty is to assume that voters’ preferences satisfy a structural constraint, such as, e.g., being single-peaked. Indeed, under this assumption many impossibility results in social choice disappear. Restricted preference domains also play an important role in computational social choice: for instance, there are voting rules that are NP-hard to compute in general, but admit efficient winner determination algorithms when voters’ preferences belong to a restricted domain. However, restricted domains that have nice social choice-theoretic properties are not necessarily attractive from an algorithmic perspective, and vice versa. In this note, we will discuss some domain restrictions that have proved to be useful from a computational perspective, and compare the use of restricted domains in computational and classic social choice theory.

Edith Elkind

The Complexity of Cake Cutting with Unequal Shares

Abstract

An unceasing problem of our prevailing society is the fair division of goods. The problem of proportional cake cutting focuses on dividing a heterogeneous and divisible resource, the cake, among n players who value pieces according to their own measure function. The goal is to assign each player a not necessarily connected part of the cake that the player evaluates at least as much as her proportional share.

In this paper, we investigate the problem of proportional division with unequal shares, where each player is entitled to receive a predetermined portion of the cake. Our main contribution is threefold. First we present a protocol for integer demands that delivers a proportional solution in fewer queries than all known algorithms. Then we show that our protocol is asymptotically the fastest possible by giving a matching lower bound. Finally, we turn to irrational demands and solve the proportional cake cutting problem by reducing it to the same problem with integer demands only. All results remain valid in a highly general cake cutting model, which can be of independent interest.

Ágnes Cseh, Tamás Fleiner

A Near Optimal Mechanism for Energy Aware Scheduling

Abstract

With the increased popularity of cloud computing it is of paramount importance to understand energy-efficiency from a game-theoretic perspective. An important question is how the operator of a server should deal with combining energy-efficiency and the particular interests of the users. Consider a cloud server, where clients/agents can submit jobs for processing. The quality of service that each agent perceives is given by a non-decreasing function of the completion time of her job which is private information. The server has to process the jobs and charge each agent while trying to optimize the social cost, defined as the energy expenditure plus the sum of the values of the cost functions of the agents. The operator would like to design a mechanism in order to optimize this objective, which ideally is computationally tractable, charges the users “fairly” and induces a game with an equilibrium.

We describe and analyze one such mechanism called modAVR, which relies on an adaption of the well-known Average Rate (AVR) algorithm for scheduling the jobs. We prove that modAVR combines the aforementioned properties with a constant Price of Anarchy, i.e., despite the fact that it is based on an algorithm designed for optimizing the energy alone, every equilibrium it results in is near-optimal for the total social cost as well. The existence of a Nash equilibrium is proven for both mixed strategies and (in a slightly more restricted setting) pure strategies.

A further interesting feature of modAVR is that it is indirect: each user needs only to declare an upper bound on the completion time of her job, and not the cost function.

Additionally, we prove that for the corresponding mechanism that uses the classical YDS algorithm for scheduling the jobs no pure Nash equilibrium can exist for a very broad and natural class of cost functions. Finally, we are able to extend several of our results for modAVR to a mechanism based on a slight variation of the YDS algorithm. This variation is known also to not admit Nash equilibria in pure strategies.

Antonios Antoniadis, Andrés Cristi

Information Elicitation for Bayesian Auctions

Abstract

In this paper we design information elicitation mechanisms for Bayesian auctions. While in Bayesian mechanism design the distributions of the players’ private types are often assumed to be common knowledge, information elicitation considers the situation where the players know the distributions better than the decision maker. To weaken the information assumption in Bayesian auctions, we consider an information structure where the knowledge about the distributions is arbitrarily scattered among the players. In such an unstructured information setting, we design mechanisms for auctions with unit-demand or additive valuation functions that aggregate the players’ knowledge, generating revenue that are constant approximations to the optimal Bayesian mechanisms with a common prior. Our mechanisms are 2-step dominant-strategy truthful and the revenue increases gracefully with the amount of knowledge the players collectively have.

Jing Chen, Bo Li, Yingkai Li

Coreness of Cooperative Games with Truncated Submodular Profit Functions

Abstract

Coreness represents solution concepts related to core in cooperative games, which captures the stability of players. Motivated by the scale effect in social networks, economics and other scenario, we study the coreness of cooperative game with truncated submodular profit functions. Specifically, the profit function \(f(\cdot )\) is defined by a truncation of a submodular function \(\sigma (\cdot )\): \(f(\cdot )=\sigma (\cdot )\) if \(\sigma (\cdot )\ge \eta \) and \(f(\cdot )=0\) otherwise, where \(\eta \) is a given threshold. In this paper, we study the core and three core-related concepts of truncated submodular profit cooperative game. We first prove that whether core is empty can be decided in polynomial time and an allocation in core also can be found in polynomial time when core is not empty. When core is empty, we show hardness results and approximation algorithms for computing other core-related concepts including relative least-core value, absolute least-core value and least average dissatisfaction value.

Wei Chen, Xiaohan Shan, Xiaoming Sun, Jialin Zhang

Simple Games Versus Weighted Voting Games

Abstract

A simple game (N, v) is given by a set N of n players and a partition of \(2^N\) into a set \(\mathcal {L}\) of losing coalitions L with value \(v(L)=0\) that is closed under taking subsets and a set \(\mathcal {W}\) of winning coalitions W with \(v(W)=1\). Simple games with \(\alpha = \min _{p\ge 0}\max _{W\in \mathcal{W},L\in \mathcal{L}} \frac{p(L)}{p(W)}<1\) are exactly the weighted voting games. Freixas and Kurz (IJGT, 2014) conjectured that \(\alpha \le \frac{1}{4}n\) for every simple game (N, v). We confirm this conjecture for two complementary cases, namely when all minimal winning coalitions have size 3 and when no minimal winning coalition has size 3. As a general bound we prove that \(\alpha \le \frac{2}{7}n\) for every simple game (N, v). For complete simple games, Freixas and Kurz conjectured that \(\alpha =O(\sqrt{n})\). We prove this conjecture up to a \(\ln n\) factor. We also prove that for graphic simple games, that is, simple games in which every minimal winning coalition has size 2, computing \(\alpha \) is NP-hard, but polynomial-time solvable if the underlying graph is bipartite. Moreover, we show that for every graphic simple game, deciding if \(\alpha <a\) is polynomial-time solvable for every fixed \(a>0\).

Frits Hof, Walter Kern, Sascha Kurz, Daniël Paulusma

Hide and Seek Game with Multiple Resources

Abstract

We study a generalization of hide and seek game of von Neumann [14], where each player has one or more resources. We characterize the value and Nash equilibria of such games in terms of their unidimensional marginal distributions. We propose a \(\mathcal {O}(n \log (n))\) time algorithm for computing unidimensional marginal distributions of equilibrium strategies and a quadratic time algorithm for computing mixed strategies given the margins. The characterization allows us to establish a number of interesting qualitative features of equilibria.

Marcin Dziubiński, Jaideep Roy

An Improved Envy-Free Cake Cutting Protocol for Four Agents

Abstract

We consider the classic cake-cutting problem of producing envy-free allocations, restricted to the case of four agents. The problem asks for a partition of the cake to four agents, so that every agent finds her piece at least as valuable as every other agent’s piece. The problem has had an interesting history so far. Although the case of three agents is solvable with less than 15 queries, for four agents no bounded procedure was known until the recent breakthroughs of Aziz and Mackenzie [2, 3]. The main drawback of these new algorithms, however, is that they are quite complicated and with a very high query complexity. With four agents, the number of queries required is close to 600. In this work we provide an improved algorithm for four agents, which reduces the current complexity by a factor of 3.4. Our algorithm builds on the approach of [3] by incorporating new insights and simplifying several steps. Overall, this yields an easier to grasp procedure with lower complexity.

Georgios Amanatidis, George Christodoulou, John Fearnley, Evangelos Markakis, Christos-Alexandros Psomas, Eftychia Vakaliou

A Truthful Mechanism for Interval Scheduling

Abstract

Motivated by cloud computing, we study a market-based approach for job scheduling on multiple machines where users have hard deadlines and prefer earlier completion times. In our model, completing a job provides a benefit equal to its present value, i.e., the value discounted to the time when the job finishes. Users submit job requirements to the cloud provider who non-preemptively schedules jobs to maximize the social welfare, i.e., the sum of present values of completed jobs. Using a simple and fast greedy algorithm, we obtain a \(1+s/(s-1)\) approximation to the optimal schedule, where \(s > 1\) is the minimum ratio of a job’s deadline to processing time. Building on our approximation algorithm, we construct a pricing rule to incentivize users to truthfully report all job requirements.

Jugal Garg, Peter McGlaughlin

On Revenue-Maximizing Mechanisms Assuming Convex Costs

Abstract

We investigate revenue-maximizing mechanisms in settings where bidders’ utility functions are characterized by convex costs. Such costs arise, for instance, in procurement auctions for energy, and when bidders borrow money at non-linear interest rates. We provide a 1 / 16e approximation guarantee for a prior-free randomized mechanism when bidders’ values are drawn from MHR distributions, and their costs are polynomial. Additionally, we propose two heuristics that allocate proportionally, using either bidders’ values or virtual values. Perhaps surprisingly, in the convex cost setting, it is preferable to allocate to multiple relatively high bidders, rather than only to bidders with the highest (virtual) value, as is optimal in the traditional quasi-linear utility setting.

Amy Greenwald, Takehiro Oyakawa, Vasilis Syrgkanis

On the Price of Stability of Social Distance Games

Abstract

We consider social distance games, where a group of utility maximizing players, connected over a network representing social proximity, wish to form coalitions (or clusters) so that they are grouped together with players that are at close distance. Given a cluster, the utility of each player depends on its distance to the other players inside the cluster and on the cluster size, and a player will deviate to another cluster if this leads to higher utility. We are interested in Nash equilibria of such games, where no player has an incentive to unilaterally deviate to another cluster, and we present bounds on the price of stability both for the normal utility function and for a slightly modified one.

Christos Kaklamanis, Panagiotis Kanellopoulos, Dimitris Patouchas

Schelling Segregation with Strategic Agents

Abstract

Schelling’s segregation model is a landmark model in sociology. It shows the counter-intuitive phenomenon that residential segregation between individuals of different groups can emerge even when all involved individuals are tolerant. Although the model is widely studied, no pure game-theoretic version where rational agents strategically choose their location exists. We close this gap by introducing and analyzing generalized game-theoretic models of Schelling segregation, where the agents can also have individual location preferences.

For our models we investigate the convergence behavior and the efficiency of their equilibria. In particular, we prove guaranteed convergence to an equilibrium in the version which is closest to Schelling’s original model. Moreover, we provide tight bounds on the Price of Anarchy.

Ankit Chauhan, Pascal Lenzner, Louise Molitor

Efficient Rational Proofs with Strong Utility-Gap Guarantees

Abstract

As modern computing moves towards smaller devices and powerful cloud platforms, more and more computation is being delegated to powerful service providers. Interactive proofs are a widely-used model to design efficient protocols for verifiable computation delegation.

Rational proofs are payment-based interactive proofs. The payments are designed to incentivize the provers to give correct answers. If the provers misreport the answer then they incur a payment loss of at least 1 / u, where u is the utility gap of the protocol.

In this work, we tightly characterize the power of rational proofs that are super efficient, that is, require only logarithmic time and communication for verification. We also characterize the power of single-round rational protocols that require only logarithmic space and randomness for verification. Our protocols have strong (that is, polynomial, logarithmic, and even constant) utility gap. Finally, we show when and how rational protocols can be converted to give the completeness and soundness guarantees of classical interactive proofs.

Jing Chen, Samuel McCauley, Shikha Singh

Removal and Threshold Pricing: Truthful Two-Sided Markets with Multi-dimensional Participants

Abstract

We consider mechanisms for markets that are two-sided and have agents with multi-dimensional strategic spaces on at least one side. The agents of the market are strategic and act to optimize their own utilities, while the mechanism designer aims to optimize a social goal, i.e., the gain from trade. We focus on one example of this setting motivated by a foreseeable privacy-aware future form of online advertising.

Recently, it has been suggested that markets of user information built around information brokers could be introduced to the online advertising ecosystem to overcome online privacy concerns. Such markets give users control over which data gets shared in online advertising exchanges. We describe a model for the above form of online advertising and design two mechanisms for this model. The first is a deterministic mechanism which is related to the vast literature on mechanism design through trade reduction and allows agents with a multi-dimensional strategic space. The second is a randomized mechanism that can handle a more general version of the model. We provide theoretical analyses of our mechanisms and study their performance using simulations based on real-world data.

Moran Feldman, Rica Gonen

A Two-Stage Mechanism for Ordinal Peer Assessment

Abstract

Peer assessment is a major method for evaluating the performance of employee, accessing the contributions of individuals within a group, making social decisions and many other scenarios. The idea is to ask the individuals of the same group to assess the performance of the others. Scores or rankings are then determined based on these evaluations. However, peer assessment can be biased and manipulated, especially when there is a conflict of interests. In this paper, we consider the problem of eliciting the underlying ordering (i.e. ground truth) of n strategic agents with respect to their performances, e.g., quality of work, contributions, scores, etc. We first prove that there is no deterministic mechanism which obtains the underlying ordering in dominant-strategy implementation. Then, we propose a Two-Stage Mechanism in which truth-telling is the unique strict Nash equilibrium yielding the underlying ordering. Moreover, we prove that our two-stage mechanism is asymptotically optimal, since it only needs \(n+1\) queries and we prove an \(\varOmega (n)\) lower bound on query complexity for any mechanism. Finally, we conduct experiments on several scenarios to demonstrate that the proposed two-stage mechanism is robust.

Zhize Li, Le Zhang, Zhixuan Fang, Jian Li

The Equilibrium Existence of a Robust Routing Game Under Interval Uncertainty

Abstract

We study an atomic routing game in a network with interval uncertainty, where the cost of each edge is load-dependent, and can be any value in a given interval whose lower and upper limits are expressed as functions of the edge load. Each player would select a path from his source to his terminal in the network that minimizes his maximum regret, where given a path (strategy) profile of the game, the maximum regret of a player is the worst-case difference between his total cost (in the case of sum-type cost) or her bottleneck cost (in the case of bottleneck-type cost) and the optimum he could attain given the choices of other players in the profile and a priori knowledge about the actual realization of edge costs. A NE of this game, termed as robust Nash equilibrium (RNE), is a path profile under which no player can reduce his maximum regret by unilateral deviation. On the negative side, we show that the problem of deciding whether a given 3-player game with the sum-type costs has an RNE is NP-hard, even if the game is symmetric and all intervals have unit length. On the positive side, we characterize network topologies, for the game with either type of costs, that guarantee the RNE existence regardless of source-terminal locations and interval settings.

Xujin Chen, Xiaodong Hu, Chenhao Wang

Online Trading as a Secretary Problem

Abstract

We consider the online problem in which an intermediary trades identical items with a sequence of n buyers and n sellers, each of unit demand. We assume that the values of the traders are selected by an adversary and the sequence is randomly permuted. We give competitive algorithms for two objectives: welfare and gain-from-trade.

Elias Koutsoupias, Philip Lazos

Constrained Swap Dynamics over a Social Network in Distributed Resource Reallocation

Abstract

We examine a resource allocation problem where each agent is to be assigned exactly one object. Agents are initially endowed with a resource that they can swap with one another. However, not all exchanges are plausible: we represent required connections between agents with a social network. Agents may only perform pairwise exchanges with their neighbors and only if it brings them preferred objects. We analyze this distributed process through two dual questions. Could an agent obtain a certain object if the swaps occurred favourably? Can an agent be guaranteed a certain level of satisfaction regardless of the actual exchanges? These questions are investigated through parameterized complexity, focusing on budget constraints such as the number of exchanges an agent may be involved in or the total duration of the process.

Abdallah Saffidine, Anaëlle Wilczynski

A Hashing Power Allocation Game in Cryptocurrencies

Abstract

Various crypto-currencies backed by Blockchain technology are now springing up like mushrooms. Miners in these peer-to-peer networks compete to maintain the validity of the underlying ledgers to earn the bootstrapped crypto-currencies. With limited hashing power, each miner needs to decide how to allocate their resource to different crypto-currencies so as to achieve the best overall payoff. Together all the miners form a hashing power allocation game. We consider the setting of the game in which the miners are risk-neutral. We show that a unique pure Nash Equilibrium exists and can be computed efficiently in this settings.

Yukun Cheng, Donglei Du, Qiaoming Han

Resource Based Cooperative Games: Optimization, Fairness and Stability

Abstract

We study the class of resource-based coalitional games. We provide efficient algorithms to compute solution concepts for weighted voting games, threshold task games and r-weighted voting games; in particular, we compute approximately optimal coalition structures, and present non-trivial bounds on the cost of stability for these classes; in particular, we improve upon the bounds given in [2] for weighted voting games.

Ta Duy Nguyen, Yair Zick

Short Paper: Strategic Contention Resolution in Multiple Channels with Limited Feedback

Abstract

We consider a game-theoretic setting of contention in communication networks. In a contention game each of \(n \ge 2\) identical players has a single information packet that she wants to transmit in a fast and selfish way through one of \(k \ge 1\) multiple-access channels by choosing a protocol. Here, we extend the model and results of the single-channel case studied in [2] by providing equilibria characterizations for more than one channels, and giving specific anonymous, equilibrium protocols with finite and infinite expected latency. For our equilibrium protocols with infinite expected latency, all players, with high probability transmit successfully in optimal time, i.e. \(\varTheta (n/k)\).

George Christodoulou, Themistoklis Melissourgos, Paul G. Spirakis

The Communication Burden of Single Transferable Vote, in Practice

Abstract

We study single-winner STV from the point of view of communication. First, we assume that voters give, in a single shot, their top-k alternatives; we define a version of STV that works for such votes, and we evaluate empirically the extent to which it approximates the standard STV rule. Second, we evaluate empirically the communication cost of the protocol for STV defined by Conitzer and Sandholm (2005) and some of its improvements.

Manel Ayadi, Nahla Ben Amor, Jérôme Lang

Mechanism Design for Two-Opposite-Facility Location Games with Penalties on Distance

Abstract

This paper is devoted to the two-opposite-facility location games with a penalty whose amount depends on the distance between the two facilities to be opened by an authority. The two facilities are “opposite” in that one is popular and the other is obnoxious. Every selfish agent in the game wishes to stay close to the popular facility and stay away from the obnoxious one; its utility is measured by the difference between its distances to the obnoxious facility and the popular one. The authority determines the locations of the two facilities on a line segment where all agents are located. Each agent has its location information as private, and is required to report its location to the authority. Using the reported agent locations as input, an algorithmic mechanism run by the authority outputs the locations of the two facilities with an aim to maximize certain social welfare. The sum-type social welfare concerns with the penalized total utility of all agents, for which we design both randomized and deterministic group strategy-proof mechanisms with provable approximation ratios, and establish a lower bound on the approximation ratio of any deterministic strategy-proof mechanism. The bottleneck-type social welfare concerns with the penalized minimum utility among all agents, for which we propose a deterministic group strategy-proof mechanism that ensures optimality.

Xujin Chen, Xiaodong Hu, Xiaohua Jia, Minming Li, Zhongzheng Tang, Chenhao Wang

An Optimal Strategy for Static Black-Peg Mastermind with Three Pegs

Abstract

Mastermind is a famous game played by a codebreaker against a codemaker. We investigate its static (also called non-adaptive) black-peg variant. Given c colors and p pegs, the codemaker has to choose a secret, a p-tuple of c colors, and the codebreaker asks a set of questions all at once. Like the secret, a question is a p-tuple of c colors. The codemaker then tells the codebreaker how many pegs in each question are correct in position and color. Then the codebreaker has one final question to find the secret. His aim is to use as few of questions as possible. Our main result is an optimal strategy for the codebreaker for \(p=3\) pegs and an arbitrary number c of colors using \( \lfloor 3c/2 \rfloor +1\) questions.

A reformulation of our result is that the metric dimension of \( \mathbb {Z}_n \times \mathbb {Z}_n \times \mathbb {Z}_n\) is equal to \( \lfloor 3n/2 \rfloor \).

Gerold Jäger, Frank Drewes

Tight Bounds on the Relative Performances of Pricing Mechanisms in Storable Good Markets

Abstract

In the storable good monopoly problem, a monopolist sells a storable good by announcing a price in each time period. Each consumer has a unitary demand per time period with an arbitrary valuation. In each period, consumers may buy none, one, or more than one good (in which case the extra goods are stored for future consumption incurring a linear storage cost). We compare the performance of two important pricing mechanisms on the profitability of the monopolist: pre-announced pricing mechanisms and price contingent mechanisms. In pre-announced pricing the prices in each time period are stated in advance; in a price contingent mechanism each price is stated at the start of the time period, and these prices are dependent upon past purchases. We prove that the monopolist can earn at most \(O(\log T +\log N)\) times more profit by using a pre-announced pricing mechanism rather than a price contingent mechanism. Here T denotes the number of time periods and N denotes the number of consumers. This bound is tight; examples exist where the monopolist would earn a factor \(\varOmega (\log T +\log N)\) more by using a pre-announced pricing mechanism.

Gerardo Berbeglia, Shant Boodaghians, Adrian Vetta

Backmatter