Understanding the formation and evolution of opinions is of broad interdisciplinary interest. Many classical models for opinion formation focus on the impact of different notions of locality , e.g., locality due to network effects among agents or the role of the proximity of opinions. In practice, however, opinion formation is often governed by the interplay of local and global influences. In this paper, we study these influences with a model for opinion formation of agents embedded in a social network. Each agent has a static intrinsic opinion as well as a public opinion that is updated asynchronously over time. Moreover, agents have access to a global aggregate (e.g., the outcome of a vote) of all public opinions. We focus on the popular median voting rule and show that pure Nash equilibria always exist. For every initial state of the dynamics, a pure equilibrium can be reached. The set of reachable equilibria forms a complete lattice, and extremal equilibria can be computed in polynomial time. We show that by uniformly increasing the influence of the global median we can enforce that the median opinion is the same in every reachable equilibrium. We can compute the increase scheme that achieves this property in polynomial time. In contrast, when we can increase the influence of the global median for a set of at most k agents, finding the set that leads to a unique median opinion in every reachable equilibrium is NP -complete.

A principal delegates a project to a team S from a pool of n agents. The project's value if all agents in S exert costly effort is f(S). To incentivize the agents to participate, the principal assigns each agent i ∈ S a share ρi ∈ [0,1] of the project's final value (i.e., designs n linear contracts). The shares must be feasible—their sum should not exceed 1. It is well-understood how to design these contracts to maximize the principal's own expected utility, but what if the goal is to coordinate the agents toward maximizing social welfare?

We study a natural application of contract design in the context of sequential exploration problems. In our principal-agent setting, a 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 is to maximize her expected reward, i.e., value minus payment. Interestingly, this natural contract scenario shares close relations with the Pandora’s Box problem. We show how to compute optimal contracts for the principal in several scenarios. A popular and important subclass is that of linear contracts, and we show how to compute optimal linear contracts in polynomial time. For general contracts, we obtain optimal contracts under the standard assumption that the agent suffers cost but obtains value only from the transfers by the principal. 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.

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.

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 Θ(1/n)-approximation and extend this result to ratios of Θ(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 three parameters. If the ratio of maximum and minimum utility for A is bounded by a factor α, we obtain an Ω(log⁡log⁡α/log⁡α)-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/α cannot be avoided. If there are at most β different utility values for A, we show a Θ(1/β)-approximation. If the utilities of P and A for each option are related by a factor γ, we obtain an Ω(1/log⁡γ)-approximation, where O(log⁡log⁡γ/log⁡γ) is best possible.

Abstract Opinion spreading in a society decides the fate of elections, the success of products, and the impact of political or social movements. A prominent model to study opinion formation processes is due to Hegselmann and Krause. It has the distinguishing feature that stable states do not necessarily show consensus, i.e., the population of agents might not agree on the same opinion. We focus on the social variant of the Hegselmann–Krause model. There arenagents, which are connected by a social network. Their opinions evolve in an iterative, asynchronous process, in which agents are activated one after another at random. When activated, an agent adopts the average of the opinions of its neighbors having a similar opinion (where similarity of opinions is defined using a parameter $$\varepsilon $$ ε ). Thus, the set of influencing neighbors of an agent may change over time. We show that such opinion dynamics are guaranteed to converge for any social network. We provide an upper bound of $${\text {O}}(n|E|^2 (\varepsilon /\delta )^2)$$ O(n|E|2(ε/δ)2) on the expected number of opinion updates until convergence to a stable state, where $$|E|$$ |E| is the number of edges of the social network, and $$\delta $$ δ is a parameter of the stability concept. For the complete social network we show a bound of $${\text {O}}(n^3(n^2 + (\varepsilon /\delta )^2))$$ O(n3(n2+(ε/δ)2)) that represents a major improvement over the previously best upper bound of $${\text {O}}(n^9 (\varepsilon /\delta )^2)$$ O(n9(ε/δ)2) .

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)). 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.

Abstract. We consider a selection problem with stochastic probing. There is a set of items whose values are drawn from independent distributions. The distributions are known in advance. Each item can be tested repeatedly. Each test reduces the uncertainty about the realization of its value. We study a testing model, where the first test reveals whether the realized value is smaller or larger than the [Formula: see text]-quantile of the underlying distribution of some constant [Formula: see text]. Subsequent tests allow us to further narrow down the interval in which the realization is located. There is a limited number of possible tests, and our goal is to design near-optimal testing strategies that allow us to maximize the expected value of the chosen item. We study both identical and nonidentical distributions and develop polynomial-time algorithms with constant approximation factors in both scenarios.

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 ≥ 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 → ∞. 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 → ∞. 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).

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. In this paper, we study a natural online variant of delegation, in which the agent searches through the options in an online fashion. How can we design algorithms for P that approximate the utility of her best option in hindsight? We show that P can obtain a Θ(1/n)-approximation and provide more 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 α, we obtain an Ω(log log α / log α)-approximation algorithm and show that this is best possible. If P cannot distinguish options with the same value for herself, we show that ratios polynomial in 1/α cannot be avoided. If the utilities of P and A for each option are related by a factor β, we obtain an Ω(1 / log β)-approximation, and O(log log β / log β) is best possible.

We study markets with mixed manna, where m divisible goods and chores shall be divided among n agents to obtain a competitive equilibrium. Equilibrium allocations are known to satisfy many fairness and efficiency conditions. While a lot of recent work in fair division is restricted to linear utilities and chores, we focus on a substantial generalization to separable piecewise-linear and concave (SPLC) utilities and mixed manna. We first derive polynomial-time algorithms for markets with a constant number of items or a constant number of agents. Our main result is a polynomial-time algorithm for instances with a constant number of chores (as well as any number of goods and agents) under the condition that chores dominate the utility of the agents. Interestingly, this stands in contrast to the case when the goods dominate the agents utility in equilibrium, where the problem is known to be PPAD-hard even without chores.

We consider the problem of maximizing the Nash social welfare when allocating a set G of indivisible goods to a set N of agents. We study instances, in which all agents have 2-value additive valuations: The value of every agent for every good is either p or q, where p and q are integers and p2. 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 APX-hard, with a lower bound of 1.000015 achieved at p/q = 4/5.

It is a well-known fact that selfish behavior degrades the performance of traffic networks. Various measures have been proposed in the literature as a remedy for the inefficiency of traffic equilibria (such as road tolls or network design techniques). However, it often seems impractical and/or politically undesirable that these measures get implemented to a substantial extent.

We study the fair and efficient allocation of a set of indivisible goods among agents, where each good has several copies, and each agent has an additively separable concave valuation function with a threshold. These valuations capture the property of diminishing marginal returns, and they are more general than the well-studied case of additive valuations. We present a polynomial-time algorithm that approximates the optimal Nash social welfare (NSW) up to a factor of e1/e ≈ 1.445. This matches with the state-of-the-art approximation factor for additive valuations. The computed allocation also satisfies the popular fairness guarantee of envy-freeness up to one good (EF1) up to a factor of 2 + ε. For instances without thresholds, it is also approximately Pareto-optimal. For instances satisfying a large market property, we show an improved approximation factor. Lastly, we show that the upper bounds on the optimal NSW introduced in Cole and Gkatzelis (2018) and Barman et al. (2018) have the same value.

No abstract available.

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.

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.

Abstract 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 determine 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. For the online bipartite matching problem, we obtain an algorithm with ratio at least 0.5721 − o(1), and an algorithm with ratio at least 0.5459 for all n ≥ 1. We extend all algorithms and ratios to k ≥ 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. We focus on minimizing the expected number of postponements when computing an optimal solution. An expected number of Θ(n log n) is always sufficient. For bipartite matching, we can show a tight bound of O(r log n), where r is the size of the optimum matching. For matroids, we can improve this further to a tight bound of O(r′ log(n/r′)), where r′ is the minimum rank of the matroid and the dual matroid.

We study an information-structure design problem (i.e., a Bayesian persuasion problem) in an online scenario. Inspired by the classic gambler's problem, consider a set of candidates who arrive sequentially and are evaluated by one agent (the sender). This agent learns the value from hiring the candidate to herself as well as the value to another agent, the receiver. The sender provides a signal to the receiver who, in turn, makes an irrevocable decision on whether or not to hire the candidate. A-priori, for each agent the distribution of valuation is independent across candidates but may not be identical. We design good online signaling schemes for the sender. To assess the performance, we compare the expected utility to that of an optimal offline scheme by a prophet sender who knows all candidate realizations in advance. We show an optimal prophet inequality for online Bayesian persuasion, with a 1/2-approximation when the instance satisfies a "satisfactory-status-quo" assumption. Without this assumption, there are instances without any finite approximation factor. We extend the results to combinatorial domains and obtain prophet inequalities for matching with multiple hires and multiple receivers.

In their seminal work on systemic risk in financial markets, Eisenberg and Noe [Larry Eisenberg and Thomas Noe, 2001] proposed and studied a model with n firms embedded into a network of debt relations. We analyze this model from a game-theoretic point of view. Every firm is a rational agent in a directed graph that has an incentive to allocate payments in order to clear as much of its debt as possible. Each edge is weighted and describes a liability between the firms. We consider several variants of the game that differ in the permissible payment strategies. We study the existence and computational complexity of pure Nash and strong equilibria, and we provide bounds on the (strong) prices of anarchy and stability for a natural notion of social welfare. Our results highlight the power of financial regulation - if payments of insolvent firms can be centrally assigned, a socially optimal strong equilibrium can be found in polynomial time. In contrast, worst-case strong equilibria can be a factor of Ω(n) away from optimal, and, in general, computing a best response is an NP-hard problem. For less permissible sets of strategies, we show that pure equilibria might not exist, and deciding their existence as well as computing them if they exist constitute NP-hard problems.

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.

We design a simple ascending-price algorithm to compute a (1 + ε)-approximate equilibrium in Arrow-Debreu markets with weak gross substitute property. It applies to an unknown market setting without exact knowledge about the number of agents, their individual utilities, and endowments. Instead, our algorithm only uses price queries to a global demand oracle. This is the first polynomial-time algorithm for most of the known tractable classes of Arrow-Debreu markets, which computes such an equilibrium with a number of calls to the demand oracle that is polynomial in log 1/ε and avoids heavy machinery such as the ellipsoid method. Demands can be real-valued functions of prices, but the oracles only return demand values of bounded precision. 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, we give the first polynomial-time algorithm to compute an exact equilibrium for markets with spending constraint utilities. This resolves an open problem posed by Duan and Mehlhorn.

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}} ~~ 1.445. The computed allocation is Pareto-optimal and approximates envy-freeness up to one item up to a factor of 2 + epsilon.

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 >= 1. We extend all algorithms and ratios to k >= 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 <=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).

We present the first constant-factor approximation algorithm for maximizing the Nash social welfare when allocating indivisible items to agents with budget-additive valuation functions. Budget-additive valuations represent an important class of submodular functions. They have attracted a lot of research interest in recent years due to many interesting applications. For every ε > 0, our algorithm obtains a (2.404 + ε)-approximation in time polynomial in the input size and 1/ε. Our algorithm relies on rounding an approximate equilibrium in a linear Fisher market where sellers have earning limits (upper bounds on the amount of money they want to earn) and buyers have utility limits (upper bounds on the amount of utility they want to achieve). In contrast to markets with either earning or utility limits, these markets have not been studied before. They turn out to have fundamentally different properties. Although the existence of equilibria is not guaranteed, we show that the market instances arising from the Nash social welfare problem always have an equilibrium. Further, we show that the set of equilibria is not convex, answering a question of [17]. We design an FPTAS to compute an approximate equilibrium, a result that may be of independent interest.

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.

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.

We study efficient algorithms for a natural learning problem in markets. There is one seller with m divisible goods and n buyers with unknown individual utility functions and budgets of money. The seller can repeatedly announce prices and observe aggregate demand bundles requested by the buyers. The goal of the seller is to learn the utility functions and budgets of the buyers. Our scenario falls into the classic domain of ''revealed preference'' analysis. Problems with revealed preference have recently started to attract increased interest in computer science due to their fundamental nature in understanding customer behavior in electronic markets. The goal of revealed preference analysis is to observe rational agent behavior, to explain it using a suitable model for the utility functions, and to predict future agent behavior. Our results are the first polynomial-time algorithms to learn utility and budget parameters via revealed preference queries in classic Fisher markets with multiple buyers. Our analysis concentrates on linear, CES, and Leontief markets, which are the most prominent classes studied in the literature. Some of our results extend to general Arrow-Debreu exchange markets.

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 this positive result with a number of hardness results for related computational questions. We prove that it isNP-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.

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 an 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.

We consider capacity maximization in wireless networks under adversarial interference conditions. There are n links, i.e., sender-receiver pairs, 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-δ)-fraction of time steps in a time window unsuccessful. For this scenario, we analyze a framework for distributed no-regret learning algorithms to get provable approximation guarantees. We obtain an O(1/δ)-approximation for the problem of maximizing the number of successful transmissions. Our approach provides even a constant-factor approximation when the jammer exactly blocks a (1-δ)-fraction of time steps. In addition, we consider the parameters of the jammer being partially unknown to the algorithm, and we also consider a stochastic jammer, for which we obtain a constant-factor approximation after a polynomial number of time steps. We extend our results to 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.

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.

Coalition formation is a fundamental problem in the organization of many multi-agent systems. In large populations, the formation of coalitions is often restricted by structural visibility and locality constraints under which agents can reorganize. We capture and study this aspect using a novel network-based model for dynamic locality within the popular framework of hedonic coalition formation games. We analyze the effects of network-based visibility and structure on the convergence of coalition formation processes to stable states. Our main result is a tight characterization of the structures based on which dynamic coalition formation can stabilize quickly. Maybe surprisingly, polynomial-time convergence can be achieved if and only if coalition formation is based on complete or star graphs.

One of the most powerful algorithmic techniques for truthful mechanism design are maximal-in-distributional-range (MIDR) mechanisms. Unfortunately, many algorithms using this paradigm rely on heavy algorithmic machinery and require the ellipsoid method or (approximate) solution of convex programs. In this paper, we present a simple and natural correlated rounding technique for designing mechanisms that are truthful in expectation. Our technique is elementary and can be implemented quickly. The main property we rely on is that the domain offers fractional optimum solutions with a tree structure. In auctions based on the generalized assignment problem, each bidder has a publicly known knapsack constraint that captures the subsets of items that are of value to him. He has a private valuation for each item and strives to maximize the value of assigned items minus payment. For this domain we design a mechanism for social welfare maximization. Our technique gives a truthful 2-approximate MIDR mechanism without using the ellipsoid method or convex programming. In contrast to some previous work, our mechanism achieves exact truthfulness.

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 $$\varDelta $$ . We design algorithms and truthful mechanisms for social welfare maximization that attain approximation ratios depending on $$\varDelta $$ . 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 \varDelta )$$ -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}((\varDelta \log \log \varDelta )/\log \varDelta )$$ . The ratios are almost optimal given existing hardness results. For 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(\varDelta )$$ when the number of items is only logarithmic in the number of bidders.

We study approximation algorithms for optimization of wireless spectrum access with n communication requests when interference conditions are given by the Rayleigh-fading model. This model extends the deterministic interference model based on the signal-to-interference-plus-noise ratio (SINR) using stochastic propagation to address fading effects observed in reality. We consider worst-case approximation guarantees for the two standard problems of capacity maximization and latency minimization. Our main result is a generic reduction of Rayleigh fading to the deterministic non-fading model. It allows to apply existing algorithms for the non-fading model in the Rayleigh-fading scenario while losing only a factor of O(log* n) in the approximation guarantee. This way, we obtain the first approximation guarantees for Rayleigh fading and, more fundamentally, show that non-trivial stochastic fading effects can be successfully handled using existing and future techniques for the non-fading model. We generalize these results in two ways. First, the same results apply for capacity maximization with variable data rates, when links obtain (non-binary) utility depending on the achieved SINR. Second, for binary utilities, we use a more detailed argument to obtain similar results even for distributed and game-theoretic approaches. Our analytical treatment is supported by simulations illustrating the performance of regret learning and, more generally, the relationship between both models.

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 study distributed load balancing in networks with selfish agents. In the simplest model considered here, there are n identical machines represented by vertices in a network and m > n selfish agents that unilaterally decide to move from one vertex to another if this improves their experienced load. We present several protocols for concurrent migration that satisfy desirable properties such as being based only on local information and computation and the absence of global coordination or cooperation of agents. Our main contribution is to show rapid convergence of the resulting migration process to states that satisfy different stability or balance criteria. In particular, the convergence time to a Nash equilibrium is only logarithmic in m and polynomial in n , where the polynomial depends on the graph structure. In addition, we show reduced convergence times to approximate Nash equilibria. Finally, we extend our results to networks of machines with different speeds or to agents that have different weights and show similar results for convergence to approximate and exact Nash equilibria.

We study combinatorial auctions for secondary spectrum markets, where short-term communication licenses are sold to wireless nodes. Channels can be assigned to multiple bidders according to interference constraints captured by a conflict graph. We suggest a novel approach to such combinatorial auctions using a graph parameter called inductive independence number. We achieve good approximation results by showing that interference constraints for wireless networks imply a bounded inductive independence number. For example, in the physical model the factor becomes O (√ k log 2 n ) for n bidders and k channels. Our algorithms can be turned into incentive-compatible mechanisms for bidders with arbitrary valuations.

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.

We consider truthfulness concepts for auctions with payments based on first- and second-order stochastic dominance. We assume bidders consider wealth in standard quasi-linear form as valuation minus payments. Additionally, they are sensitive to risk in the distribution of wealth stemming from randomized mechanisms. First- and second-order stochastic dominance are well-known to capture risk-sensitivity, and we apply these concepts to capture truth-telling incentives for bidders.

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 simple algorithmic technique that allows to turn existing and future approximation algorithms and heuristics into truthful mechanisms for a large variety of networking problems. Our approach works with 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.

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 ρ << 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(ρ)-approximate mechanisms; for weighted conflict graphs we get a factor of O(ρ ρ (log n + log k)). For submodular users we combine the convex rounding framework of [Dughmi et al. 2011] with randomized meta-rounding to obtain O(ρ)-approximate mechanisms for matroid-rank-sum valuations; for weighted conflict graphs we can fully drop the dependence on k to get O(ρ ρ log n). We conclude with promising initial results for deterministically truthful mechanisms that allow approximation factors based on ρ.

We study algorithms for wireless spectrum access of $n$ communication requests when interference conditions are given by the Rayleigh-fading model. This model extends the recently popular deterministic interference model based on the signal-to-interference-plus-noise ratio (SINR) using stochastic propagation to address fading effects observed in reality. We consider worst-case approximation guarantees for the two standard problems of capacity maximization (maximize the expected number of successful transmissions in a single slot) and latency minimization (minimize the expected number of slots until all transmissions were successful). Our main result is a generic reduction of Rayleigh fading to the deterministic SINR model. It allows to apply existing algorithms for the non-fading model in the Rayleigh-fading scenario while losing only a factor of O(logast n) in the approximation guarantee. This way, we obtain the first approximation guarantees for Rayleigh fading and, more fundamentally, show that non-trivial stochastic fading effects can be successfully handled using existing and future techniques for the non-fading model. Using a more detailed argument, a similar result applies even for distributed and game-theoretic capacity maximization approaches. For example, it allows to show that regret learning yields an O(log* n)-approximation with uniform power assignments. Our analytical treatment is supported by simulations illustrating the performance of regret learning and, more generally, the relationship between both models.

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. 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+ε)log m-approximation. This can be extended to provide a (1+ε)(log k+log m)-approximation for the general problem and k followers. The problem is also shown to be hard to approximate within $\mathcal{O}(\log^{\varepsilon}k + \log^{\varepsilon}m)$ for some ε>0. If followers have demands, the single-price algorithm provides an $\mathcal{O}(m^{2})$ -approximation, and the problem is hard to approximate within $\mathcal{O}(m^{\epsilon})$ for some ε>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. This approach can be extended to provide constant-factor approximations for any constant number of followers.

We study convergence of distributed protocols for power control in a non-cooperative wireless transmission scenario. There are n wireless communication requests or links that experience interference and noise. To be successful a link must satisfy an SINR constraint. Each link is a rational selfish agent that strives to be successful with the least power that is required. A classic approach to this problem is the fixed-point iteration due to Foschini and Miljanic , for which we prove the first bounds on worst-case convergence times - after roughly O(n \log n) rounds all SINR constraints are nearly satisfied. When agents try to satisfy each constraint exactly, however, links might not be successful at all. For this case, we design a novel framework for power control using regret learning algorithms and iterative discretization. While the exact convergence times must rely on a variety of parameters, we show that roughly a polynomial number of rounds suffices to make every link successful during at least a constant fraction of all previous rounds.

Abstract In Stackelberg pricing a leader sets prices for items to maximize revenue from a follower purchasing a feasible subset of items. We consider computationally bounded followers who cannot optimize exactly over the range of all feasible subsets, but who apply publicly known algorithms to determine the items to purchase. This corresponds to general multidimensional pricing when customers cannot optimize their valuation functions efficiently but still aim to act rationally to the best of their ability. We consider two versions of this novel type of pricing problem. In the MIn‐KNAPSACK variant items are weighted objects and the follower seeks to purchase a min‐cost selection of objects of some bounded weight. When he uses a greedy 2‐approximation algorithm, we provide a polynomial‐time (2+ε) ‐approximation algorithm for the leader's revenue maximization problem based on so‐called near‐uniform price assignments. We also prove the problem to be strongly NP‐hard. In the SET‐COVER variant items are subsets of some ground set which the follower seeks to cover. When he uses a standard primal‐dual approach, we prove that exact revenue maximization is possible in polynomial time when elements have frequency 2 (VERTEX‐COVER variant). This stands in sharp contrast to APX‐hardness for the problem with elements of frequency 3. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012

We study 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 notion termed partition equilibrium [5]. We assume that players in a strategic game are embedded in a social (or, communication) network, and there are coordination constraints defining the set of coalitions that can jointly deviate in the game. A main feature of our approach is that players act in a fashion to ignore potentially profitable (group) deviations if the change in their strategy may cause a decrease of utility to their neighbors in the network. We explore the properties of such considerate equilibria in application to the celebrated class of resource selection games (RSGs). Our main result proves existence of a super-strong considerate equilibrium in all symmetric RSGs with strictly increasing delays, for any social network among the players and feasible coalitions represented by the set of cliques. The existence proof is constructive and yields an efficient algorithm. In fact, the computed considerate equilibrium is a Nash equilibrium for a standard RSG, thus showing that there exists a state that is stable against selfish and considerate behavior simultaneously. Furthermore, we provide results on convergence of considerate dynamics.

We study distributed load balancing in networks with selfish agents. In the simplest model considered here, there are n identical machines represented by vertices in a network and m ≫ n selfish agents that unilaterally decide to move from one vetex to another if this improves their experienced load. We present several protocols for concurrent migration that satisfy desirable properties such as being based only on local information and computation and the absence of global coordination or cooperation of agents. Our main contribution is to show rapid convergence of the resulting migration process to states that satisfy different stability or balance criteria. In particular, the convergence time to a Nash equilibrium is only logarithmic in m and polynomial in n, where the polynomial depends on the graph structure. Using a slight modification with neutral moves, a perfectly balanced state can be reached after additional time polynomial in n. In addition, we show reduced convergence times to approximate Nash equilibria. Finally, we extend our results to networks of machines with different speeds or to agents that have different weights and show similar results for convergence to approximate and exact Nash equilibria.

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 study a dynamic version of capacity maximization is the physical model of wireless communication. In our model, requests for connections between pairs of points in Euclidean space of constant dimension d arrive iteratively over time. When a new request arrives, an online algorithm needs to decide whether or not to accept the request and to assign one out of k channels and a transmission power to the channel. Accepted requests must satisfy constraints on the signal-to-interference-plus-noise (SINR) ratio. The objective is to maximize the number of accepted requests.

Imitating successful behavior is a natural and frequently applied approach 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 these dynamics converge in a monotonic fashion to stable states. In such a state none of the players can improve their latency by imitating others.

We consider a dynamic load balancing scenario in which users allocate resources in a non-cooperative and selfish fashion. The perceived performance of a resource for a user decreases with the number of users that allocate the resource. In our dynamic, concurrent model, users may reallocate resources in a round-based fashion. As opposed to various settings analyzed in the literature, we assume that users have quality of service (QoS) demands. A user has zero utility when falling short of a certain minimum performance threshold and having positive utility otherwise.

Modularity is a recently introduced quality measure for graph clusterings. It has immediately received considerable attention in several disciplines, particularly in the complex systems literature, although its properties are not well understood. We study the problem of finding clusterings with maximum modularity, thus providing theoretical foundations for past and present work based on this measure. More precisely, we prove the conjectured hardness of maximizing modularity both in the general case and with the restriction to cuts and give an Integer Linear Programming formulation. This is complemented by first insights into the behavior and performance of the commonly applied greedy agglomerative approach.

We propose a visualization approach for dynamic affiliation networks in which events are characterized by a set of descriptors. It uses a radial ripple metaphor to display the passing of time and conveys relations among the different constituents through appropriate layout. Our method is particularly suitable when assuming an egocentric perspective, and we illustrate it on movie-actor biographies.

Summary form only given. We propose architecture and a general optimization framework for dynamic, distributed real-time systems. Interesting features of this model include the consideration of adaptive applications and utility functions. We extend by formalizing the corresponding multicriterial optimization problem. As the most difficult part of this problem, we identified the evaluation and comparison of the quality of single allocations and sets of allocations, respectively. To this end, we propose and examine metrics for measuring the goodness of solutions within our general resource management framework. These metrics lay the basis for further work on developing both online and offline algorithms to tackle the general optimization problem and provide an efficient adaptive resource manager for dynamic, distributed real-time systems.