 NSFPAR ID:
 10403794
 Date Published:
 Journal Name:
 Mathematics of Operations Research
 ISSN:
 0364765X
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

Fair division is the problem of allocating a set of items among a set of agents in a fair and efficient way. It arises naturally in a wide range of reallife settings. Competitive equilibrium (CE) is a central solution concept in economics to study markets, and due to its remarkable fairness and efficiency properties (e.g., envyfreeness, proportionality, core stability, Pareto optimality), it is also one of the most preferred mechanisms for fair division even though there is no money involved. The vast majority of work in fair division focuses on the case of disposable goods, which all agents like or can throw away at no cost. In this paper, we consider the case of mixed manna under linear utilities where some items are positive goods liked by all agents, some are bads (chores) that no one likes, and remaining some agents like and others dislike. The recent work of Bogomolnaia et al. [13] initiated the study of CE in mixed manna. They establish that a CE always exists and maintains all the nice properties found in the case of all goods. However, computing a CE of mixed manna is genuinely harder than in the case of all goods due to the nonconvex and disconnected nature of the CE set. Our main result is a polynomialtime algorithm for computing a CE of mixed manna when the number of agents or items is constant.more » « less

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 piecewiselinear and concave (SPLC) utilities and mixed manna. We first derive polynomialtime algorithms for markets with a constant number of items or a constant number of agents. Our main result is a polynomialtime 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 PPADhard even without chores.

This article studies a problem of strategic network inspection, in which a defender (agency) is tasked with detecting the presence of multiple attacks in the network. An inspection strategy entails monitoring the network components, possibly in a randomized manner, using a given number of detectors. We formulate the network inspection problem [Formula: see text] as a largescale bilevel optimization problem, in which the defender seeks to determine an inspection strategy with minimum number of detectors that ensures a target expected detection rate under worstcase attacks. We show that optimal solutions of [Formula: see text] can be obtained from the equilibria of a largescale zerosum game. Our equilibrium analysis involves both gametheoretic and combinatorial arguments and leads to a computationally tractable approach to solve [Formula: see text]. First, we construct an approximate solution by using solutions of minimum set cover (MSC) and maximum set packing (MSP) problems and evaluate its detection performance. In fact, this construction generalizes some of the known results in network security games. Second, we leverage properties of the optimal detection rate to iteratively refine our MSC/MSPbased solution through a column generation procedure. Computational results on benchmark water networks demonstrate the scalability, performance, and operational feasibility of our approach. The results indicate that utilities can achieve a high level of protection in largescale networks by strategically positioning a small number of detectors.more » « less

A central goal in the long literature on fair division is the design of mechanisms that implement fair outcomes, despite the participants’ strategic behavior. We study this question by measuring the fairness of an allocation using the geometric mean of the agents’ values, known as the Nash social welfare (NSW). This objective is maximized by widely known concepts such as the Nash bargaining solution, proportional fairness, and the competitive equilibrium with equal incomes; we focus on (approximately) implementing this objective and analyze the Trading Post mechanism. We consider allocating goods that are substitutes or complements and show that this mechanism achieves an approximation of two for concave utility functions and becomes essentially optimal for complements, where it can reach [Formula: see text] for any [Formula: see text]. Moreover, we show that the Nash equilibria of this mechanism are pure and provide individual fairness in the sense of proportionality.more » « less

null (Ed.)To this day, the maximum clique problem remains a computationally challenging problem. Indeed, despite researchers’ best efforts, there exist unsolved benchmark instances with 1,000 vertices. However, relatively simple algorithms solve reallife instances with millions of vertices in a few seconds. Why is this the case? Why is the problem apparently so easy in many naturally occurring networks? In this paper, we provide an explanation. First, we observe that the graph’s clique number ω is very near to the graph’s degeneracy d in most reallife instances. This observation motivates a main contribution of this paper, which is an algorithm for the maximum clique problem that runs in time polynomial in the size of the graph, but exponential in the gap [Formula: see text] between the clique number ω and its degeneracybased upper bound d+1. When this gap [Formula: see text] can be treated as a constant, as is often the case for reallife graphs, the proposed algorithm runs in time [Formula: see text]. This provides a rigorous explanation for the apparent easiness of these instances despite the intractability of the problem in the worst case. Further, our implementation of the proposed algorithm is actually practical—competitive with the best approaches from the literature.more » « less