1,721,203 research outputs found
Designing and Learning Optimal Finite Support Auctions
No full textA classical paper of Myerson shows how to construct an optimal (revenue-maximizing) auction in a model where bidders' values are drawn from known continuous distributions. In this paper we show how to adapt this approach to finite support distributions. We demonstrate that a Myerson-style auction can be constructed in time polynomial in the number of bidders and the size of the support sets. Also, we consider the scenario where the mechanism designer knows the support sets, but not the probability of each value. In this situation, we show that the optimal auction may be learned in polynomial time using a weak oracle that, given two candidate auctions, returns one with a higher expected revenue. To prove this, we introduce a new class of truthful mechanisms which we call order-based auctions. We show that the optimal mechanism is an order-based auction and use the internal structure of this class to prove the correctness of our learning algorithm as well as to bound its running time
Simple Coalitional Games with Beliefs
No full textWe introduce coalitional games with beliefs (CGBs), a natural generalization of coalitional games to environments where agents possess private beliefs regarding the capabilities (or types) of others. We put forward a model to capture such agent-type uncertainty, and study coalitional stability in this setting. Specifically, we introduce a notion of the core for CGBs, both with and without coalition structures. For simple games without coalition structures, we then provide a characterization of the core that matches the one for the full information case, and use it to derive a polynomial-time algorithm to check core nonemptiness. In contrast, we demonstrate that in games with coalition structures allowing beliefs increases the computational complexity of stability-related problems. In doing so, we introduce and analyze weighted voting games with beliefs, which may be of independent interest. Finally, we discuss connections between our model and other classes of coalitional games
Overlapping Coalition Formation Games: Charting the Tractability Frontier
No full textCooperative games with overlapping coalitions (OCF games) model scenarios where agents can distribute their resources among several tasks; each task generates a profit which may be freely divided among the agents participating in the task. The goal of this work is to initiate a systematic investigation of algorithmic aspects of OCF games. We propose a discretized model of overlapping coalition formation, where each agent i in N has a weight and may allocate an integer amount of resources to any task. Within this framework, we focus on the computation of outcomes that are socially optimal and/or stable. We discover that the algorithmic complexity of the associated problems crucially depends on the amount of resources that each agent possesses, the maximum coalition size, and the pattern of interaction among the agents. We identify several constraints that lead to tractable subclasses of OCF games, and provide efficient algorithms for games that belong to these subclasses. We supplement our tractability results by hardness proofs, which clarify the role of our constraints
Coalition Structures in Weighted Voting Games
No full textWeighted voting games are a popular model of collaboration in multiagent systems. In such games, each agent has a weight (intuitively corresponding to resources he can contribute), and a coalition of agents wins if its total weight meets or exceeds a given threshold. Even though coalitional stability in such games is important, existing research has nonetheless only considered the stability of the grand coalition. In this paper, we introduce a model for weighted voting games with coalition structures. This is a natural extension in the context of multiagent systems, as several groups of agents may be simultaneously at work, each serving a different task. We then proceed to study stability in this context. First, we define the CS-core, a notion of the core for such settings, discuss its non-emptiness, and relate it to the traditional notion of the core in weighted voting games. We then investigate its computational properties. We show that, in contrast with the traditional setting, it is computationally hard to decide whether a game has a non-empty CS-core, or whether a given outcome is in the CS-core. However, we then provide an efficient algorithm that verifies whether an outcome is in the CS-core if all weights are small (polynomially bounded). Finally, we also suggest heuristic algorithms for checking the non-emptiness of the CS-core
True Costs of Cheap Labor Are Hard To Measure: Edge Deletion and VCG Payments in Graphs
No full textWe address the problem of lowering the buyer's expected payments in shortest path auctions, where the buyer's goal is to purchase a path in a graph in which edges are owned by selfish agents. We show that by deleting some of the edges of the graph, one can reduce the total payment of the VCG mechanism by a factor of . However, we prove that it is NP-hard to find the best subset of edges to delete, even if the edge costs are small integers, or the graph has very simple structure; in the former case, this problem is hard to approximate, too. On the positive side, we describe a pseudopolynomial time algorithm for series-parallel graphs and fixed edge costs. Also, we discuss the applicability of this algorithm for the case of general (probabilistic) costs and derive a general lower bound on the performance of algorithms that are based on expected edge costs
Price of pareto optimality in hedonic games
No full textPrice of Anarchy measures the welfare loss caused by selfish behavior: it is defined as the ratio of the social welfare in a socially optimal outcome and in a worst Nash equilibrium. A similar measure can be derived for other classes of stable outcomes. In this paper, we argue that Pareto optimality can be seen as a notion of stability, and introduce the concept of Price of Pareto Optimality: This is an analogue of the Price of Anarchy, where the maximum is computed over the class of Pareto optimal outcomes, i.e., outcomes that do not permit a deviation by the grand coalition that makes all players weakly better off and some players strictly better off. As a case study, we focus on hedonic games, and provide lower and upper bounds of the Price of Pareto Optimality in three classes of hedonic games: Additively separable hedonic games, fractional hedonic games, and modified fractional hedonic games; for fractional hedonic games on trees our bounds are tight
Maximizing Revenue in Sequential Auctions
No full textWe study sequential auctions for private value objects and unit-demand bidders using second-price sealed-bid rules. We analyze this scenario from the seller's perspective and consider several approaches to increasing the total revenue. We derive the equilibrium bidding strategies for each individual auction. We then study the problem of selecting an optimal agenda, i.e., a revenue-maximizing ordering of the auctions. We describe an efficient algorithm that finds an optimal agenda in the important special case when the revenue of each auction is guaranteed to be strictly positive. We also show that the seller can increase his revenue by canceling one or more auctions, even if the number of bidders exceeds the number of objects for sale, and analyze the bidders' behavior and the seller's profit for different cancellation rules
Computational Complexity of Weighted Threshold Games
No full textWeighted threshold games are coalitional games in which each player has a weight (intuitively corresponding to its voting power), and a coalition is successful if the sum of its weights exceeds a given threshold. Key questions in coalitional games include finding coalitions that are stable (in the sense that no member of the coalition has any rational incentive to leave it), and finding a division of payoffs to coalition members (an imputation) that is fair. We investigate the computational complexity of such questions for weighted threshold games. We study the core, the least core, and the nucleolus, distinguishing those problems that are polynomial-time computable from those that are NP-hard, and providing pseudopolynomial and approximation algorithms for the NP-hard problems
Strategic Candidacy Games with Lazy Candidates
No full textIn strategic candidacy games, both voters and candidates have preferences over the set of candidates, and candidates may strategically withdraw from the election in order to manipulate the outcome according to their preferences. In this work, we extend the standard model of strategic candidacy games by observing that candidates may find it costly to run an electoral campaign and may therefore prefer to withdraw if their presence has no effect on the election outcome. We study the Nash equilibria and outcomes of natural best-response dynamics in the resulting class of games, both from a normative and from a computational perspective, and compare them with the Nash equilibria of the standard model
- …
