We consider the problem of allocating a set on indivisible items to players with private preferences in an efficient and fair way. focus valuations that have dichotomous marginals, which added value any item is either 0 or 1, aim design truthful allocation mechanisms (without money) maximize welfare are fair. For case submodular we such deterministic mechanism. The output by our mechanism Lorenz dominating, consequently satisfies many desired fairness properties, as being envy-free up (EFX),...

We consider prophet inequalities under general downward-closed constraints. In a inequality problem, decision-maker sees series of online elements with values, and needs to decide immediately irrevocably whether or not select each element upon its arrival, subject an underlying feasibility constraint. Traditionally, the decision-maker’s expected performance has been compared , i.e., offline optimum. refer this measure as Ratio Expectations (or, in short, RoE ). However, major limitation is...

We study the classic single-choice prophet inequality problem through a resource augmentation lens. Our goal is to bound [Formula: see text]-competition complexity of different types online algorithms. This metric asks for smallest k such that expected value algorithm on copies original instance at least text]-approximation off-line optimum single copy. show block threshold algorithms, which set one per copy, are optimal and give tight text]. shows algorithms approach doubly exponentially...

We provide prophet inequality algorithms for online weighted matching in general (non-bipartite) graphs, under two well-studied arrival models, namely edge and vertex arrival. The weight of each is drawn independently from an a-priori known probability distribution. Under arrival, the revealed upon algorithm decides whether to include it or not. weights all edges newly arriving previously arrived vertices are revealed, which these edges, if any, matching. To study settings, we introduce a...

We consider the problem of fair allocation indivisible goods to n agents, with no transfers. When agents have equal entitlements, well established notion maximin share (MMS) serves as an attractive fairness criterion, where qualify fair, needs give every agent at least a substantial fraction her MMS. In this paper we case arbitrary (unequal) entitlements. explain shortcomings in previous attempts that extend MMS unequal Our conceptual contribution is introduction new share, AnyPrice (APS),...

We introduce a new model of combinatorial contracts in which principal delegates the execution costly task to an agent. To complete task, agent can take any subset given set unobservable actions, each has associated cost. The cost actions is sum costs individual and principal's reward as function chosen satisfies some form diminishing returns. incentivizes agents through contract, based on observed outcome. Our main results are for case where delegated project, be successful or not. show...

We provide prophet inequality algorithms for online weighted matching in general (nonbipartite) graphs, under two well-studied arrival models: edge and vertex arrival. The weights of the edges are drawn from a priori known probability distribution. Under arrival, weight each is revealed on algorithm decides whether to include it or not. all newly arriving previously arrived vertices revealed, which these edges, if any, matching. To study settings, we introduce novel unified framework...

Online algorithms for secretary matching in bipartite weighted graphs have been studied extensively recent years. We generalize this study to general graphs, both vertex and edge arrival models.

Pandora’s problem is a fundamental model that studies optimal search under costly inspection. In the classic version, there are n boxes, each associated with known cost and distribution over values. A strategy inspects boxes sequentially obtains utility equals difference between maximum value of an inspected box total inspection cost. Weitzman (1979) presented surprisingly simple expected utility. this work we introduce new variant in which every also publicly deadline, indicating final...

The prophet and secretary problems demonstrate online scenarios involving the optimal stopping theory. In a typical or problem, selection decisions are assumed to be immediate irrevocable. However, many settings accommodate some degree of revocability. To study such scenarios, we introduce l-out-of- k setting, where decision maker can select up elements immediately irrevocably, but her performance is measured by top l in selected set. Equivalently, makes hold at any given point time, make...

The endowment effect, coined by Nobel Laureate Richard Thaler, posits that people tend to inflate the value of items they own. This bias has been traditionally studied mainly using experimental methodology. Recently, Babaioff, Dobzinski and Oren (2018) proposed a specific formulation effect in combinatorial markets, showed existence Walrasian equilibrium with respect endowed valuations (referred as equilibrium) extends from gross substitutes submodular valuations, but provably fails extend...

We study a natural combinatorial single-principal multi-agent contract design problem, in which principal motivates team of agents to exert effort toward given task. At the heart our model is reward function, maps agent efforts an expected principal. seek computationally efficient algorithms for finding optimal (or near-optimal) linear contracts functions that belong complement-free hierarchy.

We study the communication complexity of welfare maximization in combinatorial auctions with m items and two players subadditive valuations. show that outperforming trivial 1/2-approximation requires exponential communication, settling an open problem Dobzinski, Nisan Schapira [STOC'05, MOR'10] Feige [STOC'06, SICOMP '09]. To derive our results, we introduce a new class functions are "far from" fractionally (XOS) functions, establish randomized lower bounds for "near-EQUALITY" problem, both...

We study the power and limitations of posted prices in multi-unit markets, where agents arrive sequentially an arbitrary order. prove upper lower bounds on largest fraction optimal social welfare that can be guaranteed with prices, under a range assumptions about designer's information agents' valuations. Our results provide insights relative uniform non-uniform difficulty different valuation classes, implications informational assumptions. Among other results, we constant-factor guarantees...

We introduce the study of designing allocation mechanisms for fairly allocating indivisible goods in settings with interdependent valuation functions. In our setting, there is a set that needs to be allocated agents (without disposal). Each agent given private signal, and his function depends on signals all agents. Without use payments, are strong impossibility results strategyproof even without values. Therefore, we turn design always admit equilibria fair respect their true signals,...

We study the secretary problem in multi-agent environments. In standard problem, a sequence of arbitrary awards arrive online, random order, and single decision maker makes an immediate irrevocable whether to accept each award upon its arrival. The requirement make decisions arises many cases due implicit assumption regarding competition. Namely, if does not take offered immediately, it will be taken by someone else. introduce novel model, which competition is explicit. our multiple agents...

We study the classic single-choice prophet inequality problem through a resource augmentation lens. Our goal is to bound $(1-\varepsilon)$-competition complexity of different types online algorithms. This metric asks for smallest $k$ such that expected value algorithm on copies original instance, at least $(1-\varepsilon)$-approximation offline optimum single copy. show block threshold algorithms, which set one per copy, are optimal and give tight $k = \Theta(\log \log 1/\varepsilon)$. shows...

In the classical principal-agent hidden-action model, a principal delegates execution of costly task to an agent for which he can choose among actions with different costs and success probabilities accomplish task. To incentivize exert effort, commit contract, is amount payment based on task's success. A crucial assumption this model that only base outcome but not agent's chosen action. work, we relax introduce new where allowed inspect subsets at some cost depends inspected subset. If...