The ACM Transactions on Economics and Computation welcomes submissions of the highest quality that concern the intersection of computer science and economics. Of interest to the journal is any topic relevant to both economists and computer scientists, including but not limited to the following:    Agents in networks  Algorithmic game theory  Computation of equilibria  Computational social choice  Cost of strategic behavior and cost of decentralization ("price of anarchy")  Design and analysis of electronic markets  Economics of computational advertising  Electronic commerce  Learning in games and markets  Mechanism design  Paid search auctions  Privacy  Recommendation / reputation / trust systems  Systems resilient against malicious agents.

The ACM Transactions on Economics and Computation welcomes submissions of the highest quality that explore the intersection of computer science and economics. The journal is interested in topics relevant to both economists and computer scientists, including but not limited to: agents in networks, algorithmic game theory, computation of equilibria, computational social choice, the cost of strategic behavior and decentralization ("price of anarchy"), design and analysis of electronic markets, economics of computational advertising, electronic commerce, learning in games and markets, mechanism design, paid search auctions, privacy, recommendation/reputation/trust systems, and systems resilient against malicious agents.

《ACM Transactions on Economics and Computation》欢迎提交高质量的论文，探讨计算机科学与经济学的交叉领域。期刊关注的主题包括但不限于：网络中的代理、算法博弈论、均衡计算、计算社会选择、战略行为和去中心化的成本（"无序价格"）、电子市场的设计与分析、计算广告的经济学、电子商务、游戏与市场中的学习、机制设计、付费搜索拍卖、隐私、推荐/声誉/信任系统，以及抵御恶意代理的系统。

ACM Transactions on Economics and Computation

Bipartite-matching markets pair agents on one side of a market with agents, items, or contracts on the opposing side. Prior work addresses online bipartite-matching markets, where agents arrive over time and are dynamically matched to a known set of disposable resources. In this article, we propose a new model, Online Matching with (offline) Reusable Resources under Known Adversarial Distributions ( OM-RR-KAD ) , in which resources on the offline side are reusable instead of disposable; that is, once matched, resources become available again at some point in the future. We show that our model is tractable by presenting an LP-based non-adaptive algorithm that achieves an online competitive ratio of ½-ϵ for any given constant ϵ &gt; 0. We also show that no adaptive algorithm can achieve a ratio of ½ + o (1) based on the same benchmark LP. Through a data-driven analysis on a massive openly available dataset, we show our model is robust enough to capture the application of taxi dispatching services and ride-sharing systems. We also present heuristics that perform well in practice.

John P. Dickerson

Karthik A. Sankararaman

Aravind Srinivasan

Pan Xu

Allocation Problems in Ride-sharing Platforms

拼车平台中的分配问题

The success of agile development methods in software development has raised interest in System-on-Chip (SoC) design, which involves high architectural and development process complexity under time and project management pressure. This article discovers the current state of agile hardware development with the questions (1) how well literature covers the SoC development process, (2) what agile methods and practices are applied or (3) what proposals are made to increase the agility, and (4) what is the impact for the SoC community. To answer the questions, a mapping study and literature review were performed. Seven hundred thirty papers were first studied, and eventually, after a rigorous filtering process, 25 papers were thoroughly analyzed. The results show that the popular agile SW development methods are applied in 5 cases, ideas adapted from the agile Hardware manifesto in 9 cases, and 11 cases do not define the Agile HW development method. Most of the papers address shorter development time by better methodologies and tools that indirectly shape the SoC development toward agility. The focus of agile hardware development is mostly on the SoC artifacts and methodological improvements have not been quantified. However, the literature indicates a significant impact on many academic chip prototypes. The challenges are better understood and the interest in agile methods is clearly increasing. The methodological gaps in the prevalent situation encourage further research and more accurate reporting of the development in addition to the SoC artifacts.

Antti Rautakoura

Timo Hämäläinen

Does SoC Hardware Development Become Agile by Saying So: A Literature Review and Mapping Study

SoC硬件开发是否仅凭宣称就能变得敏捷：文献综述与映射研究

We evaluate the fairness of a rule allocating among agents with equal rights by computing their utility for a hypothetical worst-case share, that only depends on their own valuation and the number of agents. For indivisible goods, Budish [J. Political Econ., 2011] proposed the maximin share : the least utility of a bundle in the best partition of the objects; unfortunately maximin share is not always satisfiable. Earlier, Hill [Ann. Probab., 1987] proposed the worst maximin share over all utilities with the same largest possible single-object value. More conservative than maximin share, it is guaranteed to be satisfiable for any possible profile of utilities and its computation is elementary whereas it is NP-hard to compute maximin share. We apply Hill’s approach to the allocation of indivisible bads (objects with disutilities) and compute in closed form the worst-case minimax share for a given value of the worst single bad. We show that the worst-case minimax share is close to the original minimax share and that its monotonic closure is the best guaranteed share for all allocation instances with a common upper bound on the value of the worst single bad.

Bo Li

Herve Moulin

Ankang Sun

Yu Zhou

On Hill's Worst-Case Guarantee for Indivisible Bads

关于不可分坏品的希尔最坏情况保证

We consider the problem of pricing edges of a line graph so as to maximize the profit made from selling intervals to single-minded customers. An instance is given by a set E of n edges with a limited supply for each edge, and a set of m clients, where each client specifies one interval of E she is interested in and a budget B j which is the maximum price she is willing to pay for that interval. An envy-free pricing is one in which every customer is allocated an (possibly empty) interval maximizing her utility. Grandoni and Rothvoss (SIAM J. Comput. 2016) proposed a polynomial-time approximation scheme ( PTAS ) for the unlimited supply case with running time ( nm ) O ((1/ɛ) 1/ɛ ) , which was extended to the limited supply case by Grandoni and Wiese (ESA 2019). By utilizing the known hierarchical decomposition of doubling metrics , we give a PTAS with running time ( nm ) O (1/ ɛ 2 ) for the unlimited supply case. We then consider the limited supply case, and the notion of ɛ-envy-free pricing in which a customer gets an allocation maximizing her utility within an additive error of ɛ. For this case, we develop an approximation scheme with running time ( nm ) O (log 5/2 max e H e /ɛ 3 ) , where H e = B max ( e )/ B min ( e ) is the maximum ratio of the budgets of any two customers demanding edge e . This yields a PTAS in the uniform budget case, and a quasi-PTAS for the general case. The best approximation known, in both cases, for the exact envy-free pricing version is O (log c max ), where c max is the maximum item supply. Our method is based on the known hierarchical decomposition of doubling metrics, and can be applied to other problems, such as the maximum feasible subsystem problem with interval matrices.

Khaled Elbassioni

A QPTAS for ɛ-Envy-Free Profit-Maximizing Pricing on Line Graphs

线图上ε-无嫉妒利润最大化定价问题的拟多项式时间近似方案

How can we design mechanisms to promote efficient use of shared resources? Here, we answer this question in relation to the well-studied class of atomic congestion games, used to model a variety of problems, including traffic routing. Within this context, a methodology for designing tolling mechanisms that minimize the system inefficiency (price of anarchy) exploiting solely local information is so far missing in spite of the scientific interest. In this article, we resolve this problem through a tractable linear programming formulation that applies to and beyond polynomial congestion games. When specializing our approach to the polynomial case, we obtain tight values for the optimal price of anarchy and corresponding tolls, uncovering an unexpected link with load balancing games. We also derive optimal tolling mechanisms that are constant with the congestion level, generalizing the results of Caragiannis et al. [8] to polynomial congestion games and beyond. Finally, we apply our techniques to compute the efficiency of the marginal cost mechanism. Surprisingly, optimal tolling mechanism using only local information perform closely to existing mechanism that utilize global information, e.g., Bilò and Vinci [6], while the marginal cost mechanism, known to be optimal in the continuous-flow model, has lower efficiency than that encountered levying no toll. All results are tight for pure Nash equilibria and extend to coarse correlated equilibria.

Dario Paccagnan

Rahul Chandan

Bryce L. Ferguson

Jason R. Marden

Optimal Taxes in Atomic Congestion Games

原子拥堵博弈中的最优税收

In a game of persuasion with evidence, a sender has private information. By presenting evidence on the information, the sender wishes to persuade a receiver to take a single action (e.g., hire a job candidate, or convict a defendant). The sender’s utility depends solely on whether or not the receiver takes the action. The receiver’s utility depends on both the action and the sender’s private information. We study three natural variations. First, we consider the problem of computing an equilibrium of the game without commitment power. Second, we consider a persuasion variant, where the sender commits to a signaling scheme and the receiver, after seeing the evidence, takes the action or not. Third, we study a delegation variant, where the receiver first commits to taking the action if being presented certain evidence, and the sender presents evidence to maximize the probability the action is taken. We study these variants through the computational lens, and give hardness results, optimal approximation algorithms, and polynomial-time algorithms for special cases. Among our results is an approximation algorithm that rounds a semidefinite program that might be of independent interest, since, to the best of our knowledge, it is the first such approximation algorithm in algorithmic economics.

Martin Hoefer

Pasin Manurangsi

Alexandros Psomas

Algorithmic Persuasion with Evidence

基于证据的算法说服

Many two-sided platforms are known to steer customers towards certain products based on their willingness to pay. In this article, we study platforms’ incentives to adopt this type of market segmentation and present conditions under which this can generate distortions that negatively impact the surplus from buyers and sellers. In our environment, a monopolistic platform matches sellers with buyers. Upon being matched, each pair of buyer and seller negotiates prices. If they choose to transact, the platform receives a commission fee proportional to the value of the transaction plus a flat fee per transaction. The platform is assumed to have full information about customers’ and sellers’ outside options. We show that, as long as the market is in excess supply or as long as there is a crossing between the demand and supply curves , the platform’s optimal matching is suboptimal from the perspective of buyers and sellers.

Pedro Vaissman Guinsburg

Gustavo Quinderé Saraiva

Search Steering in Two-Sided Platforms

双边平台中的搜索引导

In multiwinner approval voting, the goal is to select a k -member committee based on voters’ approval ballots. A well-studied concept of proportionality in this context is the justified representation (JR) axiom, which demands that no large cohesive group of voters remains unrepresented. However, the JR axiom may conflict with other desiderata, such as social welfare (the number of approvals obtained by committee members) or coverage (the number of voters who approve at least one committee member). In this article, we investigate the price of imposing the JR axiom (as well as the more demanding extended justified representation (EJR) axiom) on social welfare and coverage. Our approach is twofold: we derive worst-case bounds on the loss of welfare/coverage caused by imposing JR, and study the computational complexity of finding committees with high welfare that provide JR (obtaining hardness results, approximation algorithms, and an exact algorithm for one-dimensional preferences).

Edith Elkind

Piotr Faliszewski

Ayumi Igarashi

Ulrike Schmidt-Kraepelin

Warut Suksompong

The Price of Justified Representation

合理代表权的价格

In the impartial selection problem, a subset of agents up to a fixed size k among a group of n is to be chosen based on votes cast by the agents themselves. A selection mechanism is impartial if no agent can influence its own chance of being selected by changing its vote. It is α-optimal if, for every instance, the ratio between the votes received by the selected subset is at least a fraction of α of the votes received by the subset of size k with the highest number of votes. We study deterministic impartial mechanisms in a more general setting with arbitrarily weighted votes and provide the first approximation guarantee, roughly 1/⌈ 2 n/k ⌉. When the number of agents to select is large enough compared to the total number of agents, this yields an improvement on the previously best-known approximation ratio of 1/ k for the unweighted setting. We further show that our mechanism can be adapted to the impartial assignment problem, in which multiple sets of up to k agents are to be selected, with a loss in the approximation ratio of 1/2.

短名	ACM Trans. Econ. Comput.
Journal Impact	1.09
国际分区	COMPUTER SCIENCE, INTERDISCIPLINARY APPLICATIONS(Q4)

ISSN	2167-8375, 2167-8383
h-index	23

涉及主题	计算机科学数学经济微观经济学数理经济学数学优化统计业务哲学程序设计语言工程类物理生物组合数学认识论人工智能财务数学分析政治学法学几何学市场经济机器学习算法
出版信息	出版商: Association for Computing Machinery (ACM)，出版周期: ，期刊类型: journal，开源期刊: 否
基本数据	创刊年份: 2013，原创研究文献占比: 100.00%，自引率:0.00%， Gold OA占比: 2.08%

ACM Transactions on Economics and Computation

期刊引文格式

有 1 位以上作者的期刊

有 2 位作者的期刊

有 3 位作者的期刊

有 5 位以上作者的期刊

书籍引用格式

学位论文引用格式

网页引用格式

专利引用格式

手工熬夜修改参考文献？研飞自动匹配期刊，一键轻松成稿，支持 Word/WPS

投稿经验分享

Allocation Problems in Ride-sharing Platforms

Does SoC Hardware Development Become Agile by Saying So: A Literature Review and Mapping Study

On Hill's Worst-Case Guarantee for Indivisible Bads

A QPTAS for ɛ-Envy-Free Profit-Maximizing Pricing on Line Graphs

Optimal Taxes in Atomic Congestion Games

On Hill's Worst-Case Guarantee for Indivisible Bads

Algorithmic Persuasion with Evidence

Search Steering in Two-Sided Platforms

The Price of Justified Representation

Deterministic Impartial Selection with Weights