We study the problem of allocating items to agents with submodular valuations with the goal of maximizing the weighted Nash social welfare (NSW). The best-known results for unweighted and weighted objectives are the (4+є) approximation given by Garg, Husic, Li, Végh, and Vondrák [STOC 2023] and the (233+є) approximation given by Feng, Hu, Li, and Zhang [STOC 2025], respectively.

The predominant setting in classic auction theory considers bidders as utility maximizers (UMs), who aim to maximize quasi-linear utility functions. Recent autobidding strategies in online advertising have sparked interest in auction design with value maximizers (VMs), who aim to maximize the total value obtained. In this work, we investigate revenue-maximizing auction design for selling a single item to a mix of UMs and VMs. Crucially, we assume the UM/VM type is private information of a bidder. This shift to a multi-parameter domain complicates the design of incentive compatible mechanisms. Under this setting, we first characterize the optimal auction structure for auctions with a single bidder. We observe that the optimal auction moves gradually from a first-price auction to a Myerson auction as the probability of the bidder being a UM increases from 0 to 1. We also extend our study to multi-bidder setting and present an algorithm for deriving the optimal lookahead auction with multiple mixed types of bidders.

Abstract. We consider the classical cake cutting problem where we wish to fairly divide a heterogeneous resource among interested agents. Work on this subject typically assumes that the cake is represented by an interval. We introduce a generalized setting where the cake is represented by an arbitrary undirected graph, which allows us to model the division of road networks. Unlike in the interval setting, common fairness criteria such as proportionality cannot always be satisfied in graphical cake cutting if each agent must receive a connected subgraph. We determine the optimal approximation of proportionality that can be obtained for any number of agents with additive valuations, and exhibit a tight guarantee for each graph in the case of two agents. We also study several variants and extensions, including when more than one connected piece per agent is allowed as well as when the item to be divided is undesirable.

We consider a voting scenario in which the resource to be voted upon may consist of both indivisible and divisible goods. This generalizes both the well-studied model of multiwinner voting and the recently introduced model of cake sharing. Under approval votes, we propose two variants of the extended justified representation (EJR) notion from multiwinner voting, a stronger one called EJR for mixed goods (EJR-M) and a weaker one called EJR up to 1 (EJR-1). We extend three multiwinner voting rules to our setting—GreedyEJR, the method of equal shares (MES), and proportional approval voting (PAV)—and show that while all three generalizations satisfy EJR-1, only the first one provides EJR-M. In addition, we derive tight bounds on the proportionality degree implied by EJR-M and EJR-1, and investigate the proportionality degree of our proposed rules.

Motivated by practical concerns in the online advertising industry, we study a bidder subset selection problem in single-item auctions. In this problem, a large pool of candidate bidders have independent values sampled from known prior distributions. The seller needs to pick a subset of bidders and run a given auction format on the selected subset to maximize her expected revenue. We propose two frameworks for the subset restrictions: (i) capacity constraint on the set of selected bidders; and (ii) incurred costs for the bidders invited to the auction. For the second-price auction with anonymous reserve (SPA-AR), we give constant approximation polynomial time algorithms in both frameworks (in the latter framework under mild assumptions about the market). Our results are in stark contrast to the previous work of Mehta, Nadav, Psomas, Rubinstein [NeurIPS 2020], who showed hardness of approximation for the SPA without a reserve price. We also give complimentary approximation results for other well-studied auction formats such as anonymous posted pricing and sequential posted pricing. On a technical level, we find that the revenue of SPA-AR as a set function f(S) of its bidders S is fractionally-subadditive but not submodular. Our bidder selection problem with invitation costs is a natural question about (approximately) answering a demand oracle for f(·) under a given vector of costs, a common computational assumption in the literature on combinatorial auctions. * This work is supported by Science and Technology Innovation 2030 –“New Generation of Artificial Intelligence” Major Project No.(2018AAA0100903), Innovation Program of Shanghai Municipal Education Commission, Program for Innovative Research Team of Shanghai University of Finance and Economics (IRTSHUFE) and the Fundamental Research Funds for the Central Universities. Zhihao Gavin Tang is supported by NSFC grant 61902233. Nick Gravin is supported by NSFC grant 62150610500.

The classic cake cutting problem concerns the fair allocation of a heterogeneous resource among interested agents. In this paper, we study a public goods variant of the problem, where instead of competing with one another for the cake, the agents all share the same subset of the cake which must be chosen subject to a length constraint. We focus on the design of truthful and fair mechanisms in the presence of strategic agents who have piecewise uniform utilities over the cake. On the one hand, we show that the leximin solution is truthful and moreover maximizes an egalitarian welfare measure among all truthful and position oblivious mechanisms. On the other hand, we demonstrate that the maximum Nash welfare solution is truthful for two agents but not in general. Our results assume that mechanisms can block each agent from accessing parts that the agent does not claim to desire; we provide an impossibility result when blocking is not allowed.

The classic secretary problem concerns the problem of an employer facing a random sequence of candidates and making online hiring decisions to try to hire the best candidate. In this paper, we study a game-theoretic generalization of the secretary problem where a set of employers compete with each other to hire the best candidate. Different from previous secretary market models, our model assumes that the sequence of candidates arriving at each employer is uniformly random but independent from other sequences. We consider two versions of this secretary game where employers can have adaptive or non-adaptive strategies, and provide characterizations of the best response and Nash equilibrium of each game.

Online on-demand ridesourcing service has played a huge role in transforming urban transportation. A central function in most on-demand ridesourcing platforms is to dynamically assign drivers to rider requests that could balance the request waiting times and the driver pick-up distances. To deal with the online nature of this problem, existing literature either divides the time horizon into short windows and applies a static offline assignment algorithm within each window or assumes a fully online setting that makes decisions for each request immediately upon its arrival. In this paper, we propose a more realistic model for the driver-request assignment that bridges the above two settings together. Our model allows the requests to wait after their arrival but assumes that they may leave at any time following a quitting function. Under this model, we design an efficient algorithm for assigning available drivers to requests in real-time. Our algorithm is able to incorporate future estimated driver arrivals into consideration and make strategic waiting and matching decisions that could balance the waiting time and pick-up distance of the assignment. We prove that our algorithm is optimal ex-ante in the single-request setting, and demonstrate its effectiveness in the general multi-request setting through experiments on both synthetic and real-world datasets.

We study a fair resource allocation problem with indivisible items. The agents’ preferences over items are assumed to be ordinal and have uncertainties. We adopt stochastic dominance proportionality as our fairness notion and study a sequence of problems related to finding allocations that are fair with a high probability. We provide complexity analysis for each problem and efficient algorithms for some problems. Finally, we propose several heuristic algorithms to find an allocation that is fair with the highest probability. We thoroughly evaluate the performance of the algorithms on both synthetic and real datasets.

We study the allocation of indivisible goods that form an undirected graph and quantify the loss of fairness when we impose a constraint that each agent must receive a connected subgraph. Our focus is on well-studied fairness notions including envy-freeness and maximin share fairness. We introduce the price of connectivity to capture the largest multiplicative gap between the graph-specific and the unconstrained maximin share and derive bounds on this quantity which are tight for large classes of graphs in the case of two agents and for paths and stars in the general case. For instance, with two agents we show that for biconnected graphs it is possible to obtain at least 3/4 of the maximin share with connected allocations, while for the remaining graphs the guarantee is at most 1/2. In addition, we determine the optimal relaxation of envy-freeness that can be obtained with each graph for two agents and characterize the set of trees and complete bipartite graphs that always admit an allocation satisfying envy-freeness up to one good (EF1) for three agents. Our work demonstrates several applications of graph-theoretic tools and concepts to fair division problems.

We study the allocation of indivisible goods that form an undirected graph and quantify the loss of fairness when we impose a constraint that each agent must receive a connected subgraph. Our focus is on the well-studied fairness notion of maximin share fairness. We introduce the price of connectivity to capture the largest gap between the graph-specific and the unconstrained maximin share, and derive bounds on this quantity which are tight for large classes of graphs in the case of two agents and for paths and stars in the general case. For instance, with two agents we show that for biconnected graphs it is possible to obtain at least 3/4 of the maximin share with connected allocations, while for the remaining graphs the guarantee is at most 1/2. Our work demonstrates several applications of graph-theoretic tools and concepts to fair division problems.

We study fair resource allocation when the resources contain a mixture of divisible and indivisible goods, focusing on the well-studied fairness notion of maximin share fairness (MMS). With only indivisible goods, a full MMS allocation may not exist, but a constant multiplicative approximate allocation always does. We analyze how the MMS approximation guarantee would be affected when the resources to be allocated also contain divisible goods. In particular, we show that the worst-case MMS approximation guarantee with mixed goods is no worse than that with only indivisible goods. However, there exist problem instances to which adding some divisible resources would strictly decrease the MMS approximation ratios of the instances. On the algorithmic front, we propose a constructive algorithm that will always produce an \alpha-MMS allocation for any number of agents, where \alpha takes values between 1/2 and 1 and is a monotonically increasing function determined by how agents value the divisible goods relative to their MMS values.

We consider the classical cake-cutting problem where we wish to fairly divide a heterogeneous resource, often modeled as a cake, among interested agents. Work on the subject typically assumes that the cake is represented by an interval. In this paper, we introduce a generalized setting where the cake can be in the form of the set of edges of an undirected graph, allowing us to model the division of road networks. Unlike in the canonical setting, common fairness criteria such as proportionality cannot always be satisfied in our setting if each agent must receive a connected subgraph. We determine the optimal approximation of proportionality that can be obtained for any number of agents with arbitrary valuations, and exhibit a tight guarantee for each graph in the case of two agents. In addition, when more than one connected piece per agent is allowed, we establish the best egalitarian welfare guarantee for each total number of connected pieces. We also study a number of variants and extensions, including when approximate equitability is considered, or when the item to be divided is undesirable (also known as chore division).

In single-item auction design, it is well known due to Cremer and McLean that when bidders’ valuations are drawn from a correlated prior distribution, the auctioneer can extract full social surplus as revenue. However, in most real-world applications, the prior is usually unknown and can only be learned from historical data. In this work, we investigate the robustness of the optimal auction with correlated valuations via sample complexity analysis. We prove upper and lower bounds on the number of samples from the unknown prior required to learn a (1-epsilon)-approximately optimal auction. Our results reinforce the common belief that optimal correlated auctions are sensitive to the distribution parameters and hard to learn unless the prior distribution is well-behaved.

Peer review systems such as conference paper review often suffer from the issue of miscalibration. Previous works on peer review calibration usually only use the ordinal information or assume simplistic reviewer scoring functions such as linear functions. In practice, applications like academic conferences often rely on manual methods, such as open discussions, to mitigate miscalibration. It remains an important question to develop algorithms that can handle different types of miscalibrations based on available prior knowledge. In this paper, we propose a flexible framework, namely \emph{least square calibration} (LSC), for selecting top candidates from peer ratings. Our framework provably performs perfect calibration from noiseless linear scoring functions under mild assumptions, yet also provides competitive calibration results when the scoring function is from broader classes beyond linear functions and with arbitrary noise. On our synthetic dataset, we empirically demonstrate that our algorithm consistently outperforms the baseline which select top papers based on the highest average ratings.

In the 1970s, Lovász built a bridge between graphs and alternating matrix spaces, in the context of perfect matchings [ Proceedings of FCT, 1979, pp. 565--574]. A similar connection between bipartite graphs and matrix spaces plays a key role in the recent resolutions of the noncommutative rank problem [A. Garg et al., Proceedings of FOCS, 2016, pp. 109--117; G. Ivanyos, Y. Qiao, and K. V. Subrahmanyam, Comput. Complexity, 26 (2017), pp. 717--763]. In this paper, we lay the foundation for another bridge between graphs and alternating matrix spaces, in the context of independent sets and vertex colorings. The corresponding structures in alternating matrix spaces are isotropic spaces and isotropic decompositions, both useful structures in group theory and manifold theory. We first show that the maximum independent set problem and the vertex $c$-coloring problem reduce to the maximum isotropic space problem and the isotropic $c$-decomposition problem, respectively. Next, we show that several topics and results about independent sets and vertex colorings have natural correspondences for isotropic spaces and decompositions. These include algorithmic problems, such as the maximum independent set problem for bipartite graphs, and exact exponential-time algorithms for the chromatic number, as well as mathematical questions, such as the number of maximal independent sets, and the relation between the maximum degree and the chromatic number. These connections lead to new interactions between graph theory and algebra. Some results have concrete applications to group theory and manifold theory, and we initiate a variant of these structures in the context of quantum information theory. Finally, we propose several open questions for further exploration.

We study the problem of fair division when the resources contain both divisible and indivisible goods. Classic fairness notions such as envy-freeness (EF) and envy-freeness up to one good (EF1) cannot be directly applied to the mixed goods setting. In this work, we propose a new fairness notion envy-freeness for mixed goods (EFM), which is a direct generalization of both EF and EF1 to the mixed goods setting. We prove that an EFM allocation always exists for any number of agents. We also propose efficient algorithms to compute an EFM allocation for two agents and for n agents with piecewise linear valuations over the divisible goods. Finally, we relax the envy-free requirement, instead asking for ϵ-envy-freeness for mixed goods (ϵ-EFM), and present an algorithm that finds an ϵ-EFM allocation in time polynomial in the number of agents, the number of indivisible goods, and 1/ϵ.

In the 1970’s, Lovász built a bridge between graphs and alternating matrix spaces, in the context of perfect matchings (FCT 1979). A similar connection between bipartite graphs and matrix spaces plays a key role in the recent resolutions of the non-commutative rank problem (Garg-Gurvits-Oliveira-Wigderson, FOCS 2016; Ivanyos-Qiao-Subrahmanyam, ITCS 2017). In this paper, we lay the foundation for another bridge between graphs and alternating matrix spaces, in the context of independent sets and vertex colorings. The corresponding structures in alternating matrix spaces are isotropic spaces and isotropic decompositions, both useful structures in group theory and manifold theory. We first show that the maximum independent set problem and the vertex c-coloring problem reduce to the maximum isotropic space problem and the isotropic c-decomposition problem, respectively. Next, we show that several topics and results about independent sets and vertex colorings have natural correspondences for isotropic spaces and decompositions. These include algorithmic problems, such as the maximum independent set problem for bipartite graphs, and exact exponential-time algorithms for the chromatic number, as well as mathematical questions, such as the number of maximal independent sets, and the relation between the maximum degree and the chromatic number. These connections lead to new interactions between graph theory and algebra. Some results have concrete applications to group theory and manifold theory, and we initiate a variant of these structures in the context of quantum information theory. Finally, we propose several open questions for further exploration. (Dedicated to the memory of Ker-I Ko)

The classical cake cutting problem studies how to find fair allocations of a heterogeneous and divisible resource among multiple agents. Two of the most commonly studied fairness concepts in cake cutting are proportionality and envy-freeness. It is well known that a proportional allocation among n agents can be found efficiently via simple protocols [16]. For envy-freeness, in a recent breakthrough, Aziz and Mackenzie [5] proposed a discrete and bounded envy-free protocol for any number of players. However, the protocol suffers from high multiple-exponential query complexity and it remains open to find simpler and more efficient envy-free protocols. In this paper we consider a variation of the cake cutting problem by assuming an underlying graph over the agents whose edges describe their acquaintance relationships, and agents evaluate their shares relatively to those of their neighbors. An allocation is called locally proportional if each agent thinks she receives at least the average value over her neighbors. Local proportionality generalizes proportionality and is in an interesting middle ground between proportionality and envy-freeness: its existence is guaranteed by that of an envy-free allocation, but no simple protocol is known to produce such a locally proportional allocation for general graphs. Previous works showed locally proportional protocols for special classes of graphs, and it is listed in both [1] and [8] as an open question to design simple locally proportional protocols for more general classes of graphs. In this paper we completely resolved this open question by presenting a discrete and bounded locally proportional protocol for any given graph. Our protocol has a query complexity of only single exponential, which is significantly smaller than the six towers of n query complexity of the envy-free protocol given in [5].

We investigate the efficiency of fair allocations of indivisible goods using the well-studied price of fairness concept. Previous work has focused on classical fairness notions such as envy-freeness, proportionality, and equitability. However, these notions cannot always be satisfied for indivisible goods, leading to certain instances being ignored in the analysis. In this paper, we focus instead on notions with guaranteed existence, including envy-freeness up to one good (EF1), balancedness, maximum Nash welfare (MNW), and leximin. We mostly provide tight or asymptotically tight bounds on the worst-case efficiency loss for allocations satisfying these notions.

We investigate the problem of assigning trip requests to available vehicles in on-demand ridesourcing. Much of the literature has focused on maximizing the total value of served requests, achieving efficiency on the passengers’ side. However, such solutions may result in some drivers being assigned to insufficient or undesired trips, therefore losing fairness from the drivers’ perspective. In this paper, we focus on both the system efficiency and the fairness among drivers and quantitatively analyze the trade-offs between these two objectives. In particular, we give an explicit answer to the question of whether there always exists an assignment that achieves any target efficiency and fairness. We also propose a simple reassignment algorithm that can achieve any selected trade-off. Finally, we demonstrate the effectiveness of the algorithms through extensive experiments on real-world datasets.

We investigate the problem of revenue maximization in single-item auction within the new correlation-robust framework proposed by Carroll [2017] and further developed by Gravin and Lu [2018]. In this framework the auctioneer is assumed to have only partial information about marginal distributions, but does not know the dependency structure of the joint distribution. The auctioneer's revenue is evaluated in the worst-case over the uncertainty of possible joint distribution. For the problem of optimal auction design in the correlation robust-framework we observe that in most cases the optimal auction does not admit a simple form like the celebrated Myerson's auction for independent valuations. We analyze and compare performances of several DSIC mechanisms used in practice. Our main set of results concern the sequential posted-price mechanism (SPM). We show that SPM achieves a constant (4.78) approximation to the optimal correlation-robust mechanism. We also show that in the symmetric (anonymous) case when all bidders have the same marginal distribution, (i) SPM has almost matching worst-correlation revenue as any second price auction with common reserve price, and (ii) when the number of bidders is large, SPM converges to optimum. In addition, we extend some results on approximation and computational tractability for lookahead auctions to the correlation-robust framework.

We design a simple ascending-price algorithm to compute a (1 + ε)-approximate equilibrium in Arrow-Debreu markets with weak gross substitute property. It applies to an unknown market setting without exact knowledge about the number of agents, their individual utilities, and endowments. Instead, our algorithm only uses price queries to a global demand oracle. This is the first polynomial-time algorithm for most of the known tractable classes of Arrow-Debreu markets, which computes such an equilibrium with a number of calls to the demand oracle that is polynomial in log 1/ε and avoids heavy machinery such as the ellipsoid method. Demands can be real-valued functions of prices, but the oracles only return demand values of bounded precision. Due to this more realistic assumption, precision and representation of prices and demands become a major technical challenge, and we develop new tools and insights that may be of independent interest. Furthermore, we give the first polynomial-time algorithm to compute an exact equilibrium for markets with spending constraint utilities. This resolves an open problem posed by Duan and Mehlhorn.

We investigate the ride-sharing assignment problem from an algorithmic resource allocation point of view. Given a number of requests with source and destination locations, and a number of available car locations, the task is to assign cars to requests with two requests sharing one car. We formulate this as a combinatorial optimization problem, and show that it is NP-hard. We then design an approximation algorithm which guarantees to output a solution with at most 2.5 times the optimal cost. Experiments are conducted showing that our algorithm actually has a much better approximation ratio (around 1.2) on synthetically generated data.

We study the problem of fairly dividing a heterogeneous resource, commonly known as cake cutting and chore division, in the presence of strategic agents. While a number of results in this setting have been established in previous works, they rely crucially on the free disposal assumption, meaning that the mechanism is allowed to throw away part of the resource at no cost. In the present work, we remove this assumption and focus on mechanisms that always allocate the entire resource. We exhibit a truthful envy-free mechanism for cake cutting and chore division for two agents with piecewise uniform valuations, and we complement our result by showing that such a mechanism does not exist when certain additional assumptions are made. Moreover, we give truthful mechanisms for multiple agents with restricted classes of valuations.

We study envy-free cake cutting with strategic agents, where each agent may manipulate his private information in order to receive a better allocation. We focus on piecewise constant utility functions and consider two scenarios: the general setting without any restriction on the allocations and the restricted setting where each agent has to receive a connected piece. We show that no deterministic truthful envy-free mechanism exists in the connected piece scenario, and the same impossibility result for the general setting with some additional mild assumptions on the allocations. Finally, we study a large market model where the economy is replicated and demonstrate that truth-telling converges to a Nash equilibrium.

We introduce a graphical framework for fair division in cake cutting, where comparisons between agents are limited by an underlying network structure. We generalize the classical fairness notions of envy-freeness and proportionality in this graphical setting. An allocation is called envy-free on a graph if no agent envies any of her neighbor's share, and is called proportional on a graph if every agent values her own share no less than the average among her neighbors, with respect to her own measure. These generalizations enable new research directions in developing simple and efficient algorithms that can produce fair allocations under specific graph structures. On the algorithmic frontier, we first propose a moving-knife algorithm that outputs an envy-free allocation on trees. The algorithm is significantly simpler than the discrete and bounded envy-free algorithm introduced in [Aziz and Mackenzie, 2016] for compete graphs. Next, we give a discrete and bounded algorithm for computing a proportional allocation on transitive closure of trees, a class of graphs by taking a rooted tree and connecting all its ancestor-descendant pairs.

We study the online allocation problem under a roommate market model introduced in [Chan et al., 2016]. Consider a fixed supply of n rooms and a list of 2n applicants arriving sequentially in an online fashion. The problem is to assign a room to each person upon her arrival, such that after the algorithm terminates, each room is shared by exactly two people. We focus on two objectives: (1) maximizing the social welfare, which is defined as the sum of valuations that applicants have for their rooms, plus the happiness value between each pair of roommates; (2) the allocation should satisfy certain stability conditions, such that no group of people would be willing to switch roommates or rooms. We first show a polynomial-time online algorithm that achieves constant competitive ratio for social welfare maximization. We then extend it to the case where each room is assigned to c > 2 people, and achieve a competitive ratio of Ω(1/c^2). Finally, we show both positive and negative results in satisfying different stability conditions in this online setting.

Budget feasible mechanism design is the study of procurement combinatorial auctions in which the sellers have private costs to produce items, and the buyer (auctioneer) aims to maximize her valuation function on a subset of purchased items under the budget constraint on the total payment. One of the most important questions in the field is “which valuation domains admit truthful budget feasible mechanisms with `small' approximations to the social optimum?” Singer [ Proceedings of the 51st FOCS, IEEE Press, Piscataway, NJ, 2010, pp. 765--774] showed that submodular functions have a constant approximation mechanism. Dobzinski, Papadimitriou, and Singer [ Proceedings of the 12 th ACM Conference on Electronic Commerce, ACM, New York, 2011, pp. 273--282] gave an $O(\log^2n)$ approximation mechanism for subadditive functions and remarked that “A fundamental question is whether, regardless of computational constraints, a constant-factor budget feasible mechanism exists for subadditive functions.” In this paper, we give an affirmative answer to this question. To this end we relax the prior-free mechanism design framework to the Bayesian mechanism design framework (these are two standard approaches from computer science and economics, respectively). Then we convert our results in the Bayesian setting back to the prior-free framework by employing Yao's minimax principle. Along the way, we obtain the following results: (i) a polynomial time constant approximation for XOS valuations (a.k.a. fractionally subadditive valuations, a superset of submodular functions), (ii) a polynomial time $O(\log n / \log \log n)$-approximation for general subadditive valuations, (iii) a constant approximation for general subadditive functions in the Bayesian framework---we allow correlation in the distribution of sellers' costs and provide a universally truthful mechanism, (iv) the existence of a prior-free constant approximation mechanism via Yao's minimax principle.

We study efficient algorithms for a natural learning problem in markets. There is one seller with m divisible goods and n buyers with unknown individual utility functions and budgets of money. The seller can repeatedly announce prices and observe aggregate demand bundles requested by the buyers. The goal of the seller is to learn the utility functions and budgets of the buyers. Our scenario falls into the classic domain of ''revealed preference'' analysis. Problems with revealed preference have recently started to attract increased interest in computer science due to their fundamental nature in understanding customer behavior in electronic markets. The goal of revealed preference analysis is to observe rational agent behavior, to explain it using a suitable model for the utility functions, and to predict future agent behavior. Our results are the first polynomial-time algorithms to learn utility and budget parameters via revealed preference queries in classic Fisher markets with multiple buyers. Our analysis concentrates on linear, CES, and Leontief markets, which are the most prominent classes studied in the literature. Some of our results extend to general Arrow-Debreu exchange markets.

We present the first analysis of Fisher markets with buyers that have budget-additive utility functions. Budget-additive utilities are elementary concave functions with numerous applications in online adword markets and revenue optimization problems. They extend the standard case of linear utilities and have been studied in a variety of other market models. In contrast to the frequently studied CES utilities, they have a global satiation point which can imply multiple market equilibria with quite different characteristics. Our main result is an efficient combinatorial algorithm to compute a market equilibrium with a Pareto-optimal allocation of goods. It relies on a new descending-price approach and, as a special case, also implies a novel combinatorial algorithm for computing a market equilibrium in linear Fisher markets. We complement this positive result with a number of hardness results for related computational questions. We prove that it isNP-hard to compute a market equilibrium that maximizes social welfare, and it is PPAD-hard to find any market equilibrium with utility functions with separate satiation points for each buyer and each good.

We design a simple ascending-price algorithm to compute a (1+\varepsilon)-approximate equilibrium in Arrow-Debreu exchange markets with weak gross substitute (WGS) property, which runs in time polynomial in market parameters and log 1/varepsilon. This is the first polynomial-time algorithm for most of the known tractable classes of Arrow-Debreu markets, which is easy to implement and avoids heavy machinery such as the ellipsoid method. In addition, our algorithm can be applied in an unknown market setting without exact knowledge about the number of agents, their individual utilities and endowments. Instead, our algorithm only relies on queries to a global demand oracle by posting prices and receiving aggregate demand for goods as feedback. When demands are real-valued functions of prices, the oracles can only return values of bounded precision based on real utility functions. Due to this more realistic assumption, precision and representation of prices and demands become a major technical challenge, and we develop new tools and insights that may be of independent interest.

In this paper, we introduce a trial-and-error model to study information diffusion in a social network. Specifically, in every discrete period, all individuals in the network concurrently try a new technology or product with certain respective probabilities. If it turns out that an individual observes a better utility, he will then adopt the trial; otherwise, the individual continues to choose his prior selection.

Motivated by certain applications from physics, biochemistry, economics, and computer science in which the objects under investigation are unknown or not directly accessible because of various limitations, we propose a trial-and-error model to examine search problems in which inputs are unknown. More specifically, we consider constraint satisfaction problems ⋀i Ci, where the constraints Ci are hidden, and the goal is to find a solution satisfying all constraints. We can adaptively propose a candidate solution (i.e., trial), and there is a verification oracle that either confirms that it is a valid solution, or returns the index i of a violated constraint (i.e., error), with the exact content of Ci still hidden.

We consider the classic cake cutting problem where one allocates a divisible cake to n participating agents. Among all valid divisions, fairness and efficiency (a.k.a. ~social welfare) are the most critical criteria to satisfy and optimize, respectively. We study computational complexity of computing an efficiency optimal division given the conditions that the allocation satisfies proportional fairness and assigns each agent a connected piece. For linear valuation functions, we give a polynomial time approximation scheme to compute an efficiency optimal allocation. On the other hand, we show that the problem is NP-hard to approximate within a factor of Ω 1/√n for general piecewise constant functions, and is NP-hard to compute for normalized functions.

Budget feasible mechanism design studies procurement combinatorial auctions in which the sellers have private costs to produce items, and the buyer (auctioneer) aims to maximize a social valuation function on subsets of items, under the budget constraint on the total payment. One of the most important questions in the field is "which valuation domains admit truthful budget feasible mechanisms with 'small' approximations (compared to the social optimum)?" Singer [35] showed that additive and submodular functions have a constant approximation mechanism. Recently, Dobzinski, Papadimitriou, and Singer [20] gave an O(log2n) approximation mechanism for subadditive functions; further, they remarked that: "A fundamental question is whether, regardless of computational constraints, a constant-factor budget feasible mechanism exists for subadditive functions."

Very recently, Hartline and Lucier [14] studied single-parameter mechanism design problems in the Bayesian setting. They proposed a black-box reduction that converted Bayesian approximation algorithms into Bayesian-Incentive-Compatible (BIC) mechanisms while preserving social welfare. It remains a major open question if one can find similar reduction in the more important multi-parameter setting. In this paper, we give positive answer to this question when the prior distribution has finite and small support. We propose a black-box reduction for designing BIC multi-parameter mechanisms. The reduction converts any algorithm into an ε-BIC mechanism with only marginal loss in social welfare. As a result, for combinatorial auctions with sub-additive agents we get an ε-BIC mechanism that achieves constant approximation.