Search

We explore solutions for fairly allocating indivisible items among agents assigned weights representing their entitlements. Our fairness goal is weighted-envy-freeness (WEF), where each agent deems their allocated portion relative to their entitlement at least as favorable as any other's relative to their own. In many cases, achieving WEF necessitates monetary transfers, which can be modeled as third-party subsidies. The goal is to attain WEF with bounded subsidies. Previous work in the unweighted setting of subsidies relied on basic characterizations of EF that fail in the weighted settings. This makes our new setting challenging and theoretically intriguing. We present polynomial-time algorithms that compute WEF-able allocations with an upper bound on the subsidy per agent in three distinct additive valuation scenarios: (1) general, (2) identical, and (3) binary. When all weights are equal, our bounds reduce to the bounds derived in the literature for the unweighted setting., Comment: 45 pages, 1 table

We study the effects of campaigning, where the society is partitioned into voter clusters and a diffusion process propagates opinions in a network connecting the clusters. Our model is very powerful and can incorporate many campaigning actions, various partitions of the society into clusters, and very general diffusion processes. Perhaps surprisingly, we show that computing the cheapest campaign for rigging a given election can usually be done efficiently, even with arbitrarily-many voters. Moreover, we report on certain computational simulations.

In two-sided markets, Myerson and Satterthwaite's impossibility theorem states that one can not maximize the gain-from-trade while also satisfying truthfulness, individual-rationality and no deficit. Attempts have been made to circumvent Myerson and Satterthwaite's result by attaining approximately-maximum gain-from-trade: the double-sided auctions of McAfee (1992) is truthful and has no deficit, and the one by Segal-Halevi et al. (2016) additionally has no surplus --- it is strongly-budget-balanced. They consider two categories of agents --- buyers and sellers, where each trade set is composed of a single buyer and a single seller. The practical complexity of applications such as supply chain require one to look beyond two-sided markets. Common requirements are for: buyers trading with multiple sellers of different or identical items, buyers trading with sellers through transporters and mediators, and sellers trading with multiple buyers. We attempt to address these settings. We generalize Segal-Halevi et al. (2016)'s strongly-budget-balanced double-sided auction setting to a multilateral market where each trade set is composed of any number of agent categories. Our generalization refines the notion of competition in multi-sided auctions by introducing the concepts of external competition and trade reduction. We also show an obviously-truthful implementation of our auction using multiple ascending prices., Comment: Preliminary version accepted to AAAI 2020. This version adds (1) External competition auction for arbitrary recipe vectors; (2) Obvious-truthfulness proof; (3) Simulation experiments

The study of mechanisms for multi-sided markets has received an increasingly growing attention from the research community, and is motivated by the numerous examples of such markets on the web and in electronic commerce. Many of these examples represent dynamic and uncertain environments, and thus, require, in fact, online mechanisms. Unfortunately, as far as we know, no previously published online mechanism for a multi-sided market (or even for a double-sided market) has managed to (approximately) maximize the gain from trade, while guaranteeing desirable economic properties such as incentivizing truthfulness, voluntary participation and avoiding budget deficit. In this work we present the first online mechanism for a multi-sided market which has the above properties. Our mechanism is designed for a market setting suggested by [Feldman and Gonen (2016)]; which is motivated by the foreseeable future form of online advertising. The online nature of our setting motivated us to define a stronger notion of individual rationality, called "continuous individual rationality", capturing the natural requirement that a player should never lose either by participating in the mechanism or by not leaving prematurely. Satisfying the requirements of continuous individual rationality, together with the other economic properties our mechanism guarantees, requires the mechanism to use a novel pricing scheme where users may be paid ongoing increments during the mechanism's execution up to a pre-known maximum value. As users rarely ever get paid in reality, this pricing scheme is new to mechanism design. Nevertheless, the principle it is based on can be observed in many common real life scenarios such as executive compensation payments and company acquisition deals. We believe both our new dynamic pricing scheme concept and our strengthened notion of individual rationality are of independent interest., Comment: 21 pages. This paper studies an online extension of a model suggested by arXiv:1603.08717. For completeness, we repeat some of the proofs of arXiv:1603.08717

We consider mechanisms for markets that are double-sided and have players with multi-dimensional strategic spaces on at least one side. The players of the market are strategic, and act to optimize their own utilities. The mechanism designer, on the other hand, aims to optimize a social goal, i.e., the gain from trade. We focus on one example of this setting which is motivated by the foreseeable future form of online advertising. Online advertising currently supports some of the most important Internet services, including: search, social media and user generated content sites. To overcome privacy concerns, it has been suggested to introduce user information markets through information brokers into the online advertising ecosystem. Such markets give users control over which data get shared in the online advertising exchange. We describe a model for the above foreseeable future form of online advertising, and design two mechanisms for the exchange of this model: a deterministic mechanism which is related to the vast literature on mechanism design through trade reduction and allows players with a multi-dimensional strategic space, and a randomized mechanism which can handle a more general version of the model., Comment: 27 pages

Finding optimal solutions for multi-unit combinatorial auctions is a hard problem and finding approximations to the optimal solution is also hard. We investigate the use of Branch-and-Bound techniques: they require both a way to bound from above the value of the best allocation and a good criterion to decide which bids are to be tried first. Different methods for efficiently bounding from above the value of the best allocation are considered. Theoretical original results characterize the best approximation ratio and the ordering criterion that provides it. We suggest to use this criterion., Comment: Presented at EC'00

Previous works suggested the use of Branch and Bound techniques for finding the optimal allocation in (multi-unit) combinatorial auctions. They remarked that Linear Programming could provide a good upper-bound to the optimal allocation, but they went on using lighter and less tight upper-bound heuristics, on the ground that LP was too time-consuming to be used repetitively to solve large combinatorial auctions. We present the results of extensive experiments solving large (multi-unit) combinatorial auctions generated according to distributions proposed by different researchers. Our surprising conclusion is that Linear Programming is worth using. Investing almost all of one's computing time in using LP to bound from above the value of the optimal solution in order to prune aggressively pays off. We present a way to save on the number of calls to the LP routine and experimental results comparing different heuristics for choosing the bid to be considered next. Those results show that the ordering based on the square root of the size of the bids that was shown to be theoretically optimal in a previous paper by the authors performs surprisingly better than others in practice. Choosing to deal first with the bid with largest coefficient (typically 1) in the optimal solution of the relaxed LP problem, is also a good choice. The gap between the lower bound provided by greedy heuristics and the upper bound provided by LP is typically small and pruning is therefore extensive. For most distributions, auctions of a few hundred goods among a few thousand bids can be solved in practice. All experiments were run on a PC under Matlab.