In a multi-party machine learning system, different parties cooperate on optimizing towards better models by sharing data in a privacy-preserving way. A major challenge in learning is the incentive issue. For example, if there is competition among th
e parties, one may strategically hide his data to prevent other parties from getting better models. In this paper, we study the problem through the lens of mechanism design and incorporate the features of multi-party learning in our setting. First, each agents valuation has externalities that depend on others types and actions. Second, each agent can only misreport a type lower than his true type, but not the other way round. We call this setting interdependent value with type-dependent action spaces. We provide the optimal truthful mechanism in the quasi-monotone utility setting. We also provide necessary and sufficient conditions for truthful mechanisms in the most general case. Finally, we show the existence of such mechanisms is highly affected by the market growth rate and provide empirical analysis.
We consider the principal-agent problem with heterogeneous agents. Previous works assume that the principal signs independent incentive contracts with every agent to make them invest more efforts on the tasks. However, in many circumstances, these co
ntracts need to be identical for the sake of fairness. We investigate the optimal common contract problem. To our knowledge, this is the first attempt to consider this natural and important generalization. We first show this problem is NP-complete. Then we provide a dynamic programming algorithm to compute the optimal contract in $O(n^2m)$ time, where $n,m$ are the number of agents and actions, under the assumption that the agents cost functions obey increasing difference property. At last, we generalize the setting such that each agent can choose to directly produce a reward in $[0,1]$. We provide an $O(log n)$-approximate algorithm for this generalization.
Film release dates play an important part in box office revenues because of the facts of obvious seasonality demand in the film industry and severe competition among films shown at the same time. In this paper, we study how film studios choose releas
e time for movies they produce to maximize their box offices. We first formalize this problem as an attraction competition game where players (film studios) consider both potential profits and competitors choices when deciding the release time. Then we prove that there always exists a pure Nash equilibrium and give the sufficient condition of the uniqueness of the Nash equilibrium. Our model can be generalized to an extensive game and we compute the subgame-perfect equilibrium for homogeneous players. For the case that one film studio could have multiple movies to release, we prove that finding a players best response is NP-hard and it does not guarantee the existence of a pure Nash equilibrium. Experiments are provided to support the soundness of our model. In the final state, most of film studios, accounting for 84 percent of the market, would not change their release time. The behaviors of film studios imply they are following some strategies to reach a Nash equilibrium.
In this paper, we design gross product maximization mechanisms which incentivize users to upload high-quality contents on user-generated-content (UGC) websites. We show that, the proportional division mechanism, which is widely used in practice, can
perform arbitrarily bad in the worst case. The problem can be formulated using a linear program with bounded and increasing variables. We then present an $O(nlog n)$ algorithm to find the optimal mechanism, where n is the number of players.
Over the past few years, ride-sharing has emerged as an effective way to relieve traffic congestion. A key problem for these platforms is to come up with a revenue-optimal (or GMV-optimal) pricing scheme and an induced vehicle dispatching policy that
incorporate geographic and temporal information. In this paper, we aim to tackle this problem via an economic approach. Modeled naively, the underlying optimization problem may be non-convex and thus hard to compute. To this end, we use a so-called ironing technique to convert the problem into an equivalent convex optimization one via a clean Markov decision process (MDP) formulation, where the states are the driver distributions and the decision variables are the prices for each pair of locations. Our main finding is an efficient algorithm that computes the exact revenue-optimal (or GMV-optimal) randomized pricing schemes. We characterize the optimal solution of the MDP by a primal-dual analysis of a corresponding convex program. We also conduct empirical evaluations of our solution through real data of a major ride-sharing platform and show its advantages over fixed pricing schemes as well as several prevalent surge-based pricing schemes.
