Our study of 20 knowledge workers revealed a common challenge: the difficulty of synthesizing unstructured information scattered across multiple platforms to make informed decisions. Drawing on their vision of an ideal knowledge synthesis tool, we developed Yodeai, an AI-enabled system, to explore both the opportunities and limitations of AI in knowledge work. Through a user study with 16 product managers, we identified three key requirements for Generative AI in knowledge work: adaptable user control, transparent collaboration mechanisms, and the ability to integrate background knowledge with external information. However, we also found significant limitations, including overreliance on AI, user isolation, and contextual factors outside the AI's reach. As AI tools become increasingly prevalent in professional settings, we propose design principles that emphasize adaptability to diverse workflows, accountability in personal and collaborative contexts, and context-aware interoperability to guide the development of human-centered AI systems for product managers and knowledge workers.

We study the absolute and relative structure of Pareto-optimal allocation mechanisms in settings where the planner considers more than one objective criterion. Specifically, we (i) characterize mechanisms that implement the entire Pareto frontier (which cannot be done by maximizing weighted sums of the criteria) and (ii) study how these mechanisms change along the Pareto frontier (comparative statics). To describe the core ideas, we first consider the problem of allocating a scarce public resource: a planner is distributing a fixed supply of a homogenous good among a continuum population of agents. While the individuals' valuations for the good are not known to the planner, their distribution is. The planner takes into account two criteria as objectives: allocative efficiency, defined as the sum of the agents' valuations for owned goods, and social welfare, defined as a (possibly) weighted average of the agents' payoffs. The payoff of an agent is her valuation for the good she is allocated minus the net payment she makes to the planner.

Emerging methods for participatory algorithm design have proposed collecting and aggregating individual stakeholders’ preferences to create algorithmic systems that account for those stakeholders’ values. Drawing on two years of research across two public school districts in the United States, we study how families and school districts use students’ preferences for schools to meet their goals in the context of algorithmic student assignment systems. We find that the design of the preference language, i.e. the structure in which participants must express their needs and goals to the decision-maker, shapes the opportunities for meaningful participation. We define three properties of preference languages – expressiveness, cost, and collectivism – and discuss how these factors shape who is able to participate, and the extent to which they are able to effectively communicate their needs to the decision-maker. Reflecting on these findings, we offer implications and paths forward for researchers and practitioners who are considering applying a preference-based model for participation in algorithmic decision making.

Classical frameworks in mechanism design often specify an objective function and maximize it by choosing allocation. We extend these frameworks by allowing maximizing an objective function (such as expected revenue in an auction) subject to additional constraints (such as lower bounds on efficiency or welfare). The additional complexity arising due to each additional constraint manifests in the reduced form of the optimal mechanism as at most one jump discontinuity in an "ironed" interval. We apply our results to demonstrate the simplicity of optimal mechanisms despite the presence of a side constraint in common economic applications such as contract and auction design. We also introduce a regularity condition under which the general structure of optimal mechanisms bears no additional complexity due to the presence of a side constraint. The analysis builds on the findings of Kleiner et al. (2021) by considering optimal mechanisms as extreme points of function spaces.

We study dynamic nonmonetary markets where objects are allocated to unit-demand agents with private types. An agent's value for an object is supermodular in her type and the quality of the object, and her payoff is quasilinear in her waiting cost. We analyze direct-revelation mechanisms that elicit agents' types and assign them to objects over time. We identify the welfare-maximizing mechanism and show that it can be implemented by a first-come first-served wait-list with deferrals when the marketmaker can design the information disclosed to agents about the objects. The optimal disclosure policy pools adjacent object types.

We study the problem of computing maximin share allocations, a recently introduced fairness notion. Given a set of n agents and a set of goods, the maximin share of an agent is the best she can guarantee to herself, if she is allowed to partition the goods in any way she prefers, into n bundles, and then receive her least desirable bundle. The objective then is to find a partition, where each agent is guaranteed her maximin share. Such allocations do not always exist, hence we resort to approximation algorithms. Our main result is a 2/3-approximation that runs in polynomial time for any number of agents and goods. This improves upon the algorithm of Procaccia and Wang (2014), which is also a 2/3-approximation but runs in polynomial time only for a constant number of agents. To achieve this, we redesign certain parts of the algorithm in Procaccia and Wang (2014), exploiting the construction of carefully selected matchings in a bipartite graph representation of the problem. Furthermore, motivated by the apparent difficulty in establishing lower bounds, we undertake a probabilistic analysis. We prove that in randomly generated instances, maximin share allocations exist with high probability. This can be seen as a justification of previously reported experimental evidence. Finally, we provide further positive results for two special cases arising from previous works. The first is the intriguing case of three agents, where we provide an improved 7/8-approximation. The second case is when all item values belong to {0, 1, 2}, where we obtain an exact algorithm.

Internet display advertising industry follows two main business models. One model is based on direct deals between publishers and advertisers where they sign legal contracts containing terms of fulfillment for a future inventory. The second model is a spot market based on auctioning page views in real-time on advertising exchange (AdX) platforms such as DoubleClick's Ad Exchange, RightMedia, or AppNexus. These exchanges play the role of intermediaries who sell items (e.g. page-views) on behalf of a seller (e.g. a publisher) to buyers (e.g., advertisers) on the opposite side of the market. The computational and economics issues arising in this second model have been extensively investigated in recent times. In this work, we consider a third emerging model called reservation exchange market. A reservation exchange is a two-sided market between buyer orders for blocks of advertisers' impressions and seller orders for blocks of publishers' page views. The goal is to match seller orders to buyer orders while providing the right incentives to both sides. In this work we first describe the important features of mechanisms for efficient reservation exchange markets. We then address the algorithmic problems of designing revenue sharing schemes to provide a fair division between sellers of the revenue collected from buyers. A major conceptual contribution of this work is in showing that even though both clinching ascending auctions and VCG mechanisms achieve the same outcome from a buyer perspective, however, from the perspective of revenue sharing among sellers, clinching ascending auctions are much more informative than VCG auctions.

School districts that adopt the Deferred Acceptance (DA) mechanism to assign students to schools face the tradeoff between fairness and efficiency when selecting how to exogenously break ties among equivalent students. We analyze a model with random generated preferences for students and compare two tie-breaking rules: a single lottery (STB) and DA with a separate lottery for each school (MTB). We consider three different notions for this comparison: stochastic dominance of rank distributions, variance of students' ranks, and number of Pareto improving pairs (pairs of students whom would be better off by swapping their positions).

School choice districts that implement stable matchings face various design issues that impact students' assignments to schools. We study properties of the rank distribution of students with random preferences, when schools use different tiebreaking rules to rank equivalent students. We find that under a multiple tiebreaking rule a vanishing fraction of students match to one of their top choices, in contrast to a single tiebreaking rule under which a constant fraction of students are assigned to one of their top choices. We find that when students can submit only a relatively short preference list, the multiple tiebreaking rule allows a constant fraction of students to match to one of their top choices, with only a "small" fraction of students remaining unmatched.

The inventory routing problem involves trading off inventory holding costs at client locations with vehicle routing costs to deliver frequently from a single central depot to meet deterministic client demands over a finite planing horizon. In this paper, we consider periodic solutions that visit clients in one of several specified frequencies, and focus on the case when the frequencies of visiting nodes are nested. We give the first constant-factor approximation algorithms for designing optimum nested periodic schedules for the problem with no limit on vehicle capacities by simple reductions to prize-collecting network design problems. For instance, we present a 2.55-approximation algorithm for the minimum-cost nested periodic schedule where the vehicle routes are modeled as minimum Steiner trees. We also show a general reduction from the capacitated problem where all vehicles have the same capacity to the uncapacitated version with a slight loss in performance. This reduction gives a 4.55-approximation for the capacitated problem. In addition, we prove several structural results relating the values of optimal policies of various types.

In this paper we consider a mechanism design problem in the context of large-scale crowdsourcing markets such as Amazon's Mechanical Turk mturk, ClickWorker clickworker, CrowdFlower crowdflower. In these markets, there is a requester who wants to hire workers to accomplish some tasks. Each worker is assumed to give some utility to the requester on getting hired. Moreover each worker has a minimum cost that he wants to get paid for getting hired. This minimum cost is assumed to be private information of the workers. The question then is -- if the requester has a limited budget, how to design a direct revelation mechanism that picks the right set of workers to hire in order to maximize the requester's utility? We note that although the previous work (Singer (2010) chen et al. (2011)) has studied this problem, a crucial difference in which we deviate from earlier work is the notion of large-scale markets that we introduce in our model. Without the large market assumption, it is known that no mechanism can achieve a competitive ratio better than 0.414 and 0.5 for deterministic and randomized mechanisms respectively (while the best known deterministic and randomized mechanisms achieve an approximation ratio of 0.292 and 0.33 respectively). In this paper, we design a budget-feasible mechanism for large markets that achieves a competitive ratio of 1 - 1/e ≃ 0.63. Our mechanism can be seen as a generalization of an alternate way to look at the proportional share mechanism, which is used in all the previous works so far on this problem. Interestingly, we can also show that our mechanism is optimal by showing that no truthful mechanism can achieve a factor better than 1 - 1/e, thus, fully resolving this setting. Finally we consider the more general case of submodular utility functions and give new and improved mechanisms for the case when the market is large.

Designing optimal pricing policies and mechanisms for allocating tasks to workers is central to online crowdsourcing markets. In this paper, we consider the following realistic setting of online crowdsourcing markets -- we are given a set of heterogeneous tasks requiring certain skills; each worker has certain expertise and interests which define the set of tasks she is interested in and willing to do. Given this bipartite graph between workers and tasks, we design our mechanism \truthuniform which does the allocation of tasks to workers, while ensuring budget feasibility, incentive-compatibility and achieves near-optimal utility. We further extend our results by exploiting a link with online Adwords allocation problem and present a randomized mechanism \truthfractional with improved approximation guarantees. Apart from strong theoretical guarantees, we carry out extensive experimentation using simulations as well as on a realistic case study of Wikipedia translation project with Mechanical Turk workers. Our results demonstrate the practical applicability of our mechanisms for realistic crowdsourcing markets on the web.