The 1st IJCAI-PRICAI Workshop on Applied Mechanism Design (WAMD)

Speaker: Haifeng Xu
Abstract: One of the most fruitful products of today's digital world is perhaps the unprecedented amount of information generated each day. Such information -- obtained by processing data collected from various channels -- can be used to help advertisers to more accurately target customers, loan companies to better determine borrowers' credit, investors to choose more profitable portfolios, just to list a few. Unsurprisingly, many companies have seen the great value of information and run on a business of collecting and selling information. Though the mechanism design literature has provided us a rich theory to guide the design of mechanisms for selling goods like physical products and Internet traffic, the problem of selling information turns out to be significantly different and far from being well-understood even in very basic setups. For example, information can be sold at any coarser level by adding random noise, but once sold, it can be copied freely. Information may help but also may harm a buyer (typically a decision maker). It has been observed that in some setups, the seller will have to pay back the buyer at times in order to achieve optimal revenue. In this talk, I will focus on perhaps the most basic setup where one seller sells information to a single Bayesian decision maker. I will talk about the major challenges of mechanism design for selling information in this setup and present our recent progress on designing revenue-optimal and practical mechanisms for selling information.

Speaker: John P. Dickerson
Abstract: The design of revenue-maximizing auctions with strong incentive guarantees is a core concern of economic theory. Computational auctions enable online advertising, sourcing, spectrum allocation, and myriad financial markets. Analytic progress in this space is notoriously difficult; since Myerson's 1981 work characterizing single-item optimal auctions, there has been limited progress outside of restricted settings. A recent paper by Dütting et al. circumvents analytic difficulties by applying deep learning techniques to, instead, approximate optimal auctions. In parallel, new research from Ilvento et al. and other groups has developed notions of fairness in the context of auction design. Inspired by these advances, in this talk, we discuss an extension of these techniques for approximating auctions using deep learning to address concerns of fairness while maintaining high revenue and strong incentive guarantees.

Speaker: Hadi Hosseini
Abstract: Envy-freeness up to any good (EFX) provides a strong and intuitive guarantee of fairness in the allocation of indivisible goods. But whether such allocations always exist or whether they can be efficiently computed remains an important open question. We study the existence and computation of EFX in conjunction with various other economic properties under lexicographic preferences--a well-studied preference model in artificial intelligence and economics. In sharp contrast to the known results for additive valuations, we not only prove the existence of EFX and Pareto optimal allocations, but in fact provide an algorithmic characterization of these two properties. We also characterize the mechanisms that are, in addition, strategyproof, non-bossy, and neutral. When the efficiency notion is strengthened to rank-maximality, we obtain non-existence and computational hardness results, and show that tractability can be restored when EFX is relaxed to another well-studied fairness notion called maximin share guarantee (MMS).

Speaker: Haris Aziz
Abstract: We consider the problem of probabilistic allocation of objects under ordinal preferences. Our main contribution is an allocation mechanism, called the vigilant eating rule (VER), that applies to nearly arbitrary distributional constraints. It is constrained ordinally efficient, can be computed efficiently for a large class of constraints, and treats agents equally if they have the same preferences and are subject to the same constraints. When the set feasible allocations is convex, we also present a characterization of our rule based on ordinal egalitarianism. Our general results concerning VER do not just apply to allocation problems but to any collective choice problem in which agents have ordinal preferences over discrete outcomes. As a case study, we assume objects have priorities for agents and apply VER to sets of probabilistic allocations that are constrained by stability. VER coincides with the (extended) probabilistic serial rule when priorities are flat and the agent proposing deterministic deferred acceptance algorithm when preferences and priorities are strict. While VER always returns a stable and constrained efficient allocation, it fails to be strategyproof, unconstrained efficient, and envy-free. We show however, that each of these three properties is incompatible with stability and constrained efficiency. (Joint work with Florian Brandl).

Speaker: Weiran Shen
Abstract: The existing security game literature rarely considers how information from local communities could affect the game. We propose a new game model, and introduce a new player -- a strategic informant, who can observe and report upcoming attacks -- to the defender-attacker security game setting. Characterized by a private type, the informant has his utility structure that leads to strategic behaviors. We model the game as a 3-player extensive-form game and propose a novel solution concept of Strong Stackelberg-perfect Bayesian equilibrium. To compute the optimal defender strategy, we show that a defense plan with only a linear number of informed patrol strategies could achieve the optimal defender's utility. This result significantly reduces the computational burden and allows us to solve the game in polynomial time. Finally, we conduct extensive experiments to show the effect of the strategic informant.

Speaker: Minming Li
Abstract: Recent years have seen various designs of strategyproof mechanisms in the facility location game and the obnoxious facility game, by considering the facility as a point. We extend that point to be an interval and study a novel activity scheduling game to schedule an activity in the time domain [0,1] based on all agents' time reports. The activity lasts for a time period of d with 0≤ d≤ 1, and each agent i wants his private time to be within the activity duration [y,y+d] or at least as close as possible. Thus his cost is the time difference between his time ti and the activity duration [y,y+d]. The social cost is the summation of all agents' costs. Our objective is to choose the activity starting time y so that the mechanisms are strategyproof (truthful) and efficient. We design a mechanism outputting an optimal solution and prove it is group strategyproof. For minimizing the maximum cost, we also design a strategyproof mechanism with approximation ratio 2. In the obnoxious activity scheduling game, each agent prefers his conflict time to be far away from the activity duration [y,y+d]. We respectively design deterministic and randomized group strategyproof mechanisms with provable approximation ratios and also show the lower bounds. Besides, for extension, we consider the cost/utility as the characteristic function and find group strategyproof mechanisms for minimizing the social cost and maximizing the social utility.

Speaker: Yue Jin
Abstract: Multi-agent cooperative navigation problem (MCNP) is a challenging multi-agent control problem, where multiple agents need to navigate to several targets in an unknown environment with minimum time consumption and without collision. To solve this problem, traditional methods are generally based on mapping and planning or policy design. When the environment is unknown and agents’ decisions are interweaved, these methods lack efficiency. In this paper, we formulate the MCNP as a stochastic game with a well-designed reward function, and solve the problem with a novel deep reinforcement learning method, which can learn end-to-end policies by trial and error without resorting to planning and policy design. However, applying deep reinforcement learning to the MCNP suffers from large policy solution space and non-stationary environment caused by agents’ concurrent learning. To address these challenges, we propose a hierarchical and stable multi-agent deep reinforcement learning method. In particular, we introduce a two-layer policy model to reduce the solution space and propose an interlaced leaning method to learn two hierarchies of the policy. Besides, we leverage estimating other agents' actions to stabilize multi-agent policy learning. Finally, we propose a unified algorithm to incorporate the action estimation into interlaced hierarchical policy learning to solve the MCNP. Extensive experiments demonstrate that our method can converge in a fast way and generate more efficient cooperative navigation policies compared with the state of the art.

Speaker: Yu Qiao
Abstract: Cellular traffic offloading is an important problem in mobile networking. Since the offloading resource owners (agents) are self-interested and have private costs, it is highly challenging to design a procurement mechanism to encourage agents to reveal their true costs and achieve theoretically guaranteed utility under constraints. In this report, we will discuss two cellular traffic offloading procurement mechanisms, budget-feasible and the profit maximization. We design truthful procurement mechanisms for two scenarios, respectively. The work was published in AAMAS2019 and AAAI2020.

Speaker: Shangdong Yang
Abstract: 本报告研究具有稀疏奖励的协作多智能体多目标强化学习问题。该问题广泛存在于现实应用中，例如两个工业机器人只有在协同完成一个动态目标的焊接任务时才能获得奖励。后视经验回放（Hindsight Experience Replay, HER）是针对单智能体多目标强化学习提出的，但在多智能体应用中效果不佳。报告首先对该问题进行了形式化分析，然后分析了HER在多智能体情况下的不足。由此，我们提出了一个改进的合作式后视经验回放（C-HER），它考虑了智能体之间的交互关系，并能够在稀疏奖励的情况下成功地学习到合作策略。C-HER可以与任意的离策略多智能体RL算法相结合。通过对多个合作任务的比较，证明了该方法的有效性。

Speaker: Yao Zhang
Abstract: We study a question answering problem on a social network, where a requester is seeking an answer from the agents on the network. The goal is to design reward mechanisms to incentivize the agents to propagate the requester’s query to their neighbours if they don’t have the answer. Existing mechanisms are vulnerable to Sybil-attacks, i.e., an agent may get more reward by creating fake identities. Hence, we combat this problem by first proving some impossibility results to resolve Sybil-attacks and then characterizing a class of mechanisms which satisfy Sybil-proofness (prevents Sybil-attacks) as well as other desirable properties. Except for Sybil-proofness, we also consider cost minimization for the requester and agents’ collusions. The work was published in IJCAI2020.