Kostas Kollias
Research Areas
Authored Publications
Google Publications
Other Publications
Sort By
First Passage Percolation with Queried Hints
Kritkorn Karntikoon
Aaron Schild
Yiheng Shen
Ali Sinop
AISTATS (2024)
Preview abstract
Optimization problems are ubiquitous throughout the modern world. In many of these applications, the input is inherently noisy and it is expensive to probe all of the noise in the input before solving the relevant optimization problem. In this work, we study how much of that noise needs to be queried in order to obtain an approximately optimal solution to the relevant problem. We focus on the shortest path problem in graphs, where one may think of the noise as coming from real-time traffic. We consider the following model: start with a weighted base graph $G$ and multiply each edge weight by an independently chosen, uniformly random number in $[1,2]$ to obtain a random graph $G'$. This model is called \emph{first passage percolation}. Mathematicians have studied this model extensively when $G$ is a $d$-dimensional grid graph, but the behavior of shortest paths in this model is still poorly understood in general graphs. We make progress in this direction for a class of graphs that resembles real-world road networks. Specifically, we prove that if the geometric realization of $G$ has constant doubling dimension, then for a given $s-t$ pair, we only need to probe the weights on $((\log n) / \epsilon)^{O(1)}$ edges in $G'$ in order to obtain a $(1 + \epsilon)$-approximation to the $s-t$ distance in $G'$. We also demonstrate experimentally that this result is pessimistic -- one can even obtain a short path in $G'$ with a small number of probes to $G'$.
View details
Preview abstract
Historically, much of machine learning research has focused on the performance of the algorithm alone, but recently more attention has been focused on optimizing joint human-algorithm performance. Here, we analyze a specific type of human-algorithm collaboration where the algorithm has access to a set of $n$ items, and presents a subset of size $k$ to the human, who selects a final item from among those $k$. This scenario could model content recommendation, route planning, or any type of labeling task. Because both the human and algorithm have imperfect, noisy information about the true ordering of items, the key question is: which value of $k$ maximizes the probability that the best item will be ultimately selected? For $k=1$, performance is optimized by the algorithm acting alone, and for $k=n$ it is optimized by the human acting alone.
Surprisingly, we show that for multiple of noise models, it is optimal to set $k \in [2, n-1]$ - that is, there are strict benefits to collaborating, even when the human and algorithm have equal accuracy separately. We demonstrate this theoretically for the Mallows model and experimentally for the Random Utilities models of noisy permutations. However, we show this pattern is \emph{reversed} when the human is anchored on the algorithm's presented ordering - the joint system always has strictly worse performance. We extend these results to the case where the human and algorithm differ in their accuracy levels, showing that there always exist regimes where a more accurate agent would strictly benefit from collaborating with a less accurate one, but these regimes are asymmetric between the human and the algorithm's accuracy.
View details
Data Exchange Markets via Utility Balancing
Aditya Bhaskara
Sungjin Im
Kamesh Munagala
Govind S. Sankar
WebConf (2024)
Preview abstract
This paper explores the design of a balanced data-sharing marketplace for entities with heterogeneous datasets and machine learning models that they seek to refine using data from other agents. The goal of the marketplace is to encourage participation for data sharing in the presence of such heterogeneity. Our market design approach for data sharing focuses on interim utility balance, where participants contribute and receive equitable utility from refinement of their models. We present such a market model for which we study computational complexity, solution existence, and approximation algorithms for welfare maximization and core stability. We finally support our theoretical insights with simulations on a mean estimation task inspired by road traffic delay estimation.
View details
Preview abstract
Electric vehicle (EV) adoption in long-distance logistics faces challenges like range anxiety and uneven distribution of charging stations. Two pivotal questions emerge: How can EVs be efficiently routed in a charging network considering range limits, charging speeds and prices And, can the existing charging infrastructure sustain the increasing demand for EVs in long-distance logistics? This paper addresses these questions by introducing a novel theoretical and computational framework to study the EV network flow problems. We present an EV network flow model that incorporates range restrictions and nonlinear charging rates, and identify conditions under which polynomial-time solutions can be obtained for optimal single EV routing, maximum flow, and minimum cost flow problems. We develop efficient computational methods for computing the optimal routing and flow vector using a novel graph augmentation technique. Our findings provide insights for optimizing EV routing in logistics, ensuring an efficient and sustainable future.
View details
Preview abstract
Algorithms for the computation of alternative routes in road networks power many geographic navigation systems. A good set of alternative routes offers meaningful options to the user of the system and can support applications such as routing that is robust to failures (e.g., road closures, extreme traffic congestion, etc.) and routing with diverse preferences and objective functions. Algorithmic techniques for alternative route computation include the penalty method, via-node type algorithms (which deploy bidirectional search and finding plateaus), and, more recently, electrical-circuit based algorithms. In this work we focus on the practically important family of via-node type algorithms and we aim to produce high quality alternative routes for road netowrks. We study alternative route computation in the presence of a fast routing infrastructure that relies on hierarchical routing (namely, CRP). We propose new approaches that rely on deep learning methods. Our training methodology utilizes the hierarchical partition of the graph and builds models to predict which boundary road segments in the partition should be crossed by the alternative routes. We describe our methods in detail and evaluate them against the previously studied architectures, as well as against a stronger baseline that we define in this work, showing improvements in quality in the road networks of Seattle, Paris, and Bangalore.
View details
Efficient Location Sampling Algorithms for Road Networks
Vivek Kumar
Santhoshini Velusamy
WebConf (2024)
Preview abstract
Many geographic information systems applications rely on the data provided by user devices in the road network. Such applications include traffic monitoring, driving navigation, detecting road closures or the construction of new roads, etc. This signal is collected by sampling locations from the user trajectories and is a critical process for all such systems. Yet, it has not been sufficiently studied in the literature. The most natural way to sample a trajectory is perhaps using a frequency based algorithm, e.g., sample every $x$ seconds. However, as we argue in this paper, such a simple strategy can be very wasteful in terms of resources (e.g., server-side processing, user battery) and in terms of the amount of user data that it maintains. In this work we conduct a horizontal study of various location sampling algorithms (including frequency-based, road geography-based, reservoir-sampling based, etc.) and extract their trade-offs in terms of various metrics of interest, such as, the size of the stored data and the induced quality of training for prediction tasks (e.g., predicting speeds) using the road network of New York City.
View details
Preview abstract
We develop an online learning algorithm for a navigation platform to route travelers in a congested network with multiple origin-destination (o-d) pairs while simultaneously learning the unknown cost function of road segments (edges) using the crowd-sourced data. The number of travel requests is randomly realized, and the travel time of each edge is stochastically distributed with the mean being a linear function that increases with the edge load (the number of travelers who take the edge). In each step of our algorithm, the platform updates the estimates of cost function parameters using the collected travel time data, and maintains a rectangular confidence interval of each parameter. The platform then routes travelers in the next step using an optimistic strategy based on the lower bound of the up-to-date confidence interval. The key aspect of our setting is that the number of collected data on each edge depends on the number of travelers who use it, which creates the dependency between the spatial distribution of data points and the routing strategy. We prove that the regret upper bound of our algorithm is \(O(\sqrt{T}\log(T),|E|)\), where \(T\) is the time horizon, and \(|E|\) is the number of edges in the network. Furthermore, we show that the regret bound decreases as the number of travelers increases, which implies that the platform learns faster with a larger user population. Finally, we implement our algorithm on the network of New York City, and demonstrate the efficacy using the accumulated regret.
View details
Preview abstract
We consider the classic stochastic multi-armed bandit (MAB) problem, when at each step, the online policy is given the extra power to probe (or observe) the rewards of $k$ arms before playing one of them. We derive new algorithms whose regret bounds in this model have exponentially better dependence on the time horizon when compared to the classic regret bounds. In particular, we show that $k=3$ probes suffice to achieve parameter-independent constant regret of $O(n^2)$, where $n$ is the number of arms. Such regret bounds cannot be achieved even with full feedback {\em after} the play (that is, in the experts model), showcasing the power of even a few probes {\em before} making the play. We present simulations that show benefit of our policies even on benign instances.
View details
Preview abstract
{\em Arbitrary cost-sharing} is a model in which the players of a resource selection game get to declare the payments that they will make, rather than have the payments be determined by a cost-sharing protocol. Arbitrary cost-sharing has been studied in various contexts, such as congestion games, network design games, and scheduling games. The natural counterpart of arbitrary cost-sharing in the context of a utility game is {\em arbitrary utility-sharing}, meaning that each player will request certain utility as a reward for their efforts in generating welfare for the system. This concept has received much less attention in the literature. In this paper, we initiate the study of arbitrary sharing in utility games, placing emphasis on the special case of {\em federated learning utility games}, in which players form groups that jointly execute a learning task and each player contributes certain types of data to each group. We present results on the price of anarchy and price of stability, showing that the price of anarchy is $2$ and that arbitrary utility sharing is the only known method to achieve price of stability $1$ with budget-balanced payments.
View details
Preview abstract
In this paper we present and evaluate the performance of a routing and link scheduling algorithm for millimeter wave (mmWave) backhaul networks. The proposed algorithm models the end user behavior as being selfish, i.e., it considers users always aiming to maximize their individual utility, rather than the global optimization objective. Our system utilizes popular concepts from the economics and fairness literature. Specifically, in order to forward packets between the access points that comprise the backhaul network the Shapley value method is applied, which is shown to induce solutions with reduced latency. The performance of the proposed algorithm is evaluated in terms of the total delay, as well as the price of anarchy, which represents the inefficiency of a scheduling policy when users are allowed to adapt their rates in a selfish manner and reach an equilibrium. A relaxed version of the problem is also presented, which provides a lower bound on the value of the optimal solution. This is used for the calculation of the price of anarchy, since the problem of finding the optimal solution is NP-hard. According to simulation results, the system that employs the proposed algorithm outperforms in terms of delay and price of anarchy a system that considers a First-In-First-Out (FIFO) packet forwarding policy, as well as a system that employs local search global optimization, under which users aim at optimizing the overall delay in the network.
View details
Preview abstract
A central goal in algorithmic game theory is to analyze the performance of decentralized multiagent systems, like communication and information networks. In the absence of a central planner who can enforce how these systems are utilized, the users can strategically interact with the system, aiming to maximize their own utility, possibly leading to very inefficient outcomes, and thus a high price of anarchy. To alleviate this issue, the system designer can use decentralized mechanisms that regulate the use of each resource (e.g., using local queuing protocols or scheduling mechanisms), but with only limited information regarding the state of the system. These information limitations have a severe impact on what such decentralized mechanisms can achieve, so most of the success stories in this literature have had to make restrictive assumptions (e.g., by either restricting the structure of the networks or the types of cost functions).
In this paper, we overcome some of the obstacles that the literature has imposed on decentralized mechanisms, by designing mechanisms that are enhanced with predictions regarding the missing information. Specifically, inspired by the big success of the literature on ``algorithms with predictions'', we design decentralized mechanisms with predictions and evaluate their price of anarchy as a function of the prediction error, focusing on two very well-studied classes of games: scheduling games and multicast network formation games.
View details
Preview abstract
For traffic routing platforms, the choice of which route to recommend to a user depends on the congestion on these routes -- indeed, an individual's utility depends on the number of people using the recommended route at that instance. Motivated by this, we introduce the problem of Congested Bandits where each arm's reward is allowed to depend on the number of times it was played in the past $\win$ timesteps. This dependence on past history of actions leads to a dynamical system where an algorithm's present choices also affect its future pay-offs, and requires an algorithm to plan for this. We study the congestion aware formulation in the multi-armed bandit (MAB) setup and in the contextual bandit setup with linear rewards. For the multi-armed setup, we propose a UCB style algorithm and show that its policy regret scales as $\tilde{O}(\sqrt{\K \win T})$. For the linear contextual bandit setup, our algorithm, based on an iterative least squares planner, achieves policy regret $\tilde{O}(\sqrt{dT} + \win)$. From an experimental standpoint, we corroborate the no-regret properties of our algorithms via a simulation study.
View details
Preview abstract
We study a dynamic traffic assignment model, where agents base their instantaneous routing decisions on real-time delay predictions. We formulate a mathematically concise model and derive properties of the predictors that ensure a {\em dynamic prediction equilibrium} exists. We demonstrate the versatility of our framework by showing that it subsumes the well-known full information and instantaneous information models, in addition to admitting further realistic predictors as special cases. We complement our theoretical analysis by an experimental study, in which we systematically compare the induced average travel times of different predictors, including a machine-learning model trained on data gained from previously computed equilibrium flows, both on a synthetic and a real road network.
View details
Weighted Stackelberg Algorithms for Road Traffic Optimization
Arun Chandrashekharapuram
Lisa Fawcett
Ali Sinop
SIGSPATIAL (2021)
Preview abstract
We study the problem faced by an online navigation platform that wishes to improve the total cost experienced by drivers in the road network, i.e., minimize the total travel time of vehicles on the streets. The platform has access to a fixed fraction of the traffic and needs to route it in a manner that improves the overall conditions in the network, both for platform users and non-users. This setting has been studied in the context of designing {\em Stackelberg strategies} for selfish routing games. An additional consideration for a routing platform in this setting is that it should ensure a positive experience for its users. The reasons for this are twofold: (a) the platform has a customer-service provider relationship with its users and (b) the users will opt out of following the platform's recommendations if they are systematically poor and the overall routing optimization effort will fail. This aspect is not explicitly addressed in standard Stackelberg algorithms and, in particular, some of them (e.g., Largest Latency First) move in the opposite direction of assigning user traffic to the most expensive paths so that the (selfish) non-user traffic can utilize the better part of the network. To address this challenge we formulate a weighted version of the Stackelberg routing problem in which the delay experienced by non-users of the platform is discounted by some parameter $\beta < 1$. We study natural algorithms for this problem and provide provable guarantees in the form of constant approximation ratios for various settings. In simulations with real graphs, data-induced delay functions, and realistic demands, we exhibit that such strategies improve the experience of both platform users and independent traffic in the road network and extract the trade-off between providing high quality service to the platform's users and improving the overall total cost.
View details
Preview abstract
Motivated by the emergence of popular service-based two-sided markets where sellers can serve multiple buyers at the same time, we formulate and study the two-sided cost sharing problem. In two-sided cost sharing, sellers incur different costs for serving different subsets of buyers and buyers have different values for being served by different sellers. Both buyers and sellers are self-interested agents whose values and costs are private information. We study the problem from the perspective of an intermediary platform that matches buyers to sellers and assigns prices and wages in an effort to maximize gains from trade (i.e., buyer values minus seller costs) subject to budget-balance in an incentive compatible manner. In our markets of interest, agents trade the (often same) services multiple times. Moreover, the value and cost for the same service differs based on the context (e.g., location, urgency, weather conditions, etc). In this framework, we design mechanisms that are efficient, ex-ante budget-balanced, ex-ante individually rational, dominant strategy incentive compatible, and ex-ante in the core (a natural generalization of the core that we define here).
View details
Preview abstract
We study the joint optimization problem of pricing trips in a transportation network and serving the induced demands by routing a fleet of available service vehicles to maximize revenue. Our framework encompasses applications that include traditional transportation networks (e.g., airplanes, buses) and their more modern counterparts (e.g., ride-sharing systems). We describe a simple combinatorial model, in which each edge in the network is endowed with a curve that gives the demand for traveling between its endpoints at any given price. We are supplied with a number of vehicles and a time budget to serve the demands induced by the prices that we set, seeking to maximize revenue. We first focus on a (preliminary) special case of our model with unit distances and unit time horizon. We show that this version of the problem can be solved optimally in polynomial time. Switching to the general case of our model, we first present a two-stage approach that separately optimizes for prices and routes, achieving a logarithmic approximation to revenue in the process. Next, using the insights gathered in the first two results, we present a constant factor approximation algorithm that jointly optimizes for prices and routes for the supply vehicles. Finally, we discuss how our algorithms can handle capacitated vehicles, impatient demands, and selfish (wage-maximizing) drivers.
View details
Preview abstract
Generating alternative routes in road networks is an application of significant interest for online navigation systems. A high quality set of diverse alternate routes offers two functionalities - a) support support multiple (unknown) preferences that the user may have; and b) robust to changes in network conditions. We address the latter in this paper. The main techniques that produce alternative routes in road networks are the {\em penalty} and the {\em plateau} methods, with the former providing high quality results but being too slow for practical use and the latter being fast but suffering in terms of quality. In this work we propose a novel method to produce alternative routes that is fundamentally different from the aforementioned approaches. Our algorithm borrows concepts from electrical flows and their decompositions. We provide an analysis that proves theoretical properties of our algorithm and evaluate it against the penalty and plateau methods, showing that it is as fast as the plateau method while also recovering much of the headroom towards the quality of the penalty method. The metrics we use to evaluate performance include the {\em stretch} (the average cost of the routes), the {\em diversity}, and the {\em robustness} (the connectivity between the origin and destination) of the induced set of routes.
View details
Contextual Recommendations and Low-Regret Cutting-Plane Algorithms
Guru Prashanth Guruganesh
NeurIPS (2021)
Preview abstract
We consider the following variant of contextual linear bandits motivated by routing applications in navigational engines and recommendation systems. We wish to learn a hidden $d$-dimensional value $w^*$. Every round, we are presented with a subset $\mathcal{X}_t \subseteq \mathbb{R}^d$ of possible actions. If we choose (i.e. recommend to the user) action $x_t$, we obtain utility $\langle x_t, w^* \rangle$ but only learn the identity of the best action $\arg\max_{x \in \X_t} \langle x, w^* \rangle$.
We design algorithms for this problem which achieve regret $O(d\log T)$ and $\exp(O(d \log d))$. To accomplish this, we design novel cutting-plane algorithms with low “regret” -- the total distance between the true point $w^*$ and the hyperplanes the separation oracle returns.
We also consider the variant where we are allowed to provide a list of several recommendations. In this variant, we give an algorithm with $O(d^2 \log d)$ regret and list size $\poly(d)$. Finally, we construct nearly tight algorithms for a weaker variant of this problem where the learner only learns the identity of an action that is better than the recommendation. Our results rely on new algorithmic techniques in convex geometry (including a variant of Steiner’s formula for the centroid of a convex set) which may be of independent interest.
View details
Preview abstract
A two-sided market consists of two sets of agents, each of whom have preferences over the other (Airbnb, Upwork, Lyft, Uber, etc.). We propose and analyze a repeated matching problem, where each time step consists of a single match, and our goal is to ensure fairness with respect to the cumulative allocations over an infinite time horizon. We prove several positive results, our main one being that for additive, symmetric ($v_i(j) = v_j(i)$), and binary ($v_i(j) \in \{a,1\}$) valuations, we can simultaneously (1) guarantee \emph{envy-freeness up to a single match} (EF1) and (2) select a maximum weight matching for each ``stage". Thus for this class of valuations, fairness can be achieved without sacrificing efficiency. This result holds even for \emph{dynamic valuations}, i.e., valuations that change over time. Although symmetry is a strong assumption, we show that this result cannot be extended to asymmetric binary valuations: (1) and (2) together are impossible even when valuations do not change over time, and for dynamic valuations, even (1) alone is impossible. To our knowledge, this is the first analysis of almost envy-freeness for two-sided preferences.
View details
Preview abstract
Inspired by traffic routing applications, we consider the problem of finding the shortest path from a source $s$ to a destination $t$ in a graph, when the lengths of the edges are unknown. Instead, we are given {\em hints} or predictions of the edge lengths from a collection of ML models, trained possibly on historical data and other contexts in the network. Additionally, we assume that the true length of any candidate path can be obtained by {\em probing} an up-to-date snapshot of the network. However, each probe introduces a latency, and thus the goal is to minimize the number of probes while finding a near-optimal path with high probability. We formalize this problem and show assumptions under which it admits to efficient approximation algorithms. We verify these assumptions and validate the performance of our algorithms on real data.
View details
Preview abstract
We study the inefficiency of equilibria of resource buying games, i.e., congestion games with arbitrary cost-sharing. Under arbitrary cost-sharing, players do not only declare the resources they will use, they also declare and submit a payment per resource. If the total payments on a resource cover its cost, the resource is activated, otherwise it remains unavailable to the players. Equilibrium existence and inefficiency under arbitrary cost-sharing is very well understood in certain models, such as network design games, where the joint cost of every resource (edge) is constant. In the case of congestion-dependent costs the understanding is not yet complete. For increasing per player cost functions, it is known that the optimal solution can be cast as a Nash equilibrium with the appropriate selection of payments and, hence, the price of stability is 1. In this work we initially focus on the price of anarchy for linear congestion games and prove that (in the direct generalization of the arbitrary cost-sharing model to congestion-dependent costs) it grows to infinity as the number of players grows large. However, we also show that with a natural modification to the cost-sharing model, the price of anarchy becomes 17/3. Turning our attention to strong Nash equilibria, we show that the worst-case inefficiency of the best and worst stable outcomes remains the same as for Nash equilibria, with the strong price of stability staying at 1 and the strong price of anarchy staying at 17/3. These results imply arbitrary cost-sharing is comparable to fair cost-sharing as it has a better best-case scenario and a (slightly) worse worst-case scenario.
View details
Preview abstract
We study cost-sharing games in real-time scheduling systems where the activation cost of the server at any given time is a function of its load. We focus on monomial cost functions and consider both the case when the degree is less than one (inducing positive externalities for the jobs) and when it is greater than one (inducing negative externalities for the jobs). For the former case, we provide tight price of anarchy bounds which show that the price of anarchy grows to infinity as a polynomial of the number of jobs in the game. For the latter, we observe that existing results provide constant and tight (asymptotically in the degree of the monomial) bounds on the price of anarchy. We then switch our attention to improving the price of anarchy by means of a simple coordination mechanism that has no knowledge of the instance. We show that our mechanism reduces the price of anarchy of games with $n$ jobs and unit activation costs from $\Theta(\sqrt{n})$ to $2$. We also show that for a restricted class of instances a similar improvement is achieved for monomial activation costs. This is not the case, however, for unrestricted instances of monomial costs for which we prove that the price of anarchy remains super-constant for our mechanism.
View details
Preview abstract
A core tension in the operations of online marketplaces is between segmentation (wherein platforms can increase revenue by segmenting the market into ever smaller sub-markets) and thickness (wherein the size of the sub-market affects the utility experienced by an agent). An important example of this is in dynamic online marketplaces, where buyers and sellers, in addition to preferences for different matches, also have finite patience (or deadlines) for being matched. We formalize this trade-off via a novel optimization problem that we term as 'Two-sided Facility Location': we consider a market wherein agents arrive at nodes embedded in an underlying metric space, where the distance between a buyer and seller captures the quality of the corresponding match. The platform posts prices and wages at the nodes, and opens a set of virtual clearinghouses where agents are routed for matching. To ensure high match-quality, the platform imposes a distance constraint between an agent and its clearinghouse; to ensure thickness, the platform requires the flow to any clearinghouse be at least a pre-specified lower bound. Subject to these constraints, the goal of the platform is to maximize the social surplus subject to weak budget balance, i.e., profit being non-negative. Our work characterizes the complexity of this problem by providing both hardness results as well as algorithms for this setting; in particular, we present an algorithm that yields a $(1 + \epsilon)$ approximation for the surplus for any constant $\epsilon > 0$, while relaxing the match quality (i.e., maximum distance of any match) by a constant factor.
View details
Preview abstract
In recent years, a range of online applications have facilitated resource sharing among users, resulting in a significant increase in resource utilization. In all such applications, sharing one's resources or skills with other agents increases social welfare. In general, each agent will look for other agents whose available resources complement hers, thereby forming natural sharing groups. In this paper, we study settings where a large population self-organizes into sharing groups. In many cases, centralized optimization approaches for creating an optimal partition of the user population are infeasible because either the central authority does not have the necessary information to compute an optimal partition, or it does not have the power to enforce a partition. Instead, the central authority puts in place an incentive structure in the form of a utility sharing method, before letting the participants form the sharing groups by themselves. We first analyze a simple equal-sharing method, which is the one most typically encountered in practice and show that it can lead to highly inefficient equilibria. We then propose a Shapley-sharing method and show that it significantly improves overall social welfare.
View details
Orienteering Algorithms for Generating Travel Itineraries
Zachary Friggstad
Chaitanya Swamy
WSDM (2018)
Preview abstract
We study the problem of automatically and efficiently generating itineraries
for users who are on vacation. We focus on the common case, wherein the trip
duration is more than a single day. Previous efficient algorithms based on
greedy heuristics suffer from two problems. First, the itineraries are often
unbalanced, with excellent days visiting top attractions followed by days of
exclusively lower-quality alternatives. Second, the trips often re-visit
neighborhoods repeatedly in order to cover increasingly low-tier points of
interest. Our primary technical contribution is an algorithm that addresses
both these problems by maximizing the quality of the worst day. We give
theoretical results showing that this algorithm's competitive factor is within
a factor two of the guarantee of the best available algorithm for a single day,
across many variations of the problem. We also give detailed empirical
evaluations using two distinct datasets: (a) anonymized Google historical visit
data and (b) Foursquare public check-in data. We show first that the overall
utility of our itineraries is almost identical to that of algorithms
specifically designed to maximize total utility, while the utility of the worst
day of our itineraries is roughly twice that obtained from other approaches.
We then turn to evaluation based on human raters who score our itineraries only
slightly below the itineraries created by human travel experts with deep
knowledge of the area.
View details
Preview abstract
We study utility games (Vetta, FOCS 2002) where a set of players join teams to produce social utility, and receive individual utility in the form of payments in return. These games have many natural applications in competitive settings such as labor markets, crowdsourcing, etc. The efficiency of such a game depends on the profit sharing mechanism -- the rule that maps utility produced by the players to their individual payments. We study three natural and widely used profit sharing mechanisms -- egalitarian or equal sharing, marginal gain or value addition when a player joins, and marginal loss or value depletion when a player leaves. For these settings, we give tight bounds on the price of anarchy, thereby allowing comparison between these popular mechanisms from a (worst case) social welfare perspective.
View details
Preview abstract
Recent years have witnessed the rise of many successful ecommerce marketplaces like the Amazon marketplace, Uber, AirBnB, and Upwork, where a central platform mediates economic transactions between buyers and sellers. A common feature of many of these two-sided marketplaces is that the platform has full control over search and discovery, but prices are determined by the buyers and sellers. Motivated by this, we study the algorithmic aspects of market segmentation via directed discovery in two-sided markets with endogenous prices. We consider a model where an online platform knows each buyer/seller’s characteristics, and associated demand/supply elasticities. Moreover, the platform can use discovery mechanisms (search/recommendation/etc.) to control which buyers/sellers are visible to each other. This leads to a segmentation of the market into pools, following which buyers and sellers endogenously determine market clearing transaction prices within each pool. The aim of the platform is to maximize the resulting volume of transactions/welfare in the market. We develop efficient algorithms with provable guarantees under a variety of assumptions on the demand and supply functions. We also test the validity of our assumptions on demand curves inferred from NYC taxicab log-data, as well as show the performance of our algorithms on synthetic experiments.
View details
No Results Found
