Auctions via social network, pioneered by Li et al. (2017), have been attracting considerable attention in the literature of mechanism design for auctions. However, no known mechanism has satisfied strategy-proofness, non-deficit, non-wastefulness, and individual rationality for the multi-unit unit-demand auction, except for some naïve ones. In this paper, we first propose a mechanism that satisfies all the above properties. We then make a comprehensive comparison with two naïve mechanisms, showing that the proposed mechanism dominates them in social surplus, seller's revenue, and incentive of buyers for truth-telling. We also analyze the characteristics of the social surplus and the revenue achieved by the proposed mechanism, including the constant approximability of the worst-case efficiency loss and the complexity of optimizing revenue from the seller's perspective.

Abstract We introduce a new type of distributional constraints called ratio constraints, which explicitly specify the required balance among schools in two-sided matching. Since ratio constraints do not belong to the known well-behaved class of constraints called M-convex set, developing a fair and strategyproof mechanism that can handle them is challenging. We develop a novel mechanism called quota reduction deferred acceptance (QRDA), which repeatedly applies the standard DA by sequentially reducing artificially introduced maximum quotas. As well as being fair and strategyproof, QRDA always yields a weakly better matching for students compared to a baseline mechanism called artificial cap deferred acceptance (ACDA), which uses predetermined artificial maximum quotas. Finally, we experimentally show that, in terms of student welfare and nonwastefulness, QRDA outperforms ACDA and another fair and strategyproof mechanism called Extended Seat Deferred Acceptance (ESDA), in which ratio constraints are transformed into minimum and maximum quotas.

We study hedonic games under friends appreciation, where each agent considers other agents friends, enemies, or unknown agents. Although existing work assumed that unknown agents have no impact on an agent’s preference, it may be that her preference depends on the number of unknown agents in her coalition. We extend the existing preference, friends appreciation, by proposing two alternative attitudes toward unknown agents, extraversion and introversion, depending on whether unknown agents have a slightly positive or negative impact on preference. When each agent prefers coalitions with more unknown agents, we show that both core stable outcomes and individually stable outcomes may not exist. We also prove that deciding the existence of the core and the existence of an individual stable coalition structure are respectively NPNP-complete and NP-complete.

In this paper, we study coalition formation in hedonic games through the fairness criterion of envy-freeness. Since the grand coalition is always envy-free, we focus on the conjunction of envy-freeness with stability notions. We first show that, in symmetric and additively separable hedonic games, an individually stable and justified envy-free partition may not exist and deciding its existence is NP-complete. Then, we prove that the top responsiveness property guarantees the existence of a Pareto optimal, individually stable, and envy-free partition, but it is not sufficient for the conjunction of core stability and envy-freeness. Finally, under bottom responsiveness, we show that deciding the existence of an individually stable and envy-free partition is NP-complete, but a Pareto optimal and justified envy-free partition always exists.

In this paper, we identify a new class of distributional constraints defined as a union of symmetric M-convex sets, which can represent a variety of real-life constraints in two-sided matching settings. Since M-convexity is not closed under union, a union of symmetric M-convex sets does not belong to this well-behaved class of constraints in general. Thus, developing a fair and strategyproof mechanism that can handle this class is challenging. We present a novel mechanism called Quota Reduction Deferred Acceptance (QRDA), which repeatedly applies the standard DA mechanism by sequentially reducing artificially introduced maximum quotas. We show that QRDA is fair and strategyproof when handling a union of symmetric M-convex sets. Furthermore, in comparison to a baseline mechanism called Artificial Cap Deferred Acceptance (ACDA), QRDA always obtains a weakly better matching for students and, experimentally, performs better in terms of nonwastefulness.

We investigate hedonic games under enemies aversion and friends appreciation, where every agent considers other agents as either a friend or an enemy. We extend these simple preferences by allowing each agent to also consider other agents to be neutral. Neutrals have no impact on her preference, as in a graphical hedonic game.Surprisingly, we discover that neutral agents do not simplify matters, but cause complexity. We prove that the core can be empty under enemies aversion and the strict core can be empty under friends appreciation. Furthermore, we show that under both preferences, deciding whether the strict core is non-empty, is NP^NP-complete. This complexity extends to the core under enemies aversion. We also show that under friends appreciation, we can always find a core stable coalition structure in polynomial time.