BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Jay Sethuraman

Jay Sethuraman appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Computer Science and Game TheoryData Structures and AlgorithmsDiscrete Mathematicsmath.COmath.OCq-fin.ECq-fin.GN

Catalog footprint

What is connected

10works
7topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

10 published item(s)

preprint2020arXiv

A note on the rationing of divisible and indivisible goods in a general network

The study of matching theory has gained importance recently with applications in Kidney Exchange, House Allocation, School Choice etc. The general theme of these problems is to allocate goods in a fair manner amongst participating agents. The agents generally have a unit supply/demand of a good that they want to exchange with other agents. On the other hand, Bochet et al. study a more general version of the problem where they allow for agents to have arbitrary number of divisible goods to be rationed to other agents in the network. In this current work, our main focus is on non-bipartite networks where agents have arbitrary units of a homogeneous indivisible good that they want to exchange with their neighbors. Our aim is to develop mechanisms that would identify a fair and strategyproof allocation for the agents in the network. Thus, we generalize the kidney exchange problem to that of a network with arbitrary capacity of available goods. Our main idea is that this problem and a couple of other related versions of non-bipartite fair allocation problem can be suitably transformed to one of fair allocations on bipartite networks for which we know of well studied fair allocation mechanisms.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On optimal ordering in the optimal stopping problem

In the classical optimal stopping problem, a player is given a sequence of random variables $X_1\ldots X_n$ with known distributions. After observing the realization of $X_i$, the player can either accept the observed reward from $X_i$ and stop, or reject the observed reward from $X_i$ and continue to observe the next variable $X_{i+1}$ in the sequence. Under any fixed ordering of the random variables, an optimal stopping policy, one that maximizes the player's expected reward, is given by the solution of a simple dynamic program. In this paper, we investigate the relatively less studied question of selecting the order in which the random variables should be observed so as to maximize the expected reward at the stopping time. To demonstrate the benefits of order selection, we prove a novel prophet inequality showing that, when the support of each random variable has size at most 2, the optimal ordering can achieve an expected reward that is within a factor of 1.25 of the expected hindsight maximum; this is an improvement over the corresponding factor of 2 for the worst-case ordering. We also provide a simple $O(n^2)$ algorithm for finding an optimal ordering in this case. Perhaps surprisingly, we demonstrate that a slightly more general case - each random variable $X_i$ is restricted to have 3-point support of form $\{0, m_i, 1\}$ - is NP-hard, and provide an FPTAS for that case.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Strategyproof Mechanisms for One-Dimensional Hybrid and Obnoxious Facility Location

We consider a strategic variant of the facility location problem. We would like to locate a facility on a closed interval. There are n agents located on that interval, divided into two types: type 1 agents, who wish for the facility to be as far from them as possible, and type 2 agents, who wish for the facility to be as close to them as possible. Our goal is to maximize a form of aggregated social benefit: maxisum- the sum of the agents' utilities, or the egalitarian objective- the minimal agent utility. The strategic aspect of the problem is that the agents' locations are not known to us, but rather reported to us by the agents- an agent might misreport his location in an attempt to move the facility away from or towards to his true location. We therefore require the facility-locating mechanism to be strategyproof, namely that reporting truthfully is a dominant strategy for each agent. As simply maximizing the social benefit is generally not strategyproof, our goal is to design strategyproof mechanisms with good approximation ratios. For the maxisum objective, in the deterministic setting, we provide a best-possible 3- approximate strategyproof mechanism; in the randomized setting, we provide a 23/13- approximate strategyproof mechanism and a lower bound of \frac{2}{\sqrt{3}}. For the egalitarian objective, we provide a lower bound of 3/2 in the randomized setting, and show that no bounded approximation ratio is attainable in the deterministic setting. To obtain our deterministic lower bounds, we characterize all deterministic strategyproof mechanisms when all agents are of type 1. Finally, we consider a generalized model that allows an agent to control more than one location, and provide best-possible 3- and 3/2- approximate strategyproof mechanisms for maxisum, in the deterministic and randomized settings respectively, when only type 1 agents are present.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A Note on the Assignment Problem with Uniform Preferences

Motivated by a problem of scheduling unit-length jobs with weak preferences over time-slots, the random assignment problem (also called the house allocation problem) is considered on a uniform preference domain. For the subdomain in which preferences are strict except possibly for the class of unacceptable objects, Bogomolnaia and Moulin characterized the probabilistic serial mechanism as the only mechanism satisfying equal treatment of equals, strategyproofness, and ordinal efficiency. The main result in this paper is that the natural extension of the probabilistic serial mechanism to the domain of weak, but uniform, preferences fails strategyproofness, but so does every other mechanism that is ordinally efficient and treats equals equally. If envy-free assignments are required, then any (probabilistic or deterministic) mechanism that guarantees an ex post efficient outcome must fail even a weak form of strategyproofness.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Approximately Optimal Mechanisms for Strategyproof Facility Location: Minimizing $L_p$ Norm of Costs

We consider the problem of locating a single facility on the real line. This facility serves a set of agents, each of whom is located on the line, and incurs a cost equal to his distance from the facility. An agent's location is private information that is known only to him. Agents report their location to a central planner who decides where to locate the facility. The planner's objective is to minimize a "social" cost function that depends on the agent-costs. However, agents might not report truthfully; to address this issue, the planner must restrict himself to {\em strategyproof} mechanisms, in which truthful reporting is a dominant strategy for each agent. A mechanism that simply chooses the optimal solution is generally not strategyproof, and so the planner aspires to use a mechanism that effectively {\em approximates} his objective function. In our paper, we study the problem described above with the social cost function being the $L_p$ norm of the vector of agent-costs. We show that the median mechanism (which is known to be strategyproof) provides a $2^{1-\frac{1}{p}}$ approximation ratio, and that is the optimal approximation ratio among all deterministic strategyproof mechanisms. For randomized mechanisms, we present two results. First, we present a negative result: we show that for integer $\infty>p>2$, no mechanism---from a rather large class of randomized mechanisms--- has an approximation ratio better than that of the median mechanism. This is in contrast to the case of $p=2$ and $p=\infty$ where a randomized mechanism provably helps improve the worst case approximation ratio. Second, for the case of 2 agents, we show that a mechanism called LRM, first designed by Procaccia and Tennenholtz for the special case of $L_{\infty}$, provides the optimal approximation ratio among all randomized mechanisms.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Game Theory, Statistical Mechanics and Income Inequality

The widening inequality in income distribution in recent years, and the associated excessive pay packages of CEOs in the U.S. and elsewhere, is of growing concern among policy makers as well as the common person. However, there seems to be no satisfactory answer, in conventional economic theories and models, to the fundamental question of what kind of pay distribution we ought to see, at least under ideal conditions, in a free market environment and whether this distribution is fair. We propose a game theoretic framework that addresses these questions and show that the lognormal distribution is the fairest inequality of pay in an organization comprising of homogenous agents, achieved at equilibrium, under ideal free market conditions. We also show that for a population of two different classes of agents, the final distribution is a combination of two different lognormal distributions where one of them, corresponding to the top 3-5% of the population, can be misidentified as a Pareto distribution. Our theory also shows the deep and direct connection between potential game theory and statistical mechanics through entropy, which is a measure of fairness in a distribution. This leads us to propose the fair market hypothesis, that the self-organizing dynamics of the ideal free market, i.e., Adam Smith's "invisible hand", not only promotes efficiency but also maximizes fairness under the given constraints.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

The size of the core in assignment markets

Assignment markets involve matching with transfers, as in labor markets and housing markets. We consider a two-sided assignment market with agent types and stochastic structure similar to models used in empirical studies, and characterize the size of the core in such markets. Each agent has a randomly drawn productivity with respect to each type of agent on the other side. The value generated from a match between a pair of agents is the sum of the two productivity terms, each of which depends only on the type but not the identity of one of the agents, and a third deterministic term driven by the pair of types. We allow the number of agents to grow, keeping the number of agent types fixed. Let $n$ be the number of agents and $K$ be the number of types on the side of the market with more types. We find, under reasonable assumptions, that the relative variation in utility per agent over core outcomes is bounded as $O^*(1/n^{1/K})$, where polylogarithmic factors have been suppressed. Further, we show that this bound is tight in worst case. We also provide a tighter bound under more restrictive assumptions. Our results provide partial justification for the typical assumption of a unique core outcome in empirical studies.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Approximation Algorithms for the Incremental Knapsack Problem via Disjunctive Programming

In the incremental knapsack problem ($\IK$), we are given a knapsack whose capacity grows weakly as a function of time. There is a time horizon of $T$ periods and the capacity of the knapsack is $B_t$ in period $t$ for $t = 1, \ldots, T$. We are also given a set $S$ of $N$ items to be placed in the knapsack. Item $i$ has a value of $v_i$ and a weight of $w_i$ that is independent of the time period. At any time period $t$, the sum of the weights of the items in the knapsack cannot exceed the knapsack capacity $B_t$. Moreover, once an item is placed in the knapsack, it cannot be removed from the knapsack at a later time period. We seek to maximize the sum of (discounted) knapsack values over time subject to the capacity constraints. We first give a constant factor approximation algorithm for $\IK$, under mild restrictions on the growth rate of $B_t$ (the constant factor depends on the growth rate). We then give a PTAS for $\IIK$, the special case of $\IK$ with no discounting, when $T = O(\sqrt{\log N})$.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Strategyproof and Consistent Rules for Bipartite Flow Problems

We continue the study of Bochet et al. and Moulin and Sethuraman on fair allocation in bipartite networks. In these models, there is a moneyless market, in which a non-storable, homogeneous commodity is reallocated between agents with single-peaked preferences. Agents are either suppliers or demanders. While the egalitarian rule of Bochet et al. satisfies pareto optimality, no envy and strategyproof, it is not consistent. On the other hand, the work of Moulin and Sethuraman is related to consistent allocations and rules that are extensions of the uniform rule. We bridge the two streams of work by introducing the edge fair mechanism which is both consistent and groupstrategyproof. On the way, we explore the "price of consistency" i.e. how the notion of consistency is fundamentally incompatible with certain notions of fairness like Lorenz Dominance and No-Envy. The current work also introduces the idea of strong invariance as desideratum for groupstrategyproofness and generalizes the proof of Chandramouli and Sethuraman to a more broader class of mechanisms. Finally, we conclude with the study of the edge fair mechanism in a transshipment model where the strategic agents are on the links connecting different supply/demand locations.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Groupstrategyproofness of the Egalitarian Mechanism for Constrained Rationing Problems

The key contribution of the paper is a comprehensive study of the egalitarian mechanism with respect to manipulation by a coalition of agents. Our main result is that the egalitarian mechanism is, in fact, peak group strategyproof : no coalition of agents can (weakly) benefit from jointly misreporting their peaks. Furthermore, we show that the egalitarian mechanism cannot be manipulated by any coalition of suppliers (or any coalition of demanders) in the model where both the suppliers and demanders are agents. Our proofs shed light on the structure of the two models and simpify some of the earlier proofs of strategyproofness in the earlier papers. An implication of our results is that the well known algorithm of Megiddo to compute a lexicographically optimal flow in a network is group strategyproof with respect to the source capacities (or sink capacities).

0 citations0 reviewsNo code linkedOpen access