Search

We consider the classical multiwinner election problem where the goal is to choose a subset of k unit-sized candidates (called committee) given utility functions of the voters. We allow arbitrary additional constraints on the chosen committee, and the utilities of voters to belong to a very general class of set functions called β-self bounding. When β = 1, this class includes XOS (and hence, submodular and additive) utilities as special cases. We define a novel generalization of core stability called restrained core to handle constraints on the committee, and consider multiplicative approximations on the utility under this notion. Our main result is the following: If a smooth version of Nash Welfare is globally optimized over committees that respect the constraints, then the resulting optimal committee lies in the eβ-approximate restrained core for β-self bounding utilities and arbitrary constraints. As a result we obtain the first constant approximation for stability with arbitrary additional constraints even for additive utilities (factor of e), as well as the first analysis of the stability of Nash Welfare with XOS functions even in the absence of constraints. We complement this positive result by showing that the c-approximate restrained core can be empty for c < 16/15 even for additive utilities and one additional constraint. Furthermore, the exponential dependence on β in the approximation is unavoidable for β-self bounding functions even in the absence of any constraints. We next present improved and tight approximation results for multiwinner elections with simpler classes of utility functions and simpler types of constraints. We also present an extension of restrained core to extended justified representation with constraints, and show an existence result for the special case of matroid constraints. We finally generalize our results to the setting when candidates have arbitrary sizes (Participatory Budgeting) and there are no additional constraints. Our proof techniques are different from previous analyses of Nash Welfare and are of independent interest. [ABSTRACT FROM AUTHOR]

We study the limits of an information intermediary in the classical Bayesian auction, where a revenue-maximizing seller sells one item to n buyers with independent private values. In addition, we have an intermediary who knows the buyers' private values, and can map these to a public signal so as to increase consumer surplus. This model generalizes the single-buyer setting proposed by Bergemann, Brooks, and Morris, who present a signaling scheme that raises the optimal consumer surplus, by guaranteeing that the item is always sold and the seller gets the same revenue as without signaling. Our work aims to understand how this result ports to the setting with multiple buyers. We likewise define the benchmark for the optimal consumer surplus: one where the auction is efficient (i.e., the item is always sold to the highest-valued buyer) and the revenue of the seller is unchanged. We show that no signaling scheme can guarantee this benchmark even for n=2 buyers with 2-point valuation distributions. Indeed, no signaling scheme can be efficient while preserving any non-trivial fraction of the original consumer surplus, and no signaling scheme can guarantee consumer surplus better than a factor of 1/2 compared to the benchmark. These impossibility results are existential (beyond computational), and provide a sharp separation between the single and multi-buyer settings. In light of this impossibility, we develop signaling schemes with good approximation guarantees to the benchmark. Our main technical result is an O(1)-approximation for i.i.d. regular buyers, via signaling schemes that are conceptually simple and computable in polynomial time. We also present an extension to the case of general independent distributions. [ABSTRACT FROM AUTHOR]

We study the power of price discrimination via an intermediary in bilateral trade, when there is a revenue-maximizing seller selling an item to a buyer with a private value drawn from a prior. Between the seller and the buyer, there is an intermediary that can segment the market by releasing information about the true values to the seller. This is termed signaling, and enables the seller to price discriminate. In this setting, Bergemann et al. showed the existence of a signaling scheme that simultaneously raises the optimal consumer surplus, guarantees the item always sells, and ensures the seller's revenue does not increase. Our work extends the positive result of Bergemann et al. to settings where the type space is larger, and where optimal auction is randomized, possibly over a menu that can be exponentially large. In particular, we consider two settings motivated by budgets: The first is when there is a publicly known budget constraint on the price the seller can charge and the second is the FedEx problem where the buyer has a private deadline or service level (equivalently, a private budget that is guaranteed to never bind). For both settings, we present a novel signaling scheme and its analysis via a continuous construction process that recreates the optimal consumer surplus guarantee of Bergemann et al. and further subsumes their signaling scheme as a special case. In effect, our results show settings where even though the optimal auction is randomized over a possibly large menu, there is a market segmentation such that for each segment, the optimal auction is a simple posted price scheme where the item is always sold. The settings we consider are special cases of the more general problem where the buyer has a private budget constraint in addition to a private value. We finally show that our positive results do not extend to this more general setting, particularly when the budget can bind in the optimal auction, and when the seller's mechanism allows for all-pay auctions. Here, we show that any efficient signaling scheme necessarily transfers almost all the surplus to the seller instead of the buyer. [ABSTRACT FROM AUTHOR]

We consider the algorithmic question of choosing a subset of candidates of a given size k from a set of m candidates, with knowledge of voters' ordinal rankings over all candidates. We consider the well-known and classic scoring rule for achieving diverse representation: the Chamberlin-Courant (CC) or 1-Borda rule, where the score of a committee is the average over the voters, of the rank of the best candidate in the committee for that voter; and its generalization to the average of the top s best candidates, called the s-Borda rule. Our first result is an improved analysis of the natural and well-studied greedy heuristic. We show that greedy achieves a (1 - 2 / k+1 )-approximation to the maximization (or satisfaction) version of CC rule, and a (1 - 2s / k+1 )-approximation to the s-Borda score. This significantly improves the existing submodularity-based analysis of the greedy algorithm that only shows a (1 - 1/e)-approximation. Our result also improves on the best known approximation algorithm for this problem. We achieve this result by showing that the average dissatisfaction score for the greedy algorithm is at most 2m+1/k+1 for the CC rule, and at most 2s2m+1/k+1 for s-Borda. We show these dissatisfaction score bounds are tight up to constants, and even the constant factor of 2 in the case of the CC rule is almost tight. For the dissatisfaction (or minimization) version of the problem, it is known that the average dissatisfaction score of the best committee cannot be approximated in polynomial time to within any constant factor when s is a constant (under standard computational complexity assumptions). As our next result, we strengthen this to show that the score of m+1/k+1 can be viewed as an optimal benchmark for the CC rule, in the sense that it is essentially the best achievable score of any polynomial-time algorithm even when the optimal score is a polynomial factor smaller. We show that another well-studied algorithm for this problem, called the Banzhaf rule, attains this benchmark. We finally show that for the s-Borda rule, when the optimal value is small, these algorithms can be improved by a factor of Ω (√s) via LP rounding. Our upper and lower bounds are a significant improvement over previous results, and taken together, not only enable us to perform a finer comparison of greedy algorithms for these problems, but also provide analytic justification for using such algorithms in practice. [ABSTRACT FROM AUTHOR]

In this paper, we study fairness in committee selection problems. We consider a general notion of fairness via stability: A committee is stable if no coalition of voters can deviate and choose a committee of proportional size, so that all these voters strictly prefer the new committee to the existing one. Our main contribution is to extend this definition to stability of a distribution (or lottery) over committees. We consider two canonical voter preference models: the Approval Set setting where each voter approves a set of candidates and prefers committees with larger intersection with this set; and the Ranking setting where each voter ranks committees based on how much she likes her favorite candidate in a committee. Our main result is to show that stable lotteries always exist for these canonical preference models. Interestingly, given preferences of voters over committees, the procedure for computing an approximately stable lottery is the same for both models and therefore extends to the setting where some voters have the former preference structure and others have the latter. Our existence proof uses the probabilistic method and a new large deviation inequality that may be of independent interest. [ABSTRACT FROM AUTHOR]

In this paper, we study the metric distortion of deterministic social choice rules that choose a winning candidate from a set of candidates based on voter preferences. Voters and candidates are located in an underlying metric space. A voter has cost equal to her distance to the winning candidate. Ordinal social choice rules only have access to the ordinal preferences of the voters that are assumed to be consistent with the metric distances. Our goal is to design an ordinal social choice rule with minimum distortion, which is the worst-case ratio, over all consistent metrics, between the social cost of the rule and that of the optimal omniscient rule with knowledge of the underlying metric space. The distortion of the best deterministic social choice rule was known to be between 3 and 5. It had been conjectured that any rule that only looks at the weighted tournament graph on the candidates cannot have distortion better than 5. In our paper, we disprove it by presenting a weighted tournament rule with distortion of 4.236. We design this rule by generalizing the classic notion of uncovered sets, and further show that this class of rules cannot have distortion better than 4.236. We then propose a new voting rule, via an alternative generalization of uncovered sets. We show that if a candidate satisfying the criterion of this voting rule exists, then choosing such a candidate yields a distortion bound of 3, matching the lower bound. We present a combinatorial conjecture that implies distortion of 3, and verify it for small numbers of candidates and voters by computer experiments. Using our framework, we also show that selecting any candidate guarantees distortion of at most 3 when the weighted tournament graph is cyclically symmetric. [ABSTRACT FROM AUTHOR]

We consider the problem of fairly allocating indivisible public goods. We model the public goods as elements with feasibility constraints on what subsets of elements can be chosen, and assume that agents have additive utilities across elements. Our model generalizes existing frameworks such as fair public decision making and participatory budgeting. We study a groupwise fairness notion called the core, which generalizes well-studied notions of proportionality and Pareto efficiency, and requires that each subset of agents must receive an outcome that is fair relative to its size. In contrast to the case of divisible public goods (where fractional allocations are permitted), the core is not guaranteed to exist when allocating indivisible public goods. Our primary contributions are the notion of an additive approximation to the core (with a tiny multiplicative loss), and polynomial time algorithms that achieve a small additive approximation, where the additive factor is relative to the largest utility of an agent for an element. If the feasibility constraints define a matroid, we show an additive approximation of 2. A similar approach yields a constant additive bound when the feasibility constraints define a matching. For feasibility constraints defining an arbitrary packing polytope with mild restrictions, we show an additive guarantee that is logarithmic in the width of the polytope. Our algorithms are based on the convex program for maximizing the Nash social welfare, but differ significantly from previous work in how it is used. As far as we are aware, our work is the first to approximate the core in indivisible settings. [ABSTRACT FROM AUTHOR]

The article focuses on the use of multiplicative weight update method. Topics discussed include the analysis of optimal Bayesian Incentive Compatible (BIC) auctions, the yield of optimal auctions for different types of auction settings with pseudo-polynomial times, and the implementation of incentive compatibility designed for computational problems.

With the advent of social networks such as Facebook and LinkedIn, and online offers/deals web sites, network externalties raise the possibility of marketing and advertising to users based on influence they derive from their neighbors in such networks. Indeed, a user's knowledge of which of his neighbors "liked" the product, changes his valuation for the product. Much of the work on the mechanism design under network externalities has addressed the setting when there is only one product. We consider a more natural setting when there are multiple competing products, and each node in the network is a unit-demand agent. We first consider the problem of welfare maximization under various different types of externality functions. Specifically we get a O(log n log(nm)) approximation for concave externality functions, a 2O(d)- approximation for convex externality functions that are bounded above by a polynomial of degree d, and we give a O(log3 n)-approximation when the externality function is submodular. Our techniques involve formulating non-trivial linear relaxations in each case, and developing novel rounding schemes that yield bounds vastly superior to those obtainable by directly applying results from combinatorial welfare maximization. We then consider the problem of Nash equilibriumwhere each node in the network is a player whose strategy space corresponds to selecting an item. We develop tight characterization of the conditions under which a Nash equilibrium exists in this game. Lastly, we consider the question of pricing and revenue optimization when the users in the network are selfish agents, and their private information is the vector of valuations for different items. We show that for single parameter settings (when an agents's intrinsic valuation for every item can be described using one parameter), all our approximation results for welfare maximization extend to revenue maximization. For the multi-parameter setting, we design an O(1)-approximate revenue optimal mechanism for IID agents, when the action of a single agent does not affect the externality enjoyed by remaining agents. [ABSTRACT FROM AUTHOR]

We consider the problem of designing auctions in social networks for goods that exhibit single-parameter submodular network externalities in which a bidder's value for an outcome is a fixed private type times a known submodular function of the allocation of his friends. Externalities pose many issues that are hard to address with traditional techniques; our work shows how to resolve these issues in a specific setting of particular interest. We operate in a Bayesian environment and so assume private values are drawn according to known distributions. We prove that the optimal auction is APX-hard. Thus we instead design auctions whose revenue approximates that of the optimal auction. Our main result considers step-function externalities in which a bidder's value for an outcome is either zero, or equal to his private type if at least one friend has the good. For these settings, we provide a e/e+1-approximation. We also give a $0.25$-approximation auction for general single-parameter submodular network externalities, and discuss optimizing over a class of simple pricing strategies. [ABSTRACT FROM AUTHOR]

Modern wireless interfaces support a physical layer capability called Message in Message (MIM). Briefly, MIM allows a receiver to disengage from an ongoing reception, and engage onto a stronger incoming signal. Links that otherwise conflict with each other, can be made concurrent with MIM. However, the concurrency is not immediate, and can be achieved only if conflicting links begin transmission in a specific order. The importance of link order is new in wireless research, motivating MIM-aware revisions to link scheduling protocols. This paper identifies the opportunity in MIM-aware reordering, characterizes the optimal improvement in throughput, and designs a link layer protocol to achieve it. Testbed results confirm the performance gains of the proposed system. [ABSTRACT FROM AUTHOR]

Modern wireless interfaces support a physical layer capability called Message in Message (MIM). Briefly, MIM allows a receiver to disengage from an ongoing reception, and engage onto a stronger incoming signal. Links that otherwise conflict with each other, can be made concurrent with MIM. However, the concurrency is not immediate, and can be achieved only if conflicting links begin transmission in a specific order. The importance of link order is new in wireless research, motivating MIM-aware revisions to link scheduling protocols. This paper identifies the opportunity in MIM-aware reordering, characterizes the optimal improvement in throughput, and designs a link layer protocol to achieve it. Testbed results confirm the performance gains of the proposed system. [ABSTRACT FROM AUTHOR]