Search

We study a natural application of contract design to search problems with probabilistic prior and exploration costs. These problems have a plethora of applications and are expressed concisely within the Pandora's Box model. Its optimal solution is the ingenious index policy proposed originally by Weitzman in 1979. In our principal-agent setting, the search task is delegated to an agent. The agent performs a sequential exploration of $n$ boxes, suffers the exploration cost for each inspected box, and selects the content (called the prize) of one inspected box as outcome. Agent and principal obtain an individual value based on the selected prize. To influence the search, the principal a-priori designs a contract with a non-negative payment to the agent for each potential prize. The goal of the principal to maximize her expected reward, i.e., value minus payment. We show how to compute optimal contracts for the principal in several scenarios. A popular and important subclass are linear contracts, and we show how to compute optimal linear contracts in polynomial time. For general contracts, we consider the standard assumption that the agent suffers cost but obtains value only from the transfers by the principal. Interestingly, a suitable adaptation of the index policy results in an optimal contract here. More generally, for general contracts with non-zero agent values for outcomes we show how to compute an optimal contract in two cases: (1) when each box has only one prize with non-zero value for principal and agent, (2) for i.i.d. boxes with a single prize with positive value for the principal. These results show that optimal contracts can be highly non-trivial, and their design goes significantly beyond the application or re-interpretation of the index policy.

The recent banking crisis has again emphasized the importance of understanding and mitigating systemic risk in financial networks. In this paper, we study a market-driven approach to rescue a bank in distress based on the idea of claims trading, a notion defined in Chapter 11 of the U.S. Bankruptcy Code. We formalize the idea in the context of financial networks by Eisenberg and Noe. For two given banks v and w, we consider the operation that w takes over some claims of v and in return gives liquidity to v to ultimately rescue v. We study the structural properties and computational complexity of decision and optimization problems for several variants of claims trading. When trading incoming edges of v, we show that there is no trade in which both banks v and w strictly improve their assets. We therefore consider creditor-positive trades, in which v profits strictly and w remains indifferent. For a given set C of incoming edges of v, we provide an efficient algorithm to compute payments by w that result in maximal assets of v. When the set C must also be chosen, the problem becomes weakly NP-hard. Our main result here is a bicriteria FPTAS to compute an approximate trade. The approximate trade results in nearly the optimal amount of assets of v in any exact trade. Our results extend to the case in which banks use general monotone payment functions and the emerging clearing state can be computed efficiently. In contrast, for trading outgoing edges of v, the goal is to maximize the increase in assets for the creditors of v. Notably, for these results the characteristics of the payment functions of the banks are essential. For payments ranking creditors one by one, we show NP-hardness of approximation within a factor polynomial in the network size, when the set of claims C is part of the input or not. Instead, for proportional payments, our results indicate more favorable conditions.

We study a novel approach to information design in the standard traffic model of network congestion games. It captures the natural condition that the demand is unknown to the users of the network. A principal (e.g., a mobility service) commits to a signaling strategy, observes the realized demand and sends a (public) signal to agents (i.e., users of the network). Based on the induced belief about the demand, the users then form an equilibrium. We consider the algorithmic goal of the principal: Compute a signaling scheme that minimizes the expected total cost of the induced equilibrium. We concentrate on single-commodity networks and affine cost functions, for which we obtain the following results. First, we devise a fully polynomial-time approximation scheme (FPTAS) for the case that the demand can only take two values. It relies on several structural properties of the cost of the induced equilibrium as a function of the updated belief about the distribution of demands. We show that this function is piecewise linear for any number of demands, and monotonic for two demands. Second, we give a complete characterization of the graph structures for which it is optimal to fully reveal the information about the realized demand. This signaling scheme turns out to be optimal for all cost functions and probability distributions over demands if and only if the graph is series-parallel. Third, we propose an algorithm that computes the optimal signaling scheme for any number of demands whose time complexity is polynomial in the number of supports that occur in a Wardrop equilibrium for some demand. Finally, we conduct a computational study that tests this algorithm on real-world instances., Comment: arXiv admin note: text overlap with arXiv:2205.09823

We study threshold testing, an elementary probing model with the goal to choose a large value out of $n$ i.i.d. random variables. An algorithm can test each variable $X_i$ once for some threshold $t_i$, and the test returns binary feedback whether $X_i \ge t_i$ or not. Thresholds can be chosen adaptively or non-adaptively by the algorithm. Given the results for the tests of each variable, we then select the variable with highest conditional expectation. We compare the expected value obtained by the testing algorithm with expected maximum of the variables. Threshold testing is a semi-online variant of the gambler's problem and prophet inequalities. Indeed, the optimal performance of non-adaptive algorithms for threshold testing is governed by the standard i.i.d. prophet inequality of approximately $0.745+o(1)$ as $n \to \infty$. We show how adaptive algorithms can significantly improve upon this ratio. Our adaptive testing strategy guarantees a competitive ratio of at least $0.869-o(1)$. Moreover, we show that there are distributions that admit only a constant ratio $c < 1$, even when $n \to \infty$. Finally, when each box can be tested multiple times (with $n$ tests in total), we design an algorithm that achieves a ratio of $1-o(1)$.

A debt swap is an elementary edge swap in a directed, weighted graph, where two edges with the same weight swap their targets. Debt swaps are a natural and appealing operation in financial networks, in which nodes are banks and edges represent debt contracts. They can improve the clearing payments and the stability of these networks. However, their algorithmic properties are not well-understood. We analyze the computational complexity of debt swapping in networks with ranking-based clearing. Our main interest lies in semi-positive swaps, in which no creditor strictly suffers and at least one strictly profits. These swaps lead to a Pareto-improvement in the entire network. We consider network optimization via sequences of $v$-improving debt swaps from which a given bank $v$ strictly profits. We show that every sequence of semi-positive $v$-improving swaps has polynomial length. In contrast, for arbitrary $v$-improving swaps, the problem of reaching a network configuration that allows no further swaps is PLS-complete. We identify cases in which short sequences of semi-positive swaps exist even without the $v$-improving property. In addition, we study reachability problems, i.e., deciding if a sequence of swaps exists between given initial and final networks. We identify a polynomial-time algorithm for arbitrary swaps, show NP-hardness for semi-positive swaps and even PSPACE-completeness for $v$-improving swaps or swaps that only maintain a lower bound on the assets of a given bank $v$. A variety of our results can be extended to arbitrary monotone clearing., Comment: 36 pages, 10 figures

Fair division of indivisible goods is a central challenge in artificial intelligence. For many prominent fairness criteria including envy-freeness (EF) or proportionality (PROP), no allocations satisfying these criteria might exist. Two popular remedies to this problem are randomization or relaxation of fairness concepts. A timely research direction is to combine the advantages of both, commonly referred to as Best of Both Worlds (BoBW). We consider fair division with entitlements, which allows to adjust notions of fairness to heterogeneous priorities among agents. This is an important generalization to standard fair division models and is not well-understood in terms of BoBW results. Our main result is a lottery for additive valuations and different entitlements that is ex-ante weighted envy-free (WEF), as well as ex-post weighted proportional up to one good (WPROP1) and weighted transfer envy-free up to one good (WEF(1,1)). It can be computed in strongly polynomial time. We show that this result is tight - ex-ante WEF is incompatible with any stronger ex-post WEF relaxation. In addition, we extend BoBW results on group fairness to entitlements and explore generalizations of our results to instances with more expressive valuation functions.

We study the problem of allocating a set of indivisible goods among a set of agents with \emph{2-value additive valuations}. In this setting, each good is valued either $1$ or $\sfrac{p}{q}$, for some fixed co-prime numbers $p,q\in \NN$ such that $1\leq q < p$. Our goal is to find an allocation maximizing the \emph{Nash social welfare} (\NSW), i.e., the geometric mean of the valuations of the agents. In this work, we give a complete characterization of polynomial-time tractability of \NSW\ maximization that solely depends on the values of $q$. We start by providing a rather simple polynomial-time algorithm to find a maximum \NSW\ allocation when the valuation functions are \emph{integral}, that is, $q=1$. We then exploit more involved techniques to get an algorithm producing a maximum \NSW\ allocation for the \emph{half-integral} case, that is, $q=2$. Finally, we show it is \classNP-hard to compute an allocation with maximum \NSW\ whenever $q\geq3$.

The complex interactions between algorithmic trading agents can have a severe influence on the functioning of our economy, as witnessed by recent banking crises and trading anomalies. A common phenomenon in these situations are fire sales, a contagious process of asset sales that trigger further sales. We study the existence and structure of equilibria in a game-theoretic model of fire sales. We prove that for a wide parameter range (e.g., convex price impact functions), equilibria exist and form a complete lattice. This is contrasted with a non-existence result for concave price impact functions. Moreover, we study the convergence of best-response dynamics towards equilibria when they exist. In general, best-response dynamics may cycle. However, in many settings they are guaranteed to converge to the socially optimal equilibrium when starting from a natural initial state. Moreover, we discuss a simplified variant of the dynamics that is less informationally demanding and converges to the same equilibria. We compare the dynamics in terms of convergence speed., Comment: To appear at the 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2023), full version

Financial network games model payment incentives in the context of networked liabilities. In this paper, we advance the understanding of incentives in financial networks in two important directions: minimal clearing (arising, e.g., as a result of sequential execution of payments) and seniorities (i.e., priorities over debt contracts). We distinguish between priorities that are chosen endogenously or exogenously. For endogenous priorities and standard (maximal) clearing, the games exhibit a coalitional form of weak acyclicity. A strong equilibrium exists and can be reached after a polynomial number of deviations. Moreover, there is a strong equilibrium that is optimal for a wide variety of social welfare functions. In contrast, for minimal clearing there are games in which no optimal strategy profile exists, even for standard utilitarian social welfare. Perhaps surprisingly, a strong equilibrium still exists and, for a wide range of strategies, can be reached after a polynomial number of deviations. In contrast, for exogenous priorities, equilibria can be absent and equilibrium existence is NP-hard to decide, for both minimal and maximal clearing.

We consider a largely untapped potential for the improvement of traffic networks that is rooted in the inherent uncertainty of travel times. Travel times are subject to stochastic uncertainty resulting from various parameters such as weather condition, occurrences of road works, or traffic accidents. Large mobility services have an informational advantage over single network users as they are able to learn traffic conditions from data. A benevolent mobility service may use this informational advantage in order to steer the traffic equilibrium into a favorable direction. The resulting optimization problem is a task commonly referred to as signaling or Bayesian persuasion. Previous work has shown that the underlying signaling problem can be NP-hard to approximate within any non-trivial bounds, even for affine cost functions with stochastic offsets. In contrast, we show that in this case, the signaling problem is easy for many networks. We tightly characterize the class of single-commodity networks, in which full information revelation is always an optimal signaling strategy. Moreover, we construct a reduction from optimal signaling to computing an optimal collection of support vectors for the Wardrop equilibrium. For two states, this insight can be used to compute an optimal signaling scheme. The algorithm runs in polynomial time whenever the number of different supports resulting from any signal distribution is bounded to a polynomial in the input size. Using a cell decomposition technique, we extend the approach to a polynomial-time algorithm for multi-commodity parallel link networks with a constant number of commodities, even when we have a constant number of different states of nature.

In a delegation problem, a principal P with commitment power tries to pick one out of $n$ options. Each option is drawn independently from a known distribution. Instead of inspecting the options herself, P delegates the information acquisition to a rational and self-interested agent A. After inspection, A proposes one of the options, and P can accept or reject. Delegation is a classic setting in economic information design with many prominent applications, but the computational problems are only poorly understood. In this paper, we study a natural online variant of delegation, in which the agent searches through the options in an online fashion. For each option, he has to irrevocably decide if he wants to propose the current option or discard it, before seeing information on the next option(s). How can we design algorithms for P that approximate the utility of her best option in hindsight? We show that in general P can obtain a $\Theta(1/n)$-approximation and extend this result to ratios of $\Theta(k/n)$ in case (1) A has a lookahead of $k$ rounds, or (2) A can propose up to $k$ different options. We provide fine-grained bounds independent of $n$ based on two parameters. If the ratio of maximum and minimum utility for A is bounded by a factor $\alpha$, we obtain an $\Omega(\log \log \alpha / \log \alpha)$-approximation algorithm, and we show that this is best possible. Additionally, if P cannot distinguish options with the same value for herself, we show that ratios polynomial in $1/\alpha$ cannot be avoided. If the utilities of P and A for each option are related by a factor $\beta$, we obtain an $\Omega(1/ \log \beta)$-approximation, where $O(\log \log \beta/ \log \beta)$ is best possible., Comment: 23 pages

Opinion spreading in a society decides the fate of elections, the success of products, and the impact of political or social movements. The model by Hegselmann and Krause is a well-known theoretical model to study such opinion formation processes in social networks. In contrast to many other theoretical models, it does not converge towards a situation where all agents agree on the same opinion. Instead, it assumes that people find an opinion reasonable if and only if it is close to their own. The system converges towards a stable situation where agents sharing the same opinion form a cluster, and agents in different clusters do not \mbox{influence each other.} We focus on the social variant of the Hegselmann-Krause model where agents are connected by a social network and their opinions evolve in an iterative process. When activated, an agent adopts the average of the opinions of its neighbors having a similar opinion. By this, the set of influencing neighbors of an agent may change over time. To the best of our knowledge, social Hegselmann-Krause systems with asynchronous opinion updates have only been studied with the complete graph as social network. We show that such opinion dynamics with random agent activation are guaranteed to converge for any social network. We provide an upper bound of $\mathcal{O}(n|E|^2 (\varepsilon/\delta)^2)$ on the expected number of opinion updates until convergence, where $|E|$ is the number of edges of the social network. For the complete social network we show a bound of $\mathcal{O}(n^3(n^2 + (\varepsilon/\delta)^2))$ that represents a major improvement over the previously best upper bound of $\mathcal{O}(n^9 (\varepsilon/\delta)^2)$. Our bounds are complemented by simulations that indicate asymptotically matching lower bounds., Comment: Full version with extended results compared to the AAMAS'22 version

We consider the problem of maximizing the Nash social welfare when allocating a set $\mathcal{G}$ of indivisible goods to a set $\mathcal{N}$ of agents. We study instances, in which all agents have 2-value additive valuations: The value of every agent $i \in \mathcal{N}$ for every good $j \in \mathcal{G}$ is $v_{ij} \in \{p,q\}$, for $p,q \in \mathbb{N}$, $p \le q$. Maybe surprisingly, we design an algorithm to compute an optimal allocation in polynomial time if $p$ divides $q$, i.e., when $p=1$ and $q \in \mathbb{N}$ after appropriate scaling. The problem is \classNP-hard whenever $p$ and $q$ are coprime and $p \ge 3$. In terms of approximation, we present positive and negative results for general $p$ and $q$. We show that our algorithm obtains an approximation ratio of at most 1.0345. Moreover, we prove that the problem is \classAPX-hard, with a lower bound of $1.000015$ achieved at $p/q = 4/5$.

In a game of persuasion with evidence, a sender has private information. By presenting evidence on the information, the sender wishes to persuade a receiver to take a single action (e.g., hire a job candidate, or convict a defendant). The sender's utility depends solely on whether or not the receiver takes the action. The receiver's utility depends on both the action and the sender's private information. We study three natural variations. First, we consider the problem of computing an equilibrium of the game without commitment power. Second, we consider a persuasion variant, where the sender commits to a signaling scheme and the receiver, after seeing the evidence, takes the action or not. Third, we study a delegation variant, where the receiver first commits to taking the action if being presented certain evidence, and the sender presents evidence to maximize the probability the action is taken. We study these variants through the computational lens, and give hardness results, optimal approximation algorithms, and polynomial-time algorithms for special cases. Among our results is an approximation algorithm that rounds a semidefinite program that might be of independent interest, since, to the best of our knowledge, it is the first such approximation algorithm in algorithmic economics., Comment: 34 pages

The Bayesian persuasion paradigm of strategic communication models interaction between a privately-informed agent, called the sender, and an ignorant but rational agent, called the receiver. The goal is typically to design a (near-)optimal communication (or signaling) scheme for the sender. It enables the sender to disclose information to the receiver in a way as to incentivize her to take an action that is preferred by the sender. Finding the optimal signaling scheme is known to be computationally difficult in general. This hardness is further exacerbated when there is also a constraint on the size of the message space, leading to NP-hardness of approximating the optimal sender utility within any constant factor. In this paper, we show that in several natural and prominent cases the optimization problem is tractable even when the message space is limited. In particular, we study signaling under a symmetry or an independence assumption on the distribution of utility values for the actions. For symmetric distributions, we provide a novel characterization of the optimal signaling scheme. It results in a polynomial-time algorithm to compute an optimal scheme for many compactly represented symmetric distributions. In the independent case, we design a constant-factor approximation algorithm, which stands in marked contrast to the hardness of approximation in the general case.

The Bayesian persuasion model studies communication between an informed sender and a receiver with a payoff-relevant action, emphasizing the ability of a sender to extract maximal surplus from his informational advantage. In this paper we study a setting with multiple senders, but in which the receiver interacts with only one sender of his choice: senders commit to signals and the receiver then chooses, at the interim stage, with which sender to interact. Our main result is that whenever senders are even slightly uncertain about each other's preferences, the receiver receives all the informational surplus in all equilibria of this game.

We study a game-theoretic variant of the maximum circulation problem. In a flow allocation game, we are given a directed flow network. Each node is a rational agent and can strategically allocate any incoming flow to the outgoing edges. Given the strategy choices of all agents, a maximal circulation that adheres to the chosen allocation strategies evolves in the network. Each agent wants to maximize the amount of flow through her node. Flow allocation games can be used to express strategic incentives of clearing in financial networks. We provide a cumulative set of results on the existence and computational complexity of pure Nash and strong equilibria, as well as tight bounds on the (strong) prices of anarchy and stability. Our results show an interesting dichotomy: Ranking strategies over individual flow units allow to obtain optimal strong equilibria for many objective functions. In contrast, more intuitive ranking strategies over edges can give rise to unfavorable incentive properties., Comment: 44 pages, 7 figures

In this paper we revisit the basic variant of the classical secretary problem. We propose a new approach in which we separate between an agent that evaluates the secretary performance and one that has to make the hiring decision. The evaluating agent (the sender) signals the quality of the candidate to the hiring agent (the receiver) who must make a decision. Whenever the two agents' interests are not fully aligned, this induces an information transmission (signaling) challenge for the sender. We study the sender's optimization problem subject to persuasiveness constraints of the receiver for several variants of the problem. Our results quantify the loss in performance for the sender due to online arrival. We provide optimal and near-optimal persuasive mechanisms that recover at least a constant fraction of a natural utility benchmark for the sender. The separation of evaluation and decision making can have a substantial impact on the approximation results. While in some scenarios, techniques and results closely mirror the conditions in the standard secretary problem, we also explore conditions that lead to very different characteristics., Comment: 35 pages, 2 figures

We study online secretary problems with returns in combinatorial packing domains with $n$ candidates that arrive sequentially over time in random order. The goal is to accept a feasible packing of candidates of maximum total value. In the first variant, each candidate arrives exactly twice. All $2n$ arrivals occur in random order. We propose a simple 0.5-competitive algorithm that can be combined with arbitrary approximation algorithms for the packing domain, even when the total value of candidates is a subadditive function. For bipartite matching, we obtain an algorithm with competitive ratio at least $0.5721 - o(1)$ for growing $n$, and an algorithm with ratio at least $0.5459$ for all $n \ge 1$. We extend all algorithms and ratios to $k \ge 2$ arrivals per candidate. In the second variant, there is a pool of undecided candidates. In each round, a random candidate from the pool arrives. Upon arrival a candidate can be either decided (accept/reject) or postponed (returned into the pool). We mainly focus on minimizing the expected number of postponements when computing an optimal solution. An expected number of $\Theta(n \log n)$ is always sufficient. For matroids, we show that the expected number can be reduced to $O(r \log (n/r))$, where $r \le n/2$ is the minimum of the ranks of matroid and dual matroid. For bipartite matching, we show a bound of $O(r \log n)$, where $r$ is the size of the optimum matching. For general packing, we show a lower bound of $\Omega(n \log \log n)$, even when the size of the optimum is $r = \Theta(\log n)$., Comment: 23 pages, 5 figures

We consider the task of assigning indivisible goods to a set of agents in a fair manner. Our notion of fairness is Nash social welfare, i.e., the goal is to maximize the geometric mean of the utilities of the agents. Each good comes in multiple items or copies, and the utility of an agent diminishes as it receives more items of the same good. The utility of a bundle of items for an agent is the sum of the utilities of the items in the bundle. Each agent has a utility cap beyond which he does not value additional items. We give a polynomial time approximation algorithm that maximizes Nash social welfare up to a factor of $e^{1/{e}} \approx 1.445$. The computed allocation is Pareto-optimal and approximates envy-freeness up to one item up to a factor of $2 + \eps$

Competitive equilibrium is a central concept in economics with numerous applications beyond markets, such as scheduling, fair allocation of goods, or bandwidth distribution in networks. Computation of competitive equilibria has received a significant amount of interest in algorithmic game theory, mainly for the prominent case of Fisher markets. Natural and decentralized processes like tatonnement and proportional response dynamics (PRD) converge quickly towards equilibrium in large classes of Fisher markets. Almost all of the literature assumes that the market is a static environment and that the parameters of agents and goods do not change over time. In contrast, many large real-world markets are subject to frequent and dynamic changes. In this paper, we provide the first provable performance guarantees of discrete-time tatonnement and PRD in markets that are subject to perturbation over time. We analyze the prominent class of Fisher markets with CES utilities and quantify the impact of changes in supplies of goods, budgets of agents, and utility functions of agents on the convergence of tatonnement to market equilibrium. Since the equilibrium becomes a dynamic object and will rarely be reached, our analysis provides bounds expressing the distance to equilibrium that will be maintained via tatonnement and PRD updates. Our results indicate that in many cases, tatonnement and PRD follow the equilibrium rather closely and quickly recover conditions of approximate market clearing. Our approach can be generalized to analyzing a general class of Lyapunov dynamical systems with changing system parameters, which might be of independent interest.

In cost sharing games with delays, a set of agents jointly allocates a finite subset of resources. Each resource has a fixed cost that has to be shared by the players, and each agent has a nonshareable player-specific delay for each resource. A prominent example is uncapacitated facility location (UFL), where facilities need to be opened (at a shareable cost) and clients want to connect to opened facilities. Each client pays a cost share and his non-shareable physical connection cost. Given any profile of subsets allocated by the agents, a separable cost sharing protocol determines cost shares that satisfy budget balance on every resource and separability over the resources. Moreover, a separable protocol guarantees existence of pure Nash equilibria in the induced strategic game for the agents. In this paper, we study separable cost sharing protocols in several general combinatorial domains. We provide black-box reductions to reduce the design of a separable cost-sharing protocol to the design of an approximation algorithm for the underlying cost minimization problem. In this way, we obtain new separable cost-sharing protocols in games based on arbitrary player-specific matroids, single-source connection games without delays, and connection games on $n$-series-parallel graphs with delays. All these reductions are efficiently computable - given an initial allocation profile, we obtain a cheaper profile and separable cost shares turning the profile into a pure Nash equilibrium. Hence, in these domains any approximation algorithm can be used to obtain a separable cost sharing protocol with a price of stability bounded by the approximation factor.

We study linear Fisher markets with satiation. In these markets, sellers have earning limits and buyers have utility limits. Beyond natural applications in economics, these markets arise in the context of maximizing Nash social welfare when allocating indivisible items to agents. In contrast to markets with either earning or utility limits, markets with both limits have not been studied before. They turn out to have fundamentally different properties. In general, the existence of competitive equilibria is not guaranteed. We identify a natural property of markets (termed money clearing) that implies existence. We show that the set of equilibria is not always convex, answering a question of Cole et al. [EC'17]. We design an FPTAS to compute an approximate equilibrium and prove that the problem of computing an exact equilibrium lies in the intersection of complexity classes PLS and PPAD. For a constant number of buyers or goods, we give a polynomial-time algorithm to compute an exact equilibrium. We show how (approximate) equilibria can be rounded and provide the first constant-factor approximation algorithm (with a factor of 2.404) for maximizing Nash social welfare when agents have budget-additive valuations. Finally, we significantly improve the approximation hardness for additive valuations to \sqrt{8/7} > 1.069 (over 1.00008 by Lee [IPL'17])., Comment: Restructured the paper with improved lower bound

The secretary problem is a classic model for online decision making. Recently, combinatorial extensions such as matroid or matching secretary problems have become an important tool to study algorithmic problems in dynamic markets. Here the decision maker must know the numerical value of each arriving element, which can be a demanding informational assumption. In this paper, we initiate the study of combinatorial secretary problems with ordinal information, in which the decision maker only needs to be aware of a preference order consistent with the values of arrived elements. The goal is to design online algorithms with small competitive ratios. For a variety of combinatorial problems, such as bipartite matching, general packing LPs, and independent set with bounded local independence number, we design new algorithms that obtain constant competitive ratios. For the matroid secretary problem, we observe that many existing algorithms for special matroid structures maintain their competitive ratios even in the ordinal model. In these cases, the restriction to ordinal information does not represent any additional obstacle. Moreover, we show that ordinal variants of the submodular matroid secretary problems can be solved using algorithms for the linear versions by extending [Feldman and Zenklusen, 2015]. In contrast, we provide a lower bound of $\Omega(\sqrt{n}/(\log n))$ for algorithms that are oblivious to the matroid structure, where $n$ is the total number of elements. This contrasts an upper bound of $O(\log n)$ in the cardinal model, and it shows that the technique of thresholding is not sufficient for good algorithms in the ordinal model., Comment: Full version of ICALP 2017 paper

We present the first analysis of Fisher markets with buyers that have budget-additive utility functions. Budget-additive utilities are elementary concave functions with numerous applications in online adword markets and revenue optimization problems. They extend the standard case of linear utilities and have been studied in a variety of other market models. In contrast to the frequently studied CES utilities, they have a global satiation point which can imply multiple market equilibria with quite different characteristics. Our main result is an efficient combinatorial algorithm to compute a market equilibrium with a Pareto-optimal allocation of goods. It relies on a new descending-price approach and, as a special case, also implies a novel combinatorial algorithm for computing a market equilibrium in linear Fisher markets. We complement these positive results with a number of hardness results for related computational questions. We prove that it is NP-hard to compute a market equilibrium that maximizes social welfare, and it is PPAD-hard to find any market equilibrium with utility functions with separate satiation points for each buyer and each good., Comment: 21 pages

Combinatorial auctions (CA) are a well-studied area in algorithmic mechanism design. However, contrary to the standard model, empirical studies suggest that a bidder's valuation often does not depend solely on the goods assigned to him. For instance, in adwords auctions an advertiser might not want his ads to be displayed next to his competitors' ads. In this paper, we propose and analyze several natural graph-theoretic models that incorporate such negative externalities, in which bidders form a directed conflict graph with maximum out-degree $\Delta$. We design algorithms and truthful mechanisms for social welfare maximization that attain approximation ratios depending on $\Delta$. For CA, our results are twofold: (1) A lottery that eliminates conflicts by discarding bidders/items independent of the bids. It allows to apply any truthful $\alpha$-approximation mechanism for conflict-free valuations and yields an $\mathcal{O}(\alpha\Delta)$-approximation mechanism. (2) For fractionally sub-additive valuations, we design a rounding algorithm via a novel combination of a semi-definite program and a linear program, resulting in a cone program; the approximation ratio is $\mathcal{O}((\Delta \log \log \Delta)/\log \Delta)$. The ratios are almost optimal given existing hardness results. For the prominent application of adwords auctions, we present several algorithms for the most relevant scenario when the number of items is small. In particular, we design a truthful mechanism with approximation ratio $o(\Delta)$ when the number of items is only logarithmic in the number of bidders., Comment: This is the full version of our WINE 2015 conference paper

We study social welfare of learning outcomes in mechanisms with admission. In our repeated game there are $n$ bidders and $m$ mechanisms, and in each round each mechanism is available for each bidder only with a certain probability. Our scenario is an elementary case of simple mechanism design with incomplete information, where availabilities are bidder types. It captures natural applications in online markets with limited supply and can be used to model access of unreliable channels in wireless networks. If mechanisms satisfy a smoothness guarantee, existing results show that learning outcomes recover a significant fraction of the optimal social welfare. These approaches, however, have serious drawbacks in terms of plausibility and computational complexity. Also, the guarantees apply only when availabilities are stochastically independent among bidders. In contrast, we propose an alternative approach where each bidder uses a single no-regret learning algorithm and applies it in all rounds. This results in what we call availability-oblivious coarse correlated equilibria. It exponentially decreases the learning burden, simplifies implementation (e.g., as a method for channel access in wireless devices), and thereby addresses some of the concerns about Bayes-Nash equilibria and learning outcomes in Bayesian settings. Our main results are general composition theorems for smooth mechanisms when valuation functions of bidders are lattice-submodular. They rely on an interesting connection to the notion of correlation gap of submodular functions over product lattices., Comment: Full version of WINE 2016 paper

We design a simple ascending-price algorithm to compute a $(1+\varepsilon)$-approximate equilibrium in Arrow-Debreu exchange markets with weak gross substitute (WGS) property, which runs in time polynomial in market parameters and $\log 1/\varepsilon$. This is the first polynomial-time algorithm for most of the known tractable classes of Arrow-Debreu markets, which is easy to implement and avoids heavy machinery such as the ellipsoid method. In addition, our algorithm can be applied in unknown market setting without exact knowledge about the number of agents, their individual utilities and endowments. Instead, our algorithm only relies on queries to a global demand oracle by posting prices and receiving aggregate demand for goods as feedback. When demands are real-valued functions of prices, the oracles can only return values of bounded precision based on real utility functions. Due to this more realistic assumption, precision and representation of prices and demands become a major technical challenge, and we develop new tools and insights that may be of independent interest. Furthermore, our approach also gives the first polynomial-time algorithm to compute an exact equilibrium for markets with spending constraint utilities, a piecewise linear concave generalization of linear utilities. This resolves an open problem posed by Duan and Mehlhorn (2015)., Comment: 33 pages

We study uncoordinated matching markets with additional local constraints that capture, e.g., restricted information, visibility, or externalities in markets. Each agent is a node in a fixed matching network and strives to be matched to another agent. Each agent has a complete preference list over all other agents it can be matched with. However, depending on the constraints and the current state of the game, not all possible partners are available for matching at all times. For correlated preferences, we propose and study a general class of hedonic coalition formation games that we call coalition formation games with constraints. This class includes and extends many recently studied variants of stable matching, such as locally stable matching, socially stable matching, or friendship matching. Perhaps surprisingly, we show that all these variants are encompassed in a class of "consistent" instances that always allow a polynomial improvement sequence to a stable state. In addition, we show that for consistent instances there always exists a polynomial sequence to every reachable state. Our characterization is tight in the sense that we provide exponential lower bounds when each of the requirements for consistency is violated. We also analyze matching with uncorrelated preferences, where we obtain a larger variety of results. While socially stable matching always allows a polynomial sequence to a stable state, for other classes different additional assumptions are sufficient to guarantee the same results. For the problem of reaching a given stable state, we show NP-hardness in almost all considered classes of matching games., Comment: Conference Version in WINE 2014

Max-min fairness (MMF) is a widely known approach to a fair allocation of bandwidth to each of the users in a network. This allocation can be computed by uniformly raising the bandwidths of all users without violating capacity constraints. We consider an extension of these allocations by raising the bandwidth with arbitrary and not necessarily uniform time-depending velocities (allocation rates). These allocations are used in a game-theoretic context for routing choices, which we formalize in progressive filling games (PFGs). We present a variety of results for equilibria in PFGs. We show that these games possess pure Nash and strong equilibria. While computation in general is NP-hard, there are polynomial-time algorithms for prominent classes of Max-Min-Fair Games (MMFG), including the case when all users have the same source-destination pair. We characterize prices of anarchy and stability for pure Nash and strong equilibria in PFGs and MMFGs when players have different or the same source-destination pairs. In addition, we show that when a designer can adjust allocation rates, it is possible to design games with optimal strong equilibria. Some initial results on polynomial-time algorithms in this direction are also derived.

We consider capacity maximization in wireless networks under adversarial interference conditions. There are n links, each consisting of a sender and a receiver, which repeatedly try to perform a successful transmission. In each time step, the success of attempted transmissions depends on interference conditions, which are captured by an interference model (e.g. the SINR model). Additionally, an adversarial jammer can render a (1-delta)-fraction of time steps unsuccessful. For this scenario, we analyze a framework for distributed learning algorithms to maximize the number of successful transmissions. Our main result is an algorithm based on no-regret learning converging to an O(1/delta)-approximation. It provides even a constant-factor approximation when the jammer exactly blocks a (1-delta)-fraction of time steps. In addition, we consider a stochastic jammer, for which we obtain a constant-factor approximation after a polynomial number of time steps. We also consider more general settings, in which links arrive and depart dynamically, and where each sender tries to reach multiple receivers. Our algorithms perform favorably in simulations., Comment: 22 pages, 2 figures, typos removed

We investigate online algorithms for maximum (weight) independent set on graph classes with bounded inductive independence number like, e.g., interval and disk graphs with applications to, e.g., task scheduling and spectrum allocation. In the online setting, it is assumed that nodes of an unknown graph arrive one by one over time. An online algorithm has to decide whether an arriving node should be included into the independent set. Unfortunately, this natural and practically relevant online problem cannot be studied in a meaningful way within a classical competitive analysis as the competitive ratio on worst-case input sequences is lower bounded by $\Omega(n)$. As a worst-case analysis is pointless, we study online independent set in a stochastic analysis. Instead of focussing on a particular stochastic input model, we present a generic sampling approach that enables us to devise online algorithms achieving performance guarantees for a variety of input models. In particular, our analysis covers stochastic input models like the secretary model, in which an adversarial graph is presented in random order, and the prophet-inequality model, in which a randomly generated graph is presented in adversarial order. Our sampling approach bridges thus between stochastic input models of quite different nature. In addition, we show that our approach can be applied to a practically motivated admission control setting. Our sampling approach yields an online algorithm for maximum independent set with competitive ratio $O(\rho^2)$ with respect to all of the mentioned stochastic input models. for graph classes with inductive independence number $\rho$. The approach can be extended towards maximum-weight independent set by losing only a factor of $O(\log n)$ in the competitive ratio with $n$ denoting the (expected) number of nodes.

We study probabilistic protocols for concurrent threshold-based load balancing in networks. There are n resources or machines represented by nodes in an undirected graph and m >> n users that try to find an acceptable resource by moving along the edges of the graph. Users accept a resource if the load is below a threshold. Such thresholds have an intuitive meaning, e.g., as deadlines in a machine scheduling scenario, and they allow the design of protocols under strong locality constraints. When migration is partly controlled by resources and partly by users, our protocols obtain rapid convergence to a balanced state, in which all users are satisfied. We show that convergence is achieved in a number of rounds that is only logarithmic in m and polynomial in structural properties of the graph. Even when migration is fully controlled by users, we obtain similar results for convergence to approximately balanced states. If we slightly adjust the migration probabilities in our protocol, we can also obtain fast convergence to balanced states., Comment: 20 pages, brief announcement in PODC 2013

We present algorithms for implementing local spectrum redistribution in wireless networks using a mechanism design approach. For example, in single-hop request scheduling, secondary users are modeled as rational agents that have private utility when getting assigned a channel for successful transmission. We present a rather simple algorithmic technique that allows to turn existing and future approximation algorithms and heuristics into truthful mechanisms for a large variety of networking problems. In contrast to previous work, our approach works for virtually all known interference models in the literature, including the physical model of interference based on SINR. It allows to address single-hop and multi-hop scheduling, routing, and even more general assignment and allocation problems. Our mechanisms are randomized and represent the first universally-truthful mechanisms for these problems with rigorous worst-case guarantees on the solution quality. In this way, our mechanisms can be used to obtain guaranteed solution quality even with risk-averse or risk-seeking bidders, for which existing approaches fail., Comment: 17 pages, brief announcement in SPAA'13

We study stable matching problems with locality of information and control. In our model, each agent is a node in a fixed network and strives to be matched to another agent. An agent has a complete preference list over all other agents it can be matched with. Agents can match arbitrarily, and they learn about possible partners dynamically based on their current neighborhood. We consider convergence of dynamics to locally stable matchings -- states that are stable with respect to their imposed information structure in the network. In the two-sided case of stable marriage in which existence is guaranteed, we show that the existence of a path to stability becomes NP-hard to decide. This holds even when the network exists only among one partition of agents. In contrast, if one partition has no network and agents remember a previous match every round, a path to stability is guaranteed and random dynamics converge with probability 1. We characterize this positive result in various ways. For instance, it holds for random memory and for cache memory with the most recent partner, but not for cache memory with the best partner. Also, it is crucial which partition of the agents has memory. Finally, we present results for centralized computation of locally stable matchings, i.e., computing maximum locally stable matchings in the two-sided case and deciding existence in the roommates case., Comment: Conference version in ICALP 2013; to appear in SIAM J. Disc Math

We study stable matching problems in networks where players are embedded in a social context, and may incorporate friendship relations or altruism into their decisions. Each player is a node in a social network and strives to form a good match with a neighboring player. We consider the existence, computation, and inefficiency of stable matchings from which no pair of players wants to deviate. When the benefits from a match are the same for both players, we show that incorporating the well-being of other players into their matching decisions significantly decreases the price of stability, while the price of anarchy remains unaffected. Furthermore, a good stable matching achieving the price of stability bound always exists and can be reached in polynomial time. We extend these results to more general matching rewards, when players matched to each other may receive different utilities from the match. For this more general case, we show that incorporating social context (i.e., "caring about your friends") can make an even larger difference, and greatly reduce the price of anarchy. We show a variety of existence results, and present upper and lower bounds on the prices of anarchy and stability for various matching utility structures. Finally, we extend most of our results to network contribution games, in which players can decide how much effort to contribute to each incident edge, instead of simply choosing a single node to match with.

We study truthful auctions for secondary spectrum usage in wireless networks. In this scenario, n communication requests need to be allocated to k available channels that are subject to interference and noise. We present the first truthful mechanisms for secondary spectrum auctions with symmetric or submodular valuations. Our approach to model interference uses an edge-weighted conflict graph, and our algorithms provide asymptotically almost optimal approximation bounds for conflict graphs with a small inductive independence number rho << n. This approach covers a large variety of interference models such as, e.g., the protocol model or the recently popular physical model of interference. For unweighted conflict graphs and symmetric valuations we use LP-rounding to obtain $O(\rho)$-approximate mechanisms; for weighted conflict graphs we get a factor of O(rho (log n + log k)). For submodular users we combine the convex rounding framework of Dughmi et al [STOC 2011] with randomized meta-rounding to obtain O(rho)-approximate mechanisms for matroid-rank-sum valuations; for weighted conflict graphs we can fully drop the dependence on k to get O(rho log n). We conclude with promising initialresults for deterministically truthful mechanisms that allow approximation factors based on rho.

We consider the existence and computational complexity of coalitional stability concepts based on social networks. Our concepts represent a natural and rich combinatorial generalization of a recent approach termed partition equilibrium. We assume that players in a strategic game are embedded in a social network, and there are coordination constraints that restrict the potential coalitions that can jointly deviate in the game to the set of cliques in the social network. In addition, players act in a "considerate" fashion to ignore potentially profitable (group) deviations if the change in their strategy may cause a decrease of utility to their neighbors. We study the properties of such considerate equilibria in application to the class of resource selection games (RSG). Our main result proves existence of a considerate equilibrium in all symmetric RSG with strictly increasing delays, for any social network among the players. The existence proof is constructive and yields an efficient algorithm. In fact, the computed considerate equilibrium is a Nash equilibrium for the standard RSG showing that there exists a state that is stable against selfish and considerate behavior simultaneously. In addition, we show results on convergence of considerate dynamics., Comment: 12 pages, 1 figure

We study combinatorial auctions for the secondary spectrum market. In this market, short-term licenses shall be given to wireless nodes for communication in their local neighborhood. In contrast to the primary market, channels can be assigned to multiple bidders, provided that the corresponding devices are well separated such that the interference is sufficiently low. Interference conflicts are described in terms of a conflict graph in which the nodes represent the bidders and the edges represent conflicts such that the feasible allocations for a channel correspond to the independent sets in the conflict graph. In this paper, we suggest a novel LP formulation for combinatorial auctions with conflict graph using a non-standard graph parameter, the so-called inductive independence number. Taking into account this parameter enables us to bypass the well-known lower bound of \Omega(n^{1-\epsilon}) on the approximability of independent set in general graphs with n nodes (bidders). We achieve significantly better approximation results by showing that interference constraints for wireless networks yield conflict graphs with bounded inductive independence number. Our framework covers various established models of wireless communication, e.g., the protocol or the physical model. For the protocol model, we achieve an O(\sqrt{k})-approximation, where k is the number of available channels. For the more realistic physical model, we achieve an O(\sqrt{k} \log^2 n) approximation based on edge-weighted conflict graphs. Combining our approach with the the LP-based framework of Lavi and Swamy, we obtain incentive compatible mechanisms for general bidders with arbitrary valuations on bundles of channels specified in terms of demand oracles., Comment: 24 pages

We consider network contribution games, where each agent in a social network has a budget of effort that he can contribute to different collaborative projects or relationships. Depending on the contribution of the involved agents a relationship will flourish or drown, and to measure the success we use a reward function for each relationship. Every agent is trying to maximize the reward from all relationships that it is involved in. We consider pairwise equilibria of this game, and characterize the existence, computational complexity, and quality of equilibrium based on the types of reward functions involved. For example, when all reward functions are concave, we prove that the price of anarchy is at most 2. For convex functions the same only holds under some special but very natural conditions. A special focus of the paper are minimum effort games, where the reward of a relationship depends only on the minimum effort of any of the participants. Finally, we show tight bounds for approximate equilibria and convergence of dynamics in these games., Comment: 36 pages, 2 figures

In this paper we consider strategic cost sharing games with so-called arbitrary sharing based on various combinatorial optimization problems, such as vertex and set cover, facility location, and network design problems. We concentrate on the existence and computational complexity of strong equilibria, in which no coalition can improve the cost of each of its members. Our main result reveals a connection between strong equilibrium in strategic games and the core in traditional coalitional cost sharing games studied in economics. For set cover and facility location games this results in a tight characterization of the existence of strong equilibrium using the integrality gap of suitable linear programming formulations. Furthermore, it allows to derive all existing results for strong equilibria in network design cost sharing games with arbitrary sharing via a unified approach. In addition, we are able to show that in general the strong price of anarchy is always 1. This should be contrasted with the price of anarchy of \Theta(n) for Nash equilibria. Finally, we indicate that the LP-approach can also be used to compute near-optimal and near-stable approximate strong equilibria., Comment: 17 pages, 1 figure

Imitating successful behavior is a natural and frequently applied approach to trust in when facing scenarios for which we have little or no experience upon which we can base our decision. In this paper, we consider such behavior in atomic congestion games. We propose to study concurrent imitation dynamics that emerge when each player samples another player and possibly imitates this agents' strategy if the anticipated latency gain is sufficiently large. Our main focus is on convergence properties. Using a potential function argument, we show that our dynamics converge in a monotonic fashion to stable states. In such a state none of the players can improve its latency by imitating somebody else. As our main result, we show rapid convergence to approximate equilibria. At an approximate equilibrium only a small fraction of agents sustains a latency significantly above or below average. In particular, imitation dynamics behave like fully polynomial time approximation schemes (FPTAS). Fixing all other parameters, the convergence time depends only in a logarithmic fashion on the number of agents. Since imitation processes are not innovative they cannot discover unused strategies. Furthermore, strategies may become extinct with non-zero probability. For the case of singleton games, we show that the probability of this event occurring is negligible. Additionally, we prove that the social cost of a stable state reached by our dynamics is not much worse than an optimal state in singleton congestion games with linear latency function. Finally, we discuss how the protocol can be extended such that, in the long run, dynamics converge to a Nash equilibrium., Comment: 28 pages, 1 figure

This paper studies the effects of introducing altruistic agents into atomic congestion games. Altruistic behavior is modeled by a trade-off between selfish and social objectives. In particular, we assume agents optimize a linear combination of personal delay of a strategy and the resulting increase in social cost. Our model can be embedded in the framework of congestion games with player-specific latency functions. Stable states are the Nash equilibria of these games, and we examine their existence and the convergence of sequential best-response dynamics. Previous work shows that for symmetric singleton games with convex delays Nash equilibria are guaranteed to exist. For concave delay functions we observe that there are games without Nash equilibria and provide a polynomial time algorithm to decide existence for symmetric singleton games with arbitrary delay functions. Our algorithm can be extended to compute best and worst Nash equilibria if they exist. For more general congestion games existence becomes NP-hard to decide, even for symmetric network games with quadratic delay functions. Perhaps surprisingly, if all delay functions are linear, then there is always a Nash equilibrium in any congestion game with altruists and any better-response dynamics converges. In addition to these results for uncoordinated dynamics, we consider a scenario in which a central altruistic institution can motivate agents to act altruistically. We provide constructive and hardness results for finding the minimum number of altruists to stabilize an optimal congestion profile and more general mechanisms to incentivize agents to adopt favorable behavior., Comment: 13 pages, 1 figure, includes some minor adjustments

In this paper we extend a popular non-cooperative network creation game (NCG) to allow for disconnected equilibrium networks. There are n players, each is a vertex in a graph, and a strategy is a subset of players to build edges to. For each edge a player must pay a cost \alpha, and the individual cost for a player represents a trade-off between edge costs and shortest path lengths to all other players. We extend the model to a penalized game (PCG), for which we reduce the penalty counted towards the individual cost for a pair of disconnected players to a finite value \beta. Our analysis concentrates on existence, structure, and cost of disconnected Nash and strong equilibria. Although the PCG is not a potential game, pure Nash equilibria always and pure strong equilibria very often exist. We provide tight conditions under which disconnected Nash (strong) equilibria can evolve. Components of these equilibria must be Nash (strong) equilibria of a smaller NCG. However, in contrast to the NCG, for almost all parameter values no tree is a stable component. Finally, we present a detailed characterization of the price of anarchy that reveals cases in which the price of anarchy is \Theta(n) and thus several orders of magnitude larger than in the NCG. Perhaps surprisingly, the strong price of anarchy increases to at most 4. This indicates that global communication and coordination can be extremely valuable to overcome socially inferior topologies in distributed selfish network design., Comment: 18 pages, 4 figures, extended abstract in WINE 2008

We study a multi-player one-round game termed Stackelberg Network Pricing Game, in which a leader can set prices for a subset of $m$ priceable edges in a graph. The other edges have a fixed cost. Based on the leader's decision one or more followers optimize a polynomial-time solvable combinatorial minimization problem and choose a minimum cost solution satisfying their requirements based on the fixed costs and the leader's prices. The leader receives as revenue the total amount of prices paid by the followers for priceable edges in their solutions, and the problem is to find revenue maximizing prices. Our model extends several known pricing problems, including single-minded and unit-demand pricing, as well as Stackelberg pricing for certain follower problems like shortest path or minimum spanning tree. Our first main result is a tight analysis of a single-price algorithm for the single follower game, which provides a $(1+\epsilon) \log m$-approximation for any $\epsilon >0$. This can be extended to provide a $(1+\epsilon)(\log k + \log m)$-approximation for the general problem and $k$ followers. The latter result is essentially best possible, as the problem is shown to be hard to approximate within $\mathcal{O(\log^\epsilon k + \log^\epsilon m)$. If followers have demands, the single-price algorithm provides a $(1+\epsilon)m^2$-approximation, and the problem is hard to approximate within $\mathcal{O(m^\epsilon)$ for some $\epsilon >0$. Our second main result is a polynomial time algorithm for revenue maximization in the special case of Stackelberg bipartite vertex cover, which is based on non-trivial max-flow and LP-duality techniques. Our results can be extended to provide constant-factor approximations for any constant number of followers.